中国邮递员问题综述 毕业论文

《中国邮递员问题综述 毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国邮递员问题综述摘要：本文综合论述了运筹学中的中国邮递员问题，首先简介了该问题的起源，然后建立起该问题的图论模型，旨在使邮递员的投递线路最短，给出了算法和步骤，再借助lingo软件进行了实证分析.中国邮递员问题的研究在网上交易和电子商务快速发展的今天尤其具有重要的现实意义.关键词：投递一笔画欧拉回路最短路Lingo一、引言图论是应用十分广泛的运筹学分支，它已广泛的应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域.在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决.例如，在组织生产中，为完成某项任务，各工学之间怎么样衔接，才能使生产任

2、务完成的又快又好.一个邮递员送信，要走完他负责投递的所有街道，完成任务后回到邮局，应该按照怎么样的路线走，才能使得走的路线最短.中国投递员问题是1960年我们从生产实际中提出的一个数学问题，它是从下述实际问题中抽象出来的：“一个投递员应该怎么选择一条线路，才能既把所有由他负责的信件都送到，而所走的路程又最短”.在我们开始研究中国投递员问题以前，国外有人研究过所谓旅行售货员的问题，即：“一个售货员要到个城市去售货，问他应该选择怎样的一条线路，才能既走遍所有城市，并且走的路程最短”.这是一个著名的难题.当较大时，即使使用大型电子计算机，也很难解决.投递员面临的问题显然可以归

3、纳为旅行售货员问题，事实上，只要把投递员必须送的每一个地点看成是一个城市就行了.但是一般来说，投递员每次要到约二、三百个地点送信，如果归纳为旅行售货员问题来解决，将是一个规模很大的问题，是无法解决的.但是，在仔细分析了投递员面临的问题后，我们发现这个问题具有一定的特点，即需要送信的地点一般都是比较密集的排列在街道上的，因此，实际上，我们称这个问题为“最短投递线路问题”，1965年后国外称之为“中国投递员问题”.二、概念与原理一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，

4、使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．用图论的述语，在一个连通的赋权图中，要寻找一条回路，使该回路包含中的每条边至少一次，且该回路的权数最小．也就是说要从包含的每条边的回路中找一条权数最小的回路．在实际生活中，人们为了反映一些对象之间的关系，常常会在纸上用点和线画出各种各样的示意图.13例如：8世纪时，欧洲有一个风景秀丽的小城哥尼斯堡,那里有七座桥.如图1所示：河中的小岛与河的左岸、右岸各有两座桥相连结，河中两支流间的陆地与、、各有一座桥相连结.问：一个人怎样才能一次

5、走遍七座桥，每座桥只走过一次，最后回到出发点？这个例子是历史上非常有名的哥尼斯堡7桥问题.哥尼斯堡现在是立陶宛共和国的一个城市，图1是当地奈发夫岛附近的地域图，此例子就是当地人民中间流传久远的一个难题.直到1736年，数学家欧拉首次系统研究并完全解决了这类问题.图1七桥问题引起了著名数学家欧拉（1707—1783）的关注.他把具体七桥布局化归为图2所示的简单图形，于是，七桥问题就变成一个一笔划问题：怎样才能从、、、中的某一点出发，一笔划出这个简单图形（即笔不离开纸，而且、、、、、、各条线只画一次不准重复），并且最后返回起点？图2一笔划出的图形中的各点或者都是与偶数条线相

6、连的点，或者其中只有两个点与奇数条线相连.13欧拉定理:如果一个网络是连通的并且奇顶点的个数等于0或2，那么它可以一笔划出，否则它不可以一笔划出.定义经过的每条边的迹叫做的Euler迹；闭的Euler迹叫做Euler回路或回路,含Euler回路的图叫做Euler图.直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点.定理1（1）是Euler图的充分必要条件是连通且每顶点皆偶次.（2）是Euler图的充分必要条件是连通且，是圈，.（3）中有Euler迹的充要条件是连通且至多有两个奇次点.另外一种表述：定理2对连通图

7、G（V，E），下列条件是相互等价的：（1）G是一个欧拉图；（2）G的每一个节点的度数都是偶数；（3）G的边集合E可以分解为若干个回路的并．如果一幅图是由点和线连接组成，那么与奇数条线相连的点叫“奇点”，与偶数条线相连的点叫“偶点”．　三、运作模式一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．用图论的