基于TSP旅行商模型的杭州旅游线路设计

吴莉莉 朱雪 徐俊康

摘 要：以美丽的西湖山水著称于世的杭州的旅客逐年增长，由于到达杭州的外来旅客一般停留时间短暂。因此，如何在较短的时间内，尽可能地欣赏更多的美景将成为旅客首要考虑的问题。对此，本文通过聚类分析，建立基于TSP旅行商模型的多目标优化模型，设计出在保证景点的价值最大的同时满足旅游总费用最低的路线。

关键词：熵权法；聚类分析；TSP旅行商模型；多目标

中图分类号：TP301.6 文献标识码：A 文章编号：2096-4706（2019）04-0094-03

Hangzhou Tourism Route Design Based on TSP Traveler Model

WU Lili，ZHU Xue，XU Junkang

（Zhejiang Chinese Medical University，Hangzhou 310053，China）

Abstract：Visitors in Hangzhou known for their beautiful West Lake landscape are growing year by year as foreign visitors to Hangzhou generally have a short stay. Therefore how to appreciate more beautiful scenery in a shorter period of time will become a top priority for passengers. In this regard through cluster analysis this paper establishes a multi-objective optimization model based on TSP traveler model and designs a route that Satisfies the lowest total tourism cost while ensuring the maximum value of the attraction.

Keywords：entropy method；cluster analysis；TSP traveler model；multi-objective

1 问题的提出

1.1 背景

随着经济的发展，居民的生活水平不断地提高，在满足物质基础的同时，人们有了更高的追求，而在精神的追求中，旅游业就是人们的首选。其中，以其美丽的西湖山水著称于世的杭州，2016年接待中外游客达到1.4亿人次，2017年的G20更将这个美丽的城市推向国际大舞台。作为八大古都之一的杭州拥有丰富的旅游资源：一个国家级度假区、两处国家级风景名胜、两个国家级自然保护区、五个国家级森林公园，而且杭州市政府也不断出台相关政策，加大对杭州市旅游产业的扶持力度，使得杭州迎来更多的游客。而在有限的时间内，观赏到景点的数量寥寥无几。

1.2 问题

为提高旅游的价值，本文借助计算机TSP旅行商模型，通过聚类分析，设计出在保证景点的价值最大的同时满足旅游总费用最低的路线。对此，本文以设计杭州二日游为例，进行旅游价值最大化。

2 算法

2.1 获取景点价值

2.1.1 选取景点与指标

首先搜索杭州市内知名景点，确定20个主要景点；然后查阅文献并结合实际，确定影响景点旅游价值主要指标，结果如表1所示。

2.1.2 基于熵权法对指标进行赋权

将景点作为行，评价指标作为列构建矩阵，对数据标准化处理，通过计算比重、熵值，从而得到指标权重矩阵ωj为：ωj=[0.137 0.05 0.079 0.042 0.047 0.043 0.165 0.106 0.088 0.039 0.037 0.158]。

2.1.3 计算景点旅游价值

通过查阅文献得到不同景点在各指标下的原始数据，将实际数据转化为指标得分，通过指标权重矩阵，计算出各景点旅游价值，并排序，结果如表2所示。

2.1.4 计算任意两景点间距离

在Google地图上获取20个景点的经纬度，再将经纬度转化为坐标，则景点i和景点j间的距离dij为：

2.2 TSP模型

2.2.1 建立TSP模型

Step1 建立目标函数。设第i个景点的旅游价值为yi，假设，旅客在路上的费用与距离成正比，设比例系数为k，从景点i出发到景点j最短距离和为D，即路上费用为kD。旅客观赏所有景点所需总费用为路上的费用与景点门票pi的费用之和，则可得到旅游总价值Y和费用P：

其中，xij表示景点i是否去往景点j。

Step2 确定约束条件。时间最多为48小时，每个景点最多去一次，出发点和终点需保持一致，即：

Step3 旅游路线的性价比。在此，我们用性价比来衡量路线的优劣，定义总的旅游景点的价值與总费用的比值为性价比W，即：

对此，假设两天内最多去a个旅游景点，本文采用TSP旅行商模型，以旅游价值和消费总费用为约束条件，将多目标规划变为单目标规划，建立旅游景点总价值最高、消费费用最小、观赏所有景点路径和最小目标函数：

2.2.2 确定最终路线

由于有旅游价值最大和消费总费用最小两个目标，为了求解方便，我们将性价比作为目标函数，将旅游价值和消费总费用作为约束条件，并将计划游览的景点数设置为定值，将多目标规划变为单目标规划。然后不断改变设定的景点数，就不同景点数情况下的性价比进行对比求出最优值，即：

由于西湖旅游价值最高，并且杭州以西湖闻名于世，故将起点定为西湖。通过遍历求解确定最佳路线，得到不同路线方案，如表3所示。

两日游有效游玩时间应在16小时内，由此得出杭州两日游最佳路线为：西湖→西湖博物馆→河坊街→雷峰塔→虎跑公园→宋城→千岛湖→灵隐寺，总价格为436元，性价比为2.959。

3 结 论

本文在TSP旅行商模型的基础上，通过聚类分析，设计出了杭州最佳二日游路线，为众多来到杭州的旅客提供了一个最大程度欣赏杭州美景的方案，在保证景点的价值最大的同时满足旅游总费用最低的目标，但本文模型并未考虑到旅客的喜好，旅游公司在未来还应增加旅客喜好的目标，进行更多目标化的模型构建。

参考文献：

[1] 刘啸.旅游资源的资源、环境、区位、口碑评价模式——以北京市旅游资源为例 [J].中国集体经济，2008（4）：41-42.

[2] 谌静.红色旅游目的地竞争力评价指标体系构建 [J].信阳农业高等专科学校学报，2009，19（4）：68-70.

作者简介：吴莉莉（1998-），女，汉族，浙江温州人，本科在读，研究方向：计算机科学与技术。