王哲河,林 越,張 僑

(瓊州學(xué)院 a.計(jì)算機(jī)工程學(xué)院; b.數(shù)學(xué)系; c.旅游學(xué)院,海南 三亞572022)

?

Dijkstra算法在三亞旅游線(xiàn)路規(guī)劃中的應(yīng)用

王哲河a,林 越b,張 僑c

(瓊州學(xué)院 a.計(jì)算機(jī)工程學(xué)院; b.數(shù)學(xué)系; c.旅游學(xué)院,海南 三亞572022)

建立數(shù)學(xué)模型,結(jié)合數(shù)據(jù)庫(kù)技術(shù),運(yùn)用Dijkstra算法,計(jì)算出任意兩個(gè)景點(diǎn)之間的最低費(fèi)用、最短時(shí)間、最短路程,供游客路線(xiàn)選擇和相關(guān)管理者規(guī)劃旅游線(xiàn)路時(shí)參考.

數(shù)據(jù)庫(kù);Dijkstra;最短路徑

0 引言

海南國(guó)際旅游島建設(shè)背景下,三亞因其得天獨(dú)厚的地理位置,獨(dú)特豐富的旅游資源,成為了國(guó)內(nèi)外旅游者青睞的旅游目的地之一.設(shè)計(jì)合理的旅游線(xiàn)路,方便游客選擇,降低旅游的資金、時(shí)間和精力成本是提高城市旅游管理水平、旅游形象及旅游競(jìng)爭(zhēng)力的重要途徑.旅游線(xiàn)路的優(yōu)化設(shè)計(jì)問(wèn)題已經(jīng)成為國(guó)內(nèi)外學(xué)術(shù)界研究的重要領(lǐng)域.為便于研究,同時(shí)不影響模型的適用性和科學(xué)性,本文從眾多線(xiàn)路設(shè)計(jì)影響因素中抽取景點(diǎn)間路程和道路類(lèi)型兩個(gè)關(guān)鍵要素,設(shè)置相應(yīng)的權(quán)值,構(gòu)建三亞旅游線(xiàn)路優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型,利用現(xiàn)代數(shù)據(jù)庫(kù)技術(shù)和經(jīng)典Dijkstra算法設(shè)計(jì)出了最優(yōu)(路程、時(shí)間、費(fèi)用)旅游線(xiàn)路,可供游客選擇和管理者決策參考.

1 Dijkstra算法的由來(lái)

目前,求最短路徑的算法有Dijkstra 算法、Floyd-Warshall算法、Bellman-Ford算法、Johnson算法等,每種算法都有其獨(dú)特的優(yōu)點(diǎn),其中由荷蘭計(jì)算機(jī)科學(xué)教授E.W.Dijkstra于1959 年率先提出的Dijkstra 算法可謂最經(jīng)典,它主要用于解決有向圖中源點(diǎn)到其他節(jié)點(diǎn)的最短路徑問(wèn)題[1-3,5].Dijkstra 算法的主要思想是從源點(diǎn)開(kāi)始查找邊長(zhǎng)最短的相鄰點(diǎn),然后又以此相鄰點(diǎn)作為新源點(diǎn)查找邊長(zhǎng)最短的相鄰點(diǎn),并記錄沿途各個(gè)點(diǎn)(若到達(dá)新源點(diǎn)各邊長(zhǎng)之和大于前面各邊長(zhǎng)之和時(shí)須退回到上一個(gè)源點(diǎn),換一條各邊長(zhǎng)之和次短的相鄰點(diǎn)作為新源點(diǎn)繼續(xù)查找),以此類(lèi)推,直到新的相鄰點(diǎn)為目的點(diǎn)且到達(dá)目的點(diǎn)的各邊長(zhǎng)之和最短時(shí)就停止查找.此外,邊權(quán)賦予的含義不同,其最短路徑的含義也不同,如邊權(quán)值表示的是交通費(fèi)時(shí),最短路徑實(shí)際指的是最少交通費(fèi).

2 三亞旅游線(xiàn)路的數(shù)學(xué)模型構(gòu)建

根據(jù)Dijkstra 算法主要思想,結(jié)合三亞景點(diǎn)的布局情況,可得出影響游客出行的兩個(gè)關(guān)鍵要素是景點(diǎn)間路程和道路類(lèi)型,兩者決定交通費(fèi)用高低和所需時(shí)間多少[4-6].為了便于研究,選擇三亞的幾個(gè)主要景點(diǎn)及連通各景點(diǎn)的公路所構(gòu)成的景點(diǎn)圖 (如圖1所示)作為研究對(duì)象,并約定:

①景點(diǎn):用圓圈代表,圓圈內(nèi)的數(shù)據(jù)如65|90表示天涯海角景點(diǎn)門(mén)票為65元,停留(參觀)時(shí)間為90分鐘,V4中的4表示天涯海角的景點(diǎn)號(hào).

②景點(diǎn)間路程:用曲線(xiàn)代表,曲線(xiàn)邊上的數(shù)據(jù)如45|1,45表示南山寺至落筆洞兩景點(diǎn)的直通路程為45公里,1表示此路為高速公路.

③交通費(fèi)用計(jì)算方法:高速公路1.5元/km、普通公路2元/km.

④圖1中相關(guān)數(shù)據(jù)是以三亞市公交車(chē)實(shí)際行駛路程為基礎(chǔ)進(jìn)行處理后抽象的數(shù)據(jù).

圖1 三亞主要景區(qū)景點(diǎn)示意圖

由圖的最短路徑的定義可知,要求圖1中某一個(gè)頂點(diǎn)(即景區(qū)/點(diǎn))到其他頂點(diǎn)(即景區(qū)/點(diǎn))的時(shí)間最少或費(fèi)用最低問(wèn)題,就轉(zhuǎn)換成了Dijkstra算法求最短路徑問(wèn)題.由于景區(qū)/點(diǎn)門(mén)票價(jià)格和景點(diǎn)停留平均時(shí)間均為固定值,因此只需要利用經(jīng)典Dijkstra算法計(jì)算出任意兩個(gè)景點(diǎn)間的最短路徑(路程或時(shí)間),即可計(jì)算出相應(yīng)的最小費(fèi)用及時(shí)間.假設(shè)用S,T,P分別表示景點(diǎn)至景點(diǎn)的最短路程,最短時(shí)間,最低費(fèi)用;用s,t,p,gv,gp,pv,pp分別表示兩景點(diǎn)間直通距離、景點(diǎn)門(mén)票費(fèi)、景點(diǎn)停留時(shí)間、高速公路平均速度、高速公路平均費(fèi)用、普通公路平均速度、普通公路平均費(fèi),表示景點(diǎn)序號(hào);k,z表示道路號(hào),則有:

(1)

(2)

(3)

3 三亞旅游線(xiàn)路信息邏輯模型構(gòu)建

經(jīng)典Dijkstra算法中,要求圖的每條邊的權(quán)值和每個(gè)頂點(diǎn)的值有且只有一個(gè)值.為了實(shí)現(xiàn)每條邊(或頂點(diǎn))的值有多個(gè)時(shí),需借助于數(shù)據(jù)庫(kù)表的存儲(chǔ)功能, 所以Dijkstra算法運(yùn)算時(shí)是基于數(shù)據(jù)庫(kù)表中的數(shù)據(jù)進(jìn)行操作的.根據(jù)三亞市旅游景點(diǎn)情況,可建立如下4個(gè)數(shù)據(jù)庫(kù)表來(lái)存儲(chǔ)有關(guān)信息,其結(jié)構(gòu)分別為如表1, 表2, 表3, 表4所示:

表1 道路信息

說(shuō)明:[道路等級(jí)]分為普通公路0,平均速度為80km/h;高速公路1,平均速度為120km/h.假設(shè)任兩個(gè)景點(diǎn)間道路類(lèi)型要么全為高速公路,要么全為普通公路.

表2 景點(diǎn)信息

說(shuō)明:[景點(diǎn)停留平均時(shí)間]單位為分鐘;[景點(diǎn)門(mén)票]單位為元;[景點(diǎn)等級(jí)]分為0A-5A.

表3 景點(diǎn)連通信息

說(shuō)明:[兩點(diǎn)間距]為0或-1時(shí),表示兩點(diǎn)間無(wú)直通路,單位為公里;[方向描述]用始景點(diǎn)ID→終景點(diǎn)ID表示.

表4 最優(yōu)臨時(shí)表

說(shuō)明:本表中的數(shù)據(jù)只是程序運(yùn)行時(shí)臨時(shí)產(chǎn)生, 程序關(guān)閉后其內(nèi)容將被刪除.

4 算法設(shè)計(jì)與驗(yàn)證

由于本研究是基于數(shù)據(jù)庫(kù)的Dijkstra算法應(yīng)用,所以其求解最短路徑的過(guò)程更加復(fù)雜.首先封裝一個(gè)實(shí)現(xiàn)求解最短路徑Dijkstra類(lèi),當(dāng)相關(guān)數(shù)據(jù)初始化完成后再調(diào)用此類(lèi)中的Dijkstra方法求得最短路徑(路程、時(shí)間、費(fèi)用),最后輸出結(jié)果.其程序流程如圖2所示.

為了驗(yàn)證本算法的可行性,假設(shè)游客A從三亞灣出發(fā)到南山寺為例,其計(jì)算過(guò)程如下:

第一步:找出三亞灣至南山寺的所有線(xiàn)路,然后根據(jù)公式(2),先計(jì)算出所經(jīng)道路所需要時(shí)間之和最少的道路,然后再加該道路上各景點(diǎn)的停留時(shí)間即可.

第二步:根據(jù)公式(3),先計(jì)算出所經(jīng)道路所產(chǎn)生交通費(fèi)之和最低的道路,然后再加上道上各景點(diǎn)門(mén)票費(fèi)即可.

根據(jù)圖1,可知起點(diǎn)為三亞灣,終點(diǎn)為南山寺的線(xiàn)路總共有4條,每一條線(xiàn)路的總路程、所需時(shí)間和所需費(fèi)用如表5所示.

表5 三亞灣->南山寺所有線(xiàn)路

從表5可知:選擇線(xiàn)路2,游客A所需時(shí)間和費(fèi)用都最少.

為了方便游客選擇出行線(xiàn)路和管理者規(guī)劃旅游線(xiàn)路,本研究利用Microsoft SQL Sever2012數(shù)據(jù)庫(kù)存儲(chǔ)有關(guān)景點(diǎn)的數(shù)據(jù)和VB.NET語(yǔ)言編程實(shí)現(xiàn)計(jì)算過(guò)程.根據(jù)用戶(hù)選擇的起始景點(diǎn)、目標(biāo)景點(diǎn)和優(yōu)先方案,點(diǎn)擊查詢(xún)即可查看最佳線(xiàn)路.比如查詢(xún)從三亞灣至南山寺的最佳線(xiàn)路,程序運(yùn)行效果如圖3所示:

圖3 程序運(yùn)行效果

通過(guò)模擬測(cè)試,此程序運(yùn)行效果與理論計(jì)算所得結(jié)果(表5所示)基本一致.

5 結(jié)語(yǔ)

盡管Dijkstra算法能夠求解城市旅游線(xiàn)路設(shè)計(jì)的一些最值問(wèn)題,但其算法復(fù)雜度會(huì)隨著頂(節(jié))點(diǎn)增多而增大,遍歷計(jì)算的頂(節(jié))點(diǎn)越多,計(jì)算效率也會(huì)變得更低.另外,本研究局限于影響游客出行的兩個(gè)關(guān)鍵因素進(jìn)行研究,沒(méi)有考慮諸如交通阻塞、自駕車(chē)、單行線(xiàn)、景點(diǎn)等級(jí)等其他因素對(duì)旅游線(xiàn)路選擇的影響,這是今后需要進(jìn)一步完善的地方.

[1]孟慶偉,張冬姣. 基于Dijkstra最短路徑算法的優(yōu)化及應(yīng)用研究[J].電子商務(wù),2014(12): 60-61.

[2]王一松,王直杰.基于實(shí)時(shí)交通信息的最優(yōu)路徑規(guī)劃算法研究[J].計(jì)算機(jī)與現(xiàn)代化, 2013 (2):52-54.

[3]王樹(shù)西,吳政學(xué).改進(jìn)的Dijkstra最短路徑算法及其應(yīng)用研究[J].計(jì)算機(jī)科學(xué),2012,39(5):223-227.

[4]王佳,趙宏麗.基于Dijkstra算法的京津冀旅游交通線(xiàn)路優(yōu)化研究[J].統(tǒng)計(jì)與決策,2011(13): 81-83.

[5]涂海麗.最短路徑算法及其應(yīng)用探討[J].科技廣場(chǎng),2011(9):11-14.

[6]齊信,楊泰平,段永坤,羅真富.基于MapX的Dijkstra算法在城市交通查詢(xún)中的實(shí)現(xiàn)[J].測(cè)繪與空間地理信息,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

三亞市院地科技合作項(xiàng)目(2012YD29)；瓊州學(xué)院校級(jí)青年科學(xué)基金項(xiàng)目(QYQN201428)

王哲河(1980-),男,海南澄邁人,瓊州學(xué)院計(jì)算機(jī)工程學(xué)院計(jì)算機(jī)講師,碩士,研究方向?yàn)閿?shù)據(jù)庫(kù)技術(shù)、信息化、算法應(yīng)用研究等.

TP399;F224

A

1008-6722(2015) 05-0098-05

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