Dijkstra算法与旅游路径优化

樊守伟， 严 艳， 张少杰， 田泽民

(陕西师范大学 旅游与环境学院, 陕西 西安 710062)

Dijkstra算法与旅游路径优化

樊守伟， 严 艳， 张少杰， 田泽民

(陕西师范大学 旅游与环境学院, 陕西 西安 710062)

基于旅游业快速发展的事实，为满足游客省时、省钱、走最短路程的线路需求，对Dijkstra算法加以改进，即先利用Dijkstra算法依次求出局部最优解，然后整合得到全局最优路径，从而使改进算法更适合线路设计。最终在综合考虑旅游花费、交通时间、游览路程3个因素的前提下，以西安市及周边景点为例，设计出3种自驾车旅游最优路径方案，验证了新算法的可行性。

Dijkstra算法；自驾游；旅游线路

随着自驾游如火如荼的发展，越来越多的游客参与到自驾游中。自驾车旅游者追求以最少的花销走更远的路、看更精彩的风景，并称为“穷游”，其旅游活动具有多目的地性特征。旅游线路是旅游者在目的地区域内的空间移动轨迹，即旅游空间行为路径[1]。如何设计出一条多景点间距离最短(或费用、时间最少)的旅游线路是自驾车游客的现实需求[2]。这是一个典型的TSP(Traveling Salesman Problems)问题，即必须访问版图上所有城市, 每次经过一个, 最终回到出发点, 给定所有城市之间的旅费, 应该如何计算线路以获得最小开销[3]。

TSP问题可通过多种方法解决。最容易的方法是穷举法，但当所要计算的地点数量较多时，求解就显得异常复杂、难以实现。常用的智能算法有遗传算法、蚁群算法、模拟退火算法、人工神经网络等。遗传算法程序简单、易于实现，能够并行化，但却存在早熟现象、局部寻优能力较差等问题，所以当针对一些特殊问题时，常规遗传算法并不一定是最佳选择。蚁群算法是由Dorigo提出，在解决TSP问题中得到广泛应用[4]。该算法不仅是一种自适应、自组织、并行的方法，而且可实现正向反馈，能够促使整个系统向最优解进化；但存在收敛慢、易于陷入局部最优等缺点。模拟退火算法是由Patrick将退火思想引入组合优化领域所提出一种求解大规模组合优化问题的算法[5]。该算法具有较强的局部寻优能力，并能使搜索过程避免陷入局部最优解；但它把握整个搜索过程的能力不够，不仅使得模拟退火的运算效率不高，而且也难以控制参数温度的初始值、退火速度问题、温度管理等问题[6]。Hopfield和Tank于1985年利用人工神经网络求解TSP问题[7]。该算法在大多数情况下可以求出最优解的近似解；但当城市数大于30时，其求解结果不太令人满意；当城市规模更大时，易于收敛到非法解或局部极小解，同时还存在收敛速度慢、对模型参数和初始条件敏感等缺点[8]。

而贪心算法中的Dijkstra(迪杰斯特拉)算法被认为是目前求最短路径问题的最好方法[9]，属于典型的单源最短路径算法，是交通网络最短路径算法的首选[10]，成为解决旅游交通中线路优化设计的重要方法；但其在旅游业中的应用并不完善，研究层次也较低[11]。故本文在Dijkstra算法基础上进行改进，即先利用Dijkstra算法依次求出局部最优解，然后整合得到全局最优路径，并以西安市周边景点为例，结合自驾车游客的特点，对西安市周边的自驾车旅游线路进行优化设计。

1 算法介绍及改进

1.1 Dijkstra算法

Dijkstra算法的基本思想是：设集合V是图G的顶点集合，集合S存放已经找到最短路径的顶点，初始状态时，集合S中只包含源点vi然后不断地从S集合以外的所有顶点集合VS中选择到源点vi路径长度最短的顶点vj加入到集合S中，集合S中每加入一个新的顶点vj都要修改从源点vi到VS集合中剩余顶点的当前最短路径长度值，集合VS中各顶点的新的当前最短路径长度值，为原来的最短路径长度值与从源点经过顶点vj到达该顶点的路径长度中的较小者。此过程不断重复，直到集合V中的全部顶点都加入到集合S中[12]。

1.2 Dijkstra算法在TSP问题中的改进应用

由于Dijkstra算法是单源最短路径算法，该算法不能解决全通拓扑结构图中的TSP问题，故只利用该算法寻找局部最短路径，从而形成全局最优路径。

假设集合S1存放已经找到最短路径的顶点，开始时，利用Dijkstra算法得出起点v0到所有景点的最短距离，然后，找到最短距离中的最小数值

dist[j]=min{dist[i]|(vi∈VS)}，

并把i并入到集合S1中，在以j为起点再利用Dijkstra算法计算到集合VS1所有最距离中的最小值，直到集合VS1为空集为止。其实现流程如图1所示，实现步骤如下。

步骤1 初始时，S1只包含起点v0，VS1包含除v0外的其他顶点。然后，执行Dijkstra算法，得到从v0出发到其余各顶点可能达到的最短路径长度的初值为

dist[i]=cost[v0,vi](vi∈V)。

步骤2 选择vj，使

dist[j]=min{dist[i]|(vi∈VS)}，

vj就是当前求得的一条从v0出发的最短路径的终点，将vj并入集合S1。

步骤3 令以vj为出发点，执行Dijkstra算法，得到{dist[i]|(vi∈VS)}。

步骤4 重复步骤2和步骤3，直至集合VS1为空集，依次输出各景点序号，形成每相邻两景点都是最小距离的旅游线路。

图1 程序流程

2 案例背景及实际数据

2.1 案例背景

西安市旅游资源丰富，自驾游发展势头强劲。为使研究样本具有代表性，通过对西安自驾车游客访谈，选定西安市及其周边深受自驾车游客喜爱的10个景点分析，这10个景点为钟楼(与鼓楼、回民街、城墙列为一处景点)、乾陵、法门寺、碑林、陕西历史博物馆、大雁塔、大唐芙蓉园、兵马俑、华清池、华山，并分别记为Xi(i=1,2,…,10)。

假定自驾游均以私家车为交通工具，以高速公路和非高速公路为主要道路，车速一定，路况通畅，天气等一切突发情况不纳入考虑范围，同时默认各景点之间回程与去程有多条路径。

2.2 数据来源

2.2.1 旅游景点加权图

利用Dijkstra算法进行线路优化设计时，首先需将旅游地图转化为加权有向图。本文对加权有向图做了调整，图中只标出线路，具体权值在下文给出。将每个旅游景点看作加权有向图的一个节点，景点间的交通线路作为边，各景点间的距离(或行程时间、交通费用)是对应边的权值。

2.2.2 旅游景点线路权值

(1) 距离权值

利用ArcGIS软件，首先将景点间的线路进行数字化处理，其次通过舍远取近法找出最短线路，最后利用比例尺转化得到景点间具体距离。最终得出距离权值表(表1)。

表1 景点间距离权值表 /km

注 只考虑各景点之间的距离，而景区内的距离未列入考虑范围。

(2) 时间权值

前文已假定车速一定，路况良好，可由各景点间的实际距离计算出其交通时间，从而将时间最短问题表现为具体路径问题。但最近的线路未必是最省时的，比如存在道路崎岖、弯道较多不易于行驶等问题。故本文权衡景点间各条线路的路况、距离、实际情况等选择线路，以保证路途中用时是最少的。最终得出时间权值表(表2)。

表2 景点间驾车时间权值表/min

注 只考虑各景点之间的交通时间，而景区内的游玩时间未列入考虑范围。

(3) 费用权值

旅游费用涵盖“食住行游购娱”6方面，其中只有“行”是比较可控的，其余5项因主观性较大、不确定因素多、与所访景点次序无关等因素而不考虑。交通费用与公路等级、燃油费等有关，本文按照高速公路0.6 元/车·km及燃油费0.7 元/车·km的标准计算，同样将无形的费用问题转化为具体路径问题。首先根据景点间的线路分别计算出所需的交通费用，再结合所花交通费用最少的原则确定线路，最终得出费用权值表(表3)。

表3 交通费用权值表/元

3 算法应用

利用上述景点间距离、驾车时间、交通费用等数据，在C语言环境中运行所改进的程序进行线路设计，得到如下结果。

3.1 最短路程路线

当不限定交通费用与时间、只考虑最少驾车路程时，最佳旅游线路是

X1→X4→X5→X6→X7→X9→
X8→X10→X2→X3→X1,

相对应线路为

钟楼→碑林→陕西历史博物馆→
大雁塔→大唐芙蓉园→兵马俑→
华清池→华山→乾陵→法门寺。

该线路行程共354.3 km。

3.2 最省时间路线

当不限定交通费用与路程时、只考虑所用驾车时间最少时，最佳旅游线路是

X1→X4→X5→X7→X6→X9→
X8→X10→X2→X3→X1,

相对应线路为

钟楼→碑林→陕西历史博物馆→
大唐芙蓉园→大雁塔→兵马俑→
华清池→华山→乾陵→法门寺。

该线路途中用时373 mins。

3.3 费用最少路线

当不限定时间和路程、只考虑交通费用最少问题时，最佳旅游线路是

X1→X4→X5→X6→X7→X8→
X9→X10→X2→X3→X1,

相对应线路为

钟楼→碑林→陕西历史博物馆→
大雁塔→大唐芙蓉园→华清池→
兵马俑→华山→乾陵→法门寺。

该线路驾车交通费用为 289.7 元。

4 结语

将Dijkstra算法应用到自驾游线路设计中，所设计的线路可满足自驾车游客的需求，方法具有普适性且实现简单。未来应用中，可建立全国最优旅游路径网站或旅游线路查询决策系统。旅游区旅游线路的开发水平、完善程度，起到把握控制旅游流的流量、流向的作用，因此，相关结果可扩展到区域旅游交通规划和景区内道路设计等实际应用方面，可据实际需要进行改进，为旅游相关部门提供决策支持。据此最优路径制定的旅游开发战略可推动沿线地区旅游业的进步，对区域经济的发展具有深远意义。

[1] Lue C C, Crompton J L, Stewart W P. Evidence of cumulative attraction in multidestination recreational trip decisions[J]. Journal of Travel Research,1996,35(1):41-49.

[2] 滕聪,曹文.旅游景点筛选组合及旅游线路的优化算法与应用[J].地球信息科学学报, 2010,12(5):668-673.

[3] 许丽佳,蒲海波,蒋宏健.改进遗传算法的路径规划研究[J].微计算机信息, 2006,22(2):251-253.

[4] Kan Junman, Zhang Yi. Application of an Improved Ant Colony Optimization on Generalized Traveling Salesman Problem[J]. Energy Procedia, 2012,17(4): 319-325.

[5] Zhang Jin, Liu Huaishan, Tong Siyou, et al. The improvement of ant colony algorithm and its application to TSP problem[C]//5th International Conference on Wireless Communications, Networking and Mobile Computing. Beijing:IEEE,2009:1-4.

[6] 高尚. 求解旅行商问题的模拟退火算法[J].华东船舶工业学院学报,2003,17(3):13-16.

[7] Hopfield J J, Tank D W. “Neural” computation of decisions in optimization problems[J]. Biological Cybernetics,1985,52(3):141-152.

[8] 王潮, 宣国荣.人工神经网络求解TSP问题新方法[J].计算机应用与软件,2001,18(4):59-64.

[9] 王佳,赵宏丽.基于Dijkstra算法的京津冀旅游交通线路优化研究[J].统计与决策, 2011,337(13):82-83.

[10] 陆锋. 最短路径算法: 分类体系与研究进展[J]. 测绘学报, 2001, 30(3):269-275.

[11] 吴凯. 旅游线路设计与优化中的运筹学问题[J]. 旅游科学, 2004, 18(1):41-44.

[12] 熊回香.数据结构:C/C++版[M].北京:清华大学出版社,2010:292-302.

[责任编辑:王辉]

The optimal route design for self-driving travel
based on the Dijkstra algorithm

FAN Shouwei, YAN Yan, ZHANG Shaojie, TIAN Zemin

(School of Tourism and Environment, Shaanxi Normal University, Xi’an 710062, China)

An improved scheme based on the Dijkstra algorithm is proposed to meet rapid development of tourism with high demand from self-travelers on tourism routes design for reduced cost and traffic time as well as the tour distance. This scheme can find out the local optimal path in order to achieve the global optimal path. Three optimal paths about self-driving travel in Xi’an given through this scheme are proved to be feasible.

Dijkstra algorithm, self-driving travel, tourism routes

10.13682/j.issn.2095-6533.2014.01.025

2013-11-23

陕西省社会科学基金资助项目(13Q045)

樊守伟(1988-)，女，硕士研究生，研究方向为旅游景区规划与管理。E-mail：1025443824@qq.com 严艳(1968-)，女，博士，副教授，从事旅游管理与人文地理等研究。E-mail：yanyan@snnu.edu.cn

F590

A

2095-6533(2014)01-0121-04