Dijkstra算法與旅游路徑優(yōu)化

樊守偉， 嚴(yán) 艷， 張少杰， 田澤民

(陜西師范大學(xué) 旅游與環(huán)境學(xué)院, 陜西 西安 710062)

Dijkstra算法與旅游路徑優(yōu)化

樊守偉， 嚴(yán) 艷， 張少杰， 田澤民

(陜西師范大學(xué) 旅游與環(huán)境學(xué)院, 陜西 西安 710062)

基于旅游業(yè)快速發(fā)展的事實(shí)，為滿(mǎn)足游客省時(shí)、省錢(qián)、走最短路程的線(xiàn)路需求，對(duì)Dijkstra算法加以改進(jìn)，即先利用Dijkstra算法依次求出局部最優(yōu)解，然后整合得到全局最優(yōu)路徑，從而使改進(jìn)算法更適合線(xiàn)路設(shè)計(jì)。最終在綜合考慮旅游花費(fèi)、交通時(shí)間、游覽路程3個(gè)因素的前提下，以西安市及周邊景點(diǎn)為例，設(shè)計(jì)出3種自駕車(chē)旅游最優(yōu)路徑方案，驗(yàn)證了新算法的可行性。

Dijkstra算法；自駕游；旅游線(xiàn)路

隨著自駕游如火如荼的發(fā)展，越來(lái)越多的游客參與到自駕游中。自駕車(chē)旅游者追求以最少的花銷(xiāo)走更遠(yuǎn)的路、看更精彩的風(fēng)景，并稱(chēng)為“窮游”，其旅游活動(dòng)具有多目的地性特征。旅游線(xiàn)路是旅游者在目的地區(qū)域內(nèi)的空間移動(dòng)軌跡，即旅游空間行為路徑[1]。如何設(shè)計(jì)出一條多景點(diǎn)間距離最短(或費(fèi)用、時(shí)間最少)的旅游線(xiàn)路是自駕車(chē)游客的現(xiàn)實(shí)需求[2]。這是一個(gè)典型的TSP(Traveling Salesman Problems)問(wèn)題，即必須訪(fǎng)問(wèn)版圖上所有城市, 每次經(jīng)過(guò)一個(gè), 最終回到出發(fā)點(diǎn), 給定所有城市之間的旅費(fèi), 應(yīng)該如何計(jì)算線(xiàn)路以獲得最小開(kāi)銷(xiāo)[3]。

TSP問(wèn)題可通過(guò)多種方法解決。最容易的方法是窮舉法，但當(dāng)所要計(jì)算的地點(diǎn)數(shù)量較多時(shí)，求解就顯得異常復(fù)雜、難以實(shí)現(xiàn)。常用的智能算法有遺傳算法、蟻群算法、模擬退火算法、人工神經(jīng)網(wǎng)絡(luò)等。遺傳算法程序簡(jiǎn)單、易于實(shí)現(xiàn)，能夠并行化，但卻存在早熟現(xiàn)象、局部尋優(yōu)能力較差等問(wèn)題，所以當(dāng)針對(duì)一些特殊問(wèn)題時(shí)，常規(guī)遺傳算法并不一定是最佳選擇。蟻群算法是由Dorigo提出，在解決TSP問(wèn)題中得到廣泛應(yīng)用[4]。該算法不僅是一種自適應(yīng)、自組織、并行的方法，而且可實(shí)現(xiàn)正向反饋，能夠促使整個(gè)系統(tǒng)向最優(yōu)解進(jìn)化；但存在收斂慢、易于陷入局部最優(yōu)等缺點(diǎn)。模擬退火算法是由Patrick將退火思想引入組合優(yōu)化領(lǐng)域所提出一種求解大規(guī)模組合優(yōu)化問(wèn)題的算法[5]。該算法具有較強(qiáng)的局部尋優(yōu)能力，并能使搜索過(guò)程避免陷入局部最優(yōu)解；但它把握整個(gè)搜索過(guò)程的能力不夠，不僅使得模擬退火的運(yùn)算效率不高，而且也難以控制參數(shù)溫度的初始值、退火速度問(wèn)題、溫度管理等問(wèn)題[6]。Hopfield和Tank于1985年利用人工神經(jīng)網(wǎng)絡(luò)求解TSP問(wèn)題[7]。該算法在大多數(shù)情況下可以求出最優(yōu)解的近似解；但當(dāng)城市數(shù)大于30時(shí)，其求解結(jié)果不太令人滿(mǎn)意；當(dāng)城市規(guī)模更大時(shí)，易于收斂到非法解或局部極小解，同時(shí)還存在收斂速度慢、對(duì)模型參數(shù)和初始條件敏感等缺點(diǎn)[8]。

而貪心算法中的Dijkstra(迪杰斯特拉)算法被認(rèn)為是目前求最短路徑問(wèn)題的最好方法[9]，屬于典型的單源最短路徑算法，是交通網(wǎng)絡(luò)最短路徑算法的首選[10]，成為解決旅游交通中線(xiàn)路優(yōu)化設(shè)計(jì)的重要方法；但其在旅游業(yè)中的應(yīng)用并不完善，研究層次也較低[11]。故本文在Dijkstra算法基礎(chǔ)上進(jìn)行改進(jìn)，即先利用Dijkstra算法依次求出局部最優(yōu)解，然后整合得到全局最優(yōu)路徑，并以西安市周邊景點(diǎn)為例，結(jié)合自駕車(chē)游客的特點(diǎn)，對(duì)西安市周邊的自駕車(chē)旅游線(xiàn)路進(jìn)行優(yōu)化設(shè)計(jì)。

1 算法介紹及改進(jìn)

1.1 Dijkstra算法

Dijkstra算法的基本思想是：設(shè)集合V是圖G的頂點(diǎn)集合，集合S存放已經(jīng)找到最短路徑的頂點(diǎn)，初始狀態(tài)時(shí)，集合S中只包含源點(diǎn)vi然后不斷地從S集合以外的所有頂點(diǎn)集合VS中選擇到源點(diǎn)vi路徑長(zhǎng)度最短的頂點(diǎn)vj加入到集合S中，集合S中每加入一個(gè)新的頂點(diǎn)vj都要修改從源點(diǎn)vi到VS集合中剩余頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度值，集合VS中各頂點(diǎn)的新的當(dāng)前最短路徑長(zhǎng)度值，為原來(lái)的最短路徑長(zhǎng)度值與從源點(diǎn)經(jīng)過(guò)頂點(diǎn)vj到達(dá)該頂點(diǎn)的路徑長(zhǎng)度中的較小者。此過(guò)程不斷重復(fù)，直到集合V中的全部頂點(diǎn)都加入到集合S中[12]。

1.2 Dijkstra算法在TSP問(wèn)題中的改進(jìn)應(yīng)用

由于Dijkstra算法是單源最短路徑算法，該算法不能解決全通拓?fù)浣Y(jié)構(gòu)圖中的TSP問(wèn)題，故只利用該算法尋找局部最短路徑，從而形成全局最優(yōu)路徑。

假設(shè)集合S1存放已經(jīng)找到最短路徑的頂點(diǎn)，開(kāi)始時(shí)，利用Dijkstra算法得出起點(diǎn)v0到所有景點(diǎn)的最短距離，然后，找到最短距離中的最小數(shù)值

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

并把i并入到集合S1中，在以j為起點(diǎn)再利用Dijkstra算法計(jì)算到集合VS1所有最距離中的最小值，直到集合VS1為空集為止。其實(shí)現(xiàn)流程如圖1所示，實(shí)現(xiàn)步驟如下。

步驟1 初始時(shí)，S1只包含起點(diǎn)v0，VS1包含除v0外的其他頂點(diǎn)。然后，執(zhí)行Dijkstra算法，得到從v0出發(fā)到其余各頂點(diǎn)可能達(dá)到的最短路徑長(zhǎng)度的初值為

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

步驟2 選擇vj，使

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

vj就是當(dāng)前求得的一條從v0出發(fā)的最短路徑的終點(diǎn)，將vj并入集合S1。

步驟3 令以vj為出發(fā)點(diǎn)，執(zhí)行Dijkstra算法，得到{dist[i]|(vi∈VS)}。

步驟4 重復(fù)步驟2和步驟3，直至集合VS1為空集，依次輸出各景點(diǎn)序號(hào)，形成每相鄰兩景點(diǎn)都是最小距離的旅游線(xiàn)路。

圖1 程序流程

2 案例背景及實(shí)際數(shù)據(jù)

2.1 案例背景

西安市旅游資源豐富，自駕游發(fā)展勢(shì)頭強(qiáng)勁。為使研究樣本具有代表性，通過(guò)對(duì)西安自駕車(chē)游客訪(fǎng)談，選定西安市及其周邊深受自駕車(chē)游客喜愛(ài)的10個(gè)景點(diǎn)分析，這10個(gè)景點(diǎn)為鐘樓(與鼓樓、回民街、城墻列為一處景點(diǎn))、乾陵、法門(mén)寺、碑林、陜西歷史博物館、大雁塔、大唐芙蓉園、兵馬俑、華清池、華山，并分別記為Xi(i=1,2,…,10)。

假定自駕游均以私家車(chē)為交通工具，以高速公路和非高速公路為主要道路，車(chē)速一定，路況通暢，天氣等一切突發(fā)情況不納入考慮范圍，同時(shí)默認(rèn)各景點(diǎn)之間回程與去程有多條路徑。

2.2 數(shù)據(jù)來(lái)源

2.2.1 旅游景點(diǎn)加權(quán)圖

利用Dijkstra算法進(jìn)行線(xiàn)路優(yōu)化設(shè)計(jì)時(shí)，首先需將旅游地圖轉(zhuǎn)化為加權(quán)有向圖。本文對(duì)加權(quán)有向圖做了調(diào)整，圖中只標(biāo)出線(xiàn)路，具體權(quán)值在下文給出。將每個(gè)旅游景點(diǎn)看作加權(quán)有向圖的一個(gè)節(jié)點(diǎn)，景點(diǎn)間的交通線(xiàn)路作為邊，各景點(diǎn)間的距離(或行程時(shí)間、交通費(fèi)用)是對(duì)應(yīng)邊的權(quán)值。

2.2.2 旅游景點(diǎn)線(xiàn)路權(quán)值

(1) 距離權(quán)值

利用ArcGIS軟件，首先將景點(diǎn)間的線(xiàn)路進(jìn)行數(shù)字化處理，其次通過(guò)舍遠(yuǎn)取近法找出最短線(xiàn)路，最后利用比例尺轉(zhuǎn)化得到景點(diǎn)間具體距離。最終得出距離權(quán)值表(表1)。

表1 景點(diǎn)間距離權(quán)值表 /km

注 只考慮各景點(diǎn)之間的距離，而景區(qū)內(nèi)的距離未列入考慮范圍。

(2) 時(shí)間權(quán)值

前文已假定車(chē)速一定，路況良好，可由各景點(diǎn)間的實(shí)際距離計(jì)算出其交通時(shí)間，從而將時(shí)間最短問(wèn)題表現(xiàn)為具體路徑問(wèn)題。但最近的線(xiàn)路未必是最省時(shí)的，比如存在道路崎嶇、彎道較多不易于行駛等問(wèn)題。故本文權(quán)衡景點(diǎn)間各條線(xiàn)路的路況、距離、實(shí)際情況等選擇線(xiàn)路，以保證路途中用時(shí)是最少的。最終得出時(shí)間權(quán)值表(表2)。

表2 景點(diǎn)間駕車(chē)時(shí)間權(quán)值表/min

注 只考慮各景點(diǎn)之間的交通時(shí)間，而景區(qū)內(nèi)的游玩時(shí)間未列入考慮范圍。

(3) 費(fèi)用權(quán)值

旅游費(fèi)用涵蓋“食住行游購(gòu)?qiáng)省?方面，其中只有“行”是比較可控的，其余5項(xiàng)因主觀性較大、不確定因素多、與所訪(fǎng)景點(diǎn)次序無(wú)關(guān)等因素而不考慮。交通費(fèi)用與公路等級(jí)、燃油費(fèi)等有關(guān)，本文按照高速公路0.6 元/車(chē)·km及燃油費(fèi)0.7 元/車(chē)·km的標(biāo)準(zhǔn)計(jì)算，同樣將無(wú)形的費(fèi)用問(wèn)題轉(zhuǎn)化為具體路徑問(wèn)題。首先根據(jù)景點(diǎn)間的線(xiàn)路分別計(jì)算出所需的交通費(fèi)用，再結(jié)合所花交通費(fèi)用最少的原則確定線(xiàn)路，最終得出費(fèi)用權(quán)值表(表3)。

表3 交通費(fèi)用權(quán)值表/元

3 算法應(yīng)用

利用上述景點(diǎn)間距離、駕車(chē)時(shí)間、交通費(fèi)用等數(shù)據(jù)，在C語(yǔ)言環(huán)境中運(yùn)行所改進(jìn)的程序進(jìn)行線(xiàn)路設(shè)計(jì)，得到如下結(jié)果。

3.1 最短路程路線(xiàn)

當(dāng)不限定交通費(fèi)用與時(shí)間、只考慮最少駕車(chē)路程時(shí)，最佳旅游線(xiàn)路是

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

相對(duì)應(yīng)線(xiàn)路為

鐘樓→碑林→陜西歷史博物館→
大雁塔→大唐芙蓉園→兵馬俑→
華清池→華山→乾陵→法門(mén)寺。

該線(xiàn)路行程共354.3 km。

3.2 最省時(shí)間路線(xiàn)

當(dāng)不限定交通費(fèi)用與路程時(shí)、只考慮所用駕車(chē)時(shí)間最少時(shí)，最佳旅游線(xiàn)路是

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

相對(duì)應(yīng)線(xiàn)路為

鐘樓→碑林→陜西歷史博物館→
大唐芙蓉園→大雁塔→兵馬俑→
華清池→華山→乾陵→法門(mén)寺。

該線(xiàn)路途中用時(shí)373 mins。

3.3 費(fèi)用最少路線(xiàn)

當(dāng)不限定時(shí)間和路程、只考慮交通費(fèi)用最少問(wèn)題時(shí)，最佳旅游線(xiàn)路是

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

相對(duì)應(yīng)線(xiàn)路為

鐘樓→碑林→陜西歷史博物館→
大雁塔→大唐芙蓉園→華清池→
兵馬俑→華山→乾陵→法門(mén)寺。

該線(xiàn)路駕車(chē)交通費(fèi)用為 289.7 元。

4 結(jié)語(yǔ)

將Dijkstra算法應(yīng)用到自駕游線(xiàn)路設(shè)計(jì)中，所設(shè)計(jì)的線(xiàn)路可滿(mǎn)足自駕車(chē)游客的需求，方法具有普適性且實(shí)現(xiàn)簡(jiǎn)單。未來(lái)應(yīng)用中，可建立全國(guó)最優(yōu)旅游路徑網(wǎng)站或旅游線(xiàn)路查詢(xún)決策系統(tǒng)。旅游區(qū)旅游線(xiàn)路的開(kāi)發(fā)水平、完善程度，起到把握控制旅游流的流量、流向的作用，因此，相關(guān)結(jié)果可擴(kuò)展到區(qū)域旅游交通規(guī)劃和景區(qū)內(nèi)道路設(shè)計(jì)等實(shí)際應(yīng)用方面，可據(jù)實(shí)際需要進(jìn)行改進(jìn)，為旅游相關(guān)部門(mén)提供決策支持。據(jù)此最優(yōu)路徑制定的旅游開(kāi)發(fā)戰(zhàn)略可推動(dòng)沿線(xiàn)地區(qū)旅游業(yè)的進(jìn)步，對(duì)區(qū)域經(jīng)濟(jì)的發(fā)展具有深遠(yuǎn)意義。

[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] 滕聰,曹文.旅游景點(diǎn)篩選組合及旅游線(xiàn)路的優(yōu)化算法與應(yīng)用[J].地球信息科學(xué)學(xué)報(bào), 2010,12(5):668-673.

[3] 許麗佳,蒲海波,蔣宏健.改進(jìn)遺傳算法的路徑規(guī)劃研究[J].微計(jì)算機(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] 高尚. 求解旅行商問(wèn)題的模擬退火算法[J].華東船舶工業(yè)學(xué)院學(xué)報(bào),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] 王潮, 宣國(guó)榮.人工神經(jīng)網(wǎng)絡(luò)求解TSP問(wèn)題新方法[J].計(jì)算機(jī)應(yīng)用與軟件,2001,18(4):59-64.

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

[10] 陸鋒. 最短路徑算法: 分類(lèi)體系與研究進(jìn)展[J]. 測(cè)繪學(xué)報(bào), 2001, 30(3):269-275.

[11] 吳凱. 旅游線(xiàn)路設(shè)計(jì)與優(yōu)化中的運(yùn)籌學(xué)問(wèn)題[J]. 旅游科學(xué), 2004, 18(1):41-44.

[12] 熊回香.數(shù)據(jù)結(jié)構(gòu):C/C++版[M].北京:清華大學(xué)出版社,2010:292-302.

[責(zé)任編輯:王輝]

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

陜西省社會(huì)科學(xué)基金資助項(xiàng)目(13Q045)

樊守偉(1988-)，女，碩士研究生，研究方向?yàn)槁糜尉皡^(qū)規(guī)劃與管理。E-mail：1025443824@qq.com 嚴(yán)艷(1968-)，女，博士，副教授，從事旅游管理與人文地理等研究。E-mail：yanyan@snnu.edu.cn

F590

A

2095-6533(2014)01-0121-04