基于某中国的邮递员问的题目地物流配送线路优化

1、实用标准文案基于中国邮递员问题的物流配送线路优化摘要 ：针对物流配送的线路优化问题，以配送总路程最小为目标，在充分考虑 中国邮递员问题的基础上，寻求求解优化方案以及建立线路优化模型。关键词 ：线路优化 中国邮递员问题 最小树法 优化模型1. 引言随着市场竞争的日益加剧、 世界经济一体化的程度的加快和科学技术的飞速 发展，许多企业已经把物流作为提高竞争力和提升核心的竞争能力的重要手段， 将先进的物流理论和物流技术引入企业的生产和经营管理中。 这一产业在我国现 今还处于发展阶段， 与国外物流业相比， 我国物流业自身存在的一些问题逐渐对 企业自身的发展和盈利造成了瓶颈。 在众多的问题中， 物流效率问

2、题是较为突出 的一个。而物流网络是否科学健全又是决定物流效率的关键一环， 作为实现物流 合理化的重要内容和手段， 研究物流配送路径有助于企业降低物流成本， 提高运 作效率，全面提高顾客满意度， 使企业在现今物流业服务竞争逐渐激烈的环境下 站稳脚跟，让企业获得更多的利润和更为长远的发展。用图的语言来描述物流线路优化问题， 就是给定一个连通图 G，在每条边上 有一个非负的权，要寻求一个圈，经过 G 的每条边至少一次，并且圈的权数最 小。这个问题是由我国管梅谷同志于 1962 年首先提出来的，因此国际上称它为 中国邮递员问题。精彩文档实用标准文案2.问题描述中国邮递员问题的描述： 一个邮递员送信，

3、在邮局里挑选出他所有负责的街 区的各条街道的邮件， 并按一定的次序排列， 然后按一定路线投递这些邮件， 最 后返回邮局。 自然邮递员必须走过他负责的街区的每一条街道至少一次， 并希望 选择一条总路程最短的投递路线。下面我们介绍一下图论问题中的定义和定理。定义 1 ：在一个多重边的连通图中，从某个顶点出发，经过不同的线路，又 回到原出发点，这样的线路称为欧拉图。定义 2 ：设 G 是一个无向连通图，若存在一个回路，经过 G 中的每一条边 一次且仅一次，则称这个同路为欧拉回路：定义 3 ：设 G 足一个无向连通图，若在 G 中通过某顶点的弧的个数为偶数 时，这个顶点被称为偶点，否则被称为奇点。定理

4、 1 ：一个非空连通图是欧拉图当且仅当它没有奇点。定理 2 ：一个连通图有欧拉迹当且仅当它最多有两个奇点。定理 3：设 C是一条经过赋权连通图 C 的每条边至少一次的回路，则 C是G 的最优回路，当且仅当 C 对应的欧拉图 G 满足：(1) G 的每条边至多重复出现一次；(2) G 的每个圈上重复出现的边的权之和不超过该圈总权的一半。基于以上定义和定理，应用图论描述中国邮递员问题如下：在一个连通图 G=(V ，E)中， E 中的每一条边对应一条街道，每条边的权重 l(e)= 街道的长度。v 中某一个顶点为邮局， 其余为街道的交叉点。 在连通图 c=(V ， E)上找一个圈，该圈过每边至少一次，

5、且圈上所有边的权和最小。精彩文档实用标准文案此问题分为两种情况：（1）若 G 中的顶点均为偶点， 即 G 中存在欧拉回路， 则该回路过每条边一 次且仅一次，此回路即为所求的投递路线；（2）若 G 中有奇点，不存在欧拉回路，所投递的路线至少有一街道要重复 走一次或多次。在 G 中有奇点的情况中，选择的最佳投递路线就等同于选择重复边的权和最小的路线。 下面我们来介绍初始邮递路线的确定、 改进，以及一个邮递路线是否是最优路线的判定标准的方法 图上作业法。（1）初始邮递路线的确定方法。任何一个图中， 若奇点的个数为偶数， 就可以把它们两两配成对， 而每对奇点之间必有一条链（图是连通的） ，我们把这条链

6、的所有边作为重复边追加到图 中去，这样得到的新连通图必无奇点，这就给出了初始投递路线如在下图中，v1 是邮局所在地，并有四个奇点 v2,v4,v6,v8, 将它们两两配对，比如 v2 和 v4 为一对， v6 和 v8 为一对。v72 v8 4v1 v749 v4 4v3v52）改进邮递路线，使重复边的总长不断减少般地，在邮递路线上，如果在边 vi,vj 旁边有两条以上的重复边，从中去精彩文档实用标准文案掉偶数条，那么可以得到一个总长度较少的邮递路线。4v5根据定理 3 的满足条件， 在最优邮递路线上， 图中每一个圈的重复边的总权 小于或者等于该圈总权的一半，得出下列欧拉圈就是最优邮递路线。v

7、3 中国邮递9员 问题简v单4 图上作业4 法虽然最后v5找 出了最优路线， 但寻找奇点的配 对关系，难免带有一定的盲目性， 不如针对这一症结所在， 尽可能地将初始方案 做得好一些， 以减少后期调整所出现的麻烦， 这就需要考虑和利用网络最小树的 理念。精彩文档实用标准文案管谷梅先生在 1960 的时候给出过求最优集的相关判定定理， 然而实际操作 中我们却有更贴近实际的解决方法，这即是判优准则。以上面提到的线路为例， 演示此方法，具体的步骤如下：(1)奇点出作出标记。v1v8v7v3v5(2) 求该网络最小树 (使用避圈法或是破圈法，在操作中尽可能多保留与奇点v1v8v794v3v4v5相连的边

8、 )。(3) 在最小树的奇点处添加添加重复边，以消灭奇点(4) 同到原来的问题，且按判优准则。v1 v8 v7精彩文档49 v4 4 v5该题圆实用标准文案满解决v3!在此寻找最优解的过程中，始终遵循的两个准则为：准则 1 ：最优解中重边的重数不多于 2；准则 2 ：最优解中每个初等圈中，重边总权数不大于该圈总权数的一半。 通过实际解决最优路径问题发现，借助最小树的理念处理中国邮路问题时， 能够充分的考虑原有网络的信息， 这样在添加重边， 消失奇点的过程中可以做到 有的放矢。而避免了之前使用方法局部求解导致的局限性。当然这种方法是一种初级方案， 还有待于进一步的验证。 因为在实际计算中， 逐一

9、验证全部有效圈的工作量实在太大， 作为一种很接近于求解最优解的初始解 的办法，这不失为一种不错的方法，值得我们去使用。精彩文档实用标准文案4. 中国邮递员问题规划模型的建立在用图上作业法求解中国邮递员问题时， 需检查图中的每一条回路。 当图中 回路较多时，检查不便且容易出错。对此，受求解最短路问题的 EXCEL 解法的 启发，本文建立基于 EXCEL 的“中国邮递员问题”的整数规划模型。nnminz i ,j 1cij xiji ,j 1cpq xpq1,2 np.q 1i, js.t1,2 nx ji 1p,qxiji1,2 nxpqxqp 1p1,2 nnnnnM与i直接相连的点j Mxi

10、jxpqq Nx jixqpj M q NN与p直接相连的点xij0,1i, j1,2 nxpq0,1p,q1,2 nz配送总路程xij0 1型决策变量式中： xpq0 1型决策变量n图中顶点数量cij顶点 i到 j的距离cpq顶点 p到q的距离在此模型中，将线路分为实际弧 cij 和虚拟弧 cpq是无向的，设定 0-1 型决策nn变量 xij 和 xpq ，目标函数 min zcij xijcpq xpq 表示为所走的实际弧和虚i ,j 1 p.q 1拟弧的最小路程。将线路分别设为实际边和虚拟边，边是有向的。约束条件xij xji 1表示每一条实际边走且只能走一次。 而虚拟边的约束条件是 x

11、pq xqp 1，即每条虚拟边最多走一次。设定流入某一顶点的线路为正，而流出此顶点 的线路为负，则约束条件xij xpqxjixqp 是用来保证每一个顶点j M q N j M q N精彩文档实用标准文案流人流出的线路总和为零，即保证每一个节点为偶点。4、应用推广本文研究了物流配送路径优化问题。基于 EXCEL 通过构建图书配送的中国 邮递员问题优化模型， 实现了物流配送路径的遍历性和路程的最小化。 通过本文 的研究，可以在物流配送过程中节省物流配送时间， 降低配送成本， 也可为其它 遍历路程最小化问题路径优化提供借鉴。 。利用中国邮递员问题的图上作业法或最小树法来分析得出投递的最优路线。 在时间、路程、费用之间找到一个平衡点，这个平衡点就是绩效的来源。在最优 路线之下可以大大地压缩投递成