基于贪婪算法的旅游路线优化问题

滕 泉，沈景凤，徐 斌，王玮玮

(1.上海理工大学 机械工程学院，上海200082;2上海材料研究所 减振技术事业部，上海 200082；3.大连海事大学 交通运输管理学院，辽宁 大连 116026)

基于贪婪算法的旅游路线优化问题

滕 泉1，沈景凤1，徐 斌2，王玮玮3

(1.上海理工大学 机械工程学院，上海200082;2上海材料研究所 减振技术事业部，上海 200082；3.大连海事大学 交通运输管理学院，辽宁 大连 116026)

针对目前国内旅游线路的设计多偏向于从景区特色出发，而较少从旅行时间和路径入手的问题，利用贪婪算法设计数学模型。在旅行者不多于15天的旅行约束条件下，对国内201个5A风景区进行聚类分块，将201个景区简化为31个省市。算得从西安市出发到各省市的旅行时间并得到21条符合要求的旅行路线。将相关结果以更直观的图像形式展现，为旅行路线的设计研究提供了参考。

旅游线路；最优化问题；聚类贪婪算法；约束条件

一个旅游区域内各个景点分布在不同的位置，对这些景点浏览的先后顺序则有多种方式，可以组合成不同的旅游线路[1-2]。针对目前旅游业的路线设计成果不完善的情况，为了让游客花费较少的时间而尽可能多地浏览景点，设计出最优的旅游线路是必要的[3-4]。本文以西安市为例，运用贪婪算法，对旅游路线进行优化，实验对象为我国部分省市(港澳台地区不含5A风景区)200多个5A级风景区的旅游线路优化，得到从西安出发到各地的最佳旅游线路，并得到线路图。

1 线路背景

自2007年3月7日至2015年7月13日，全国旅游景区质量等级评定委员会分29批共批准了201家景区为国家5A级旅游景区。依据常规作息时间，设定一位自驾游爱好者拟按此景区名单制定旅游计划。因时间限制该旅游爱好者每次旅游的时间不超过15天，确定出符合该游客的旅行线路，给出每一次旅游的具体行程。对游客的行车速度做如下参考：在高速公路上的行车平均速度为90 km/h，在普通公路上的行车平均速度为40 km/h。

2 问题分析

此问题中，旅行计划需设计从西安出发到各省201个旅游景点的旅行计划，因数据量太大，先对景点进行聚类分块。根据201个5A级景点分属于31个省份(港澳台地区不含有5A景区)，以各省会为中心，将201个景点分成31个省区组[5]。将原201个点简化成31个，然后制定各省的旅行方案。旅行方案：先从西安出发到达各个省区的省会，再从此省省会出发遍历该省所有景点，之后再去下一个省。

此问题的约束条件：每次出行不超过15天，可对问题做简化处理，以15天为界限，设计n条旅行时长<15天旅行路线，再将此n条旅行线路组合使得所用旅行时间最短。

一般各个省的旅行总时间不会超过15天，分别计算各个省最短旅行时间。此步理解为TSP(旅行商问题)中确定最短时间、最优路径、最短路径的问题，可查阅省内各景点的两两相对距离，建立矩阵，利用Lingo软件编辑算法，计算出每个省区的旅行时间[6-8]。

3 贪婪算法对旅游路线优化设计

在完成各省的时间计算后，利用贪婪算法，设计从西安出发到各省的旅行路线[9-10]。贪心策略为：(1)从西安出发，首先选择其他30个省省会之一C0作为下一游览省；(2)计算西安到该省会时间di0、在该省游玩的时间ti、以及该省返回西安的时间D，若上述时间之和<15天，再选择离C0市最近的省会城市作为第二游览省，依次选择第三游览省、第i游览省，直到旅行时长大于15天，输出第一条旅行线路；(3)将选过的省去除，再执行第2步，直到游遍31个省区，依次输出第2条、第3条、…、第n条线路；(4)计算以C0市作为第一游览城市该路线需要的总时间；(5)将其他29个省的省会C1、C2、…、Ci作为第一游览城市，计算路线总时间；(6)比较得出30种方法的最优路线计划。

3.1 名词和符号说明

在运用贪婪算法进行旅游线路设计时的符号如表1所示。

表1 贪婪算法的符号说明

3.2 模型的基本假设

(1)不考虑高铁和航班的推迟或取消，忽略天气影响或不可预测的事故； (2)旅馆处于非满客状态，即总可预订到房间；(3)在时间的认识上，将当天早8点到次日的早8点定义为一天； (4)不考虑实际生活中出现的堵车等车等不可知现象。

4 模型建立及求解

根据此问题约束条件：每次出行不超过15天。做简化处理，以15天为界，设计n条旅行时长<15天旅行路线，再将此n条旅行线路组合得最短时间路线。

旅行计划需要设计从西安到201个旅游景点的旅行计划，因数据量太大，先对景点进行聚类分块，根据201个5A级景点分属于31个省份，以各省省会为中心，将201个景点分成31个省区组。旅行方案为先从西安出发到达某省区的省会，再从该省省会出发遍历该省所有景点，再去下一个省游玩。若到达某省后返回西安时间达到15天，则旅行终止，该行程为符合要求的一条线路[11-12]。将游玩过的城市去掉，执行上述循环，直到游玩遍所有省区为止。

4.1 数据处理与聚类分块

根据201个5A级景点分属于31个省份，以各省省会为中心，将201个景点分成31个省区组(注：若A省内存在离B省城市更近的景点，则此景点划入B省)。通过百度地图，查找某省内景区间各景点所在城市两两之间的距离dij，列出矩阵，以河南省为例，如表2所示。

表2 河南省内主要旅游城市相对距离(数据来源：百度地图2015-00-20)

4. 2 各省省内旅行最短时间的计算

一般各个省的旅行总时间不会超过15天，先分别计算各个省最短旅行时间。从某省的省会城市出发，依次走完这个省的所有景区，然后回到省会城市，形成一闭合环路。欲求走完此环路所用时间最短，即求此环路的路程最短。此问题即TSP中确定最短时间、最优路径、最短路径的问题[13]。数学模型如下：

图1 河南省旅行示意图

查阅相关数据，以此方法，分别求得31个省内路线，并计算游完每个省所用的时间T(T与最后规划时间前后误差≤0.5天)，如表3所示。

表3 各省份区遍历所有景点所需要的时间

5 启发式算法制定全国最短路线

在完成各省旅行时间计算之后，将全国201个5A级景区简化为31个点，从西安出发向外辐射设计线路。此步利用贪婪算法设计从西安出发到各省的旅行路线[14]。贪心策略为：

(1)从西安出发，首先选择其他30个省省会之一C1作为下一游览省；

(2)计算西安到该省会时间di0、在该省游玩的时间ti、以及该省返回西安的时间D，若上述时间之和<15天，再选择离C1市最近的省会城市作为第二游览省，依次选择第三游览省、第i游览省，直到旅行时长>15天，输出第一条旅行线路；

(3)将选过的省去除，再执行第2步，直到游遍31个省区，依次输出第2条、第3条、…、第n条线路；

(4)计算将C1市作为第一游览城市该路线需要的总时间；

(5)将其他29个省C2、C3、…、Ci作为第一游览城市，计算路线总时间。

比较得出30种方法的最优路线计划。寻找最优路径的算法为：

(1)统计建立全国各个城市两两之间相互时间里程表，形成一个C31×C31的矩阵，建立数据库；

(2)以西安为起点，从其他30个省会城市里任选一个城市作为C0，在C0省游玩的时间为t0，求C0距西安的车程时间为D，消耗时间为T=D+t0；

(3)以第一游览城市C0为起点，筛选距离西安车程最近的省会城市Ci，记Ci与C0的车程时间为di0，在Ci省游玩的时间为ti，总消耗时间为T=D+t0+di0+ti；

(4)以Ci省的省会城市为起点，重复第一步的过程，筛选距离Ci车程最近的省会城市Cj，记Cj与Ci的距离车程为dji，在Cj省游玩的时间为tj，总游玩时间T=D+t0+di0+ti+dji+tj；

(5)如果T<=15，执行上述循环结构，如果T>15，算法终止，记录算法终止的前n次计算经过的城市Ci，Cj……Cn，打印“西安—Ci—Cj……Cn”作为第一条旅游路线；

(6)将Ci，Cj，…，Cn从数据库中剔除，形成一个C31-n×C31-n的矩阵，形成新的数据库；

(7)在C31-n×C31-n的矩阵的数据库中，继续执行上述(1)～(5)步，继续打印，形成第2,3,4,…,i条旅游路线；

(8)当数据库中全部城市被读取，形成一个C0×C0的矩阵时，算法终止，统计记录下全部1，2，3，…，n条线路。计算这些线路总的要花的时间；

(9)依次将其他30个城市作为以第一游览城市C0执行上述过程，求出30条方案，比较他们消耗的时间，选出最优解。

利用计算机编程，实现该算法的求解，得到问题的一个较优解。分析并调试的此解一共得到21条路线，如表4所示。

表4 21条旅游路线

根据各省份的线路，绘制直观图像如图1所示。

图1 西安到各省份的旅游线路图

分析上表，此路线结果中：从西安出发到全国各省的旅游线路天数<10天的有3条，天数>10天且<15天的有19条。

6 结束语

随着旅游业的发展，设计出合理完善的旅游路线不但有利于我国旅游业的发展，而且有利于游客和旅游社在旅行过程中节约时间和费用成本。然而现阶段的旅行线路设计多偏重于景区的特色搭配，很少从优化旅行的时间和距离入手[15-16]。鉴于此情况，本文运用贪婪算法对旅游路线进行设计，根据游客的时间需求，设计出满足游客需求的旅游线路，对西安市的旅游爱好者出行旅游起到一定的参考作用。本文在采用贪婪算法进行旅游线路优化过程中，模型将201个景区划分为31个省，实际问题进行了一定的简化，导致模型与事实存在一定的偏差，许多方面还有待完善。期望在以后的研究中有更完善的成果，使用该方法规划的旅游线路能够具有一定的方便性，比且和实际能紧密结合，让这一理论在旅游规划方面能够扩展开来，更好的用于实际中。

[1] Denstadli J M, Jacobsen J K S.The long and winding roads:perceived quality of scenic tourism routes[J].Tourism Management,2011,32(4):780-789.

[2] Briedenhann J,Wickens E.Tourism routes as a tool for the economic development of rural areas—vibrant hope or impossible dream?[J].Tourism Management,2004,25(1):71-79.

[3] 楚义芳.关于旅游线路设计的初步研究[J].旅游学刊,1992(2):9-13.

[4] 安贺新.体验经济时代旅游业发展模式研究[J].经济研究参考,2011(17):61-63.

[5] 杨冠军.基于混合聚类的大本体分块映射及评价方法研究[D].长沙:中南大学,2009.

[6] 周康,强小利,同小军,等.求解TSP算法[J].计算机工程与应用,2007,43(29):43-47.

[7] 唐晓云,赵黎明,秦彬.灰色系统理论及其在旅游预测中的应用—以广西桂林为例[J].西安电子科技大学学报:社会科学版,2007,17(2):1-5.

[8] 曹旭,张喆,马少仙.最短路问题在旅游线路优化中的应用[J].科技广场,2012(2):115-118.

[9] 姚成果.基于随机行驶时间的城市旅游线路优化研究[D].哈尔滨:哈尔滨工业大学,2007.

[10] 常友渠,肖贵元,曾敏.贪心算法的探讨与研究[J].重庆电力高等专科学校学报,2008,13(3):40-42.

[11] 聂小东.基于贪婪算法的排课系统的研究与实现[D].广州:广东工业大学,2006.

[12] 刘月华,吕永标,雷春霞,等.基于贪婪算法的太阳能小屋光伏电池组合分析[J].电子科技,2013,26(4):102-105.

[13] 邹时林,阮见,刘波,等.最短路径算法在旅游线路规划中的应用—以庐山为例[J].测绘科学,2008,33(5):190-192.

[14] 樊守伟,严艳,张少杰,等.Dijkstra算法与旅游路径优化[J].西安邮电大学学报,2014,19(1):121-124.

[15] 岳秋菊,任志国,蔡晓龙,等.基于最短路径优化问题佛洛依德算法系统的设计与实现[J].甘肃高师学报,2010,15(5):41-43.

[16] 潘玉侠,梁勤欧.基于遗传算法的旅游线路优化[J].浙江师范大学学报:自然科学版,2011,34(3):350-354.

Tourism Route Optimization Based on Greedy Algorithm

TENG Quan1，SHEN Jingfeng1，XU Bin2，WANG Weiwei3

(1.School of Mechanical Engineering,University of Shanghai for Science and Technology,Shanghai 200082,China;2.Damping Technology Department,Shanghai Research Institute of Materials,Shanghai 200082,China;3.School of Transportation Management,Dalian Maritime University,Dalian 116026,China)

In view of the present domestic tourist route design much favor from characteristics of scenic spots, and less from the travel time and path,Greedy algorithm is used to establish mathematical model.TIn the traveler not more than 15 days of travel constraints,201 domestic 5A scenic spots were clustered,and the 201 scenic spots will be reduced to 31 provinces and cities,Travel time is from xi ’an to various provinces and cities and get 21 conform to the requirements of the travel routes,The results are presented in a more intuitive image format,an innovative approach in the travel route design research.

tourist routes;optimization problem;clustering greedy algorithm;restrictions

2016- 11- 24

滕泉(1992-)，男，硕士研究生。研究方向：CAE，精密测量。沈景凤(1968-)，女，博士，副教授。研究方向：机械设计与理论等。

10.16180/j.cnki.issn1007-7820.2017.09.038

TP306.1；F592

A

1007-7820(2017)09-142-04