邮递员问题与旅行商问题讨论

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