Hamilton模型在智慧文旅设计中的应用研究

薛 慧，许苗峰（.海联金汇（北京）金融科技有限公司，北京 00048；.中国联通智能城市研究院，北京 00048）

1 概述

随着我国国民经济的快速发展，人们生活水平得到很大提升，旅行需求也不断增加，投入到旅行方面的花费也越来越多。国家旅游局统计结果表明：2014年中国旅游总收入33 800亿元，同比增长14.7%，2015年上半年中国旅游业收入或达17 000万亿元，同比增长10.8%。面对着具有广阔前景的旅游业市场空间，旅行商推出了大量丰富多彩的旅行线路来满足旅客的需要。

我国幅员辽阔，交通路线复杂，要想在有限的假期内游览更多的地方，减少不必要的交通花费，合理安排旅行活动，就必须在出行时做好旅行线路的规划工作。针对旅行线路方面的研究，研究者们设计了Stewart and Vogt多目的地的旅行模式［1］、Lundgren旅行模式［2］、Campbell模式［3］、最短路问题［4］、TSP问题［5］、最大流问题的旅游线路优化设计模型［6］等多种旅行模式。

在现实生活中，要经常考虑旅行路线的优化问题，即旅客确定从某点出发，要经过每个节点一次，最后返回到出发地的最佳环游路径，并且行程是最短的，这个问题也属于旅行商问题（TSP），即赋权Hamilton回路最小化问题［7］。其中一种著名的解法，就是求一条总权最小的Hamilton圈［8］。然而到目前为止，对于这个问题仍没有一个有效的算法。本文对传统的Hamilton算法进行优化，基于该算法建立了旅行路线的优化程序。以云南省的5A级景点为实验对象，利用该程序优化了从首府城市昆明出发到达各景点的旅游线路，展现了改进后的Hamilton算法在线路优化方面的可行性和高效性。

根据全国高速公路的实际状况，本文利用ArcGIS地理软件对高速公路、二级公路的数据进行了处理，并对5A级景区进行了准确定位，发现我国所有的5A级景点，除了极少数景点附近只有1条高速公路，其余的景点均有2条或者2条以上高速公路。其次，5A级景点大部分集中于东南沿海以及中部地区，这些地方的交通较为发达，可以满足景点之间的距离近似于直线距离。

2 Hamilton算法对旅行线路的优化求解

假设一位旅行者想要一次性游览完中国云南省所有的5A级景点，本文为该旅行者设计一条最优的旅行线路，因为旅行花费主要由景点之间的远近决定，且不同的人对交通的选择也不相同，但这里的最优旅行路线简化为求连接云南省所有5A级景点的总距离，要求规划出最短的旅行线路。

2.1 Hamilton算法思想

定义一个图G（V，E），旅行者游览的云南省6个5A级景点抽象为图G中的6个顶点，构成5A级景点集V，以两两景点之间的实际距离为旅行代价。根据Hamilton回路的定义，目标线路经过且不重复经过每一个顶点，即每一个顶点只有一条线路进入、一条线路出去，且除起点与终点外，各边不构成圈。于是寻求环游云南最短旅行路线的问题转化成了求总距离最短的Hamilton圈。下面给出求近似最优Hamilton圈的最邻近算法的基本思想［5］：

步骤1：任意一个点V0作为起点，找一条与V0关联且权最小的边C1，C1的另一个端点记为V1，得到一条路V0V1。

步骤2：设已选出路V0V1…Vi，在V（G）-{V0V1…VpV0}中取一个与Vi最邻近的相邻顶点Vi+1得到路V0V1…Vi+1。

步骤3：若i+1＜n-1，则用i代替i+1返回步骤2；否则，记V0V1…VpV0，停止。

得到一条近似最优的Hamilton回路。用最邻近算法求得的Hamilton算法一般不是最优解。但通过改良，可以获得更短的Hamilton回路。设C=V1V2…VnV1是图G的一个Hamilton圈。对圈C中所满足1＜i+1＜j＜V的i，j，按照以下算法可以得到一条新的Hamilton圈C1。

步骤1：在C上检查是否有i≠j，使得ViVj∈E(G)且w(ViVj)+w(Vi+1Vj+1)＜w(ViVi+1)+w(VjVj+1)，则构成新圈C1=V1V2…ViVjVj-1…Vi+1Vj-1…VnV1。

步骤2：用C1代替C转到步骤1，直到终止。

这种算法称之为改良圈算法，它是一种近似算法，给出的结果不一定是最优的，却是比较好的结果。

2.2 Hamilton圈的函数模型

由于在寻求环游云南省最短旅行线路这个问题中，图G的顶点个数不算大，于是根据Hamilton圈的定义建立了一个0-1整数规划优化模型，公式（1）为目标函数，公式（2）～（5）为约束条件。

设dij是景点i和j之间的直线距离，首先对两两景点间是否存在连线关系引入0-1变量Xij：

如果景点i和景点j边连接，即表示旅行者走过景点i后，下一个目标为景点j。目标函数是求最小距离的Hamilton圈，即：

该目标函数还需满足3个约束条件：

每个顶点只能有1条边进去，即：

每个顶点只能有1条边出去，即：

除起点与终点外，各边够不成圈。这里引入水平变量l(i)，表达到达不同景点的顺序，即景点i是第l(i)个目的地。于是有，起点i=1的水平变量l(i)=0，且0≤l(i)≤n-1，其中n是景点个数，此处n=6。若景点i与景点j边连线，则有l(j)=l(i)+1。所以为了保证起点与终点外，各边不构成圈，需要满足：

2.3 Hamilton圈的计算机求解算法

Hamilton算法能实现遍历所有景点的最短路径，且不走重复路。本设计基于Hamilton算法的改良圈建立了省内任意景点间的路线优化程序，该程序还可用于旅游线路的优化、环路的建设等。根据Hamilton回路的思想设计了Hamilton改良圈算法的Matlab编程，其具体方案如下：

在操作过程中，需要给出每个景点的经纬度坐标以及对每个景点进行编号，因为Matlab程序不能对汉字进行识别。

3 模型应用

选取我国云南省6个5A级景点，将这些景点依此编号1～6。因为5A级景点交通设施完善，或具有一级公路或高等级航道，所以景点间穿行方便，故可用直线距离代替各个景点之间的实际距离，各个景点所在的城市的经纬度易得，具体情况如表1所示。

表1 云南省各5A级景点的经纬度（单位：°）

应用上述的Matlab程序计算各地景点的直线距离，求解的程序结果如下：

最优路线为：ans=1 6 2 3 4 5 1。

由输出结果可知，从省会昆明环游云南省6个5A级景点的线路，优化后的顺序为昆明石林风景区→中科院西双版纳热带植物园→迪庆藏族自治州香格里拉普达措国家公园→丽江玉龙雪山景区→丽江古城景区→大理崇圣寺三塔文化旅游区→昆明石林风景区。为了形成效果鲜明的对比，将该路线未进行算法前与进行算法后的路线做成了图，具体情况分别如图1、图2所示。

图1 未进行Hamilton算法的初始圈

图2 进行Hamilton算法后的改良圈

从图1和图2可以看出，图1具有交叉点，说明以常规的环游方法，有很大的可能会走重复路，这无疑增加了旅行的花费与时间，未经过算法优化的旅行线路实际旅行起来会比较盲目，保证不了环游的路线最短；而图2是通过了Hamilton算法优化后的环游路线，没有了交叉点，优化了环游的线路，整个线路走法也更加地清晰明了。同时可以看出，本文对Hamilton算法的程序进行了调整之后，使得使用程序者无需调整，只需一次分配便可获最小的Hamilton圈。

4 结论

对于求解最优Hamilton圈这样的旅行商问题，要同时满足算法的精确度、稳定性、运行速度这3个条件是十分困难的。因为算法存在着这些缺点，所以在算法设计方面，本文通过调整规则来改善算法，让算法在稳定性和准确性中作出尽可能的最优；同时，在程序上加入了迭代的部分，自动提高了算法的运行速度。以往研究中，基于Hamilton算法的线路优化，至少需要做3次调整，才能得到最优通路。本文对Hamilton算法的程序进行了调整，使得使用程序者无需调整，只需一次分配便可获最小的Hamilton圈，从优化云南省5A级景点的旅行线路能够充分看出程序的便捷性。因此，改良的Hamilton算法是求解最优哈密尔顿圈的有效新方法，能够对旅客实际旅行能够提供实用性帮助。