专题2车辆路径问题课件.pptx

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

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

3、very)n按任务性质分类按任务性质分类 有对弧服务问题(如中国邮递员问题)和对点服务问题(如旅行商问题)以及混合服务问题(如交通车路线安排问题)n按按车辆载货状况车辆载货状况分类分类 有满载问题和非满载问题第6页，共37页。n按按车场数目车场数目分类分类 有单车场问题和多车场问题n按按车辆类型车辆类型分类分类 有单车型问题和多车型问题n按按车辆对车场的所属关系车辆对车场的所属关系分类分类 有车辆开放问题(车辆可不返回车场)和车辆封闭问题(车辆必须返回车场)n按按已知信息的特征已知信息的特征分类分类 有确定性VRP和不确定性VRP,其中不确定性VRP 可进一步分为随机VRP(SVRP)和模糊V

4、RP(FVRP)第7页，共37页。n按按优化目标数来优化目标数来分类分类 有单目标问题和多目标问题n按按约束条件约束条件分类分类1.有距离约束的VRP问题(Distance Constrained Vehicle Routing Problem)2.有能力约束的VRP问题(Vehicle Routing Problem with Capacity Restriction)3.对称问题和非对称问题4.三角不等式问题第8页，共37页。n按按约束条件约束条件分类分类5.有等需求问题(Equal Demand)和非等需求问题(Unequal Demand)6.有时间窗的VRP问题(Vehicle Ro

5、uting Problem with Time Window)该问题中还包括柔性时间窗约束和刚性时间窗约束 第9页，共37页。五、VRP问题的数学模型(1)问题问题 从一个配送中心出发，向多个客户点送货，然后在同一天内返回到该配送中心，要安排一个满意的运行路线。(2)已知条件已知条件1.配送中心拥有的车辆台数m及每辆车的载重量（吨位）为2.需求点 数为n及每个点的需货量为3.配送中心到各需求点的费用及各需求点之间的费用为iP(1,2,.,)iW im(1,2,.,)iR in(1,2,.,1;1,2,.,;,0ijC injn ij i 表示配送中心）第10页，共37页。五、VRP问题的数学模

6、型(3)目标目标 各车辆行走的路径使总运输费用最小。(4)模型中符号定义模型中符号定义1.所有收货点的货物量需求为2.车辆的容量限制3.决策变量iWiRijkX1 第k辆车从点i到点j2 0 否则 kiY 1 需求点i由车辆k送货2 0 否则 ;,0,1,.,1,2,.;1,2,.,ij i jnin km 第11页，共37页。五、VRP问题的数学模型数学模型为：数学模型为：011110 =.1,2,.,;(1)11,2,.,;(2)0,1,2,.,;1,2,.,;(3)nnKijijkijknikikiKkiknijkkjiM inzCXs tR YWkmYinXYjn kK 00,1,2,

7、.,;1,2,.,;(4)0,1,2,.,;1,2,.,;(5),0,1,2,.,;1,2,.,(6)nijkkijkjijkXYin kKYin kKXijn kK 或或 0每辆车所运送的货物量不超过其载重量每个需求点由且仅由一辆车送货若客户点j由车辆k送货，则车辆k必由某点i到达点j若客户点i由车辆k送货，则车辆k送完该点的货后必到达另一点j第12页，共37页。六、VRP算法类型及简要介绍VRP算法类型分枝定界法分枝定界法(Branch and Bound Approach)割平面法割平面法(Cutting Planes Approach)网络流算法网络流算法(Network Flow A

8、pproach)动态规划算法动态规划算法(Dynamic Programming Approach)构造算法构造算法(Constructive Algorithm)两阶段算法两阶段算法(Two Phase Algorithm)亚启发式算法亚启发式算法(Metaheuristics Algorithm)第13页，共37页。C-W节约算法算法的思想算法的思想假定有n个访问地，把每个访问地看成一个点，并取其中的一个点作为基点。首先将每个点与基点相联接，构成线路1j1(j2，3,n)这样就得到一个具有n-1条线路的图。旅行者按照此路线访问的n个点所走的路程总为 z=2c1j,其中c1j 为点1到点j(

9、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)越大，所节约的路程越多，因此应优先将这段弧插入到旅行线路中。第14页，共37页。算法的步骤算法的步骤(1)选取基点，将基点与其他各点联接，得到n-1条线路1-j-1(j2，3,n)(2)对不违背条件的所有可联接点对(i,j)计算节约值s(i,j)=c1i+c1j cij(3)将所有的s(i,j)按其值由大到小排列。(4)按s(i,j)值的上述顺序，逐个考察其端点i和j

10、，若满足以下条件，就将弧(i,j)插入到线路中。其条件是：1)点i和点j不在一条线路上2)点i和点j均与基点相邻。(5)返回步骤(4),直至考察完所有的弧为止。通过上面的步骤，使问题的解逐步得到改善，最后达到满意解。C-W节约算法第15页，共37页。y2520151050510152025xABCDEFG各点坐标：A(10,23)B(0,13)C(1,0)D(21,2)E(13,4)F(11,6)G(10,10)例：用C-W节约算法求解下述TSP问题，已知访问点的位置如下所示第16页，共37页。各点坐标：A(10,23)B(0,13)C(1,0)D(21,2)E(13,4)F(11,6)G(1

11、0,10)2520151050510152025xABCDEFGy第17页，共37页。到 从ABCDEFGA014.1424.723.7119.2417.0313.00B013.0423.7115.8113.0410.44C020.1012.6511.6613.45D08.2510.7713.60E02.836.71F04.12G0各点对之间的距离，cij=cji第18页，共37页。序号弧节约值序号弧节约值1(D,E)34.709(E,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,

12、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按各段弧节约值由大到小的顺序进行排列第19页，共37页。序号弧线路及说明插入该弧的节约值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-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

13、,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.11第20页，共37页。2520151050510152025xABCDEFGy最后得到的线路为A-G-D-E-F-C-B-A，线路总长度为76.52第21页，共37页。插入法算法思想算法思想 在已有的路径中插入别的需求点，从而不断扩大配送路径，在插入其他需求点时，需检验是否满足最大运距约束、最大载重量约束和作业时间约束等条件。算法步骤算法步骤1.分别对于每

14、台配送车辆适当选择客户群。2.在配送中心与客户群之间构筑路径，以此作为初始路径。3.对于客户群之外的客户k按照适当顺序，在具有实施可能性而且使总的费用增加最小。第22页，共37页。PiPjP0PkPiPjP0PkCikCkiCijkkijikkjijjcccV由此带来的费用：其中 为插入客户k时，客户j的等待时间增量kjV第23页，共37页。Sweep算法算法思想 顾客点的位置以极坐标给出。仓库假设在原点的位置，客户点按照角度的逐步增加被排序，如果两个点有同样的角度，那么半径小的先访问。然后在满足可行性条件的前提下,按角度大小归并到不同的子路径中,最后再根据TSP的优化算法对所得到的子路径进行

15、优化。算法步骤1.从仓库出发。2.在目前的车辆路径中加入目前序号最小的顾客点，如果车辆超载了，选择一个新的车辆，回到步骤13.重复步骤2直到所有的客户点都被访问。4.构造完初始路径后，通过交换路径中的节点来改善调度。第24页，共37页。132456780度第25页，共37页。先路径后分组算法算法思想 先松弛模型中关于车辆载重和距离等的约束，构造一个或几个很长的路径，然后把这些很长的线路分解成一些短而可行的线路。算法步骤1.寻求对于每个节点通过一次且只通过一次的巡回路径。2.在满足步骤1上的路径中节点的连续性和给定的条件（最大装载量或最大距离）下进行分组。3.确定各组需求点的最优访问顺序。第26

16、页，共37页。常用的分组方法有集合划分算法(Set Partitioning Approach)、集合覆盖算法(Set Covering Approach)、最优划分法(Optimal Partitioning Method)和填充曲线法(Spacefilling Curve Method)第27页，共37页。先分组后路径算法算法思路 这种方法先按节点和/或弧的要求进行分组或划群,然后对每一组设计一条经济的路线。算法步骤1.先将客户按其地理位置和需求量合理地分成若干组，每组客户的需求总量不超过配送车辆的装载限量。2.对各组加上仓库求巡回路径。第28页，共37页。领域分派法Gillett&Mil

17、ler的扇形分派法Marchetti&Spaccamela的极线分派法第29页，共37页。领域分派法Karp的矩形分派法Haimovitch&Rinnooy Kan的圆形分派法第30页，共37页。近年来关于VRP的研究国内关于VRP研究的特点是：(1)所研究的问题类型确定性占大多数。(2)开始使用蚁群算法、粒子群、免疫算法等新的启发式算法解决VRP问题。(3)研究具有时间窗约束的VRP。(4)我国开始研究关于开路式VRP，但是文献非常少，仅1篇。第31页，共37页。近年来关于VRP的研究国外关于VRP研究的特点是：国外对VRP问题研究比国内早大约30余年，因此国外关于VRP问题的文献相当丰富，

18、而且对该问题的研究还有逐年增加的趋势。国外的VRP研究主要集中在新的约束条件或新的问题实例下VRP的建模及快速求解方法上，来更好的适用于不同的实际情况。第32页，共37页。The EndThank You第33页，共37页。depotcustomer第34页，共37页。中国邮递员问题 一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程第35页，共37页。TSP问题 旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。第36页，共37页。VRP资源n学校的学术期刊网及英文全文数据库n搜索引擎，如google、baidu等n文摘索引数据库，如Scopus等第37页，共37页。