6章 配送路线选择与车辆调度(精品).ppt

《6章 配送路线选择与车辆调度(精品).ppt》由会员分享，可在线阅读，更多相关《6章 配送路线选择与车辆调度(精品).ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 配送路线选择与车辆调度配送路线选择与车辆调度学习要点：学习要点：u单中心配送路线选择与车辆调度；u多中心配送路线选择与车辆调度。1第一节第一节 单中心配送路线选择与车辆调度单中心配送路线选择与车辆调度 一、单中心配送的节约法原理一、单中心配送的节约法原理 单中心配送，是指一个配送中心向所属n个用户送货，各用户的需求量为bj(j=1,2,n)。假定以汽车作为配送车辆，配送车按其载重量的大小不同有p种，载重量为QK(K=1,2p)的发送车有xK台,QK-1QK,且 （61）解决这类配送问题的一种有效方法节约法。节约法是由克拉克（Clarke）和怀特（Wright）提出来的，是一种启发

2、式方法。2节约法的基本原理节约法的基本原理 如图62，由物流网点B0向两个用户B1、B2送货，B0至各用户的最短运输距离分别为d0,1和d0,2；用户需求量各为b1，b2；两用户之间的最短运输距离为d1,2。当用两台车分别对两个用户各自往返送货时，运输总距离为：B2B1B02d0,22d0,1图图32 各用户分别送货各用户分别送货3 如果改用一台车巡回送货（假定汽车能够负荷b1、b2时），如图63，则总运输距离为 后一种方案比前一种方案可节约运输里程 式65称为节约量公式，为B1和B2之间的节约量。显然，将节约量大的两个用户连接起来采用巡回方式送货，则可获得较大的节约。（6-5）B2B1B0d

3、1,2d0,2d0,1图图63 节约法示意图节约法示意图4二、节约法的计算过程节约法的计算过程 设由配送中心B0向用户Bj(j=1,2,n)送货，各用户需求量为bj；配送中心与用户间的最短距离为d0,j，用户之间的距离为di,j(i=1,2,n;j=1,2,n)；配送车按其载重量的大小不同有p种，载重量为QK(K=1,2p)的发送车有xK台，QK-1QK。假定：（6-6）5计算过程如下：计算过程如下：先求初始解。先求初始解。假定载重量最小的汽车台数是无限多的，即x1=。对每一用户各派一台最小的车往返送货，得一初始可行方案。显然这一方案的运输效率是很低的，而且x1=的假设实际也不存在。6 然后迭

4、代求满意解。然后迭代求满意解。计算每两个用户之间的节约量，按节约法原理对方案进行修正。修正时，以节约量的大小为顺序，从大到小依次将节约量大的用户连接到巡回路线中，并考虑汽车载重量和各种车辆台数的约束。反复进行这样的修正，直至再没有可连接的用户时为止。整个计算过程可在节约量表上进行。下面用例子说明计算过程。7 例：由配送中心B0向12个用户Bj(j=1,2,12)送货，各点之间的运输里程和各用户的需求量见表6-1。表6-2为可供调度的车辆数目及其载重量。表表6-1 6-1 各点之间里程表（单位：公里）各点之间里程表（单位：公里）表表6-2 6-2 可供调度的汽车可供调度的汽车8 解：由表6-1中

5、的数据，按节约量公式（6-5）计算每两用户之间的节约量Si,ji,j 列于表6-3，称节约量表。表表6-3 6-3 节约量表（单位：公里）节约量表（单位：公里）如如:S S1,21,2d d0,10,1+d d0,20,2d d1,2 1,2 9 914145 5 1818 S S2,42,4d d0,20,2+d d0,40,4d d2,4 2,4 141423231717 20209 设ti,j(i=0,1,12;j=1,2,12；ij)表示i、j两点是否连接在一起的决策变量，并对其取值作如下定义：ti,j=1 表示i、j用户连接，即在同一巡回路线中；ti,j=0 表示i、j用户不连接，即

6、不在同一巡回路线中；t0,j=2 表示j用户只与配送中心B。连接，由一台车单独送货。根据以上定义，对任一用户j,有以下等式成立：j=1,n （6-7）10迭代求解：迭代求解：第一步，求初始解第一步，求初始解 每用户各派一台车单独送货，得初始方案如表64。表中B0列中的数字为ti,j的取值。此方案的总行程为728公里。按表64的初始方案，所用汽车台数如表65所列。11 表表6-4 6-4 初始方案初始方案 表表6 65 5 初始方案所用汽车台数初始方案所用汽车台数12 第二步，按下述条件在初始方案表中寻找具有第二步，按下述条件在初始方案表中寻找具有最大节约量的用户最大节约量的用户i i、j j（

7、1）t0,i、t0,j0ij；（2）Bi、Bj尚未连接在一条巡回路线中；（3）考虑车辆台数和载重量的约束。如果最大节约量有两个或两个以上相同时，可随机取一个。按此条件，在初始方案表64中寻到具有最大节约量的一对用户为：i=11,j=12，其节约量为92公里。将11和12两用户连接到一个运输回路中，并在对应的格中记上t11,12的值，用“1）”表示。13 第三步，按第三步，按t ti,ji,j的定义和公式的定义和公式6 67 7修正修正t ti,ji,j的值。的值。B11与B12连接，即令t11,12=1，由公式67得：t0,11=1 t0,12=1 其他不变。14第四步，按以下原则修正第四步，

8、按以下原则修正b bi i、b bj j （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公里。15表表6-6 6-6 第一次迭代方案第一次迭代方案表表6-7 6-7 该方案所用汽车台数该方案所用汽车台数16 重复重复第二步，按下述条件在第一次迭代方案表第二步，按下述条件在第一次迭代方案表6 66 6中寻找具有最大节约量的用户中寻找具有最大节约量的用

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

10、步，按以下原则修正b bi i、b bj j （1）t0,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公里。19表6-8第二次迭代方案表6-9该方案所用汽车台数该方案所用汽车台数20表表6-10 6-10 第三次迭代方案第三次迭代方案 表表6-11 6-11 该方案所用汽车台数该方案所用汽车

11、台数 为什么不选为什么不选B B1010B B9 9、B B1010B B8 8？可否将可否将B B1111与与B B7 7连连接？接？21得到第一条配送路线：B0B7B10B11B12B0，行程112公里，用6吨车配送，载重5.6吨；开始下一条配送路线的选择，过程如何？22 表表6-12 6-12 第四次迭代方案第四次迭代方案 表表6-13 6-13 该方案所用汽车台数该方案所用汽车台数23表表6-14 6-14 第五次迭代方案第五次迭代方案 表表6-15 6-15 该方案所用汽车台数该方案所用汽车台数24得到二条配送路线：B0B6B8B9B0，行程80公里，用6吨车配送，载重5.1吨；再开

12、始下一条配送路线的选择，过程与前相同。25 反复进行第二第四步，直至没有可连接的用户时为止，得最终满意配送方案如表6-16，表6-17。表表6-16 6-16 满意配送方案满意配送方案 表表6-17 6-17 最终方案所用汽车台数最终方案所用汽车台数26 满意配送方案有四条配送路线，它们是：B0B7B10B11B12B0，行程112公里，用6吨车配送，载重5.6吨；B0B6B8B9B0，行程80公里，用6吨车配送，载重5.1吨；B0B5B0，行程44公里，用4吨车配送，载重1.7吨；B0B1B2B3B4B0，行程54公里，用6吨车配送，载重5.8吨；满意方案共用四台车配送，总行程290公里。2

13、7第三节第三节 多中心配送路线选择与车辆调度多中心配送路线选择与车辆调度一、制定多中心配送方案的基本思想一、制定多中心配送方案的基本思想多中心配送与单中心配送不同的是，制定配送计划时，不仅要选择配送路线和调度车辆，还要确定各配送中心所服务的用户对象。所以，制定多中心配送的配送计划，首先将所有用户按一定的方法分派给各配送中心，形成每个配送中心的服务区，然后用上一节讨论的节约法在各配送中心的服务区选择配送路线和调度车辆。28 二、制定多中心配送方案的边界点方法二、制定多中心配送方案的边界点方法 1.1.边界点与非边界点边界点与非边界点 设di(t)表示用户i与配送中心t之间的距离，记集合 ，p是配

14、送中心的个数。计算 ，minDi和subminDi分别表示集合Di中的最小值和次小值；取适当的（0 1），比较r(i)与的大小，当r(i)，称i为非边界点，否则为边界点。显然，通过改变值的大小可以控制边界点的个数。29 2.2.非边界点的分派非边界点的分派 对非边界点，按最近分派原则，将它们分别分派给离它们最近的配送中心。30 3.3.边界点的分派边界点的分派 对边界点的分派，按r(i)1 和r(i)=1 两种情况分别处理。（1）当 r(i)1时，用 节 约 法 进 行 分 派。首先考虑由最近的配送中心对每个点单独派车配送，构成初始解。一旦两个点或多个点已被分派给同一个配送中心时，这些点为永久

15、分派，不能再分派给其他配送中心；如果i，j不在同一配送中心，按一般节约法将其连接并分别试分配给与之对应的两个配送中心，连接产生的节约量按下式（68）计算。31式中：选最大者，将i,j分派给对应的t。j点还未给一永久分派，挪到非最近点时点还未给一永久分派，挪到非最近点时否则否则 i点还未给一永久分派，挪到非最近点时点还未给一永久分派，挪到非最近点时否则否则 32（2）当r(i)=1时，按如下方法分派。将i分别试分派给各配送中心t（t1，p)，若j和k是已分派给配送中心t的用户，将点i插入用户j与k之间；若t中心只有一个用户j，则将i插入j与t之间。对配送中心t产生的运输距离增加量按（69）式计算

16、。按增加量最小原则，将用户i分派给使djik(t)或dij(t)最小的配送中心。（69）33 对所有用户分派完毕后，分别在每个配送中心的服务区域内，用节约法确定配送路线和进行车辆调度，得到各配送中心的配送计划。34 例：例：假设有三个配送中心（编号是1,2,3）给10个用户（编号是4,13）配送货物。配送中心与用户以及用户与用户之间的运输距离如表6-18。表表6-18 配送中心及用户之间的距离（单位：公里）配送中心及用户之间的距离（单位：公里）35计算r(i)，得表6-19。表表6-196-19 r(ir(i)数值表数值表36取=0.7,所有r(i)的用户分派给最近的配送中心，如表6-20。表

17、表6-20非边界点用户分派表非边界点用户分派表37对r(i)且r(i)1的点8，10和12，根据式（68）计算 (i,j=8,10,12;t=1,2,3)，并按从大到小的顺序排列，列于表6-21。表表6-21 r(i)1的边界点用户试连接的节约量表的边界点用户试连接的节约量表根据表6-21，按节约量最大原则，把用户8和10分派给配送中心1，得到永久分配。把用户12分派给配送中心3。38对r(i)=1的用户13，分别试分派给各配送中心，根据式（69）计算最小增加值，并按从小到大的顺序排列，列于表6-22。表表622 用户用户13试分派增加值试分派增加值根据表6-22，按增加值最小原则，把用户13分派给中心1，并插入到用户5和10之间，得最终分派方案，如表623。39表表623 最终用户分派方案最终用户分派方案 对各个配送中心分派的用户，再用节约法求每个配送中心的配送方案，得到最后结果。40