物流配送优化(第二章)ppt课件

1、第二章 物流配送车辆途径问题 2.1 问题的描画及各组成部分特点2.2 车辆途径问题的分类 2.3 车辆途径问题的研讨现状和开展趋势 12.1 问题的描画及各组成部分特点配送活动中的配送车辆行驶线路优化确定问题，是近二十多年来国际运筹学界的研讨热点之一。 运筹学界将此类问题统称之为车辆途径问题Vehicle Routing Problem, VRP，或车辆调度问题Vehicle Scheduling Problem, VSP。普通描画是：对一系列给定的客户点，确定配送车辆行驶道路，使其从配送中心出发，有序地对它们进展效力，并在满足一定的约束条件下如车辆载分量、客户需求量、效力时间限制等，使总运

2、输本钱到达最小如运用车辆数最少、车辆行驶总间隔最短等。普通把最小化车辆运用数作为第一优化目的，而最小化车辆行驶间隔作为第二优化目的。 2车辆途径问题的特点1. 道路网road network弧表示路段，点表示道路交叉点、配送中心和客户。弧的权cij表示其间隔或行驶时间。32. 客户customer 用图上的小圆点表示； 需运送或收取的货物量需求量di (或di和pi )；要求提供效力的时间段，即时间窗time window 在客户点所破费的效力时间si； 能用于效力该客户的车辆集合。3. 配送中心车场distribution center，depot 用图上的小方点表示；车辆行驶道路开场并终止

3、于配送中心或某一个客户点；其特征由所配备的车辆种类和数量、以及所能处置的货物总量来描画。 44. 车辆vehicle 车辆是自备还是外租，完成义务后能否前往； 车辆的装载才干;车辆运用费;可用于进展货物装卸的设备.5. 驾驶员driver 给驾驶员安排取送货义务时，必需符合任务时间方面的有关规定。 6. 途径编排中的限制条件 车辆的当前负载不能超越车辆的装载量； 客户只需求送货、取货、或取送货兼有；在客户所要求的时间窗和驾驶员的任务时间内提供效力；访问客户的顺序要求。 57. 行驶间隔和行驶时间必需知道客户点与客户点之间，配送中心与客户点之间的行驶间隔和行驶时间。8. 目的objectives

4、 最小化总运输本钱，其大小取决于所需求的车辆数或线路数、总行驶间隔时间；最小化与客户的不完全效力等有关的惩罚值； 平衡各线路上的行驶时间和车辆载分量。 62.2 车辆途径问题的分类根据配送车辆完成配送义务后能否必需前往原出发点以及前往的方式，可将问题分为闭合式和开放式两大类。在不需严厉区分的场所，统称VRP。7当车辆完成运输义务后必需前往原出发点时即车辆的行驶道路是闭合式的，称之为闭合式车辆途径问题Closed VRP，通常简称为车辆途径问题VRP。8当不要求车辆完成义务后前往原出发点，或者是假设要求前往原出发点，那么沿原去程道路前往时即车辆的行驶道路是开放式的，称之为开放式车辆途径问题Ope

5、n VRP，OVRP。9根据所包含的约束条件，问题又可进一步分类。以闭合式VRP为例，可归纳如下： DCVRP 路程长度 VRPPD 装载才干 取送作业 CVRP VRPPDTW 时间窗 VRPTW 回程运输 VRPBTW VRPB102.2.1 带装载才干的VRPCapacitated VRP，CVRP问题的特点是VRP中的最根本型式。一切客户都属于要送货的或要取货的，其需求量预先知道，且不能被分割。 车辆类型一样且都停放在一个配送中心。对车辆只需装载才干限制。 问题的目的是最小化效力一切客户的总费用即所需求的车辆数及其车辆行驶间隔或行驶时间。 问题的描画可描画为如下的图论问题11设G =

6、(V, A)为一个完备图，其中V = 0,n为顶点集，A是弧集。顶点i = 1,n表示客户，而顶点0表示配送中心。有时配送中心用顶点n +1来表示。 每条弧对应着一个非负的费用cij，表示从点i到点j的行驶费用。 在一些测试算例中，顶点与给定坐标的平面上的点相对应，且弧的费用cij被定义为对应于顶点i和j的两点间的欧氏间隔。 yj j (xj, yj) yi i (xi, yi) xj xi12在配送中心备有一样类型的车辆，每辆的装载才干为C。每一条线路上的送货义务只由一辆车承当。 每个客户 i 有一个知的需求送往交付的非负需求量di，假设di C。效力一切客户至少所需求的车辆数 13CVRP

7、是求一个具有最小总费用的由K条简单回路组成的集合每个回路对应于一条配送车辆行驶线路，并满足 (1)每个回路从配送中心出发并前往配送中心； (2) 每个客户点只在一条回路上； (3) 一条回路上各客户点的需求量之和不超越车辆装载才干C。总费用普通包括所运用的车辆数即回路数和车辆行驶费用两项。通常都以为，多用一辆车所带来的固定费用的添加，总是超越其因总行驶间隔缩短所带来的节省，因此，普通把最小化车辆运用数作为第一优化目的，最小化行驶费用作为第二目的。 14当备有的车辆类型不是同一种时，即有不同的装载才干Ck，k =1,K，那么就为经常思索的另一种变形。CVRP是NP-难的，并且是游览商问题TSP的

8、普通化。在TSP中，要求确定一条经过图G中一切顶点的、费用最小的回路哈密顿回路，当CVRP中的Cdi和K=1时就为此情形。 152.2.2 领路程长度的VRPDistance-Constrained and Capacitated VRP，DCVRP特点既有车辆装载才干限制，又有最大路程长度限制。描画每条弧对应着一个非负的长度tij，普通地，费用矩阵与长度矩阵相一致，即cij = tij。 每条线路上各弧的总长度不能超越线路的最大长度L。当弧的长度代表的是行驶时间时，每个客户i就对应着一个效力时间si，表示车辆必需在该客户点停留的时间长度。 162.2.3 带时间窗的VRPVRP with t

9、ime windows，VRPTW除了车辆装载才干约束外，每个客户i 都有一个与之相联络的要求提供效力的时间区间 ai, bi。 1.带硬时间窗的VRPVRP with hard time windows,VRPHTW。在不需求严厉区分的场所，普通就称为带时间窗的VRP。特点 客户的效力必需在相应的时间窗内开场，车辆在客户点的效力时间长度为si。 当车辆提早到达客户点时，必需等待到时辰ai才可开场效力。不允许在bi之后到达并开场效力。17对于配送中心，设效力时间s0 = 0，时间窗 a0, b0。应留意的是，时间窗的要求导致每条线路具有隐含的方向性，以及线路长度的限制，最大线路长度为L =b0

10、。 描画VRPHTW是求一个具有最小总费用的由K条简单回路组成的集合，并满足1、2、3同CVRP；4对每个客户i，效力在时间窗ai, bi内开场，车辆的停留时间长度为si。 当ai = 0, bi = +时，VRPHTW就为CVRP。 182.带软时间窗的VRP VRP with soft time windows, VRPSTW时间窗要求是软的，即允许效力的开场时间有所偏离时间窗早于ai或晚于bi ，但要根据所带来的不方便程度支付一定的惩罚。可定义惩罚函数来计算。 假设某个客户的时间窗不能被违反硬的，那么有偏离时应支付的惩罚设为无穷大。可见VRPHTW实践上是VRPSTW的一种特殊情形。 由

11、于允许以支付惩罚偏离时间窗，与VRPHTW相比，VRPSTW往往会在所需求的车辆数、或各线路总间隔和总行驶时间方面获得较大的节省。 192.2.4 带回程运输的VRP VRP with backhauls，VRPB特点客户集：去程客户，L=1, 2, , n 回程客户，B=n+1, , n+m先效力去程客户，后效力回程客户。 描画求一个具有最小总费用的由K条简单回路组成的集合，并满足 1、2同CVRP；3一条回路上各去程客户点和回程客户点的需求量之和分别不超越车辆装载才干C； 4一切去程客户必需先于回程客户得到效力。 20扩展带回程运输和时间窗的VRPVRP with backhauls an

12、d time windows, VRPBTW 212.2.5 带取送货的VRP VRP with pickup and delivery，VRPPD特点客户i对应着两个量：di，送往客户i的货物数量 pi，从客户i收取的货物数量Oi表示需送往客户i的货物的始发点， Di表示待取货物的终到点。 在每个客户点，规定先卸后装。描画求一个具有最小总费用的由K条简单回路组成的集合，并满足 1、2同CVRP；3车辆的当前负载必需坚持非负且C； 224当Oi不是配送中心时，它必需与客户i在同一线路上且先于客户i得到效力；5当Di不是配送中心时，它必需与客户i在同一线路上且后于客户i得到效力。 扩展带取送货和

13、时间窗的VRPVRP with pickup and delivery and time windows, VRPPDTW。 232.3 车辆途径问题的研讨现状和开展趋势 Dantzig和Ramser于1959年首先对VRP进展了研讨。他们描画了一个将汽油送往各加油站的实践问题，并提出了相应的数学规划模型及其求解算法。1964年，Clarke和Wright提出一种对Dantzig-Ramser方法进展改良的较有效的启发式算法Clarke-Wright节约算法。在这两篇开创性的论文发表后，VRP很快引起学术界和实践任务者的极大注重，成为近二十多年来运筹学领域的研讨热点之一。特别是物流配送活动中的

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

15、 CVRP的三下标车辆流模型。 定义变量26模型272.3.2 VRP的计算复杂性和求解算法 对VRP求解算法的研讨不断是重点和难点。现已证明，几乎一切类型的VRP均为NP-难问题。VRP之所以引起学术界的极大注重，除了它具有广泛的运用背景外，是由于相当难解，从而富有挑战性。目前已提出了许多求解VRP的算法，究其本质，可分为准确算法和启发式算法两大类。28准确算法 指可求出其最优解的算法，且普通要求问题能用相应的数学模型表示。 目前用于求解VRP的准确算法主要有 分支定界法Branch-and-Bound Algorithm 分支切面法Branch-and-Cut Algorithm 割平面法

16、Cutting Plane Method 因VRP是NP-难问题，其准确算法的计算量随问题规模的增大呈指数增长，在实践中的运用范围有限。但在对相应的启发式算法的质量评价等实际研讨任务中却很有意义。从实践运用的角度来说，公认的明智做法是设计相应的启发式算法来求出问题的近优解。 29启发式算法 是基于直观或阅历构造的算法，普通不要求非得将问题表述为某种规范的数学模型；在可接受的计算量内求出问题的称心解，但不能保证最优。1960-1990年间，所提出的求解VRP的启发式算法都是基于经典的启发式方法的思想。 1990年以来，随着通用启发式算法meta-heuristics的出现，如模拟退火(SA)、忌讳搜索(TS)、遗传算法(GA)等，研