基于Hamilton回路的交通线路规划

孙波，刘士彩，王玉潇，郭帅，张家迎

（1.山东科技大学信息工程系；2. 山东科技大学机电工程系；3. 山东科技大学网络中心，泰安271000，中国）

1 引言

近年来，随着交通事业的快速发展，越来越多的人倾向于出行旅游，而大多数人在出行时会选择自驾，那么合理的线路规划就显得尤为重要。两个城市间的线路规划问题已取得重大成就，但途经多个城市时，如何选择最短线路，制定多个目标间的交通线路规划方案，节约出行时间，成为许多学者关注的重点。

最短路径问题是经典的线路规划问题，在路径规划方面有很多已经取得成效的算法，如Dijkstra算法、蚁群算法、遗传算法、Floyd算法等。其中，王佳[1]等将Dijkstra算法应用在京津冀旅游交通线路优化的实际问题上。Dijkstra算法[2]是目前多数系统解决最短路径问题的理论基础，其优点是程序设计简单、通用性强；缺点是该算法不是专门地针对特定两点。蚁群算法是一种新型算法，是观察蚁群的行为时受启发而提出的，王震霆等[3]提出蚁群算法能适应环境的变化并且还有记忆能力，但蚁群算法的正反馈过程容易陷入局部极小值，为此提出了一种改进的蚁群算法以解决扩大搜索空间和寻找最优解之间的矛盾。张雁翔等[4]在研究旅行商（Traveling Salesman Problem，TSP）问题时发现是高度并行、随机、自适应的全局寻优搜索算法，该算法具有强大的鲁棒性和全局搜索能力；缺点是局部寻优能力较差且容易出现早熟现象。代修宇等[5]在优化改良Floyd算法时发现该算法虽然能够求出任意一对顶点之间的最短路径，但是它的每一个顶点分别要与其它n-1个顶点作为边的长度进行比较，因此其时间复杂度为O（n3），并且传统Floyd算法不能直观反映出各个顶点之间最短路径序列的先后关系。

以上算法在线路优化问题上各有优势，且都可以有效的解决线路优化问题，但要解决多地间的线路优化问题，求最短Hamilton回路的改良圈算法相比于以上算法要简便很多，基于Hamilton回路的改良圈算法具有简单易懂、效率高、且适用范围广等优点。现今，汽车出行成为主流的出行方式，如果出行的起点和终点重合，利用Hamilton回路的自身特点可以很好地求解此类问题。本文通过改良圈算法求解权值最短Hamilton回路，制定了多目标间的线路规划方案，大大缩短了人们的出行时间，为人们的出行提供了便利。

2 算法介绍

哈密顿图（Hamilton path）是一个含有哈密顿回路的无向图，由指定的起点到达指定的终点，途中经过所有其他节点且只经过一次，闭合的哈密顿路径称作哈密顿回路，含有图中所有顶点的路径称作哈密顿路径[6]。哈密顿回路图，与欧拉回路图互相呼应，欧拉回路要求通过每条边有且仅有一次，而哈密顿回路图则要求通过每个顶点有且仅有一次。哈密顿的实现需要满足以下两个条件：

（1）哈密顿图是封闭的环；

（2）哈密顿图是一个连通图，且图中任意两点可达经过图（有向图或无向图）中所有顶点有且仅有一次。

Hamilton改良圈算法步骤如下：

（1）从任何节点开始，将其加入到解的集合中，进行初始化，构造图G（s，e），s表示一个节点，e表示一条边，下面图1-图3反映了G（s，e）的变化。在图G（s，e）中找到一个起点s1，从与该结点连接的边中选择最短的那条边的结点加入到解的集合中，这就是所谓的最近邻居，即寻找距离s1最近的点s2，若同时有多条边距离相等，任选一条即可，且保证s2与s1之间的权重值最小，构成线路s1s2，如图1所示。

图1 两点间线路规划

（2）从上述运算所选的最近邻居出发，重复上述过程，但应避免已选择过的结点，以免提前形成回路，即再以s2为起点，寻找与s2权重距离最小的点 s3，构成s1s2s3，如图2所示。

图2 三点间线路规划

（3）以此类推，当所有结点都加到解的集合中后，将最后加入的结点与起始结点连接，就可以得到哈密顿回路了，若已经选出路线s1s2…si，再在图G中找到一个与 si（i=1，2，…，n）最近的点 si+1，就得到了 s1s2…sisi+1，如图3所示。

图3 多点间线路规划

（4）当i+1＜n-1时，用i代替i+1重复3），否则回路 A= s1s2…sns1。

（5）当所有结点都加到解的集合中后，将最后加入的结点与起始结点连接，就可以得到哈密顿回路了。

为了得到一个更好的算法，本文应用改良算法即可得到优化后的Hamilton A：

（6）对于 1≤ i＜i+1＜j≤ n，构建新的 Hamilton 圈Aij=s1…sj-1sj-2…si+1sj+1…sns1它是由 A 中将 si和 sj之间的边逆序后得到的。

（7）若 w（sisj）+w（si+1s(j+1） ＜w（sjsj+1）+w（sjsj+1），则该圈替换有效，继续执行以上步骤，直至无法优化。

3 模型建立

在途经城市个数确定的情况下，为了解决多目标的线路规划问题，最小化人们的出行距离，节省出行时间及出行费用，根据城市与城市间距离，构建基于Hamilton算法的线路规划模型，完成多个城市间的线路规划[7]。多目标的线路规划问题首先要确定其对应的目标函数，然后确定满足该函数的约束条件，构建最优Hamilton圈，完成模型的建立。

基于改良圈算法的推导，需要确定其相应的参数。令x_ij表示从第i个城市到第j个城市所要行走的距离，r_ij是判断出行者是否从第i个城市到第j个城市的0-1型变量，n表示途径的城市个数，令目标函数D表示多目标间的最短出行距离。

该目标函数需要满足以下约束条件：

（1）城市个数约束。整个出行线路是封闭图形，即出行者最终要重新回到起点，当i,j的值从1取到n时，rij的和表示出行者要途经的城市总数，城市个数约束为：

（2）0-1变量的约束。Hamilton算法最终线路为一个回路，每个节点代表一个城市，每一个点只可以有一条边与之相连，若有一条边输入则必须有一条边输出，得到以下约束：

当i=1时，表示起点，此时∑i=1rij=1；

当j=1时，表示回到起点，此时∑j=1rij=1。

综上可知其约束条件为：

根据Hamilton改良圈算法和已构建的目标函数，求取各目标城市出行最佳线路，即要在图 中求解出一个权值最小的Hamilton圈，即最优圈。求解最优圈的思想为：先求出一个Hamilton圈A，然后修改A得到具有较小权的另一个Hamilton圈，反复修改得到最优圈。按照以上思路，先用最邻近算法求解近似最优Hamilton圈，步骤如下：

（1）选取任意一个顶点s0作为起点，找一条与s0关联且权最小的边e1， e1的另一个端点记作 v1，得到一条路s0s1；

组织是人类走向文明的产物。作为一个独立的概念，组织传播最早见于西蒙(H.A.Siom)在1945年发表的关于管理行为的文章中。由于受到企业管理理论的影响，组织传播研究早期主要集中于组织内部的管理传播技巧方面。20世纪70～80年代后，在社会学、文化学等学科的介入下，组织传播研究呈现多元化的趋势。现在，西方的组织传播研究可分为功能主义、解释主义和批判学派三大取向，并以功能主义为主导[12]。韦伯将组织定义为一个为完成协作任务而进行的具有一定目的性人际活动的体系。在一个组织中，交流能否被接受取决于上层领导的权力合法化的程度。

（2）假设已选出路线s1s2…si，在现有路径中找到一个与si最邻近的顶点si+1，得到s0s1s2…sisi+1；

（3）若i+1＜n-1 ，则用i代替i+1返回（2），否则，记为Hamilton圈A=s0s1…sns0；，停止。

于是得到了一个近似最优圈，但最邻近算法求得的Hamilton圈一般不是最优解，在此基础上，继续通过改良圈算法，就可以获得更短的Hamilton圈。将A=s1s2…sns1作为改良圈算法的初始圈，按照以下方法，最终可以得到一个最优圈A1。

（4） 所 有 满 足 1＜i+1＜n 的 i，j ， 可 构 造 新 的Hamilton 圈 ： Aij=s1s2…sisjsj-1sj-2…si+1sj+1sj+2…sns1，它是由圈A删去边sisi+1和sjsi+1，添加边vivi和vi+1vj+1后得到的，若 w（sisj）+w（si+1sj+1）＜w（sjsj+1）+w（sjsj+1），则以Aij代替圈A，Aij称为A的改良圈。

（5）返回（4），直至无法改进，得到最优圈A1，停止。

建立以上模型后，得到了一个最优的Hamilton圈，下面通过实例验证此算法的有效性。

4 模型仿真

以某游客的山东省内自驾游为例，假设游客需途经滨州、济南、潍坊、临沂、聊城、青岛六座城市作为线路规划点，分别以1、2、3、4、5、6代表这六座城市，为缩短路程，应用构建的模型，求解最优Hamilton，规划了出行线路，验证算法的可行性。城市路线分布及其城市间距离如图4所示。

图4 最短线路距离

根据图得到各城市间的距离数据如下

（1，2）=163.5；（1，3）=167.5；（1，4）=354.2；（1，5）=241；（1，6）=315.4；

（2，3）=208.2；（2，4）=246.9；（2，5）=126.6；（2，6）=351.2；

（3，4）=249；（3，5）=312.1；（3，6）=175.4；

（4，5）=353；（4，6）=276.5；

（5，6）=467.7；

由此，得到距离矩阵Q：

根据模型得到目标函数值：

为了验证算法的有效性，将距离矩阵代入到程序中，利用matlab软件实现算法。主要算法如下：

function main

clc，clear

global a

a=zeros（6）；

a（1，2）=163.5；a（1，3）=167.5；a（1，4）=354.2；a（1，5）=241；a（1，6）=315.4；

a（2，3）=208.2；a（2，4）=246.9；a（2，5）=126.6；a（2，6）=351.2；

a（3，4）=249；a（3，5）=312.1；a（3，6）=175.4；

a（4，5）=353；a（4，6）=276.5；

a（5，6）=467.7；

a=a+a'；L=size（a，1）；

c1=[1 2:5 6]；

[circle，long]=modifycircle（c1，L）；

c2=[1 6 2:5]；

[circle2，long2]=modifycircle（c2，L）；

if long2＜long

long=long2；

circle=circle2；

end

circle，long

matlab程序运行结果如下：

circle =

1 3 6 4 2 5

long =

1.2339 e+03

所得结果显示以滨州为起点遍历其他五座城市并回到起点的最短路径为：1→3→6→4→2→5→1，即：滨州→潍坊→青岛→临沂→济南→聊城，得到的六节点有向图如图5。

图5 六节点有向图

根据有向图得到邻接矩阵Z如下，其中1表示两城市间存在连线，该线路在Hamilton回路中，0表示两城市间无连线。

则此Hamilton回路总长为1233.9km，与目标函数所求数据相同，验证了该算法具有好的有效性。城市间的线路即是通过导航软件所得出的两城市间的最短线路，简化后的线路规划图如图6。

图6 线路规划图

5 结语

本文通过基于Hamilton回路的改良圈算法来解决现实中的交通线路规划问题，求取步骤为：首先通过导航类软件获得任意两地点间的最短线路及距离，然后构建一个赋权的完全图G（s，e），边上的权就是两点间最短路线的距离，利用MATLAB求取最短路线。利用改良算法求取最优哈密顿回路，是解决线路规划的主流算法，算法简单易懂，且适用范围广，利于推广；利用Matlab软件进行了实例验证，结果表明了算法具有可行性与有效性。本文以山东的6个城市作为例子，进而可通过该例推广到全国各地的出行线路优化当中，优化出行线路。

基于本文的研究，其他研究者可以将出行的时间和金钱花费赋予一定的权重，代替距离来解决出行的最小花费问题，求取利益最大化的线路。此外，影响游客出行的因素包括路程、交通费用和时间等，利用改良算法可求出出行时间最短或花费最少的线路，但道路的路况、交通拥堵状况等问题都对时间和费用有较大影响，在后期的研究中，将进一步综合研究各种因素，考虑各因素影响的权重，根据实际路况信息，设计并建立更合理的模型。