《仓储与配送管理第十章 配送的组织与管理》由会员分享，可在线阅读，更多相关《仓储与配送管理第十章 配送的组织与管理（86页珍藏版）》请在金锄头文库上搜索。
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
8、,D,在该图中，从任一点出发，能否通过每条线段一次且仅仅一次后又回到原来的出发点,图1和图2当中哪一个图满足：从图中任何一点出发，途径每条边，最终还能回到出发点？由此试想一下：一个图应该满足什么条件才能达到上面要求呢？,一笔画问题：从某一点开始画画，笔不离纸，各条线路仅画一次，最后回到原来的出发点。,类似的问题：一笔画问题,字的一笔画：如“中、日、口、串”等可一笔画,而：“田、目”等不能一笔画,图的一笔画：,可一笔画,不可一笔画,田,日,中,白,回,不连通,可一笔画,可一笔画,不可一笔画,可一笔画,可一笔画,不可一笔画,不可一笔画,一笔画问题,凡是能一笔画出的图，奇点的个数最多有两个。始点与终
9、点重合的一笔画问题，奇点的个数必是0。 在一个多重边的连通图中，从某个顶点出发，经过不同的线路，又回到原出发点，这样的线路必是欧拉图，即能一笔画出的图必是欧拉图。,中国邮递员问题,一个邮递员送信，要走完他负责投递的全部街道，投完后回到邮局，应该怎样走，使所走的路程最短？ 这个问题是我国管梅谷同志1962年首先求出来的，因此在国际上通称为中国邮递员问题。在物流活动中，经常会遇到这样的问题，如：每天在大街小巷行驶的垃圾车、洒水车、各售货点的送货车等都需要解决一个行走的最短路程问题。 这个问题就是一笔画问题。,邮路问题的图论描述：,取一无向赋权连通图G=（V，E）,E中的每一条边对应一条街道,每条边
10、的非负权l(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个初等圈
13、,G3,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）v6v5v4v9v8v
14、7v6,（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,第二步：调整可行方案,其次，如果把图中某个圈上的重复边去掉，而给原来没有重复边的边上加上重复边，图中仍然没有奇点。因而如果在某个圈上重复边的总权数大于这个圈的总权数的一半，像上面所说的那样做一次调整，将会得到一个总权下降的可行方案。,第二步：调整可行方案,在图4-10中，圈（v2,v3,v4, v9,v2）的总长度为24，但圈上重复边总权为14，大于该圈总长度的一半，因此可以做一次调整，以v2,v9，v9,v4上的重复边代v2,v3，v3,v4上的重复边，使重复边总长度下降为17。见图4,
