邮递员问题与旅行商问题讨论
摘要：中国邮递员问题（Chinese Postmen Problem）是由我国数学家
管梅谷教授在1962年首次提出并研究的。深入研究这个问题，我们
发现这个问题的根本，其实就是图论中的最短路径问题。本文主要
运用欧拉图及其相关性质来展开研究的，希望通过图论的相关方法得
到问题的最优解，主要思想是：找到欧拉图中的最小权数，最小权数
即为最优解。首先，在对邮递员问题进行分析时，我们需要给出在讨
论过程中所需要的相关定理。其次，本文将从欧拉图及其回路方面着
手，找出在中国邮递员问题在相关情况下的最优解。而旅行商问题
（Traveling Salesman Problem ）也是数学领域中著名问题之一。其具有重要的理论和实际研究价值，在工程实践中应用广泛。本
文将采用三种方法求解旅行商问题，分别为：遗传算法、蚁群算
法和模拟退火算法。在得到结果后，我们比较了三种算法的优劣，得出它们不同的适用范围：蚁群算法适用于缓慢上网较精确的求
解场合；模拟退火算法适用于快速精确的求解；遗传算法适用于
快速求解，但存在结果准备度要求不高的情况。
关键词：欧拉图、欧拉回路、最小权数、遗传算法、蚁群算法、
模拟退火算法
1 ：引 言
中国邮递员问题和旅行商问题都是著名图论问题。它们在现实生
活中也很重要的意义。中国邮递员问题最早是由管梅谷首先提出并进
行研究的，国际上现在统称之为中国邮递员问题。该问题具有很强的
现实意义。早期关于中国邮递员问题的讨论总是基于无向图展开的，
事实上，由于单行线或上下行路线的坡度等原因，这一问题有时必须
借助于有向图来进行研究和解决。到目前为止，对中国邮递员问题的
研究主要是从图论角度展开的，给出的多数都是各种启发式算法或递
推算法。如果中国邮递员问题中的图是欧拉图，那么欧拉回路就是最
优回路。但一般情形下中国邮递员问题的相关图不是欧拉图，最优回
路包含某些边至少两次。这时求最优回路的思想是：在图G 中添加
一些重复边使新图G*成为欧拉图，且使得所有添加的重复边的权和
最小。再由G*的欧拉回路得到G 的最优回路。本文也沿袭了以往的
方法，从欧拉图方面进行研究，试图得出当中国邮递员问题的图为欧
拉图时的最短路径，从而得出中国邮递员问题的最优解。 而旅行商问题又称旅行推销员问题，它是一种典型的组合优化问
题，已经证明了是一个NP 难题。其描述如下：给定n 个城市和两两
城市之间的距离，有一个旅行商从某一个城市出发，要求确定一条经
过各城市当且仅当一次的最短路线。旅行商问题易于陈述难于求解。
目前求解旅行商问题的方法可分为两大类：精确算法和近似算法。常
用的精确算法求解方法主要有：分枝定界法、线性规划法和动态规划
法，其计算程度十分复杂，难以解决大规模问题。近似算法又分为巡
回路径构造算法、巡回路径优化算法和智能算法，其算法简单，计算
量小。而其中，智能算法的研究最为引人注目，如模拟退火、遗传算
法、蚁群算法等，它们给旅行商问题提供了新的途径。本文就是用这
三种方法来求解旅行商问题。
首先，我们来看中国邮递员问题。
2：中国邮递员问题
2.1 定义基础
定义 经过G 的每条边的迹叫做G 的欧拉迹，封闭的欧拉迹叫做
欧拉回路或E 回路，含有欧拉回路的图叫做欧拉图。
定理 （i ）G 是欧拉图的充分必要条件是G 连通且每顶点皆偶次。
（ii ）G 是欧拉图的充分必要条件是G 连通且G = c i ，C i 是i -1d
圈，E (c i ) E (c j ) =Φ(i ≠j ) 。
（iii ）G 中有欧拉迹的充要条件是G 连通且至多有两个奇次点。
2.2 问题描述
中国邮递员问题描述如下：邮递员从邮局出发送信，要求对辖
区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择
一条最短路线？该问题用图论的语言可描述为：即在一个带权图G
中，能否找到一条回路C ，使C 包含G 的每条边最少一次且C 的长度
又最短？邮递员最优投递路线问题最早是由管梅谷首先提出并进行
研究的, 国际上现在统称之为中国邮递员问题。管梅谷给出了这一
问题的奇偶点图上作业法。Edmonds 等给出了中国邮递员问题的改
进算法, 较前者的计算更为有效。管梅谷对有关中国邮递员问题的
研究情况进行了综述。
2.3 问题分析
现假设邮递员问题的图为图G ：
(1)：若G 没有奇数度结点，则G 是欧拉图，于是欧拉回路C
是唯一的最小长度的投递路线。
（2）：若 G 不是欧拉图，则含有所有边的闭途径必须重复经过
一些边，最优回路要求重复经过的边的权之和达到最小。闭途径重复
经过一些边，实质上可看成给图 G 添加了一些重复边（其权与原边
的权相等），最终消除了奇度顶点形成一个欧拉图。因此，在这种情
况下求最优回路可分为两步进行：首先给图 G 添加一些重复边得到
欧拉图G *，使得添加边的权之和∑w (e ) 最小，（其中F=E (G *) \E (G ) ）；
ε∈F
然后用 Fleury 算法求G *的一条欧拉环游。这样便得到 G的最优回
路C 。
2.4 问题解答
1）：当图G 是欧拉图时，可用Fleury 算法求欧拉回路。
Fleury算法如下：
i) 任取ν(0) ∈V (G ) , 令P 0=ν0
ii） 设P i =ν0e 1ν1e 2... e i νi 已经行遍，按下面方法从E (G ) -{e 1, e 2,..., e i }
中选取：
a）e i +1与νi 相关联
b）除非无别的边可供行遍，否则e i +1不应该为中的
G i =G -{e 1, e 2,..., e i }桥。
iii ）当（ii ）不能在进行时，算法停止。
（Fleury 流程图见附录一）
2）：当图G 不是欧拉图时，我们所要找的最短路径即为权数最小的
路径。现给出找到权数最小的方法步骤如下：
设G 是连通加权图
i)求G 中奇次顶集合V 0={ν|ν∈V (G ), d (ν) =1(mod2)}。
ii）对中的每个顶对μ、ν，求距离d (μ, ν) 。(d (u , v ) 是u 与v 的距
离，可用Floyd 算法求得) 。
iii）构造加权完全图K |V |， V (K |V |) =V 0, K |V |中边μν之权为d (μ, ν) 。000
iv)求加权图K |V |的总权最小的完备匹配M 0
v）在G 中求M 中同一边之端点间的最短轨
vi）把G 中在（v ）求得的每条最短轨上每条边加一条等权的倍
边，使之边变成同权倍边，得欧拉图G '
vii）用FE 算法求得G ' 的一条欧拉回路W ' ，W ' 即为中国邮路
3：旅行商问题
3.1 定义基础
i) 遗传算法:是一种基于生物自然选择与遗传机理的随机搜索算
法。 ii) 蚁群算法:是一种全新的通过模拟自然界蚂蚁寻径的行为的进化
算法
iii) 模拟退火法:是一种模拟熔化状态下物体由逐渐冷却至最终达结
晶状态这一物理过程的近似全局优化算法。
3.2 问题描述
TSP问题（Traveling Salesman Problem ），即旅行商问题，
是数学领域中著名问题之一。假设有一个旅行商人要拜访N 个城
市，他必须选择所要走的路径，路径的限制是每个城市只能拜访
一次，而且最后要回到原来出发的城市。路径的选择目标是要求
得的路径路程为所有路径之中的最小值。即：给定一个完全无向带
权图G=(V,E)，其每条边(u,v)∈E 有一非负整数权值w(u,v)。要求
找出G 的一条经过每个顶点一次且仅经过一次的回路，使得该回路上
所有边的权值之和尽可能地小。从图论的角度来看，该问题实质是在
一个带权完全无向图中，找一个权值最小的哈密顿回路使得我们能够
通过这些城市至少一次。 3.3 问题分析
用图论描述旅行商问题，那就是已知赋权图G=（C,L ），找
出总权值最小的哈密顿图圈。其中C={c 1, c 2,..., c n }为顶点集，这里表
示n 个城市的集合；L={l ij |c i , c j ∈C }为各顶点相互连接组成的边集，
这里是集合C 中元素（城市）两两连接的集合。每一边都存在与
之对应的权值，构成D=（d ij ）矩阵，实际应用中的可以表示距离、
费用、时间、油量等。
对于对旅行商问题，d ij =d ji ，∀i , j =1, 2, 3,..., n 。若对于城市
C={c 1, c 2,..., c n }的一个访问顺序为T={t 1, t 2, t 3,..., t i ,..., t n }，其中
t i ∈C (i =1, 2, 3,..., n ) ，且记t n +1=t 1。则旅行商问题的数学模型为：
min l =∑d t i t i +1 i =1n
3.4 问题解答
3.4.1 遗传算法解答
一般的，遗传算法以一群随机产生的可行解开始，每个解用一串编码表示为个体，由优化目标函数确定个体的适应度对个体进行评价。通过交叉、变异等遗传算子的操作对种群进行组合产生下一代个体，逐步向优化的种群进化。
遗传算法求解旅行商问题的基本步骤如下：
1）在搜索空间中随机产生初始种群；
2）计算每个个体的目标函数，经调整得到相应的适应度值（路线长度）；
3）通过遗传算子操作产生下一代个体；
4）在下一代个体的基础上回到步骤2），纪录下每代的最好个体，直到达到最大迭代次数；
5）输出最好个体，终止整个程序。
3.4.2 蚁群算法解答
蚂蚁群找到食物时，它们总能找到一条从食物到巢穴之前的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机的挑选一条路径前行，与此同时释放出与路线长度有关的信息素。路径越长，释放的激素浓度越低。当后来的蚂蚁在次碰到这个路口时，选择激素浓度较高路径就会相对较大。这样就形
成了一个正反馈。最优路径上的激素浓度越来越大，而其他的路径上激素浓度却会随着时间的流逝而消减。这样，整个蚁群最终会找到最优路径。
蚁群算法求解旅行商问题的步骤如下：
1）令nc=0（nc 为迭代步数或搜索次数）；每条边上的τij (0) =c（常数），并且∆τij =0；放置m 个蚂蚁到n 个城市上。
2）将各个蚂蚁的初始出发点置于当前解集b μ中；对每个蚂蚁k
k （1,2，... ，m ），按概率P ij k 移至下一城市j ，将城市j 置于
b μk 中。
3）经过n 各时刻，蚂蚁k 可走完所有的城市，完成一次循环。计算每个蚂蚁走过的总路线长度L k ，更新找到的最短路径。
4）更新每条边上的信息量τij (t +n ) 。
5）对于每一条边，∆τij =0；nc=nc+1
6）若 nc
3.4.3 模拟退火算法求解
模拟退火法是了利用所求解问题的求解过程与熔化物体退火过程的相似性，采用随机模拟物体退火过程来完成问题的求解，即在控制参数（温度）的作用下对参数的值进行调整，直到找到能使能量函数达到全局极小值的参数。为了在退火过程中不丢失最低能状态，降温时初始温度足够高，下降速率要小。
模拟退火算法求解步骤如下：
运行速度最慢。其次，比较三种算法的准确度。遗传算法求得平均路线长度为18 216千米，平均18.45%；蚁群算法为15 648千米，平均1.75%；模拟退火算法为16 981千米，平均10.42%。就解得分布而言，蚁群算法的结果分布最集中，均在目前最优解所在区间[15 000,16 000]，如图1所示：其中纵坐标表示“求解结果分区间的个数”。
图1 三种算法得到的结果分布区间
最后，比较三种算法的巡回路线与目前最好结果的相似程度，如图2所示；遗传算法的巡回路线除华北和华中地区外，其他地区与目前最好结果的巡回路线大体一致；蚁群算法和模拟退火算法除西北和西南地区外，其他地区与目前最好结果的巡回回路线存在明显差异。
由以上比较分析得出：蚁群算法的最短路线长度较好，平均路线长度最好，但是其运行速度太慢，都超过了1分钟，故，蚁群算法适用于缓慢地较精确的求解场合；模拟退火法的最短长度最好，平均路
邮递员问题与旅行商问题讨论
摘要：中国邮递员问题（Chinese Postmen Problem）是由我国数学家
管梅谷教授在1962年首次提出并研究的。深入研究这个问题，我们
发现这个问题的根本，其实就是图论中的最短路径问题。本文主要
运用欧拉图及其相关性质来展开研究的，希望通过图论的相关方法得
到问题的最优解，主要思想是：找到欧拉图中的最小权数，最小权数
即为最优解。首先，在对邮递员问题进行分析时，我们需要给出在讨
论过程中所需要的相关定理。其次，本文将从欧拉图及其回路方面着
手，找出在中国邮递员问题在相关情况下的最优解。而旅行商问题
（Traveling Salesman Problem ）也是数学领域中著名问题之一。其具有重要的理论和实际研究价值，在工程实践中应用广泛。本
文将采用三种方法求解旅行商问题，分别为：遗传算法、蚁群算
法和模拟退火算法。在得到结果后，我们比较了三种算法的优劣，得出它们不同的适用范围：蚁群算法适用于缓慢上网较精确的求
解场合；模拟退火算法适用于快速精确的求解；遗传算法适用于
快速求解，但存在结果准备度要求不高的情况。
关键词：欧拉图、欧拉回路、最小权数、遗传算法、蚁群算法、
模拟退火算法
1 ：引 言
中国邮递员问题和旅行商问题都是著名图论问题。它们在现实生
活中也很重要的意义。中国邮递员问题最早是由管梅谷首先提出并进
行研究的，国际上现在统称之为中国邮递员问题。该问题具有很强的
现实意义。早期关于中国邮递员问题的讨论总是基于无向图展开的，
事实上，由于单行线或上下行路线的坡度等原因，这一问题有时必须
借助于有向图来进行研究和解决。到目前为止，对中国邮递员问题的
研究主要是从图论角度展开的，给出的多数都是各种启发式算法或递
推算法。如果中国邮递员问题中的图是欧拉图，那么欧拉回路就是最
优回路。但一般情形下中国邮递员问题的相关图不是欧拉图，最优回
路包含某些边至少两次。这时求最优回路的思想是：在图G 中添加
一些重复边使新图G*成为欧拉图，且使得所有添加的重复边的权和
最小。再由G*的欧拉回路得到G 的最优回路。本文也沿袭了以往的
方法，从欧拉图方面进行研究，试图得出当中国邮递员问题的图为欧
拉图时的最短路径，从而得出中国邮递员问题的最优解。 而旅行商问题又称旅行推销员问题，它是一种典型的组合优化问
题，已经证明了是一个NP 难题。其描述如下：给定n 个城市和两两
城市之间的距离，有一个旅行商从某一个城市出发，要求确定一条经
过各城市当且仅当一次的最短路线。旅行商问题易于陈述难于求解。
目前求解旅行商问题的方法可分为两大类：精确算法和近似算法。常
用的精确算法求解方法主要有：分枝定界法、线性规划法和动态规划
法，其计算程度十分复杂，难以解决大规模问题。近似算法又分为巡
回路径构造算法、巡回路径优化算法和智能算法，其算法简单，计算
量小。而其中，智能算法的研究最为引人注目，如模拟退火、遗传算
法、蚁群算法等，它们给旅行商问题提供了新的途径。本文就是用这
三种方法来求解旅行商问题。
首先，我们来看中国邮递员问题。
2：中国邮递员问题
2.1 定义基础
定义 经过G 的每条边的迹叫做G 的欧拉迹，封闭的欧拉迹叫做
欧拉回路或E 回路，含有欧拉回路的图叫做欧拉图。
定理 （i ）G 是欧拉图的充分必要条件是G 连通且每顶点皆偶次。
（ii ）G 是欧拉图的充分必要条件是G 连通且G = c i ，C i 是i -1d
圈，E (c i ) E (c j ) =Φ(i ≠j ) 。
（iii ）G 中有欧拉迹的充要条件是G 连通且至多有两个奇次点。
2.2 问题描述
中国邮递员问题描述如下：邮递员从邮局出发送信，要求对辖
区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择
一条最短路线？该问题用图论的语言可描述为：即在一个带权图G
中，能否找到一条回路C ，使C 包含G 的每条边最少一次且C 的长度
又最短？邮递员最优投递路线问题最早是由管梅谷首先提出并进行
研究的, 国际上现在统称之为中国邮递员问题。管梅谷给出了这一
问题的奇偶点图上作业法。Edmonds 等给出了中国邮递员问题的改
进算法, 较前者的计算更为有效。管梅谷对有关中国邮递员问题的
研究情况进行了综述。
2.3 问题分析
现假设邮递员问题的图为图G ：
(1)：若G 没有奇数度结点，则G 是欧拉图，于是欧拉回路C
是唯一的最小长度的投递路线。
（2）：若 G 不是欧拉图，则含有所有边的闭途径必须重复经过
一些边，最优回路要求重复经过的边的权之和达到最小。闭途径重复
经过一些边，实质上可看成给图 G 添加了一些重复边（其权与原边
的权相等），最终消除了奇度顶点形成一个欧拉图。因此，在这种情
况下求最优回路可分为两步进行：首先给图 G 添加一些重复边得到
欧拉图G *，使得添加边的权之和∑w (e ) 最小，（其中F=E (G *) \E (G ) ）；
ε∈F
然后用 Fleury 算法求G *的一条欧拉环游。这样便得到 G的最优回
路C 。
2.4 问题解答
1）：当图G 是欧拉图时，可用Fleury 算法求欧拉回路。
Fleury算法如下：
i) 任取ν(0) ∈V (G ) , 令P 0=ν0
ii） 设P i =ν0e 1ν1e 2... e i νi 已经行遍，按下面方法从E (G ) -{e 1, e 2,..., e i }
中选取：
a）e i +1与νi 相关联
b）除非无别的边可供行遍，否则e i +1不应该为中的
G i =G -{e 1, e 2,..., e i }桥。
iii ）当（ii ）不能在进行时，算法停止。
（Fleury 流程图见附录一）
2）：当图G 不是欧拉图时，我们所要找的最短路径即为权数最小的
路径。现给出找到权数最小的方法步骤如下：
设G 是连通加权图
i)求G 中奇次顶集合V 0={ν|ν∈V (G ), d (ν) =1(mod2)}。
ii）对中的每个顶对μ、ν，求距离d (μ, ν) 。(d (u , v ) 是u 与v 的距
离，可用Floyd 算法求得) 。
iii）构造加权完全图K |V |， V (K |V |) =V 0, K |V |中边μν之权为d (μ, ν) 。000
iv)求加权图K |V |的总权最小的完备匹配M 0
v）在G 中求M 中同一边之端点间的最短轨
vi）把G 中在（v ）求得的每条最短轨上每条边加一条等权的倍
边，使之边变成同权倍边，得欧拉图G '
vii）用FE 算法求得G ' 的一条欧拉回路W ' ，W ' 即为中国邮路
3：旅行商问题
3.1 定义基础
i) 遗传算法:是一种基于生物自然选择与遗传机理的随机搜索算
法。 ii) 蚁群算法:是一种全新的通过模拟自然界蚂蚁寻径的行为的进化
算法
iii) 模拟退火法:是一种模拟熔化状态下物体由逐渐冷却至最终达结
晶状态这一物理过程的近似全局优化算法。
3.2 问题描述
TSP问题（Traveling Salesman Problem ），即旅行商问题，
是数学领域中著名问题之一。假设有一个旅行商人要拜访N 个城
市，他必须选择所要走的路径，路径的限制是每个城市只能拜访
一次，而且最后要回到原来出发的城市。路径的选择目标是要求
得的路径路程为所有路径之中的最小值。即：给定一个完全无向带
权图G=(V,E)，其每条边(u,v)∈E 有一非负整数权值w(u,v)。要求
找出G 的一条经过每个顶点一次且仅经过一次的回路，使得该回路上
所有边的权值之和尽可能地小。从图论的角度来看，该问题实质是在
一个带权完全无向图中，找一个权值最小的哈密顿回路使得我们能够
通过这些城市至少一次。 3.3 问题分析
用图论描述旅行商问题，那就是已知赋权图G=（C,L ），找
出总权值最小的哈密顿图圈。其中C={c 1, c 2,..., c n }为顶点集，这里表
示n 个城市的集合；L={l ij |c i , c j ∈C }为各顶点相互连接组成的边集，
这里是集合C 中元素（城市）两两连接的集合。每一边都存在与
之对应的权值，构成D=（d ij ）矩阵，实际应用中的可以表示距离、
费用、时间、油量等。
对于对旅行商问题，d ij =d ji ，∀i , j =1, 2, 3,..., n 。若对于城市
C={c 1, c 2,..., c n }的一个访问顺序为T={t 1, t 2, t 3,..., t i ,..., t n }，其中
t i ∈C (i =1, 2, 3,..., n ) ，且记t n +1=t 1。则旅行商问题的数学模型为：
min l =∑d t i t i +1 i =1n
3.4 问题解答
3.4.1 遗传算法解答
一般的，遗传算法以一群随机产生的可行解开始，每个解用一串编码表示为个体，由优化目标函数确定个体的适应度对个体进行评价。通过交叉、变异等遗传算子的操作对种群进行组合产生下一代个体，逐步向优化的种群进化。
遗传算法求解旅行商问题的基本步骤如下：
1）在搜索空间中随机产生初始种群；
2）计算每个个体的目标函数，经调整得到相应的适应度值（路线长度）；
3）通过遗传算子操作产生下一代个体；
4）在下一代个体的基础上回到步骤2），纪录下每代的最好个体，直到达到最大迭代次数；
5）输出最好个体，终止整个程序。
3.4.2 蚁群算法解答
蚂蚁群找到食物时，它们总能找到一条从食物到巢穴之前的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机的挑选一条路径前行，与此同时释放出与路线长度有关的信息素。路径越长，释放的激素浓度越低。当后来的蚂蚁在次碰到这个路口时，选择激素浓度较高路径就会相对较大。这样就形
成了一个正反馈。最优路径上的激素浓度越来越大，而其他的路径上激素浓度却会随着时间的流逝而消减。这样，整个蚁群最终会找到最优路径。
蚁群算法求解旅行商问题的步骤如下：
1）令nc=0（nc 为迭代步数或搜索次数）；每条边上的τij (0) =c（常数），并且∆τij =0；放置m 个蚂蚁到n 个城市上。
2）将各个蚂蚁的初始出发点置于当前解集b μ中；对每个蚂蚁k
k （1,2，... ，m ），按概率P ij k 移至下一城市j ，将城市j 置于
b μk 中。
3）经过n 各时刻，蚂蚁k 可走完所有的城市，完成一次循环。计算每个蚂蚁走过的总路线长度L k ，更新找到的最短路径。
4）更新每条边上的信息量τij (t +n ) 。
5）对于每一条边，∆τij =0；nc=nc+1
6）若 nc
3.4.3 模拟退火算法求解
模拟退火法是了利用所求解问题的求解过程与熔化物体退火过程的相似性，采用随机模拟物体退火过程来完成问题的求解，即在控制参数（温度）的作用下对参数的值进行调整，直到找到能使能量函数达到全局极小值的参数。为了在退火过程中不丢失最低能状态，降温时初始温度足够高，下降速率要小。
模拟退火算法求解步骤如下：
运行速度最慢。其次，比较三种算法的准确度。遗传算法求得平均路线长度为18 216千米，平均18.45%；蚁群算法为15 648千米，平均1.75%；模拟退火算法为16 981千米，平均10.42%。就解得分布而言，蚁群算法的结果分布最集中，均在目前最优解所在区间[15 000,16 000]，如图1所示：其中纵坐标表示“求解结果分区间的个数”。
图1 三种算法得到的结果分布区间
最后，比较三种算法的巡回路线与目前最好结果的相似程度，如图2所示；遗传算法的巡回路线除华北和华中地区外，其他地区与目前最好结果的巡回路线大体一致；蚁群算法和模拟退火算法除西北和西南地区外，其他地区与目前最好结果的巡回回路线存在明显差异。
由以上比较分析得出：蚁群算法的最短路线长度较好，平均路线长度最好，但是其运行速度太慢，都超过了1分钟，故，蚁群算法适用于缓慢地较精确的求解场合；模拟退火法的最短长度最好，平均路