《仓储与配送管理第十章》由会员分享，可在线阅读，更多相关《仓储与配送管理第十章（86页珍藏版）》请在金锄头文库上搜索。
1、仓储与配送管理天津工业大学管理学院天津工业大学管理学院第十章 配送的组织与管理u制定配送计划的方法 u配送路线的制定方法 u配送的经营管理与质量管理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问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了客户的需求，必须是多辆交通工具以及运输工具的 行车顺序两个问题的求解。相对于
4、TSP问题，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表
8、示两岸，连线AB表示A、B之间有一座桥。ABCD在该图中，从任一点出发，能否通过 每条线段一次且仅仅一次后又回到原 来的出发点bca图1v2v3v1v4图2 图1和图2当中哪一个图满足：从图中任何一点出发 ，途径每条边，最终还能回到出发点？ 由此试想一下：一个图应该满足什么条件才能达到 上面要求呢？一笔画问题：从某一点开始画画，笔不离纸，各条线路仅 画一次，最后回到原来的出发点。类似的问题：一笔画问题字的一笔画：如“中、日、口、串”等可一笔画而：“田、目”等不能一笔画图的一笔画：可一笔画不可一笔画田日中白 回不连通可一笔画可一笔画不可一笔 画可一笔画可一笔画不可一笔画不可一笔画一笔画问题 凡是
9、能一笔画出的图，奇点的个数最多 有两个。始点与终点重合的一笔画问题 ，奇点的个数必是0。 在一个多重边的连通图中，从某个顶点 出发，经过不同的线路，又回到原出发 点，这样的线路必是欧拉图，即能一笔 画出的图必是欧拉图。中国邮递员问题 一个邮递员送信，要走完他负责投递的 全部街道，投完后回到邮局，应该怎样 走，使所走的路程最短？ 这个问题是我国管梅谷同志1962年首先 求出来的，因此在国际上通称为中国邮 递员问题。在物流活动中，经常会遇到 这样的问题，如：每天在大街小巷行驶 的垃圾车、洒水车、各售货点的送货车 等都需要解决一个行走的最短路程问题 。 这个问题就是一笔画问题。邮路问题的图论描述：取
10、一无向赋权连通图G=（V，E） E中的每一条边对应一条街道每条边的非负权l(e)=街道的长度V中某一个顶点为邮局，其余为街道的交叉点1、若G中的顶点均为偶点 ，即G中存在欧拉回路， 则该回路过每条边一次且仅一次，此回路即为所求的投递路线邮路问题的图论描述：在无向连通赋权G =（V，E）上找一个圈，该圈过每边至少一次，且圈上所有边的权和最小2、G中有奇点：不存在欧拉回路投递路线：至少有一街道要重复走一次或多次即不存在每条街道走一次且只走一次的投递路线分析：重复边结论： 选择最佳投递路线=选择重复边的权和最小的路线111111111111111111111111111反之，对邮路图G，对该链上的每
11、一条边增加一条重复边111111111111111111投递路线欧拉图结论：对任意一个含奇点的邮路图G，由于奇点的个 数为偶数个，把每两个配成一对，由于G为连 通图，每对奇点之间至少存在一条链，对该条 链上的每一条边增加一条重复边，可得一欧拉 图，该欧拉图对应一条投递路线 寻找最佳投递路线方法：在原邮路图上增加一些重复边得一个欧拉图， 在所得欧拉图上找出一条欧拉回路。计算重复边 的权和，重复边权和最小欧拉回路既为所求的最 佳投递路线管梅谷奇偶点图上作业法奇偶点图上作业法：例：求解右图所示的邮路问题 第一步：确定一个初始可行方案 方法： 检查图G中是否有奇点无奇点： ，找出一条以v1为 起点的欧
12、拉回路 ，该回路就是最佳投递路线有奇点：图G已是欧拉图把所有奇点两两配成一对，每对奇点找一条链 ，在该条链上的每一条边增加一条重复边，得 一个欧拉图G1， 由G1所确定的欧拉回路即为 一个可行方案 v2，v8，v4，v6G中有奇点： 取v2到v4的一条链：v2v1v6v7v8v9v4 取v6到v8的一条链：v6v1v2v3v4v9v8G243469544354G1显然G1不是最佳方案G1是欧拉图，第二步：调整可行方案，使重复边权和下降重复边权和=若图中某条边有两条或多于两条的重复边同时去掉偶数条， G2使图中每一条边最多有一条重复边G2的重复边权和=24346954435步骤1、可得到重复边权
13、和较小的欧拉图4G2243469544354512124346954435G2是欧拉图， 重复边权和=21G242、使图中每个初等圈重复边的权和不大于该圈权和的一半9个初等 圈24346954435G24G3G3是欧拉图， 重复边权和=17G32434695443546（1）v1v2v5v6v116 7（2）v6v5v8v7v61410（3）v2v3v4v5v2244（4）v5v4v9v8v516G3的初等圈权和重复边权和13（5）v1v2v5v8v7v6v124G4243469544354G42434695443547（1）v1v2v5v6v116 4（2）v6v5v8v7v6144（3）v
14、2v3v4v5v2248（4）v5v4v9v8v516G4的初等圈权和重复边权和11（5）v1v2v5v8v7v6v124（6）v2v3v4v9v8v5v2324（8）v6v5v4v9v8v7v6（7）v1v2v3v4v5v6v12811 224 （9）v1v2v3v4v9v8v7v6v1367G4是最佳方案奇偶点图上作业法： 第一步：确定一个初始可行方案 方法： 检查图G中是否有奇点。 无奇点：，找出一条以v0为起点的 欧拉回路，该回路就是最佳投递路线有奇点：图G已是欧拉图把所有奇点两两配成一对，每对奇点找一条 链，在该条链上的每一条边增加一条重复边 第二步：调整可行方案，使重复边权和下降
15、1、使图中每一条边最多有一条重复边 若图中某条边有两条或多于两条的重复边， 同时去掉偶数条 2、使图中每个初等圈重复边的权和该圈权和的一半若图中某初等圈重复边的权和大于该圈权和的一半 去掉圈中的重复边同时将圈中没有重复边的边加上重复边 车辆从某配送中心（ v1）出发，给街道边 上的超市（ v2,v3,v4,v5,v6,v7,v8, v9）送货，如图4-8 所示。案例v1v3v2v4v8v7v6v5v9254339546444图1 显然街区图上有奇点（4个），不满 足“一笔画”的条件，则必然有一些 街道要被重复走过（添加重复边）才 能回到原出发点。此时得到的图就无 奇点。 那么该怎样添加重复边，
16、使得图中全 为偶点呢？ 其实可以通过连接匹配的奇点得到！第一步：确定初始可行方案v1v3v2v4v8v7v6v5v9254339546444图2 这样就得到初始方案.在这个图中，没有 奇点，故称它为欧拉图。对应于这个可 行方案，重复边总权为51。想一想 这样的可行方案是不是只有一种呢？ 在确定一个可行方案后，怎么判断这个 方案是否为最优方案？ 若不是最优方案，如何调整这个方案？第二步：调整可行方案 最优方案必须满足以下（1）（2）两个 条件： （1）在最优方案中,图的每一边最多有 一条重复边 （2）在最优方案中,图中每个圈上的重 复边的总权不大于该圈总权的一半。 为什么?第二步：调整可行方案 首先，去掉多余的重复边，使图中 每一边最多有一条重复边。见图3v1v2v3v4v5v6v7v8v9444342346955图3第二步：调整可行方案 其次，如果把图中某个圈上的重复边去 掉，而给原来没有重复边的边上加上
