基于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-),女,汉族,浙江温州人,本科在读,研究方向:计算机科学与技术。
转载注明来源:https://www.xzbu.com/1/view-14771215.htm