中国邮递员模型研究

《中国邮递员模型研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国邮递员模型研究一、中国邮递员问题概述著名图论问题之一。邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线?关于邮递员最优投递路线问题最早是由管梅谷首先提出并进行研究的,国际上现在统称之为中国邮递员问题。管梅谷给出了这一问题的奇偶点图上作业法。Edmonds等给出了中国邮递员问题的改进算法,较前者的计算更为有效。管梅谷对有关中国邮递员问题的研究情况进行了综述。早期关于中国邮递员问题的讨论总是基于无向图展开的,事实上,由于单行线或上下行路线的坡度等原因,这一问题有时必须借助于有向图来进行研究和解决。到目

2、前为止,对中国邮递员问题的研究主要是从图论角度展开的,给出的多数都是各种启发式算法或递推算法。本文从数学规划的角度进行研究。数学规划建模具有借助软件包求解方便、易于修改和推广等多方面的优点,即使对于大型问题也易于建模分析和解决的优点。1、传统中国邮递员问题的建模一些基本概念:定义经过的每条边的迹叫做的Euler迹；闭的Euler迹叫做Euler回路或回路；含Euler回路的图叫做Euler图。直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。定理（i）是Euler图的充分必要条件是连通且每顶点

3、皆偶次。（ii）是Euler图的充分必要条件是连通且，是圈，。（iii）中有Euler迹的充要条件是连通且至多有两个奇次点。问题（管梅谷，1960）：一位邮递员从邮局出发投递邮件，经过他所管辖的每条街道至少一次，然后回到邮局。请为他选择一条路线，使其所行路程尽可能短。图论模型：求赋权连通图中含有所有边的权最小的闭途径。这样的闭途径称为最优回路。思想：（1）若G是Euler图，则G的Euler环游便是最优回路，可用Fleury算法求得；（2）若G不是Euler图，则含有所有边的闭途径必须重复经过一些边，最优回路要求重复经过的边的权之和达到最小。闭途径重复

4、经过一些边，实质上可看成给图G添加了一些重复边（其权与原边的权相等），最终消除了奇度顶点形成一个Euler图。因此，在这种情况下求最优回路可分为两步进行：首先给图G添加一些重复边得到Euler图，使得添加边的权之和最小，（其中）；然后用Fleury算法求的一条Euler环游。这样便得到G的最优回路。问题是：如何给图G添加重复边得到Euler图，使得添加边的权之和最小？方法一（图上作业法）定理1设C是一条经过赋权连通图G的每条边至少一次的回路，则C是G的最优回路当且仅当C对应的Euler图满足：（1）G的每条边在中至多重复出现一次；（2）G的每个圈上在中

5、重复出现的边的权之和不超过该圈总权的一半。奇偶点图上作业法：先分奇偶点，奇点对对联；联线不重迭，重迭要改变；圈上联线长，不得过半圈。基本步骤：1、确定第一个可行方案。找到图中所有奇顶点（必有偶数点）将它们两两配对。新图中无奇顶点，得到第一个可行方案。2、调整可行方案，使重复边总长度下降。3检查图中的每个圈，如果每个圈重复边总长度不超过该圈总长度的一半，则已求得最优解。否则进行调整：将这个圈的重复边去了，而将原来没有重复边的各边加上重复边，其他各圈的边不变，根据2再一次调整。奇偶点图上作业法虽然通俗易懂，但使用时需要检查图的每个圈，对于有很多圈的图，计算

6、量很大，实际当中用得较少。方法二（Edmonds-Johnson方法）定理2设G是赋权连通图，G中有个奇度顶点。设则是以G的奇度顶点为起点和终点的条无公共边的最短路。基于此定理，Edmonds和Johnson于1973年给出了求解邮递员问题的有效算法。Edmonds-Johnson算法：对于非Euler图，1973年，Edmonds和Johnson给出下面的解法：设是连通赋权图。（i）求。（ii）对每对顶点，求（是与的距离，可用Floyd算法求得）。（iii）构造完全赋权图，以为顶点集，以为边的权。（iv）求中权之和最小的完美对集。（v）求中边的端点之

7、间的在中的最短轨。（vi）在（v）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。（vii）在（vi）中得的图上求Euler回路即为中国邮递员问题的解。若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求。Fleury算法：（1）任取，令.（2）设已经行遍，按下面方法来从中选取：（a）与相关联；（b）除非无别的边可供行遍，否则不应该为中的桥。（3）当（2）不能再进行时，算法停止。判断是否为欧拉图（连通性和奇度点）图　YesNo输出无欧拉回路与相关联i=i+1,非桥Yes、输出欧拉回路Fleury

8、算法流程图1、利用LINGO中国邮递员0-1规划求解在中国邮递员问题中，不算出地点，n个邮局有