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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 配送路线选择与车辆调度,学习要点：,单中心配送路线选择与车辆调度；,多中心配送路线选择与车辆调度。,1,第一节 单中心配送路线选择与车辆调度,一、单中心配送的节约法原理,单中心配送，是指一个配送中心向所属,n,个用户送货，各用户的需求量为,b,j,(,j,=1,2,n,),。,假定以汽车作为配送车辆，配送车按其载重量的大小不同有,p,种，载重量为,Q,K,(,K,=1,2,p,),的发送车有,x,K,台,Q,K,-1,Q,K,且,（,6,1,）,解决这类配送问题的一种有效方法,节约法。节约法是由克拉克（,Clarke,）和怀特（,Wright,）提出来的，是一种启发式方法。,2,节约法的基本原理,如图,6,2,，由物流网点,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,图,3,2,各用户分别送货,3,如果改用一台车巡回送货（假定汽车能够负荷,b,1,、,b,2,时），如图,6,3,，则总运输距离为,后一种方案比前一种方案可节约运输里程,式,6,5,称为节约量公式，,为,B,1,和,B,2,之间的节约量。,显然，将节约量大的两个用户,连接起来采用巡回方式送货，,则可获得较大的节约。,（,6-5,）,B,2,B,1,B,0,d,1,2,d,0,2,d,0,1,图,6,3,节约法示意图,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,9,14,5,18,S,2,4,d,0,2,+,d,0,4,d,2,4,14,23,17,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,迭代求解：,第一步，求初始解,每用户各派一台车单独送货，得初始方案如表,6,4,。表中,B,0,列中的数字为,t,i,j,的取值。此方案的总行程为,728,公里。,按表,6,4,的初始方案，所用汽车台数如表,6,5,所列。,11,表,6-4,初始方案 表,6,5,初始方案所用汽车台数,12,第二步，按下述条件在初始方案表中寻找具有最大节约量的用户,i,、,j,（,1,）,t,0,i,、,t,0,j,0,i,j,；,（,2,）,B,i,、,B,j,尚未连接在一条巡回路线中；,（,3,）考虑车辆台数和载重量的约束。,如果最大节约量有两个或两个以上相同时，可随机取一个。,按此条件，在初始方案表,6,4,中寻到具有最大节约量的一对用户为：,i,=11,j,=12,，其节约量为,92,公里。将,11,和,12,两用户连接到一个运输回路中，并在对应的格中记上,t,11,12,的值，用,“,1,）,”,表示。,13,第三步，按,t,i,j,的定义和公式,6,7,修正,t,i,j,的值。,B,11,与,B,12,连接，即令,t,11,12,=1,，,由公式,6,7,得：,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,重复,第二步，按下述条件在第一次迭代方案表,6,6,中寻找具有最大节约量的用户,i,、,j,（,1,）,t,0,i,、,t,0,j,0,i,j,；,（,2,）,B,i,、,B,j,尚未连接在一条巡回路线上；,（,3,）考虑车辆台数和载重量的约束。,如果最大节约量有两个或两个以上相同时，可随机取一个。,按此条件，在表,6,6,中寻得具有最大节约量的用户有两对，分别为：,i,=10,j,=11,和,i,=10,j,=12,，其节约量均为,84,公里，任取一对,i,=10,j,=11,，将其连接到一个回路中。,17,重复,第三步，按,t,i,j,的定义和公式,6,7,修正,t,i,j,的值。,B,10,与,B,11,连接，则,t,10,11,=1,，,由公式,6,7,得：,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.8,1.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,不在同一配送中心，按一般节约法将其连接并分别试分配给与之对应的两个配送中心，连接产生的节约量按下式（,6,8,）计算。,31,式中：,选 最大者，将,i,j,分派给对应的,t,。,j,点还未给一永久分派，挪到非最近点时,否则,i,点还未给一永久分派，挪到非最近点时,否则,32,（,2,）当,r(i)=1,时，按如下方法分派。,将,i,分别试,分派给各配送中心,t,（,t,1,，,p),，若,j,和,k,是已分派给配送中心,t,的用户，,将,点,i,插入用户,j,与,k,之间；若,t,中心只有一个用户,j,，,则将,i,插入,j,与,t,之间。对配送中心,t,产生的运输距离增加量按（,6,9,）式计算。,按增加量最小原则，将用户,i,分派给使,d,jik,(t,),或,d,ij,(t,),最小的配送中心。,（,6,9,）,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,，根据式（,6,8,）计算,(,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,，分别试分派给各配送中心，根据式（,6,9,）计算最小增加值，,并按从小到大的顺序排列，列于表,6-22,。,表,6,22,用户,13,试分派增加值,根据表,6-22,，按增加值最小原则,，把用户,13,分派给中心,1,，并插入到用户,5,和,10,之间，得最终分派方案，如表,6,23,。,39,表,6,23,最终用户分派方案,对各个配送中心分派的用户，再用节约法求每个配送中心的配送方案，得到最后结果。,40,