摘 要：本文针对游遍我国201个5A级景区的旅游路线规划问题进行了深入探讨，基于实际情况考虑，假设旅游爱好者每年有不超过30天的外出旅游时间，每年外出旅游的次数不超过4次，每次旅游的时间不超过15天；而且考虑到安全因素，行车时间限定于每天7：00至19：00之间，每天开车时间不超过8小时，景区开放时间统一为8：00至18：00。在无费用限制情况下，以时间最短为目标建立了优化模型。采用以区域为单位，对31个省市自治区用SPSS进行合理的聚类分析，以按省份分类为主结合距离数据，并用改进的Hamilton圈算法，采用LINGO编程实现，得到了西安的自驾游爱好者游遍全国201个5A级景区至少需要12.5年。

关键词：旅游路线规划；非线性规划；聚类分析；哈密顿圈

1 问题的提出

旅游活动正在成为全球经济发展的重要动力之一，它加速国际资金流转和信息、技术管理的传播，创造高效率消费行为模式、需求和价值等。随着我国国民经济的快速发展，人们生活水平得到很大提升，越来越多的人积极参与有益于身心健康的旅游活动。

一位自驾游爱好者拟按国家旅游局公布的201个5A级景区名单制定旅游计划。该旅游爱好者每年有不超过30天的外出旅游时间，每年外出旅游的次数不超过4次，每次旅游的时间不超过15天；基于个人旅游偏好确定了在每个5A级景区最少的游览时间。基于安全考虑，行车时间限定于每天7：00至19：00之间，每天开车时间不超过8小时；在每天的行程安排上，若安排全天游览则开车时间控制在3小时内，安排半天景区游览，开车时间控制在5小时内；在高速公路上的行车平均速度为90公里/小时，在普通公路上的行车平均速度为40公里/小时。该旅游爱好者计划在每一个省会城市至少停留24小时，以安排专门时间去游览城市特色建筑和体验当地风土人情。景区开放时间统一为8：00至18：00。请考虑下面问题：在行车线路的设计上采用高速优先的策略，即先通过高速公路到达与景区邻近的城市，再自驾到景区。从网上可以查到各景区到相邻城市的道路和行车时间参考信息，国家高速公路相关信息，以及若干省会城市之间高速公路路网相关信息。请设计合适的方法，建立数学模型，以该旅游爱好者的常住地在西安市为例，规划设计旅游线路，试确定游遍201个5A级景区至少需要几年？

2 问题的分析

根据问题描述述，可以知道这是一个旅游路线优化问题，旅游路线规划从区域范围可以分为三个部分：城市之间的旅游路线规划、城市内各景区的旅游路线规划、景区内各景点的旅游路线规划。城市之间的旅游路线规划和景区内各景点的旅游路线规划都是从一点出发，经过其他点，且只经过一次，最后回到出发点的路线规划，即图论中的旅行商问题（又称TSP问题）。如果将此算法直接用到旅游路线的选择上，则可以简单地表现为考虑两景区的路程，但对旅游者而言，如果仅仅考虑景区间的相互距离肯定是不够的。给定旅游地图，游客在旅行过程中总想从出发地到目的地的距离最短， 以节省费用和时间。本文针对旅游者主要关心的问题——时间、费用和体验，并且考虑在各个不同景区停留的时间，对已有算法加以改进，以此来满足该算法在旅游景区路线选择上的需要，，最终得到适合的最优旅游线路。国家旅游线路空间跨度大，其发展必然要以区域为基础，依托区域现状进行开发和设计，最终实现以线路的发展带动整个区域旅游业发展。基于此，先运用聚类分析的方法分成一定类别数。然后在类中找出最优路线。基于此，我们要采用以区域为单位，对31个省市自治区用SPSS根据距离和坐标两者相结合的指标进行合理的聚类分析，并用改进的Hamilton圈算法，在只考虑时间、但费用不限的前提下，采用LINGO编程实现，得到西安的自驾游爱好者游遍全国201个5A级景区至少需要的年数。

3 问题的求解

聚类分析是数据挖掘的一项重要的方法。聚类问题实际上是将一组数据分成若干个组，每个组里的对象具有很大的相似性，不同的组之间存在尽量大的差异性。K-均值聚类分析法又称快速样本聚类法，是非系统聚类中常用的聚类法。 具体做法如下：

a.按照指定的分类数目n，按某种方法选择观测量，设为{Z1，Z2，…}，作为初始聚心 ；

b.计算每个观测量的欧式距离，即。按接近原则将将每个观测量选入一个类中，然后计算个类的中心位置，即均值，作为新的聚心；

c.使用计算出来的新聚心重新进行分类，分类完毕后继续计算各类的中心位置，作为新的聚心，如此反复操作，直到两次迭代计算的聚心之间距离的最大改变量小于初始聚心间最小距离的倍数时，或者达到迭代次数的上限，迭代停止。

哈密顿圈：对于旅游路线的规划有如下三点基本要求：

a.在尽可能短的时间内给出旅游路线规划。

b.旅游路线要经过所有景区，且只经过一次，最后回到起始地。

c.景区与景区之间的距离要尽可能的短。

要求算法的反应时间尽可能快，同时规划出的路线质量不但要短，而且要人性化。这是一个旅行商问题，重要在找出最小权Hamilton圈，称这种圈为最优圈。设，则对于所有适合1