专题2-车辆路径问题ppt课件

1、2006.12.8张军张军主要内容n什么是什么是VRPnVRP背景及运用背景及运用nVRP问题定义问题定义nVRP问题的分类问题的分类nVRP问题数学模型问题数学模型nVRP算法类型及简要引见算法类型及简要引见n近年来关于近年来关于VRP的研讨的研讨一、什么是VRP VRPVehicle Routing Problem 车辆途径问题车辆途径问题 当不思索时间要求，仅根据空间位置安排当不思索时间要求，仅根据空间位置安排线路时，称为车辆途径问题。线路时，称为车辆途径问题。二、VRP的背景及运用 车辆途径问题是由G.Dantzig和J.Ramser于1959年首先提出来的,很快引起运筹学、管理学、计

2、算机运用、组合数学、图论等学科的专家学者的高度注重。 其研讨结果在运输系统、物流配送系统、快递收发系统中都已得到广泛运用。三、VRP问题定义 对一系列发货点或收货点，组织适当的行车道路，使车辆有序地经过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下，到达一定的目的(如路程最短、费用最小、时间尽量少、运用车辆尽量少等)。四、VRP问题的分类n按义务特征分类按义务特征分类n 装货问题装货问题(Pure Pick Up )(Pure Pick Up )、卸货问题、卸货问题(Pure Delivery)(Pure Delivery)及装卸混合

3、问题及装卸混合问题(Combined Pick Up and Delivery)(Combined Pick Up and Delivery)n按义务性质分类按义务性质分类n 有对弧效力问题有对弧效力问题( (如中国邮递员问题如中国邮递员问题) ) 和对点效力问题和对点效力问题( (如游览商问题如游览商问题) ) n 以及混合效力问题以及混合效力问题( (如交通车道路安排如交通车道路安排问题问题) )n按车辆载货情况分类按车辆载货情况分类n 有满载问题和非满载问题有满载问题和非满载问题n按车场数目分类按车场数目分类n 有单车场问题和多车场问题有单车场问题和多车场问题n按车辆类型分类按车辆类型分

4、类n 有单车型问题和多车型问题有单车型问题和多车型问题n按车辆对车场的所属关系分类按车辆对车场的所属关系分类n 有车辆开放问题有车辆开放问题( (车辆可不前往车场车辆可不前往车场) )和车辆封锁问题和车辆封锁问题( (车辆必需前往车场车辆必需前往车场) )n按知信息的特征分类按知信息的特征分类n 有确定性有确定性VRPVRP和不确定性和不确定性VRP,VRP,其中不确其中不确定性定性VRP VRP 可进一步分为随机可进一步分为随机VRP(SVRP)VRP(SVRP)和和模糊模糊VRP(FVRP)VRP(FVRP)n按优化目的数来分类按优化目的数来分类n 有单目的问题和多目的问题有单目的问题和多

5、目的问题n按约束条件分类按约束条件分类n有间隔约束的有间隔约束的VRPVRP问题问题(Distance (Distance Constrained Vehicle Routing Problem)Constrained Vehicle Routing Problem)n有才干约束的有才干约束的VRPVRP问题问题(Vehicle (Vehicle Routing Problem with Capacity Routing Problem with Capacity Restriction )Restriction )n对称问题和非对称问题对称问题和非对称问题n三角不等式问题三角不等式问题按约束

6、条件分类有等需求问题(Equal Demand)和非等需求问题(Unequal Demand)有时间窗的VRP问题(Vehicle Routing Problem with Time Window) 该问题中还包括柔性时间窗约束和刚性时间窗约束 五、VRP问题的数学模型(1)问题问题 从一个配送中心出发，向多个客户从一个配送中心出发，向多个客户点送货，然后在同一天内前往到该点送货，然后在同一天内前往到该配送中心，要安排一个称心的运转配送中心，要安排一个称心的运转道路。道路。(2)知条件知条件配送中心拥有的车辆台数配送中心拥有的车辆台数m及每辆车的及每辆车的载分量吨位为载分量吨位为需求点需求点

7、数为数为n及每个点的需货量为及每个点的需货量为配送中心到各需求点的费用及各需求点配送中心到各需求点的费用及各需求点之间的费用为之间的费用为iP(1,2,.,)iW im(1,2,., )iR in(1,2,.,1;1,2,., ;,0ijC injn ij i 表示配送中心）五、VRP问题的数学模型(3)目的目的 各车辆行走的途径使总运输费用最小。各车辆行走的途径使总运输费用最小。(4)模型中符号定义模型中符号定义一切收货点的货物量需求为一切收货点的货物量需求为车辆的容量限制车辆的容量限制决策变量决策变量iWiRijkX 第k辆车从点i到点j 0 否那么 kiY 需求点i由车辆k送货 0 否那

8、么 ; ,0,1,.,1,2,. ;1,2,.,ij i jnin km 五、VRP问题的数学模型数学模型为：数学模型为：011110 =. .1, 2,.,;(1)11, 2,.,;(2 )0,1, 2,.,;1, 2,.,;(3)nnKijijkijknikikiKkiknijkkjiM inzCXs tR YWkmYinXYjn kK 00,1, 2,.,;1, 2,.,;(4 )0,1, 2,.,;1, 2,.,;(5),0,1, 2,.,;1, 2,.,(6 )nijkkijkjijkXYin kKYin kKXijn kK 或或 0每辆车所运送的货物量不超越其载分量每个需求点由且仅

9、由一辆车送货假设客户点j由车辆k送货，那么车辆k必由某点i到达点j假设客户点i由车辆k送货，那么车辆k送完该点的货后必到达另一点j六、VRP算法类型及简要引见VRP算法类型准确解法启发式算法分枝定界法分枝定界法(Branch and Bound Approach)割平面法割平面法(Cutting Planes Approach)网络流算法网络流算法(Network Flow Approach)动态规划算法动态规划算法(Dynamic Programming Approach)构造算法构造算法(Constructive Algorithm )两阶段算法两阶段算法(Two Phase Algori

10、thm)亚启发式算法亚启发式算法(Metaheuristics Algorithm)C-W节约算法算法的思想假定有n个访问地，把每个访问地看成一个点，并取其中的一个点作为基点。首先将每个点与基点相联接，构成线路1j1(j2，3,n)这样就得到一个具有n-1条线路的图。游览者按照此道路访问的n个点所走的路程总为 z=2c1j ,其中c1j 为点1到点j(j2，3,n)的路段长度，这里假定c1j cj1对一切点j。假设联接点i和j,即使游览者走弧(i,j),所节约的路程值(i,j)可计算如下：s(i,j)=2 c1i+2 c1j (c1i + c1j + cij )。对不同的点对s(i,j)越大，

11、所节约的路程越多，因此应优先将这段弧插入到游览线路中。算法的步骤算法的步骤(1)(1)选取基点，将基点与其他各点联接，得选取基点，将基点与其他各点联接，得到到n-1n-1条线路条线路1-j-1(j1-j-1(j2 2，3,n)3,n)(2)(2)对不违背条件的一切可联接点对对不违背条件的一切可联接点对(i,j)(i,j)计算节约值计算节约值s(i,j)=c1i + c1j cijs(i,j)=c1i + c1j cij(3)(3)将一切的将一切的s(i,j)s(i,j)按其值由大到小陈列。按其值由大到小陈列。(4)(4)按按s(i,j)s(i,j)值的上述顺序，逐个调查其端值的上述顺序，逐个调

12、查其端点点i i和和j j，假设满足以下条件，就将弧，假设满足以下条件，就将弧(i,j)(i,j)插入到线路中。其条件是：插入到线路中。其条件是：点点i i和点和点j j不在一条线路上不在一条线路上点点i i和点和点j j均与基点相邻。均与基点相邻。(5)(5)前往步骤前往步骤(4),(4),直至调查完一切的弧为止。直至调查完一切的弧为止。 经过上面的步骤，使问题的解逐渐得经过上面的步骤，使问题的解逐渐得到改善，最后到改善，最后到达称心解。到达称心解。 C-W节约算法y2520151050510152025xABCDEFG各点坐标：A(10,23)B(0,13)C(1,0)D(21,2)E(1

13、3,4)F(11,6)G(10,10)例：用C-W节约算法求解下述TSP问题，知访问点的位置如下所示各点坐标：A(10,23)B(0,13)C(1,0)D(21,2)E(13,4)F(11,6)G(10,10)2520151050510152025xABCDEFGy到 从ABCDEFGA014.1424.723.7119.2417.0313.00B013.0423.7115.8113.0410.44C020.1012.6511.6613.45D08.2510.7713.60E02.836.71F04.12G0各点对之间的间隔，cij=cji序号弧节约值序号弧节约值1(D,E)34.709(E,

14、G)25.532(E,F)33.4410(C,G)24.253(C,E)31.2911(D,G)23.114(C,F)30.0712(B,F)18.135(D,F)29.9713(B,E)17.576(C,D)28.3114(B,G)16.707(F,G)25.9115(B,D)14.148(B,C)25.80按各段弧节约值由大到小的顺序进展陈列序号弧线路及阐明插入该弧的节约值0A-B-A,A-C-A,A-D-A,A-E-A,A-F-A,A-G-A1(D,E)A-B-A,A-C-A,A-D-E-A,A-F-A,A-G-A34.702(E,F)A-B-A,A-C-A,A-D-E-F-A,A-G-

15、A33.443(C,E)E点与基点A不相邻，不插入04(C,F)A-B-A,A-D-E-F-C-A,A-G-A30.075，6(D,F)(C,D)这些点已在同一条线路上07(F,G)F点与基点A不相邻，不插入08(B,C)A-D-E-F-C-B-A,A-G-A25.89，10(E,G)(C,G)E点、C点与基点A不相邻，不插入011(D,G)A-G-D-E-F-C-B-A23.112520151050510152025xABCDEFGy最后得到的线路为A-G-D-E-F-C-B-A，线路总长度为76.52插入法算法思想算法思想 在已有的途径中插入别的需求点，从在已有的途径中插入别的需求点，从而

16、不断扩展配送途径，在插入其他需求而不断扩展配送途径，在插入其他需求点时，需检验能否满足最大运距约束、点时，需检验能否满足最大运距约束、最大载分量约束和作业时间约束等条件。最大载分量约束和作业时间约束等条件。算法步骤算法步骤分别对于每台配送车辆适中选择客户群。分别对于每台配送车辆适中选择客户群。在配送中心与客户群之间构筑途径，以此在配送中心与客户群之间构筑途径，以此作为初始途径。作为初始途径。对于客户群之外的客户对于客户群之外的客户k按照适当顺序，在按照适当顺序，在具有实施能够性而且使总的费用添加最具有实施能够性而且使总的费用添加最小。小。 PiPjP0PkPiPjP0PkCikCkiCijkk

17、ijikkjijjcccV由此带来的费用：其中 为插入客户k时，客户j的等待时间增量kjVSweep算法算法思想 顾客点的位置以极坐标给出。仓库假设在原点的位置，客户点按照角度的逐渐添加被排序，假设两个点有同样的角度，那么半径小的先访问。然后在满足可行性条件的前提下,按角度大小归并到不同的子途径中,最后再根据TSP的优化算法对所得到的子途径进展优化。算法步骤从仓库出发。在目前的车辆途径中参与目前序号最小的顾客点，假设车辆超载了，选择一个新的车辆，回到步骤1反复步骤2直到一切的客户点都被访问。构造完初始途径后，经过交换途径中的节点来改善调度。132456780度先途径后分组算法算法思想 先松弛模

18、型中关于车辆载重和间隔等的约束，构造一个或几个很长的途径，然后把这些很长的线路分解成一些短而可行的线路。算法步骤寻求对于每个节点经过一次且只经过一次的巡回途径。在满足步骤1上的途径中节点的延续性和给定的条件最大装载量或最大间隔下进展分组。确定各组需求点的最优访问顺序。 常用的分组方法有集合划分算法(Set Partitioning Approach)、集合覆盖算法(Set Covering Approach)、最优划分法(Optimal Partitioning Method)和填充曲线法(Spacefilling Curve Method)先分组后途径算法算法思绪 这种方法先按节点和/或弧的要求进展分组或划群,然后对每一组设计一条经济的道路。算法步骤先将客户按其地理位置和需求量合理地分成假设干组，每组客户的需求总量不超越配送车辆的装载限量。对各组加上仓库求巡回途径。 领域分派法Gillett&Miller的扇形分派法Marchetti&Spaccamela的极线分派法 领域分派法Karp的矩形分派法Haimovitch&