6章-配送路线选择与车辆调度方案

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 配送路线选择与车辆调度,学习要点：,单中心配送路线选择与车辆调度；,多中心配送路线选择与车辆调度。,1,第一节 单中心配送路线选择与车辆调度,一、单中心配送的节约法原理,单中心配送，是指一个配送中心向所属n个用户送货，各用户的需求量为,b,j,(,j,=1,2,n,)。假定以汽车作为配送车辆，配送车按其载重量的大小不同有,p,种，载重量为,Q,K,(,K,=1,2,p,)的发送车有,x,K,台,Q,K,-1,Q,K,且,（61）,解决这类配送问题的一种有效方法节约法。节约法是由克拉克（Clarke）和怀特（Wright）提出来的，是一种启发式方法。,2,节约法的基本原理,如图62，由物流网点,B,0,向两个用户,B,1,、,B,2,送货，,B,0,至各用户的最短运输距离分别为,d,0,1,和,d,0,2,；用户需求量各为,b,1,，,b,2,；两用户之间的最短运输距离为,d,1,2,。当用两台车分别对两个用户各自往返送货时，运输总距离为：,B,2,B,1,B,0,2d,0,2,2d,0,1,图32 各用户分别送货,3,如果改用一台车巡回送货（假定汽车能够负荷,b,1,、,b,2,时），如图63，则总运输距离为,后一种方案比前一种方案可节约运输里程,式,6,5,称为节约量公式，,为,B,1,和,B,2,之间的节约量。,显然，将节约量大的两个用户,连接起来采用巡回方式送货，,则可获得较大的节约。,（6-5）,B,2,B,1,B,0,d,1,2,d,0,2,d,0,1,图63 节约法示意图,4,二、,节约法的计算过程,设由配送中心,B,0,向用户,B,j,(,j,=1,2,n,)送货，各用户需求量为,b,j,；配送中心与用户间的最短距离为,d,0,j,，用户之间的距离为,d,i,j,(,i,=1,2,n,;,j,=1,2,n)；配送车按其载重量的大小不同有,p,种，载重量为,Q,K,(,K,=1,2,p,)的发送车有,x,K,台，,Q,K,-1,Q,K,。,假定：,（6-6）,5,计算过程如下：,先求初始解。,假定载重量最小的汽车台数是无限多的，即x,1,=。对每一用户各派一台最小的车往返送货，得一初始可行方案。显然这一方案的运输效率是很低的，而且,x,1,=的假设实际也不存在。,6,然后迭代求满意解。,计算每两个用户之间的节约量，按节约法原理对方案进行修正。修正时，以节约量的大小为顺序，从大到小依次将节约量大的用户连接到巡回路线中，并考虑汽车载重量和各种车辆台数的约束。反复进行这样的修正，直至再没有可连接的用户时为止。,整个计算过程可在节约量表上进行。,下面用例子说明计算过程。,7,例：由配送中心,B,0,向12个用户,B,j,(j=1,2,12)送货，,各点之间的运输里程和各用户的需求量见表6-1。表6-2为可供调度的车辆数目及其载重量,。,表6-1 各点之间里程表（单位：公里）表6-2 可供调度的汽车,8,解：由表,6-1,中的数据，按节约量公式（,6-5,）计算每两用户之间的节约量S,i,j,列于表,6-3,，称节约量表。,表6-3 节约量表（单位：公里）,如:,S,1,2,d,0,1,+,d,0,2,d,1,2,9145,18,S,2,4,d,0,2,+,d,0,4,d,2,4,142317,20,9,设,t,i,j,(,i,=0,1,12;,j,=1,2,12；,i,j,)表示,i,、,j,两点是否连接在一起的决策变量，并对其取值作如下定义：,t,i,j,=1 表示,i,、,j,用户连接，即在同一巡回路线中；,t,i,j,=0 表示,i,、,j,用户不连接，即不在同一巡回路线中；,t,0,j,=2 表示,j,用户只与配送中心,B,。连接，由一台车单独送货。,根据以上定义，对任一用户j,有以下等式成立：,j=1,n,（6-7）,10,迭代求解：,第一步，求初始解,每用户各派一台车单独送货，得初始方案如表64。表中,B,0,列中的数字为,t,i,j,的取值。此方案的总行程为728公里。,按表64的初始方案，所用汽车台数如表65所列。,11,表6-4 初始方案 表65 初始方案所用汽车台数,12,第二步，按下述条件在初始方案表中寻找具有最大节约量的用户,i,、,j,（1）,t,0,i,、,t,0,j,0,i,j,；,（2）,B,i,、,B,j,尚未连接在一条巡回路线中；,（3）考虑车辆台数和载重量的约束。,如果最大节约量有两个或两个以上相同时，可随机取一个。,按此条件，在初始方案表64中寻到具有最大节约量的一对用户为：,i,=11,j,=12，其节约量为92公里。将11和12两用户连接到一个运输回路中，并在对应的格中记上,t,11,12,的值，用“1）”表示。,13,第三步，按,t,i,j,的定义和公式67修正,t,i,j,的值。,B,11,与,B,12,连接，即令,t,11,12,=1，由公式67得：,t,0,11,=1,t,0,12,=1,其他不变。,14,第四步，按以下原则修正,b,i,、,b,j,（1）,t,0,i,或,t,0,j,等于0时，令,b,i,或,b,j,等于0；,（2）,t,0,i,或,t,0,j,等于1时，令,b,i,或,b,j,等于所在巡回路线中所有用户需求量之和，以此代替原,b,i,或,b,j,因此,b,11,=,b,12,=1.1+1.7=2.8（吨）,得改进方案（表6-6、表6-7）。,改进后的方案比原方案少一台发送车，总发送距离减少92公里。,15,表6-6 第一次迭代方案,表6-7 该方案所用汽车台数,16,重复第二步，按下述条件在第一次迭代方案表66中寻找具有最大节约量的用户,i,、,j,（1）,t,0,i,、,t,0,j,0,i,j,；,（2）,B,i,、,B,j,尚未连接在一条巡回路线上；,（3）考虑车辆台数和载重量的约束。,如果最大节约量有两个或两个以上相同时，可随机取一个。,按此条件，在表66中寻得具有最大节约量的用户有两对，分别为：,i,=10,j,=11和,i,=10,j,=12，其节约量均为84公里，任取一对,i,=10,j,=11，将其连接到一个回路中。,17,重复,第三步，按,t,i,j,的定义和公式67修正,t,i,j,的值。,B,10,与,B,11,连接，则,t,10,11,=1，由公式67得：,t,0,11,=0,t,0,10,=1,其他不变。,18,重复第四步，按以下原则修正,b,i,、,b,j,（1）,t,0,i,或,t,0,j,等于0时，令,b,i,或,b,j,等于0；,（2）,t,0,i,或,t,0,j,等于1时，令,b,i,或,b,j,等于所在巡回路线中所有用户需求量之和，以此代替原,b,i,或,b,j,因此,b,10,=,b,12,=2.81.6=4.4（吨）,b,11,=,0,得第二次迭代方案（表6-8、表6-9）。,第二次迭代方案比第一次迭代方案又少一台配送车，只需10台，其中一台为5吨车；总发送距离比前一方案减少84公里。,19,表6-8 第二次迭代方案 表6-9,该方案所用汽车台数,20,表6-10 第三次迭代方案 表6-11 该方案所用汽车台数,为什么不选B,10,B,9,、B,10,B,8,？,可否将B,11,与B,7,连接？,21,得到第一条配送路线：,B,0,B,7,B,10,B,11,B,12,B,0,，行程112公里，用6吨车配送，载重5.6吨；,开始下一条配送路线的选择，过程如何？,22,表6-12 第四次迭代方案 表6-13 该方案所用汽车台数,23,表6-14 第五次迭代方案 表6-15 该方案所用汽车台数,24,得到二条配送路线：,B,0,B,6,B,8,B,9,B,0,，行程80公里，用6吨车配送，载重5.1吨；,再开始下一条配送路线的选择，过程与前相同。,25,反复进行第二,第四步，直至没有可连接的用户时为止，得最终满意配送方案如表6,-16,，表,6-17,。,表6-16 满意配送方案 表6-17 最终方案所用汽车台数,26,满意配送方案有四条配送路线，它们是：,B,0,B,7,B,10,B,11,B,12,B,0,，行程112公里，用6吨车配送，载重5.6吨；,B,0,B,6,B,8,B,9,B,0,，行程80公里，用6吨车配送，载重5.1吨；,B,0,B,5,B,0,，行程44公里，用4吨车配送，载重1.7吨；,B,0,B,1,B,2,B,3,B,4,B,0,，行程54公里，用6吨车配送，载重5.8吨；,满意方案共用四台车配送，总行程290公里。,27,第三节 多中心配送路线选择与车辆调度,一、制定多中心配送方案的基本思想,多中心配送与单中心配送不同的是，制定配送计划时，不仅要选择配送路线和调度车辆，还要确定各配送中心所服务的用户对象。,所以，制定多中心配送的配送计划，首先将所有用户按一定的方法分派给各配送中心，形成每个配送中心的服务区，然后用上一节讨论的节约法在各配送中心的服务区选择配送路线和调度车辆。,28,二、制定多中心配送方案的边界点方法,1.边界点与非边界点,设d,i,(t)表示用户i与配送中心t之间的距离，记集合 ，,p,是配送中心的个数。计算 ，minD,i,和subminD,i,分别表示集合D,i,中的最小值和次小值；取适当的（0,1），比较r(i)与的大小，当r(i)，称i为非边界点，否则为边界点。,显然，通过改变值的大小可以控制边界点的个数。,29,2.非边界点的分派,对非边界点，按最近分派原则，将它们分别分派给离它们最近的配送中心。,30,3.边界点的分派,对边界点的分派，按r(i)1 和r(i)=1 两种情况分别处理。,（1）当r(i)1时，用节约法进行分派。首先考虑由最近的配送中心对每个点单独派车配送，构成初始解。一旦两个点或多个点已被分派给同一个配送中心时，这些点为永久分派，不能再分派给其他配送中心；如果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）式计算。,按增加量最小原则，将用户i分派给使d,jik,(t)或d,ij,(t)最小的配送中心。,（69）,33,对所有用户分派完毕后，分别在每个配送中心的服务区域内，用节约法确定配送路线和进行车辆调度，得到各配送中心的配送计划。,34,例：,假设有三个配送中心（编号是1,2,3）给10个用户（编号是4,13）配送货物。配送中心与用户以及用户与用户之间的运输距离如表6-18。,表6-18配送中心及用户之间的距离（单位：公里）,35,计算r(i)，得表6-19。,表6-19 r(i)数值表,36,取=0.7,所有r(i),的用户分派给最近的配送中心，如表6-20。,表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(