Dijkstra算法在三亚旅游线路规划中的应用

王哲河,林 越,张 侨

(琼州学院 a.计算机工程学院; b.数学系; c.旅游学院,海南 三亚572022)



Dijkstra算法在三亚旅游线路规划中的应用

王哲河a,林 越b,张 侨c

(琼州学院 a.计算机工程学院; b.数学系; c.旅游学院,海南 三亚572022)

建立数学模型,结合数据库技术,运用Dijkstra算法,计算出任意两个景点之间的最低费用、最短时间、最短路程,供游客路线选择和相关管理者规划旅游线路时参考.

数据库;Dijkstra;最短路径

0 引言

海南国际旅游岛建设背景下,三亚因其得天独厚的地理位置,独特丰富的旅游资源,成为了国内外旅游者青睐的旅游目的地之一.设计合理的旅游线路,方便游客选择,降低旅游的资金、时间和精力成本是提高城市旅游管理水平、旅游形象及旅游竞争力的重要途径.旅游线路的优化设计问题已经成为国内外学术界研究的重要领域.为便于研究,同时不影响模型的适用性和科学性,本文从众多线路设计影响因素中抽取景点间路程和道路类型两个关键要素,设置相应的权值,构建三亚旅游线路优化设计的数学模型,利用现代数据库技术和经典Dijkstra算法设计出了最优(路程、时间、费用)旅游线路,可供游客选择和管理者决策参考.

1 Dijkstra算法的由来

目前,求最短路径的算法有Dijkstra 算法、Floyd-Warshall算法、Bellman-Ford算法、Johnson算法等,每种算法都有其独特的优点,其中由荷兰计算机科学教授E.W.Dijkstra于1959 年率先提出的Dijkstra 算法可谓最经典,它主要用于解决有向图中源点到其他节点的最短路径问题[1-3,5].Dijkstra 算法的主要思想是从源点开始查找边长最短的相邻点,然后又以此相邻点作为新源点查找边长最短的相邻点,并记录沿途各个点(若到达新源点各边长之和大于前面各边长之和时须退回到上一个源点,换一条各边长之和次短的相邻点作为新源点继续查找),以此类推,直到新的相邻点为目的点且到达目的点的各边长之和最短时就停止查找.此外,边权赋予的含义不同,其最短路径的含义也不同,如边权值表示的是交通费时,最短路径实际指的是最少交通费.

2 三亚旅游线路的数学模型构建

根据Dijkstra 算法主要思想,结合三亚景点的布局情况,可得出影响游客出行的两个关键要素是景点间路程和道路类型,两者决定交通费用高低和所需时间多少[4-6].为了便于研究,选择三亚的几个主要景点及连通各景点的公路所构成的景点图 (如图1所示)作为研究对象,并约定:

①景点:用圆圈代表,圆圈内的数据如65|90表示天涯海角景点门票为65元,停留(参观)时间为90分钟,V4中的4表示天涯海角的景点号.

②景点间路程:用曲线代表,曲线边上的数据如45|1,45表示南山寺至落笔洞两景点的直通路程为45公里,1表示此路为高速公路.

③交通费用计算方法:高速公路1.5元/km、普通公路2元/km.

④图1中相关数据是以三亚市公交车实际行驶路程为基础进行处理后抽象的数据.

图1 三亚主要景区景点示意图

由图的最短路径的定义可知,要求图1中某一个顶点(即景区/点)到其他顶点(即景区/点)的时间最少或费用最低问题,就转换成了Dijkstra算法求最短路径问题.由于景区/点门票价格和景点停留平均时间均为固定值,因此只需要利用经典Dijkstra算法计算出任意两个景点间的最短路径(路程或时间),即可计算出相应的最小费用及时间.假设用S,T,P分别表示景点至景点的最短路程,最短时间,最低费用;用s,t,p,gv,gp,pv,pp分别表示两景点间直通距离、景点门票费、景点停留时间、高速公路平均速度、高速公路平均费用、普通公路平均速度、普通公路平均费,表示景点序号;k,z表示道路号,则有:

(1)

(2)

(3)

3 三亚旅游线路信息逻辑模型构建

经典Dijkstra算法中,要求图的每条边的权值和每个顶点的值有且只有一个值.为了实现每条边(或顶点)的值有多个时,需借助于数据库表的存储功能, 所以Dijkstra算法运算时是基于数据库表中的数据进行操作的.根据三亚市旅游景点情况,可建立如下4个数据库表来存储有关信息,其结构分别为如表1, 表2, 表3, 表4所示:

表1 道路信息

说明:[道路等级]分为普通公路0,平均速度为80km/h;高速公路1,平均速度为120km/h.假设任两个景点间道路类型要么全为高速公路,要么全为普通公路.

表2 景点信息

说明:[景点停留平均时间]单位为分钟;[景点门票]单位为元;[景点等级]分为0A-5A.

表3 景点连通信息

说明:[两点间距]为0或-1时,表示两点间无直通路,单位为公里;[方向描述]用始景点ID→终景点ID表示.

表4 最优临时表

说明:本表中的数据只是程序运行时临时产生, 程序关闭后其内容将被删除.

4 算法设计与验证

由于本研究是基于数据库的Dijkstra算法应用,所以其求解最短路径的过程更加复杂.首先封装一个实现求解最短路径Dijkstra类,当相关数据初始化完成后再调用此类中的Dijkstra方法求得最短路径(路程、时间、费用),最后输出结果.其程序流程如图2所示.

为了验证本算法的可行性,假设游客A从三亚湾出发到南山寺为例,其计算过程如下:

第一步:找出三亚湾至南山寺的所有线路,然后根据公式(2),先计算出所经道路所需要时间之和最少的道路,然后再加该道路上各景点的停留时间即可.

第二步:根据公式(3),先计算出所经道路所产生交通费之和最低的道路,然后再加上道上各景点门票费即可.

根据图1,可知起点为三亚湾,终点为南山寺的线路总共有4条,每一条线路的总路程、所需时间和所需费用如表5所示.

表5 三亚湾->南山寺所有线路

从表5可知:选择线路2,游客A所需时间和费用都最少.

为了方便游客选择出行线路和管理者规划旅游线路,本研究利用Microsoft SQL Sever2012数据库存储有关景点的数据和VB.NET语言编程实现计算过程.根据用户选择的起始景点、目标景点和优先方案,点击查询即可查看最佳线路.比如查询从三亚湾至南山寺的最佳线路,程序运行效果如图3所示:

图3 程序运行效果

通过模拟测试,此程序运行效果与理论计算所得结果(表5所示)基本一致.

5 结语

尽管Dijkstra算法能够求解城市旅游线路设计的一些最值问题,但其算法复杂度会随着顶(节)点增多而增大,遍历计算的顶(节)点越多,计算效率也会变得更低.另外,本研究局限于影响游客出行的两个关键因素进行研究,没有考虑诸如交通阻塞、自驾车、单行线、景点等级等其他因素对旅游线路选择的影响,这是今后需要进一步完善的地方.

[1]孟庆伟,张冬姣. 基于Dijkstra最短路径算法的优化及应用研究[J].电子商务,2014(12): 60-61.

[2]王一松,王直杰.基于实时交通信息的最优路径规划算法研究[J].计算机与现代化, 2013 (2):52-54.

[3]王树西,吴政学.改进的Dijkstra最短路径算法及其应用研究[J].计算机科学,2012,39(5):223-227.

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

[5]涂海丽.最短路径算法及其应用探讨[J].科技广场,2011(9):11-14.

[6]齐信,杨泰平,段永坤,罗真富.基于MapX的Dijkstra算法在城市交通查询中的实现[J].测绘与空间地理信息,2010(2): 136-139.

Application of the Dijkstra Algorithm in Sanya Tourist Route Planning

WANG Zhe-hea,LIN Yueb, ZHANG Qiaoc

(a.College of Computer Engineering; b. Mathematics Department; c. College of Tourism, Qiongzhou University, Sanya Hainan, 572022,China)

The minimum cost between any two specific scenic spots, the shortest time, the shortest distance are calculated by establishing mathematical model, applying database technology, and using the Dijkstra algorithm. Thus are provided the references for route selection and planning tourist routes.

Database; Dijkstra; shortestpath

2015-03-08

三亚市院地科技合作项目(2012YD29)；琼州学院校级青年科学基金项目(QYQN201428)

王哲河(1980-),男,海南澄迈人,琼州学院计算机工程学院计算机讲师,硕士,研究方向为数据库技术、信息化、算法应用研究等.

TP399;F224

A

1008-6722(2015) 05-0098-05

10.13307/j.issn.1008-6722．2015．05．21