仓储与配送管理第十章

《仓储与配送管理第十章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

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

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

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