配送路线选择与车辆调度-徐天亮

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第六章 配送路线选择与车辆调度,主要内容：,配送路线安排与车辆调度问题及节约法原理；,单中心配送路线选择与车辆调度；,多中心配送路线选择与车辆调度；,货车配载 。,2,第一节 配送路线安排与车辆调度问题及节约法原理,一、配送路线安排与车辆调度问题,配送路线安排与车辆优化调度问题常被分为车辆路线安排问题（,Vehicle Routing Problem,，简记,VRP,）和车辆调度问题（,Vehicle Scheduling Problem,，简记,VSP,），前者仅从空间位置考虑车辆路线的安排和车辆调度，后者则要考虑时间要求。显然,VSP,问题比,VRP,问题讨论的范围宽，,或者说，,VSP,问题是有时间约束的,VRP,问题。本书主要讨论,VRP,问题。,3,VRP,问题的描述,VRP,问题一般可描述为：对一系列装货点或（和）卸货点，组织适当合理的行车路线，使车辆有序地通过它们，在满足一定的约束（如货物需求量、发送量，车辆容量、数目限制、车辆行驶里程限制等）条件下，达到一定的目标（如最短路程、最小费用、最短时间、最少车辆等）。,4,VRP,问题的分类,VRP,问题又根据不同标准分为：车辆满载问题（一个用户的货运量大于一辆车的容量，完成任务需要多辆车）与非满载问题（一个用户的货运量不大于一辆车的容量，完成任务只需要一辆车）、单车场问题（一个货场或一个配送中心）与多车场问题（多个货场或多个配送中心）、单车型（所有车辆容量相同）与多车型问题（车辆容量不全相同），以及优化目标的单目标与多目标问题。,5,二、,VRP,问题精确求解方法的局限性,1. VRP,问题求解思路,VRP,问题的求解方法一般相当复杂，通常的做法是应用相关技术将问题分解或者转化为一个或多个已经研究过的基本问题（如旅行商问题、指派问题、运输问题、最短路问题、最小费用流问题、中国邮递员问题等），再使用相对比较成熟的基本理论和方法进行求解。,6,2.,精确算法的局限性,VRP,问题的求解方法可分为两大类，即精确算法和启发式算法。精确算法主要有分枝定界法、割平面法、网络流算法、动态规划方法等。精确算法随着配送系统规模的增大，其计算量呈指数递增，使得获取系统最优解越来越困难。因此，精确算法在实际应用中受到很大的局限。,7,三、节约法原理,为了克服精确优化方法的不足，人们提出了许多能获得,“,满意,”,解的启发式算法。启发式算法是一种基于直观或经验构造的算法，它运用一些经验法则，并通过模仿人的跟踪校正过程来求得系统的满意解。,启发式算法中最具有代表性的是由,Clarke,和,Wright,提出的节约法（,Saving Method,）。,8,节约法的基本原理：,9,10,11,第二节 单中心配送路线选择与车辆调度,12,如果将配送中心也作为一个用户点，货车从配送中心出发，对所有用户巡回送货后回到配送中心，这样就把单车非满载车辆的配送路线安排问题转化为个点的旅行商问题（,Traveling Salesman Problem,，简记,TSP,）。它的解是：从配送中心出发，对所有用户巡回一次回到配送中心的距离最短的路线。,13,14,15,16,17,18,19,20,t,06,+t,16,+t,26,+t,36,+t,46,+t,56,+t,76,=2;,因此如果,t67=t76=1,则,t06=1,含义就是配送第,6,个客户的车辆不是完成任务直接返回中心了。,t,07,+t,17,+t,27,+t,37,+t,47,+t,57,+t,67,=2;,因此如果,t67=t76=1,则,t07=1,含义就是配送第,7,个客户的车辆不是完成任务直接返回中心了。,21,22,23,二、多车非满载配送路线安排与车辆调度,24,25,26,此模型用精确算法求解更加困难，,下面仍用节约法求解此类问题的满意解。求解的过程与例,6-1,基本相同，只是在方案改进的过程中，寻找具有最大节约量的用户,i,、,j,时，增加了考虑车辆载重量和可调度车辆数的约束，而且，车辆调度时优先使用载重量大的车辆。,27,例：由配送中心,B,0,向,12,个用户,B,j,(j=1,2,12),送货，,各点之间的运输里程和各用户的需求量见表,6-1,。表,6-2,为可供调度的车辆数目及其载重量,。,表,6-1,各点之间里程表（单位：公里） 表,6-2,可供调度的汽车,28,解：由表,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,29,设,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,）,30,迭代求解：,第一步，求初始解,每用户各派一台车单独送货，得初始方案如表,6,4,。表中,B,0,列中的数字为,t,i,j,的取值。此方案的总行程为,728,公里。,按表,6,4,的初始方案，所用汽车台数如表,6,5,所列。,31,表,6-4,初始方案 表,6,5,初始方案所用汽车台数,32,第二步，按下述条件在初始方案表中寻找具有最大节约量的用户,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,）,”,表示。,33,第三步，按,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,其他不变。,34,第四步，按以下原则修正,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,公里。,35,表,6-6,第一次迭代方案,表,6-7,该方案所用汽车台数,36,重复第二步，按下述条件在第一次迭代方案表,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,，将其连接到一个回路中。,37,重复,第三步，按,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,其他不变。,38,重复第四步，按以下原则修正,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,公里。,39,表,6-8,第二次迭代方案 表,6-9,该方案所用汽车台数,40,表,6-10,第三次迭代方案 表,6-11,该方案所用汽车台数,为什么不选,B,10,B,9,、,B,10,B,8,？,可否将,B,11,与,B,7,连接？,41,得到第一条配送路线：,B,0,B,7,B,10,B,11,B,12,B,0,，行程,112,公里，用,6,吨车配送，载重,5.6,吨；,开始下一条配送路线的选择，过程如何？,42,表,6-12,第四次迭代方案 表,6-13,该方案所用汽车台数,43,表,6-14,第五次迭代方案 表,6-15,该方案所用汽车台数,44,得到二条配送路线：,B,0,B,6,B,8,B,9,B,0,，行程,80,公里，用,6,吨车配送，载重,5.1,吨；,再开始下一条配送路线的选择，过程与前相同。,45,反复进行第二,第四步，直至没有可连接的用户时为止，得最终满意配送方案如表,6,-16,，表,6-17,。,表,6-16,满意配送方案 表,6-17,最终方案所用汽车台数,46,满意配送方案有四条配送路线，它们是：,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,公里。,47,第三节 多中心配送路线选择与车辆调度,一、制定多中心配送方案的基本思想,多中心配送与单中心配送不同的是，制定配送计划时，不仅要选择配送路线和调度车辆，还要确定各配送中心所服务的用户对象。,所以，制定多中心配送的配送计划，首先将所有用户按一定的方法分派给各配送中心，形成每个配送中心的服务区，然后用上一节讨论的节约法在各配送中心的服务区选择配送路线和调度车辆。,48,二、制定多中心配送方案的边界点方法,1.,边界点与非边界点,设,d,i,(t),表示用户,i,与配送中心,t,之间的距离，记集合 ，,p,是配送中心的个数。计算 ，,minD,i,和,subminD,i,分别表示集合,D,i,中的最小值和次小值；取适当的,（,0, 1,），比较,r(i),与,的大小，当,r(i),，称,i,为非边界点，否则为边界点。,显然，通过改变,值的大小可以控制边界点的个数。,49,2.,非边界点的分派,对非边界点，按最近分派原则，将它们分别分派给离它们最近的配送中心。,50,3.,边界点的分派,对边界点的分派，按,r(i)1,和,r(i)=1,两种情况分别处理。,（,1,）当,r(i)1,时，用节约法进行分派。 首先考虑由最近的配送中心对每个点单独派车配送，构成初始解。一旦两个点或多个点已被分派给同一个配送中心时，这些点为永久分派，不能再分派给其他配送中心；如果,i,，,j,不在同一配送中心，按一般节约法将其连接并分别试分配给某一配送中心，连接产生的节约量按下式（,6.8,）计算。,51,式中：,选 最大者，将,i,j,分派给对应的,t,。,j,点还未给一永久分派，挪到非最近配送中心,否则,i,点还未给一永久分派，挪到非最近配送中心,否则,52,（,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,）,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,的边界点用户试连接的节约量表,根据表,6-21,，按节约量最大原则，把用户,8,和,10,分派给配送中心,1,，得到永久分配。把用户,12,分派给配送中心,3,。,58,对,r(i)=1,的用户,13,，分别试分派给各配送中心，根据式（,6.9,）计算最小增加值，,并按从小到大的顺序排列，列于表,6-22,。,表,6,22,用户,13,试分派增加值,根据表,6-22,，按增加值最小原则,，把用户,13,分派给中心,1,，并插入到用户,5,和,10,之间，得最终分派方案，如表,6,23,。,59,表,6,23,最终用户分派方案,对各个配送中心分派的用户，再用节约法求每个配送中心的配送方案，得到最后结果。,