运筹学 中国邮递员问题

中国邮递员问题综述摘要：本文综合论述了运筹学中的中国邮递员问题，首先简介了该问题的起源，然后建立起该问题的图论模型，旨在使邮递员的投递线路最短，给出了算法和步骤，再借助lingo 软件进行了实证分析. 中国邮递员问题的研究在网上交易和电子商务快速发展的今天尤其具有重要的现实意义.关键词：投递一笔画欧拉回路最短路 Lingo一、引言图论是应用十分广泛的运筹学分支，它已广泛的应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域.在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决.例如，在组织生产中，为完成某项任务，各工学之间怎么样衔接，才能使生产任务完成的又快又好.一个邮递员送信，要走完他负责投递的所有街道，完成任务后回到邮局，应该按照怎么样的路线走，才能使得走的路线最短.中国投递员问题是1960年我们从生产实际中提出的一个数学问题，它是从下述实际问题中抽象出来的：“一个投递员应该怎么选择一条线路，才能既把所有由他负责的信件都送到，而所走的路程又最短”.在我们开始研究中国投递员问题以前，国外有人研究过所谓旅行售货员的问题，即：“一个售货员要到n个城市去售货，问他应该选择怎样的一条线路，才能既走遍所有城市，并且走的路程最短”. 这是一个著名的难题.当n较大时，即使使用大型电子计算机，也很难解决.投递员面临的问题显然可以归纳为旅行售货员问题，事实上，只要把投递员必须送的每一个地点看成是一个城市就行了.但是一般来说，投递员每次要到约二、三百个地点送信，如果归纳为旅行售货员问题来解决，将是一个规模很大的问题，是无法解决的.但是，在仔细分析了投递员面临的问题后，我们发现这个问题具有一定的特点，即需要送信的地点一般都是比较密集的排列在街道上的，因此，实际上，我们称这个问题为“最短投递线路问题”，1965年后国外称之为“中国投递员问题”.二、概念与原理一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．用图论的述语，在一个连通的赋权图)G中，要寻找一条回路，使该回路包含G中V,(E的每条边至少一次，且该回路的权数最小．也就是说要从包含G的每条边的回路中找一条权数最小的回路．在实际生活中，人们为了反映一些对象之间的关系，常常会在纸上用点和线画出各种各样的示意图.例如：8世纪时，欧洲有一个风景秀丽的小城哥尼斯堡, 那里有七座桥.如图1所示：河中的小岛A 与河的左岸B 、右岸C 各有两座桥相连结，河中两支流间的陆地D 与A 、B 、C 各有一座桥相连结.问：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？这个例子是历史上非常有名的哥尼斯堡7桥问题.哥尼斯堡现在是立陶宛共和国的一个城市，图1是当地奈发夫岛附近的地域图，此例子就是当地人民中间流传久远的一个难题.直到1736年，数学家欧拉首次系统研究并完全解决了这类问题.图1七桥问题引起了著名数学家欧拉（1707—1783）的关注.他把具体七桥布局化归为图2所示的简单图形，于是，七桥问题就变成一个一笔划问题：怎样才能从A 、B 、C 、D 中的某一点出发，一笔划出这个简单图形（即笔不离开纸，而且a 、b 、c 、d 、e 、f 、g各条线只画一次不准重复），并且最后返回起点？ABCDa bcd fgde图2一笔划出的图形中的各点或者都是与偶数条线相连的点，或者其中只有两个点与奇数条线相连.欧拉定理: 如果一个网络是连通的并且奇顶点的个数等于0或2，那么它可以一笔划出，否则它不可以一笔划出.定义 经过G 的每条边的迹叫做G 的Euler 迹；闭的Euler 迹叫做Euler 回路或E 回路,含Euler 回路的图叫做Euler 图.直观地讲，Euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点.定理1（1）G 是Euler 图的充分必要条件是G 连通且每顶点皆偶次.（2）G 是Euler 图的充分必要条件是G 连通且 di i C G 1==，i C 是圈，)()()(j i C E C E j i ≠Φ= .（3）G 中有Euler 迹的充要条件是G 连通且至多有两个奇次点.另外一种表述：定理2 对连通图G （V ，E ），下列条件是相互等价的： （1）G 是一个欧拉图；（2）G 的每一个节点的度数都是偶数；（3）G 的边集合E 可以分解为若干个回路的并．如果一幅图是由点和线连接组成，那么与奇数条线相连的点叫“奇点”，与偶数条线相连的点叫“偶点”．三、运作模式一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．用图论的述语，在一个连通的赋权图),(E V G 中，要寻找一条回路，使该回路包含G 中的每条边至少一次，且该回路的权数最小．也就是说要从包含G 的每条边的回路中找一条权数最小的回路．如果G 是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若G 不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多．本次的要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法．所谓欧拉G 路与哥尼斯堡7桥问题相联系的．在哥尼斯堡7桥问题中，欧拉证明了不存在这样的回路，使它经过图中每条边且只经过一次又回到起始点．与此相反，设),(E V G 为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉回路，并称图G 为欧拉图．在一个图中，连接一个节点的边数称为该节点的度数．对欧拉图，我们有下列结果： 定理3 下列条件是相互等价的： （1）G 是一个欧拉图；（2）G 的每一个节点的度数都是偶数；（3）G 的边集合E 可以分解为若干个回路的并．证明 ：()()12⇒ 已知G 为欧拉图，则必存在一个欧拉回路．回路中的节点都是偶度数．()()23⇒ 设G 中每一个节点的度数均为偶数．若能找到一个回路1C 使1C G =，则结论成立．否则，令11\C G G =，由1C 上每个节点的度数均为偶数，则1G 中的每个节点的度数亦均为偶数．于是在1G 必存在另一个回路2C ．令2121\C G G G =，···．由于G 为有限图，上述过程经过有限步，最后必得一个回路r C 使 r r r C G G \1-=上各节点的度数均为零，即1-=r r G C 这样就得到G 的一个分解 r C C C G ⋅⋅⋅=21．()()31⇒ 设G C C C r =⋅⋅⋅12 ，其中i C （I=1,2,…,r ）均为回路．由于G 为连通图，对任意回路i C ,必存在另一个回路j C 与之相连，即i C 与j C 存在共同的节点．现在我们从图G 的任意节点出发，沿着所在的回路走，每走到一个共同的节点处，就转向另一个回路，···，这样一直走下去就可走遍G 的每条边且只走过一次,最后回到原出发节点，即G 为一个欧拉图．利用定理1去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了．下面介绍一种求欧拉回路的算法即：弗罗莱算法算法步骤如下：（1）任取起始点v v R 00,;→（2）设路)},({,),,({),,({1211201r r i i r i i i v v e v v e v v e R -⋅⋅⋅=已选出，则从E\},,,{21r e e e ⋅⋅⋅中选出边1+r e ，使1+r e 与r i v 相连，除非没有其它选择，G e r r \{}+1仍应为连通的． （3）重复步骤（2），直至不能进行下去为止．定理4 有向图存在欧拉回路的充分必要条件是对任意节点，进入该节点边数（进数）与离开该点的边数（出数）相等．如果G 是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若G 不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多．本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法．首先注意到，若图G 有奇数度节点，则G 的奇数度节点必是偶数个．把奇数度节点分为若干对，每对节点之间在G 中有相应的最短路，将这些最短路画在一起构成一个附加的边子集E '．令//E G G +=，即把附加边子集/E 迭加在原图G 上形成一个多重图/G ，这时G /中连接两个节点之间的边不止一条．显然/G 是一个欧拉图，因而可以求出/G 的欧拉回路．该欧拉回路不仅通过原图G 中每条边，同时还通过E 中的每条边，且均仅一次．邮递员问题的难点在于当G 的奇数度节点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集/E 的权数)(.E ω为最小？为此有下列定理．定理 5 设),(E V G 为一个连通的赋权图，则使附加边子集/E 的权数)(/E ω为最小的充分必要条件是/E G +中任意边至多重复一次，且/E G +中的任意回路中重复边的权数之和不大于该回路总权数的一半．必要性．用反证法．设存在一种奇节点集的配对，使其附加边子集/E 权数 )(/E ω为最小．若/E G +中有一条边重复n n ()≥2次，由于/E G +为欧拉图，所以删去相应的二次重复边后仍为欧拉图．这样，相应的附加边子集的权数将减小，这与)(/E ω为最小的假设矛盾．这说明/E 中的边均互不相同．其次，若/E G +中存在一个回路，使它的重复边的权数之和大于该回路总权数的一半，则在/E 中删去这些重复边（注意：这些边均在/E 中），而代之以该回路的其余部分的边再重复一次．经过这种替代后所得到的边子集//E 仍为附加子集，且)(///E E ωω≤）（，又产生矛盾．充分性．设有两个附加边子集/E 和//E ，均使/E G +/和//E G +中每条边至多重复一次，且每个回路中的重复边的权数和不大该回路权数的一半，我们来证明)()(///E E ωω≡．首先注意到，由/E 和//E 不相同的部分组成的图（记为]\[//////）（E E E E G ）是由一个或若干个欧拉子图所组成的．这是因为///E E +中每个节点的度数均为偶数，而/E 和//E 的公共边数也是偶数，故]\[//////）（E E E E G 中每个节点的度数仍为偶数，所以它若为连通图时是一个欧拉图；若为非连通图时则由若干个欧拉子图组成．]\[//////）（E E E E G 的任何回路都由E /和E //中的边组成，而E /和E //在回路中的权数分别不大于该回路权数的一半，因而任何回路中属于/E 中的权数之和与属于//E 中的边数之和必定相等，所以)()(///E E ωω=．它就是最优附加边子集的权数，即/E 和//E 均为使附加边子集的权数达到最小的最优附加边子集.四 数型分析由定理3可得一个寻找邮递员问题最优解的方法．现举例如下：A1A2A3A4B3B4431233图3例1 知邮递员要投递的街道如图3示，试求最优邮路．先找出奇节点：1A ，2A ，3A ，4A ，1B ，2B ，3B ，4B ．奇节点进行配对，不妨把1A 与1B ，2A 与2B ，A 3与B 3，3A 与3B 配对，求其最短路．显然它不是最优解．下面我们根据定理3来进行调解．A1A2A3A4B3B4431233图4第一次调整：删去多于一条的重复边，即3A 与3B ，4A 与4B 中的),,(34B A 调整后，实际上成为1A 与2B ，2A 与1B ，3A 与4A ，3B 与4B 的配对，它们的最短路如图4示．A1A2A3A4B3B4431233图5第二次调整：发现在回路{1A ，2A ，2B ，4A ，3B 4B ，1B ，1A }中重复边的权数和为11，大于该回路权数20的一半．因而调整时，把该回路的重复边删去，代之以重复其余部分，得图5．可以看出，实际上是调整为1A 与2A ，1B 与4B ，3A 与4A ，2B 与3B 配对．A1A2A3A4B3B4431233图6第三次调整：在图5中发现回路{3A ，4A ，2B ，3A }中重复边的权数和为7，大于该回路权数10的一半，因而删去原重复边（3A ，2V ，4A ）和（4A ，2B ），而添加（2B ，3A ），得到图6．进行检查发现，既没有多于一条的重复边，也没有任何回路使其重复边的权数之和大于该回路的一半，因此图6就是最优的附加边子集/E ，而/E G 为欧拉图，因此，可以求得最优的路线为1143221A B B B A B A −→−−→−−→−−→−−→−−→−.五 优化模型上述的邮递员问题，假定了邮递员的投递范围内的每条街道的上行和下行使没有差别的，而在实际信件的投递过程中是不可能的，如果遇到单行线街道、街道有一定的坡度、街道两边不能单行中同时投递等问题.这样的问题称之为广义的中国邮递员问题.这一广义的中国邮递员问题可以抽象为一个有向图问题.类似于前面描述的邮递员问题（称之为传统的邮递员问题），广义的邮递员问题可以综述为：给定一个连通有向图),(E V G 每个弧e 上有非负权)(e ω，需要寻找G 的一个回路，它过每个弧至少一次，且使得总权最小.对于广义的中国邮递员问题，添加弧的个数至多1条有时已经不再可行，即需要添加多条弧，才能使对应的连通有向图G 的任一定点的进向弧数与出向弧数相同，从而使),(E V G '',存在回路（E 回路）.在此，如E V V e J I ∈=),(,则称弧e 是顶点J V 的进向弧，同时也是I V 的出向弧.可以证明，如),(E V G 的顶点数为n ，则每条弧上至多增加)1(-n 条添加弧，即可实现各顶点的进项弧数与出向弧数相等.根据以上分析，对于),(E V G 的每条弧E e j i ∈,定义一正整数变量j i x ,，表示弧j i e ,上增加了)1(,-j i x 条添加弧，由此形成一个有向图),(E V G ''.类似以上的分析，可以有广义的中国邮递员显示整数规划模型（GCPP ）:min j i Ej i ji x w,),(,∑∈s.t.Ej i x ni xxj i Ej i ji Ej i ji ∈∀===-∑∑∈∈),(n ....2,1......2,1,0,,,,,，或通过这一模型的求解，可以得到广义的中国邮递员问题的最优投递路线. 考虑下图的中国邮递员问题：V1V2V3V4V5V6V7V825344图77V1V2V3V4V63图8根据前面的模型讨论，这一数值例式邮递员问题对应的整数规划模型如下：)(4)(9)(4)(4)(5)(4)(3)(6)(3)(5)(4)(2min 4,55,44,33,45,66,54,99,43,22,36,99,66,77,62,99,28,99,8)1,22,18,77,81,88,1x x x x x x x x x x x x x x x x x x x x x x x x +++++++++++++++++++++++08,12,11,81,2=--+x x x x03,29,21,22,32,92,1=---++x x x x x x 04,32,33,43,2=--+x x x x05,49,43,44,54,94,3=---++x x x x x x 05,46,55,45,6=--+x x x x05,69,67,66,56,96,7=---++x x x x x x 08,76,77,87,6=--+x x x x 09,87,81,88,98,78,1=---++x x x x x x08,96,94,92,99,89,69,49,2=----+++x x x x x x x x ,11,88,1≥+x x 18,77,8≥+x x 11,22,1≥+x x 18,99,8≥+x x 16,77,6≥+x x 12,99,2≥+x x 19,66,9≥+x x 12,33,2≥+x x 19,44,9≥+x x 15,66,5≥+x x14,33,4≥+x x 14,55,4≥+x x 10,或=j i x lingo 程序如下：表9运行lingo9.0得到结果如下Feasible solution found.Total solver iterations: 6Variable Value MINZ 88.00000 X18 0.000000 X81 1.000000 X87 2.000000 X78 0.000000 X12 1.000000 X21 0.000000 X89 0.000000 X98 3.000000 X29 0.000000 X92 1.000000 X67 0.000000X76 2.000000X69 1.000000X96 0.000000X32 0.000000X23 2.000000X94 0.000000X49 3.000000X56 0.000000X65 1.000000X43 0.000000X34 2.000000X54 1.000000X45 0.000000Row Slack or Surplus1 0.0000002 0.0000003 0.0000004 0.0000005 0.0000006 0.0000007 0.0000008 0.0000009 0.00000010 0.00000011 0.00000012 1.00000013 0.00000014 2.00000015 1.00000016 0.00000017 0.00000018 1.00000019 2.00000020 0.00000021 1.00000022 0.000000所以这一问题的最优解是15,44,55,66,54,93,49,62,39,26,78,98,77,81,88,11,22,1=================x x x x x x x x x x x x x x x x x 其它0,=j i x ，最小权重为88.假定邮局在定点V 1,则有如下最优投递路线：1,88,11,22,33,44,55,44,99,66,55,66,77,88,99,22,1e e e e e e e e e e e e e e e e −→−−→−−→−−→−−→−−→−−→−−→−−→−−→−−→−−→−−→−−→−−→−注意这一问题的最优投递路线不唯一.同理可以求得邮局从任何一丁点出发时的最优投递路线.六 结束语现在我国经济正处于高速发展的过程中，尤其是信息产业的快速发展更是日新月异，而在这其中，电子商务行业更是异军突起，发展迅猛，以淘宝网、当当网、卓越网等为代表的网站更是带动了第三产业的迅猛发展，而与之相关的邮递产业也就提出了更加严格的考验，而如何更加快速、及时、准确的把信件送到客户的手中，更是邮递行业竞争的激烈点，所以说研究邮递员问题就显得会很有现实意义.当然，在本文之外还有很多涉及此问题的相关论题，我们还要不断努力，不断学习，为我国的邮递事业进到一点贡献.参考文献：[1]管梅谷 奇偶点图上作业法[M].数学学报, 1960.3.[2]管梅谷 邮递员问题综述[M].数学研究与评论1965.5[3]李玮 、王雷 中国邮递员问题的DNA 计算[M] 中国教育出版,2009.6[4]许志国、桂湘云 运筹学（第三版）[M]清华大学出版社2008.7[5]韩中庚. 用运筹学——模型、方法计算[M].清华大学出版,2007.9[6]哈拉里 图论 [M] 上海科技出版社 1980.9[7]李念祖 关于中国邮递员问题的最有完全子图算法社[J] 2009.19(07)[8]吴杰 求解中国邮递员问题的一种思路[J] 科技资讯 2007,16[9]冯俊文 中国邮递员问题的整数规划模型[J] ,2010.12[10] 金毅 对中国邮递员的理性分析 [J], 科技经济市场 2009.5A review of the Chinese postman problemGao KunAbstract: This article gives a conmprehensive review of the Chinese postman problem(CPP), the use of operations research principles of graph theory, Euler circuit, by the Konigsberg problem associated with the first issue of a stroke, the postman problem into a graph theory-related model, using the shortest Road principle of making the shortest postman's delivery routes, and further discussed the actual situation in China generalized directed graph based on the Chinese postman problem, the corresponding model, then study the Chinese postman problem. This article is mainly based on modern internet proposed The rapid development of trade, mail efficiency hasbecome a highly competitive industry, this question will be more importmant. Otherwise, there has many questions besides this article , so we should continue to learning and do our best to contribute to our post bussiness.Keywords:Post, A Stroke, Euler Circult, Shortest Path, Lingo本文综合论述了运筹学中的中国邮递员问题，首先简介了该问题的起源，然后建立起该问题的图论模型，旨在使邮递员的投递线路最短，给出了算法和步骤，再借助lingo软件进行了实证分析. 中国邮递员问题的研究在网上交易和电子商务快速发展的今天尤其具有重要的现实意义.。

☐图的存储表示；☐顶点的度数；☐图的连通性；☐顶点间的最短路径；☐欧拉图的判断，欧拉回路输出；问题描述：一个邮递员从邮局出发走遍每条街道，最后返回邮局，找到一条最短的行走线路？最短欧拉回路！问题提出：我国数学家管梅谷先生在20世纪60年代提出一笔画游戏✈✈满足“一笔画”：☐凡是由偶点组成的连通图,一定可以一笔画成.画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图☐凡是只有两个奇点的连通图（其余都为偶点）,一定可以一笔画成.画时必须把一个奇点为起点,另一个奇点终点☐其他情况的图都不能一笔画出实例：一个邮递员投递信件要走的街道如图所示，图中的数字表示各条街道的千米数，他从邮局出发，要走遍各街道，最后回到邮局。

怎样走才能使所走的行程最短？全程多少千米？ 2 1 2111怎么样使非欧拉图变为欧拉图？除去奇点！添加边或删除边。

怎么样除去奇点？这里应该采用的办法？重复某些边（添加边）2 1 23分析：图中共有8个奇点，不可能不重复地走遍所有的路。

必须在8个奇点间添加4条线，才能消除所有奇点，从而成为能从邮局出发最后返回邮局的一笔画。

当然要在距离最近的两个奇点间添加一条连线，图中虚线所示，共添加4条连线，这4条连线表示要重复走的路，显然，这样重复走的路程最短，全程34千米。

走法不唯一邮局2 1 2111 2 1 23☐建立街区无向网的邻接矩阵；☐求各顶点的度数；☐求出所有奇度点；☐图的连通性判断；☐求出每一个奇度点到其它奇度结点的最短路径；☐根据最佳方案添加边，对图进行修改，使之满足一笔画；☐对图进行一笔画，并输出；其一：“添加”哪些边？☐“添加”的边所依附的顶点必须均是奇度顶点☐“添加”的边必须是已有的边，也就是有的边不止走一次其二：如何选择代价最小的边？☐奇数顶点之间的最短路径☐Dijstra算法☐Floyd算法其三：输出一笔画？☐FE算法（F leury E uler）V4U1U6V3U5U2V1U4V2U31111111222222533V4V3V1V241.求奇度点的最短路径2.构造奇度点间的完全加权图3.求图的最佳（总权最小）完备匹配M={1,4;2,3}4.求1和4之间的最短轨V1 U1 V4；2和3之间的最短轨V2 U4 V3；5. 加同权边即可一个实例如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配给定一个图G ，M 为G 边集的一个子集，如果M 满足当中的任意两条边都不依附于同一个顶点，则称M 是一个匹配1.求奇度点的最短路径2.构造奇度点间的完全加权图3.求图的最佳（总权最小）完备匹配M={1,4;2,3}4.求1和4之间的最短轨V1 U1 V4；2和3之间的最短轨V2 U4 V3；5. 加同权边即可给定一个图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配1.取G 中的起始顶点V 0，令P 0=V 02.假设沿着P i = v 0e 1v 1e 2v 2…e i v i 走到顶点vi ，按下面方法从E(G)-{e 1,e 2,…,e i }中选e i+1①e i+1与v i 相关联；②除非没有别的边可供选择，否则e i+1不应该是G i =G-{e 1,e 2,…,e i }中的桥3.当2不能再进行时算法停止V4V1V2V5V6V7V8V3V4V1V2V5V6V7V8V3总结步骤1.求图G中奇度结点集合V0={v}；2.对V0中的每个顶点对u，v，用Dijkstra算法求距离d(u,v)；3.构造加权完全图；4.求加权图的总权最小的完备匹配M；5.在G中求M中同一边的结点间的最短轨；6.把G中在上一步求得的每条最短轨之边变成同权倍边，得到欧拉图G1；7.用FE算法求G1的一条欧拉回路W，W即为解；举例：邮递员要从邮局出发，走遍左下图(单位：千米)中所有街道，最后回到邮局，怎样走路程最短？全程多少千米？其二：如何选择代价最小的边？☐奇数顶点之间的最短路径☐Dijstra算法☐Floyd算法☐最小生成树的方法☐Prim算法☐Kruskal算法奇度结点间最短路径计算➢如果只有两个奇度结点，那么最短路径就是原来每条街道代价加上两个奇度顶点之间的最短代价之和；➢如果有多个奇度结点，要进行不同的组合。

中国邮递员问题第一篇：中国邮递员问题运筹学第六组运筹学个人心得之中国邮递员问题我们第六组做的第二次案例就是中国邮递员问题，这个问题是运筹学中的经典命题。

这个案例讲的是：在中国的六个县城，每个县城都有一个县局，县局下面设立若干个邮政所，每天邮递员的任务就是从县局出发，依次到每一个邮政所送邮件，要求每个邮政所都必须去，而且只能去一次。

这就涉及到一个路线的规划问题，怎么走才能使得邮递员走的路最少，而且能够完成任务。

在做题之前考虑了很久，真不知道从何着手，国为以前确实没有接触过这个类型的题，没有一个能够行得通的办法。

后来，我们选定了一个代表性的区域，来尝试求解，国为第六个区域的变量最多，所以就选择这个区域作为突破口。

只要第六个区域求解成功，其它五个区域便迎刃而解了。

首先，我们画了一个由第六区域的十七个点所组成的17*17矩阵，一一对应设定变量，在去除对角线的17个变量之后，我们得到272个变量。

这是一个非常庞大的变量群体，若按传统的线性规划方法求解，求解过程将会变得异常艰辛，而且以前的模板，求解工具都不能求解这么多变量。

所以我们一度陷入混乱，求解工作停滞不前。

后来老师在对这价目案例作初步的讲解的时候，提出了用运输模型来对这个问题进行求解，此话一出，真是如醍醐灌顶，酣畅极了，眼前简直豁然一亮，真想“拍案而起”。

若用运输模型求解，这个问题将会变得非常简单。

一方面由于每行的出发点只能有一个，而每列的终点也只能有一个，这样看来，邮运筹学第六组递员总是变成了一个产销平衡的运输问题，产量和销量都有是1。

这样我们就完成了求解工作，在第一次求解得出结论后，我们画了一个路线图，发现有几个两点循环，没有形成一条大通路，于是我们重新加入了两点循环约束，进行二次求解；在第二次求解完成后，我们又重新画了路线图，结果发现有四点循环于是我们又加入四点循环约束，进行第三次求解，在得到第三次求解的结果后，我们又画出了路线图，这次刚好形成了一个完整的通路，保证了邮递员每点都走到且行走的路线最合理。

中国邮递员数学问题
中国邮递员数学问题是一个著名的数学问题，也称为"中国邮递员问题"。

这个问题源于邮递员在担任邮递员工作时，需要沿着不同的街道进行投递。

邮递员必须走遍每一条街道至少一次，然后回到出发地点。

问题的目标是寻找一条最短的路径，使得邮递员能够满足投递的要求。

具体问题描述如下：给定一个城市的街道网络图，每条街道上都有一个正整数表示街道的长度。

邮递员需要从一个特定地点出发，沿着街道网络进行投递，然后回到出发地点。

要求邮递员经过的路径总长度最短。

这个问题属于旅行商问题的变种，是一个NP-完全问题。

因为问题规模较大，难以找到一个最优解。

因此，通常采用近似算法进行求解，如TSP（Traveling Salesman Problem）等。

邮递员问题在实际中有很多应用，比如快递员的路线规划、物流配送等。

解决这个问题可以提高物流效率，减少成本。

中国邮递员问题解法中国邮递员问题是一个著名的组合优化问题，实际上是一个旅行商问题（Traveling Salesman Problem，TSP）的变种。

问题描述：给定一个城市集合和城市之间的距离矩阵，求解一个最短的邮递员路径，使邮递员能够从出发城市出发，经过每个城市恰好一次，最后回到出发城市。

解法：1.暴力搜索暴力搜索是最简单直观的解法。

遍历所有可能的路径，计算每个路径的总距离，最后选择最短的路径。

这种解法的时间复杂度为O(n!)，随着城市数量的增加而急剧增加，效率非常低，只适用于小规模问题。

2.动态规划动态规划是一个更高效的解法。

使用一个二维数组dp[i][j]表示从城市i出发经过城市集合j的最短路径长度，其中j是一个二进制数，表示哪些城市已经访问过。

动态规划的转移方程为：dp[i][j] = min{dp[k][j XOR (1 << k)] + distance[i][k]}，其中k表示已经访问的最后一个城市。

利用这个递推关系，可以逐步计算出dp[0][1<<n-1]，即从城市0出发经过所有城市的最短路径。

最后，将此路径与每个城市的距离相加，得到最终的最短路径长度。

3.贪心算法贪心算法是一种更简单的解法。

首先选择一个起始城市，然后每次选择距离最近且未被访问过的城市，将其加入路径中。

重复此过程，直到访问完所有城市，然后回到起始城市。

这种解法的时间复杂度为O(n^2)，但由于贪心策略的局限性（可能会出现回头或死胡同），所以得到的解并不一定是最优解。

以上是三种常用的解决中国邮递员问题的方法，具体可以根据实际情况选择合适的算法进行求解。

附录2《图论》课程专题论文论文题目： 中国邮递员问题各种算法的对比分析班 级： 2008级数学与应用数学组 长： 马利巍2011年 12 月 27 日论文评价指标与鉴定意见摘要本文基于无向图的传统中国邮递员问题,给出了相应的显式整数规划模型,进一步讨论了一类基于有向图的广义中国邮递员问题,给出了相应的显式整数规划模型；并研究了随机中国邮递员问题,建立了相应的确定型等价模型。

并可以利用奇度数结点的配对来进行求解。

根据此思想给出了一种新的求解思路——通过去掉原始图中的偶度数结点并利用最小生成树来确定奇度数结点的配对。

提出了“虚拟权值”和“虚拟节点”的概念[]5,给出了中国邮递员问题的一种基于DNA 计算的求解算法。

新算法首先利用多聚酶链式反应技术来排除非解,从而得到中国邮递员问题的所有可行解；然后,结合基于表面的DNA 计算方法与荧光标记等技术,最终从所有可行解中析出最优解。

通过各种算法分析比较表明,新算法具有易于解读、编码简单等特点。

关键字：中国邮递员问题整数规划最优化模型奇度数结点最小生成树DNA计算多聚酶链式反应AbstractBased on the traditional Chinese to figure without the postman problem,The corresponding display integer programming model，further discussed based on adirected graph of the generalized China the postman problem，the corresponding display integer programming model；And the traditional China the postman problem，established the corresponding equivalent model that can and can use odd degree of nodes to solving matching。