第六章配送路线选择与车辆调度-徐天亮.ppt

1、1,第六章 配送路线选择与车辆调度,主要内容： 配送路线安排与车辆调度问题及节约法原理； 单中心配送路线选择与车辆调度； 多中心配送路线选择与车辆调度； 货车配载 。,2,第一节 配送路线安排与车辆调度问题及节约法原理,一、配送路线安排与车辆调度问题 配送路线安排与车辆优化调度问题常被分为车辆路线安排问题（Vehicle Routing Problem，简记VRP）和车辆调度问题（Vehicle Scheduling Problem，简记VSP），前者仅从空间位置考虑车辆路线的安排和车辆调度，后者则要考虑时间要求。显然VSP问题比VRP 问题讨论的范围宽，或者说，VSP问题是有时间约束的VRP

2、 问题。本书主要讨论VRP问题。,3,VRP问题的描述,VRP问题一般可描述为：对一系列装货点或（和）卸货点，组织适当合理的行车路线，使车辆有序地通过它们，在满足一定的约束（如货物需求量、发送量，车辆容量、数目限制、车辆行驶里程限制等）条件下，达到一定的目标（如最短路程、最小费用、最短时间、最少车辆等）。,4,VRP问题的分类,VRP问题又根据不同标准分为：车辆满载问题（一个用户的货运量大于一辆车的容量，完成任务需要多辆车）与非满载问题（一个用户的货运量不大于一辆车的容量，完成任务只需要一辆车）、单车场问题（一个货场或一个配送中心）与多车场问题（多个货场或多个配送中心）、单车型（所有车辆容量相

3、同）与多车型问题（车辆容量不全相同），以及优化目标的单目标与多目标问题。,5,二、VRP问题精确求解方法的局限性,1. VRP问题求解思路 VRP问题的求解方法一般相当复杂，通常的做法是应用相关技术将问题分解或者转化为一个或多个已经研究过的基本问题（如旅行商问题、指派问题、运输问题、最短路问题、最小费用流问题、中国邮递员问题等），再使用相对比较成熟的基本理论和方法进行求解。,6,2.精确算法的局限性,VRP问题的求解方法可分为两大类，即精确算法和启发式算法。精确算法主要有分枝定界法、割平面法、网络流算法、动态规划方法等。精确算法随着配送系统规模的增大，其计算量呈指数递增，使得获取系统最优解越来

4、越困难。因此，精确算法在实际应用中受到很大的局限。,7,三、节约法原理,为了克服精确优化方法的不足，人们提出了许多能获得“满意”解的启发式算法。启发式算法是一种基于直观或经验构造的算法，它运用一些经验法则，并通过模仿人的跟踪校正过程来求得系统的满意解。 启发式算法中最具有代表性的是由Clarke和Wright提出的节约法（Saving Method）。,8,节约法的基本原理：,9,10,11,第二节 单中心配送路线选择与车辆调度,12,如果将配送中心也作为一个用户点，货车从配送中心出发，对所有用户巡回送货后回到配送中心，这样就把单车非满载车辆的配送路线安排问题转化为个点的旅行商问题（Trave

5、ling Salesman Problem，简记TSP）。它的解是：从配送中心出发，对所有用户巡回一次回到配送中心的距离最短的路线。,13,14,15,16,17,18,19,20,t06+t16+t26+t36+t46+t56+t76=2;因此如果t67=t76=1,则t06=1 含义就是配送第6个客户的车辆不是完成任务直接返回中心了。 t07+t17+t27+t37+t47+t57+t67=2;因此如果t67=t76=1,则t07=1 含义就是配送第7个客户的车辆不是完成任务直接返回中心了。,21,22,23,二、多车非满载配送路线安排与车辆调度,24,25,26,此模型用精确算法求解更加

6、困难，下面仍用节约法求解此类问题的满意解。求解的过程与例6-1基本相同，只是在方案改进的过程中，寻找具有最大节约量的用户i、j时，增加了考虑车辆载重量和可调度车辆数的约束，而且，车辆调度时优先使用载重量大的车辆。,27,例：由配送中心B0向12个用户Bj (j=1,2,12)送货，各点之间的运输里程和各用户的需求量见表6-1。表6-2为可供调度的车辆数目及其载重量。,表6-1 各点之间里程表（单位：公里） 表6-2 可供调度的汽车,28,解：由表6-1中的数据，按节约量公式（6.5）计算每两用户之间的节约量Si,j 列于表6-3，称节约量表。,表6-3 节约量表（单位：公里）,如:S1,2d0

7、,1+d0,2d1,2 9145 18,S2,4d0,2+d0,4d2,4 142317 20,29,设ti,j(i=0,1,12; j=1,2,12；ij )表示i、j两点是否连接在一起的决策变量，并对其取值作如下定义： ti,j=1 表示i、j用户连接，即在同一巡回路线中； ti,j=0 表示i、j用户不连接，即不在同一巡回路线中； t0,j=2 表示j用户只与配送中心B。连接，由一台车单独送货。 根据以上定义，对任一用户j,有以下等式成立：,j=1, , n （6.7）,30,迭代求解：,第一步，求初始解 每用户各派一台车单独送货，得初始方案如表64。表中B0列中的数字为ti,j的取值。

8、此方案的总行程为728公里。 按表64的初始方案，所用汽车台数如表65所列。,31,表6-4 初始方案 表65 初始方案所用汽车台数,32,第二步，按下述条件在初始方案表中寻找具有最大节约量的用户i、j,（1）t0,i、t0,j0ij； （2）Bi、Bj尚未连接在一条巡回路线中； （3）考虑车辆台数和载重量的约束。 如果最大节约量有两个或两个以上相同时，可随机取一个。 按此条件，在初始方案表64中寻到具有最大节约量的一对用户为：i=11,j=12，其节约量为92公里。将11和12两用户连接到一个运输回路中，并在对应的格中记上t11,12的值，用“1）”表示。,33,第三步，按ti,j的定义和公

9、式67修正ti,j的值。,B11与B12连接，即令t11,12=1，由公式（6.7）得： t0,11=1 t0,12=1 其他不变。,34,第四步，按以下原则修正bi、bj,（1）t0,i或t0,j等于0时，令bi或bj等于0； （2）t0,i或t0,j等于1时，令bi或bj等于所在巡回路线中所有用户需求量之和，以此代替原bi或bj,因此 b11=b12=1.1+1.7=2.8（吨） 得改进方案（表6-6、表6-7）。 改进后的方案比原方案少一台发送车，总发送距离减少92公里。,35,表6-6 第一次迭代方案 表6-7 该方案所用汽车台数,36,重复第二步，按下述条件在第一次迭代方案表66中寻

10、找具有最大节约量的用户i、j,（1）t0i、t0j0ij； （2）Bi、Bj尚未连接在一条巡回路线上； （3）考虑车辆台数和载重量的约束。 如果最大节约量有两个或两个以上相同时，可随机取一个。 按此条件，在表66中寻得具有最大节约量的用户有两对，分别为：i=10,j=11和i=10,j=12 ，其节约量均为84公里，任取一对i=10, j=11，将其连接到一个回路中。,37,重复第三步，按ti,j的定义和公式（6.7）修正ti,j的值。,B10与B11连接，则t10,11=1，由公式（6.7）得： t0,11=0 t0,10=1 其他不变。,38,重复第四步，按以下原则修正bi、bj,（1）t

11、0,i或t0,j等于0时，令bi或bj等于0； （2）t0,i或t0,j等于1时，令bi或bj等于所在巡回路线中所有用户需求量之和，以此代替原bi或bj,因此 b10=b12=2.81.6=4.4（吨） b11=0 得第二次迭代方案（表6-8、表6-9）。 第二次迭代方案比第一次迭代方案又少一台配送车，只需10台，其中一台为5吨车；总发送距离比前一方案减少84公里。,39,表6-8 第二次迭代方案 表6-9 该方案所用汽车台数,40,表6-10 第三次迭代方案 表6-11 该方案所用汽车台数,为什么不选B10B9、B10B8？,可否将B11与B7连接？,41,得到第一条配送路线：B0B7B10

12、B11B12B0，行程112公里，用6吨车配送，载重5.6吨； 开始下一条配送路线的选择，过程如何？,42,表6-12 第四次迭代方案 表6-13 该方案所用汽车台数,43,表6-14 第五次迭代方案 表6-15 该方案所用汽车台数,44,得到二条配送路线：B0B6B8B9B0，行程80公里，用6吨车配送，载重5.1吨； 再开始下一条配送路线的选择，过程与前相同。,45,反复进行第二第四步，直至没有可连接的用户时为止，得最终满意配送方案如表6-16，表6-17。 表6-16 满意配送方案 表6-17 最终方案所用汽车台数,46,满意配送方案有四条配送路线，它们是：,B0B7B10B11B12B

13、0，行程112公里，用6吨车配送，载重5.6吨； B0B6B8B9B0，行程80公里，用6吨车配送，载重5.1吨； B0B5B0，行程44公里，用4吨车配送，载重1.7吨； B0B1B2B3B4B0，行程54公里，用6吨车配送，载重5.8吨； 满意方案共用四台车配送，总行程290公里。,47,第三节 多中心配送路线选择与车辆调度,一、制定多中心配送方案的基本思想 多中心配送与单中心配送不同的是，制定配送计划时，不仅要选择配送路线和调度车辆，还要确定各配送中心所服务的用户对象。 所以，制定多中心配送的配送计划，首先将所有用户按一定的方法分派给各配送中心，形成每个配送中心的服务区，然后用上一节讨论

14、的节约法在各配送中心的服务区选择配送路线和调度车辆。,48,二、制定多中心配送方案的边界点方法,1.边界点与非边界点 设di(t)表示用户i与配送中心t之间的距离，记集合 ，p是配送中心的个数。计算 ，minDi和subminDi分别表示集合Di中的最小值和次小值；取适当的（0 1），比较r(i)与的大小，当r(i)，称i为非边界点，否则为边界点。 显然，通过改变值的大小可以控制边界点的个数。,49,2.非边界点的分派,对非边界点，按最近分派原则，将它们分别分派给离它们最近的配送中心。,50,3.边界点的分派,对边界点的分派，按r(i)1 和r(i)=1 两种情况分别处理。 （1）当r(i)1

15、时，用节约法进行分派。 首先考虑由最近的配送中心对每个点单独派车配送，构成初始解。一旦两个点或多个点已被分派给同一个配送中心时，这些点为永久分派，不能再分派给其他配送中心；如果i，j不在同一配送中心，按一般节约法将其连接并分别试分配给某一配送中心，连接产生的节约量按下式（6.8）计算。,51,式中： 选 最大者，将i,j分派给对应的t。,j点还未给一永久分派，挪到非最近配送中心 否则,i点还未给一永久分派，挪到非最近配送中心 否则,52,（2）当r(i)=1时，按如下方法分派。 将i分别试分派给各配送中心t（t1，p)，若j和k是已分派给配送中心t的用户，将点i插入用户j与k之间；若t中心只有

16、一个用户j，则将i插入j与t之间。对配送中心t产生的运输距离增加量按（6.9）式计算。 按增加量最小原则，将用户i分派给使djik(t)或dij(t)最小的配送中心。,（6.9）,53,对所有用户分派完毕后，分别在每个配送中心的服务区域内，用节约法确定配送路线和进行车辆调度，得到各配送中心的配送计划。,54,例：假设有三个配送中心（编号是1,2,3）给10个用户（编号是4,13）配送货物。配送中心与用户以及用户与用户之间的运输距离如表6-18。,表6-18配送中心及用户之间的距离（单位：公里）,55,计算r(i)，得表6-19。 表6-19 r(i)数值表,56,取=0.7,所有r(i)的用户分派给最近的配送中心，如表6-20。 表6-20非边界点用户分派表,57,对r(i)且r(i)1的点8，10和12，根据式（6.8）计算 (i,j=8,10,12;t=1,2,3)，并按从大到小的顺序排列，列于表6-21。 表6-21 r(i)1的边界点用