物流配送车辆路径问题课件.ppt

1、路漫漫其悠远路漫漫其悠远2022-6-2物流配送车辆路径问题物流配送车辆路径问题路漫漫其悠远路漫漫其悠远2.1 问题的描述及各组成部分特点配送活动中的配送车辆行驶线路优化确定问题，是近二十多年来国际运筹学界的研究热点之一。 运筹学界将此类问题统称之为车辆路径问题VRP或车辆调度问题一般描述是：对一系列给定的客户点，确定配送车辆行驶路线，使其从配送中心出发，有序地对它们进行服务，并在满足一定的约束条件下（如车辆载重量、客户需求量、服务时间限制等），使总运输成本达到最小（如使用车辆数最少、车辆行驶总距离最短等）。一般把最小化车辆使用数作为第一优化目标，而最小化车辆行驶距离作为第二优化目标。 路漫漫

2、其悠远路漫漫其悠远n车辆路径问题的特点1. 道路网 弧表示路段，点表示道路交叉点、配送中心和客户。 弧的权cij表示其距离或行驶时间。路漫漫其悠远路漫漫其悠远客户 用图上的小圆点表示； 需运送或收取的货物量（需求量）di 或di和pi ； 要求提供服务的时间段，即时间窗（time window） 在客户点所花费的服务时间si 能用于服务该客户的车辆集合。配送中心（车场） 用图上的小方点表示； 车辆行驶路线开始并终止于配送中心或某一个客户点； 其特征由所配备的车辆种类和数量、以及所能处理的货物总量来描述。 路漫漫其悠远路漫漫其悠远车辆 车辆是自备还是外租，完成任务后是否返回； 车辆的装载能力;

3、车辆使用费; 可用于进行货物装卸的设备.驾驶员 给驾驶员安排取送货任务时，必须符合工作时间方面的有关规定。路径编排中的限制条件 车辆的当前负载不能超过车辆的装载量； 客户只要求送货、取货、或取送货兼有； 在客户所要求的时间窗和驾驶员的工作时间内提供服务； 访问客户的顺序要求。 路漫漫其悠远路漫漫其悠远行驶距离和行驶时间 必须知道客户点与客户点之间，配送中心与客户点之间的行驶距离和行驶时间。 目标 最小化总运输成本，其大小取决于所需要的车辆数（或线路数）、总行驶距离（时间）； 最小化与客户的不完全服务等有关的惩罚值； 均衡各线路上的行驶时间和车辆载重量。 路漫漫其悠远路漫漫其悠远2.2 车辆路径

4、问题的分类n根据配送车辆完成配送任务后是否必须返回原出发点以及返回的形式，可将问题分为闭合式和开放式两大类。n在不需严格区分的场合，统称路漫漫其悠远路漫漫其悠远n当车辆完成运输任务后必须返回原出发点时（即车辆的行驶路线是闭合式的），称之为闭合式车辆路径问题（Closed VRP）通常简称为车辆路径问题路漫漫其悠远路漫漫其悠远n当不要求车辆完成任务后返回原出发点，或者是若要求返回原出发点，则沿原去程路线返回时（即车辆的行驶路线是开放式的），称之为开放式车辆路径问题（Open VRP，OVRP）路漫漫其悠远路漫漫其悠远n根据所包含的约束条件，问题又可进一步分类。以闭合式VRP为例，可归纳如下： D

5、CVRP 路程长度 VRPPD 装载能力 取送作业 CVRP VRPPDTW 时间窗 VRPTW 回程运输 VRPBTW VRPB路漫漫其悠远路漫漫其悠远2.2.1 带装载能力的VRP（Capacitated VRP，CVRP）n问题的特点是VRP中的最基本型式。所有客户都属于要送货的或要取货的，其需求量预先知道，且不能被分割。 车辆类型相同且都停放在一个配送中心。对车辆只有装载能力限制。 问题的目标是最小化服务所有客户的总费用（即所需要的车辆数及其车辆行驶距离或行驶时间）。 n问题的描述（可描述为如下的图论问题）路漫漫其悠远路漫漫其悠远设GV A 为一个完备图，其中Vn 为顶点集，A是弧集。

6、顶点i n表示客户，而顶点0表示配送中心。有时配送中心用顶点n来表示。每条弧对应着一个非负的费用cij表示从点i到点j的行驶费用在一些测试算例中，顶点与给定坐标的平面上的点相对应，且弧的费用cij被定义为对应于顶点i和j的两点间的欧氏距离。yj j (xj, yj) yi i (xi, yi) xj xi路漫漫其悠远路漫漫其悠远在配送中心备有相同类型的车辆，每辆的装载能力为C。每一条线路上的送货任务只由一辆车承担。i 有一个已知的需要送往交付的非负需求量di假设di C服务所有客户至少所需要的车辆数路漫漫其悠远路漫漫其悠远是求一个具有最小总费用的由K条简单回路组成的集合（每个回路对应于一条配送

7、车辆行驶线路），并满足 每个回路从配送中心出发并返回配送中心； 每个客户点只在一条回路上； 一条回路上各客户点的需求量之和不超过车辆装载能力C总费用一般包括所使用的车辆数（即回路数）和车辆行驶费用两项。通常都认为，多用一辆车所带来的固定费用的增加，总是超过其因总行驶距离缩短所带来的节省，因此，一般把最小化车辆使用数作为第一优化目标，最小化行驶费用作为第二目标。 路漫漫其悠远路漫漫其悠远当备有的车辆类型不是同一种时，即有不同的装载能力Ckk K则就为经常考虑的另一种变形。是难的，并且是旅行商问题的一般化在中，要求确定一条经过图G中所有顶点的、费用最小的回路（哈密顿回路），当中的Cdi和K时就为此

8、情形。 路漫漫其悠远路漫漫其悠远2.2.2 带路程长度的VRP（Distance-Constrained and Capacitated VRP，DCVRP）n特点既有车辆装载能力限制，又有最大路程长度限制。n描述每条弧对应着一个非负的长度tij一般地，费用矩阵与长度矩阵相一致，即cij tij每条线路上各弧的总长度不能超过线路的最大长度L当弧的长度代表的是行驶时间时，每个客户i就对应着一个服务时间si表示车辆必须在该客户点停留的时间长度。路漫漫其悠远路漫漫其悠远2.2.3 带时间窗的VRP（VRP with time windows，VRPTW）除了车辆装载能力约束外，每个客户i 都有一个与

9、之相联系的要求提供服务的时间区间 ai bi1.带硬时间窗的VRPhardVRPHTW在不需要严格区分的场合，一般就称为带时间窗的n特点客户的服务必须在相应的时间窗内开始，车辆在客户点的服务时间长度为si当车辆提前到达客户点时，必须等待到时刻ai才可开始服务。不允许在bi之后到达并开始服务。路漫漫其悠远路漫漫其悠远对于配送中心，设服务时间s0时间窗 a0b0应注意的是，时间窗的要求导致每条线路具有隐含的方向性，以及线路长度的限制，最大线路长度为Lb0n描述是求一个具有最小总费用的由K条简单回路组成的集合，并满足同对每个客户i服务在时间窗 ai bi内开始，车辆的停留时间长度为si当aibi时就

10、为路漫漫其悠远路漫漫其悠远2.带软时间窗的softVRPSTW时间窗要求是软的，即允许服务的开始时间有所偏离时间窗（早于ai或晚于bi但要根据所带来的不方便程度支付一定的惩罚。可定义惩罚函数来计算。 若某个客户的时间窗不能被违反（硬的），则有偏离时应支付的惩罚设为无穷大。可见实际上是的一种特殊情形。由于允许以支付惩罚偏离时间窗，与相比，往往会在所需要的车辆数、或各线路总距离和总行驶时间方面获得较大的节省。 路漫漫其悠远路漫漫其悠远2.2.4 带回程运输的VRP （VRP with backhauls，VRPB）n特点客户集：去程客户，L=1, 2, , n 回程客户，B=n+1, , n+m先

11、服务去程客户，后服务回程客户。 描述求一个具有最小总费用的由K条简单回路组成的集合，并满足同一条回路上各去程客户点和回程客户点的需求量之和分别不超过车辆装载能力C所有去程客户必须先于回程客户得到服务路漫漫其悠远路漫漫其悠远n扩展带回程运输和时间窗的路漫漫其悠远路漫漫其悠远2.2.5 带取送货的VRP （VRP with pickup and delivery，VRPPD）n特点客户i对应着两个量：di送往客户i的货物数量 pi从客户i收取的货物数量Oi表示需送往客户i的货物的始发点， Di表示待取货物的终到点。 在每个客户点，规定先卸后装。描述求一个具有最小总费用的由K条简单回路组成的集合，并

12、满足同车辆的当前负载必须保持非负且 C路漫漫其悠远路漫漫其悠远当Oi不是配送中心时，它必须与客户i在同一线路上且先于客户i得到服务；当Di不是配送中心时，它必须与客户i在同一线路上且后于客户i得到服务。n扩展带取送货和时间窗的路漫漫其悠远路漫漫其悠远2.3 车辆路径问题的研究现状和发展趋势 和于1959年首先对进行了研究。他们描述了一个将汽油送往各加油站的实际问题，并提出了相应的数学规划模型及其求解算法。1964年，和提出一种对方法进行改进的较有效的启发式算法节约算法。在这两篇开创性的论文发表后，很快引起学术界和实际工作者的极大重视，成为近二十多年来运筹学领域的研究热点之一。特别是物流配送活动

13、中的配送车辆行驶路径问题，是近年来VRP的重点研究对象和应用领域。路漫漫其悠远路漫漫其悠远1983年，Bodin等人在长达140多页的对VRP的研究进展进行综述的文章中，就列举了699篇相关的参考文献。1995年出版的 中，第八卷就是专门讨论车辆路径问题的。 2002年，和在其出版的著作中，对的最新研究进展和发展趋势进行了比较全面的分析。与国际上相比，国内对的研究相对较少，最近几年才陆续有一些相关的研究成果发表。通过各国研究人员的共同努力，现已提出了许多用于求解不同类型的的最优解和近优解的模型及其精确算法和启发式算法。 路漫漫其悠远路漫漫其悠远2.3.1 车辆路径问题的模型 的三下标车辆流模型

14、。定义变量路漫漫其悠远路漫漫其悠远模型路漫漫其悠远路漫漫其悠远2.3.2 VRP的计算复杂性和求解算法 对VRP求解算法的研究一直是重点和难点。现已证明，几乎所有类型的VRP均为NP-难问题。之所以引起学术界的极大重视，除了它具有广泛的应用背景外，是因为相当难解，从而富有挑战性。目前已提出了许多求解VRP的算法，究其实质，可分为精确算法和启发式算法两大类。路漫漫其悠远路漫漫其悠远n精确算法 指可求出其最优解的算法，且一般要求问题能用相应的数学模型表示。 目前用于求解VRP的精确算法主要有分支定界法（Branch-and-Bound Algorithm） 分支切面法（Branch-and-Cut

15、 Algorithm）割平面法（Cutting Plane Method） 因VRP是NP-难问题，其精确算法的计算量随问题规模的增大呈指数增长，在实际中的应用范围有限。但在对相应的启发式算法的质量评估等理论研究工作中却很有意义。从实际应用的角度来说，公认的明智做法是设计相应的启发式算法来求出问题的近优解。 路漫漫其悠远路漫漫其悠远n启发式算法是基于直观或经验构造的算法，一般不要求非得将问题表述为某种标准的数学模型；在可接受的计算量内求出问题的满意解，但不能保证最优。1960-1990年间，所提出的求解VRP的启发式算法都是基于经典的启发式方法的思想。1990年以来，随着通用启发式算法（met

16、a-heuristics）的出现，如模拟退火(SA)、禁忌搜索(TS)、遗传算法(GA)等，研究运用这些算法来构造求解VRP的算法已成为主流和当前的研究热点，并已取得了许多令人鼓舞的成果。求出的解高出最优解（或已知最好解）： 基于经典启发式方法：2-10%； 基于通用启发式方法：0.5%路漫漫其悠远路漫漫其悠远n发展趋势为了使现代启发式算法能在商业软件中得到应用，开发更快、更简单、更健壮的算法已成为一种趋势，尽管这将在解的质量方面带来一些小损失。在算法测试与比较方面，研究人员目前已取得一个共识：必须使用公开的标准测试算例（benchmark instances)对所提出的算法进行测试。这样，其测试结果才具有可比性和说服力。