仓储与配送管理第十章.ppt

1、仓储与配送管理,天津工业大学管理学院,第十章 配送的组织与管理,制定配送计划的方法 配送路线的制定方法 配送的经营管理与质量管理,TSP问题 TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题.假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。,10.1 制定配送计划的方法 10.1.1 TSP与VRP,中国邮递员问题（Chinese Postman Problem CPP） 在中国还有另一个描述方法：一个邮递员从邮局

2、出发，到所辖街道投递邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题， 因为是我国学者管梅古谷教授于1962年提出的这个问题并且给出了一个解法。,配送路线问题（Route of Distribution）TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）！。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的

3、高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。,多回路运输问题（Vehicle Routing Problem, VRP）回路运输问题在物流中的解释是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。 VRP问题和TSP问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了客户的需求，必须是多辆交通工具以及运输工具的行车顺序两个问题的求解。相对于TSP问题，

4、VRP问题更复杂，求解更困难，但也更接近实际情况。,最近邻点法（Nearest Neighbor）这是一种用于解决TSP问题的启发式算法。方法简单，但得到的解并不十分理想，可以作为进一步优化的初始解。求解的过程一共四步：首先从零点开始，作为整个回路的起点，然后找到离刚刚加入到回路的上一节点最近的一个节点，并将其加入到回路中。重复上一步，直到所有的节点都加入到回路中，最后，将最后一个加入的节点和起点连接起来，构成了一个TSP问题的解。最近插入法（Nearest Insertion）最近插入法是另一个TSP问题的求解方法。它的求解过程也是4步：首先从一个节点出发，找到一个最近的节点，形成一个往返式

5、子回路；在剩下的节点中，寻找一个离子回路中某一节点最近的节点，再在子回路中找到一个弧，使弧的两端节点到刚寻找到的最近节点的距离之和减去弧长的值最小，实际上就是把新找到的节点加入子回路以后使得增加的路程最短，就把这个节点增加到子回路中。重复以上过程，直到所有的节点都加入到子回路中。最近插入法比最近邻点法复杂，但可以得到相对比较满意的解。,节约里程法（Saving Algorithm）节约算法是用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。它的核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小得幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。

6、优化过程分为并行方式和串行方式两种。,10.2.1 配送路线的确定方法,10.2 配送路线与车辆调度,一：配送路线确定原则：成本低、效益高、路线短、吨公里小、劳动耗少、运力运用合理等。 二：配送路线确定的限制条件：用户对货物品种、规格、路量的要求，满足用户对货物发到时间的要求，在允许通行时间内进行配送，车辆载重量和容积的限制，配送能力等。 三：配送路线的确定方法,(一）中国邮递员问题（TSP）,利用欧拉图和欧拉回路求解。 欧拉回路：连通图G中，若存在一条回路，经过每边一次且仅一次，称这条回路为欧拉回路，具有欧拉回路的图为欧拉图。而且，连通图G为欧拉图的充要条件是图中所有点全为偶点。,七桥问题

7、Seven Bridges Problem,18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛以及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？,普莱格尔河,欧拉于1736年研究并解决了此问题， 他用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。之后他发表一篇论文，证明了上述走法是不可能的。并且给出了连通网络可一笔画的充要条件这一著名的结论。,用A、B表示两座小岛，C、D表示两岸， 连线AB表示A、B之间有一座桥。,A,B,C,D,在该图

8、中，从任一点出发，能否通过每条线段一次且仅仅一次后又回到原来的出发点,图1和图2当中哪一个图满足：从图中任何一点出发，途径每条边，最终还能回到出发点？ 由此试想一下：一个图应该满足什么条件才能达到上面要求呢？,一笔画问题：从某一点开始画画，笔不离纸，各条线路仅画一次，最后回到原来的出发点。,类似的问题：一笔画问题,字的一笔画：如“中、日、口、串”等可一笔画,而：“田、目”等不能一笔画,图的一笔画：,可一笔画,不可一笔画,田,日,中,白,回,不连通,可一笔画,可一笔画,不可一笔画,可一笔画,可一笔画,不可一笔画,不可一笔画,一笔画问题,凡是能一笔画出的图，奇点的个数最多有两个。始点与终点重合的一

9、笔画问题，奇点的个数必是0。 在一个多重边的连通图中，从某个顶点出发，经过不同的线路，又回到原出发点，这样的线路必是欧拉图，即能一笔画出的图必是欧拉图。,中国邮递员问题,一个邮递员送信，要走完他负责投递的全部街道，投完后回到邮局，应该怎样走，使所走的路程最短？ 这个问题是我国管梅谷同志1962年首先求出来的，因此在国际上通称为中国邮递员问题。在物流活动中，经常会遇到这样的问题，如：每天在大街小巷行驶的垃圾车、洒水车、各售货点的送货车等都需要解决一个行走的最短路程问题。 这个问题就是一笔画问题。,邮路问题的图论描述：,取一无向赋权连通图G=（V，E）,E中的每一条边对应一条街道,每条边的非负权l

10、(e)=街道的长度,V中某一个顶点为邮局，其余为街道的交叉点,1、若G中的顶点均为偶点,，即G中存在欧拉回路，,则该回路过每条边一次且仅一次，,此回路即为所求的投递路线,邮路问题的图论描述：,在无向连通赋权G =（V，E）上找一个圈，,该圈过每边至少一次，且圈上所有边的权和最小,2、G中有奇点：,不存在欧拉回路,投递路线：至少有一街道要重复走一次或多次,即不存在每条街道走一次且只走一次的投递路线,分析：,重复边,结论： 选择最佳投递路线=选择重复边的权和最小的路线,反之，对邮路图G，,对该链上的每一条边增加一条重复边,投递路线,欧拉图,结论：,对任意一个含奇点的邮路图G，由于奇点的个数为偶数个

11、，把每两个配成一对，由于G为连通图，每对奇点之间至少存在一条链，对该条链上的每一条边增加一条重复边，可得一欧拉图，该欧拉图对应一条投递路线,寻找最佳投递路线方法：,在原邮路图上增加一些重复边得一个欧拉图，在所得欧拉图上找出一条欧拉回路。计算重复边的权和，重复边权和最小欧拉回路既为所求的最佳投递路线,管梅谷奇偶点图上作业法,奇偶点图上作业法：,例：求解右图所示的邮路问题,第一步：确定一个初始可行方案,方法：,检查图G中是否有奇点,无奇点：,，找出一条以v1为 起点的欧拉回路,，该回路就是最佳投递路线,有奇点：,图G已是欧拉图,把所有奇点两两配成一对，每对奇点找一条链，在该条链上的每一条边增加一条

12、重复边，得一个欧拉图G1， 由G1所确定的欧拉回路即为一个可行方案,v2,，v8,，v4,，v6,G中有奇点：,取v2到v4的一条链：,v2v1v6v7v8v9v4,取v6到v8的一条链：,v6v1v2v3v4v9v8,G,G1,显然G1不是最佳方案,G1是欧拉图，,第二步：调整可行方案， 使重复边权和下降,重复边权和=,若图中某条边有两条或多于两条的重复边,同时去掉偶数条，,G2,使图中每一条边最多有一条重复边,G2的重复边权和=,步骤1、,可得到重复边权和较小的欧拉图,4,51,21,G2是欧拉图，,重复边权和=21,2、使图中每个初等圈重复边的 权和不大于该圈权和的一半,9个初等圈,G3

13、,G3是欧拉图，,重复边权和=17,G3,6,（1）v1v2v5v6v1,16,7,（2）v6v5v8v7v6,14,10,（3）v2v3v4v5v2,24,4,（4）v5v4v9v8v5,16,G3的初等圈,权和,重复边权和,13,（5）v1v2v5v8v7v6v1,24,G4,G4,7,（1）v1v2v5v6v1,16,4,（2）v6v5v8v7v6,14,4,（3）v2v3v4v5v2,24,8,（4）v5v4v9v8v5,16,G4的初等圈,权和,重复边权和,11,（5）v1v2v5v8v7v6v1,24,（6）v2v3v4v9v8v5v2,32,4,（8）v6v5v4v9v8v7v6

14、,（7）v1v2v3v4v5v6v1,28,11,22,4,（9）v1v2v3v4v9v8v7v6v1,36,7,G4是最佳方案,奇偶点图上作业法：,第一步：确定一个初始可行方案,方法：,检查图G中是否有奇点。,无奇点：,，找出一条以v0为起点的,欧拉回路，该回路就是最佳投递路线,有奇点：,图G已是欧拉图,把所有奇点两两配成一对，每对奇点找一条链，在该条链上的每一条边增加一条重复边,第二步：调整可行方案，使重复边权和下降,1、使图中每一条边最多有一条重复边,若图中某条边有两条或多于两条的重复边， 同时去掉偶数条,2、使图中每个初等圈重复边的权和该圈权和的一半,若图中某初等圈重复边的权和大于该圈

15、权和的一半,去掉圈中的重复边同时将圈中没有重复边的边加上重复边,车辆从某配送中心（v1）出发，给街道边上的超市（v2,v3,v4,v5,v6,v7,v8,v9）送货，如图4-8所示。,案例,显然街区图上有奇点（4个），不满足“一笔画”的条件，则必然有一些街道要被重复走过（添加重复边）才能回到原出发点。此时得到的图就无奇点。 那么该怎样添加重复边，使得图中全为偶点呢？ 其实可以通过连接匹配的奇点得到！,第一步：确定初始可行方案,这样就得到初始方案.在这个图中，没有奇点，故称它为欧拉图。对应于这个可行方案，重复边总权为51。,想一想,这样的可行方案是不是只有一种呢？ 在确定一个可行方案后，怎么判断

16、这个方案是否为最优方案？ 若不是最优方案，如何调整这个方案？,第二步：调整可行方案,最优方案必须满足以下（1）（2）两个条件： （1）在最优方案中,图的每一边最多有一条重复边 （2）在最优方案中,图中每个圈上的重复边的总权不大于该圈总权的一半。 为什么?,第二步：调整可行方案,首先，去掉多余的重复边，使图中每一边最多有一条重复边。见图3,图3,第二步：调整可行方案,其次，如果把图中某个圈上的重复边去掉，而给原来没有重复边的边上加上重复边，图中仍然没有奇点。因而如果在某个圈上重复边的总权数大于这个圈的总权数的一半，像上面所说的那样做一次调整，将会得到一个总权下降的可行方案。,第二步：调整可行方案

17、,在图4-10中，圈（v2,v3,v4, v9,v2）的总长度为24，但圈上重复边总权为14，大于该圈总长度的一半，因此可以做一次调整，以v2,v9，v9,v4上的重复边代v2,v3，v3,v4上的重复边，使重复边总长度下降为17。见图4,图4,检查图4中圈（v1,v2, v9, v6,v7, v8,v1）的总长度为24，但圈上重复边总权为13，大于该圈总长度的一半，因此可以做一次调整，使重复边总长度下降为15。见图5。,图5,检查图5，均满足条件（1）和（2），于是得到最优方案。图5中的任一欧拉圈都是汽车的最优配送路线。 如：v1-v2-v9-v8-v1-v8-v7-v6-v5-v4-v9-

18、v6-v9-v4-v3-v2-v1是汽车的一条最优配送路线。,课堂练习,10.2 配送路线与车辆调度,单中心配送路线选择与车辆调度,一、单中心配送的节约法原理 单中心配送，是指一个配送中心向所属n个用户送货，各用户的需求量为bj(j=1,2,n)。假定以汽车作为配送车辆，配送车按其载重量的大小不同有p种，载重量为QK(K=1,2p)的发送车有xK台,QK-1QK,且 （61） 解决这类配送问题的一种有效方法节约法。节约法是由克拉克（Clarke）和怀特（Wright）提出来的，是一种启发式方法。,节约法的基本原理,如图102，由物流网点B0向两个用户B1、B2送货，B0至各用户的最短运输距离分

19、别为d0,1和d0,2；用户需求量各为b1，b2；两用户之间的最短运输距离为d1,2。当用两台车分别对两个用户各自往返送货时，运输总距离为：,图102 各用户分别送货,如果改用一台车巡回送货（假定汽车能够负荷b1、b2时），如图103，则总运输距离为 后一种方案比前一种方案可节约运输里程 式105称为节约量公式， 为B1和B2之间的节约量。 显然，将节约量大的两个用户 连接起来采用巡回方式送货， 则可获得较大的节约。,（10-5）,图103 节约法示意图,二、节约法的计算过程,设由配送中心B0向用户Bj (j=1, 2, , n)送货，各用户需求量为bj；配送中心与用户间的最短距离为d0,j，

20、用户之间的距离为di,j (i=1, 2, , n; j=1, 2, , n)；配送车按其载重量的大小不同有p种，载重量为QK(K=1,2p)的发送车有xK台，QK-1QK。 假定：,（10-6）,计算过程如下：,先求初始解。 假定载重量最小的汽车台数是无限多的，即x1=。对每一用户各派一台最小的车往返送货，得一初始可行方案。显然这一方案的运输效率是很低的，而且x1=的假设实际也不存在。,然后迭代求满意解。 计算每两个用户之间的节约量，按节约法原理对方案进行修正。修正时，以节约量的大小为顺序，从大到小依次将节约量大的用户连接到巡回路线中，并考虑汽车载重量和各种车辆台数的约束。反复进行这样的修正

21、，直至再没有可连接的用户时为止。 整个计算过程可在节约量表上进行。 下面用例子说明计算过程。,例：由配送中心B0向12个用户Bj (j=1,2,12)送货，各点之间的运输里程和各用户的需求量见表10-1。表10-2为可供调度的车辆数目及其载重量。,表10-1 各点之间里程表（单位：公里） 表10-2 可供调度的汽车,解：由表10-1中的数据，按节约量公式（10-5）计算每两用户之间的节约量Si,j 列于表10-3，称节约量表。,表6-3 节约量表（单位：公里）,如:S1,2d0,1+d0,2d1,2 9145 18,S2,4d0,2+d0,4d2,4 142317 20,设ti,j(i=0,1

22、,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）,迭代求解：,第一步，求初始解 每用户各派一台车单独送货，得初始方案如表104。表中B0列中的数字为ti,j的取值。此方案的总行程为728公里。 按表104的初始方案，所用汽车台数如表105所列。,表10-4 初始方案 表105 初始方案所用汽

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

24、步，按以下原则修正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（吨） 得改进方案（表10-6、表10-7）。 改进后的方案比原方案少一台发送车，总发送距离减少92公里。,表6-6 第一次迭代方案 表6-7 该方案所用汽车台数,重复第二步，按下述条件在第一次迭代方案表66中寻找具有最大节约量的用户i、j,（1）t0i、t0j0ij； （2）Bi、Bj尚未连接在一条巡回路线上； （3）考虑车辆台数和载重量的约束。 如果最大节约

25、量有两个或两个以上相同时，可随机取一个。 按此条件，在表66中寻得具有最大节约量的用户有两对，分别为：i=10,j=11和i=10,j=12 ，其节约量均为84公里，任取一对i=10, j=11，将其连接到一个回路中。,重复第三步，按ti,j的定义和公式67修正ti,j的值。,B10与B11连接，则t10,11=1，由公式67得： t0,11=0 t0,10=1 其他不变。,重复第四步，按以下原则修正bi、bj,（1）t0,i或t0,j等于0时，令bi或bj等于0； （2）t0,i或t0,j等于1时，令bi或bj等于所在巡回路线中所有用户需求量之和，以此代替原bi或bj,因此 b10=b12=

26、2.81.6=4.4（吨） b11=0 得第二次迭代方案（表6-8、表6-9）。 第二次迭代方案比第一次迭代方案又少一台配送车，只需10台，其中一台为5吨车；总发送距离比前一方案减少84公里。,表6-8 第二次迭代方案 表6-9 该方案所用汽车台数,表6-10 第三次迭代方案 表6-11 该方案所用汽车台数,为什么不选B10B9、B10B8？,可否将B11与B7连接？,得到第一条配送路线：B0B7B10B11B12B0，行程112公里，用6吨车配送，载重5.6吨； 开始下一条配送路线的选择，过程如何？,表6-12 第四次迭代方案 表6-13 该方案所用汽车台数,表6-14 第五次迭代方案 表6

27、-15 该方案所用汽车台数,得到二条配送路线：B0B6B8B9B0，行程80公里，用6吨车配送，载重5.1吨； 再开始下一条配送路线的选择，过程与前相同。,反复进行第二第四步，直至没有可连接的用户时为止，得最终满意配送方案如表6-16，表6-17。 表6-16 满意配送方案 表6-17 最终方案所用汽车台数,满意配送方案有四条配送路线，它们是：,B0B7B10B11B12B0，行程112公里，用6吨车配送，载重5.6吨； B0B6B8B9B0，行程80公里，用6吨车配送，载重5.1吨； B0B5B0，行程44公里，用4吨车配送，载重1.7吨； B0B1B2B3B4B0，行程54公里，用6吨车配送，载重5.8吨； 满意方案共用四台车配送，总行程290公里。,第三节 多中心配送路线选择与车辆调度,一、制定多中心配送方案的基本思想 多中心配送与单中心配送不同的是，制定配送计划时，不仅要选择配送路线和调度车辆，还要确定各配送中心所服务的用户对象。 所以，制定多中心配送的配送计划，首先将所有用户按一定的方法分派给各配送中心，形成每个配送中心的服务区，然后用上一节讨论的节约法在各配送中心的服务区选择配送路线和调度车辆。,10.3 配送的质量管理,10.3.1 配送服务概述,一、配送服务的含义和要素 （一）配送服务的含义 配送服务就是物流配送过程中为满足客户需求所实施的一系列配送活动过程及