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

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

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

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

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

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

Dijkstra算法；自駕游；旅游線路

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

TSP問題可通過多種方法解決。最容易的方法是窮舉法，但當(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)能力較差等問題，所以當(dāng)針對(duì)一些特殊問題時(shí)，常規(guī)遺傳算法并不一定是最佳選擇。蟻群算法是由Dorigo提出，在解決TSP問題中得到廣泛應(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)化問題的算法[5]。該算法具有較強(qiáng)的局部尋優(yōu)能力，并能使搜索過程避免陷入局部最優(yōu)解；但它把握整個(gè)搜索過程的能力不夠，不僅使得模擬退火的運(yùn)算效率不高，而且也難以控制參數(shù)溫度的初始值、退火速度問題、溫度管理等問題[6]。Hopfield和Tank于1985年利用人工神經(jīng)網(wǎng)絡(luò)求解TSP問題[7]。該算法在大多數(shù)情況下可以求出最優(yōu)解的近似解；但當(dāng)城市數(shù)大于30時(shí)，其求解結(jié)果不太令人滿意；當(dāng)城市規(guī)模更大時(shí)，易于收斂到非法解或局部極小解，同時(shí)還存在收斂速度慢、對(duì)模型參數(shù)和初始條件敏感等缺點(diǎn)[8]。

而貪心算法中的Dijkstra(迪杰斯特拉)算法被認(rèn)為是目前求最短路徑問題的最好方法[9]，屬于典型的單源最短路徑算法，是交通網(wǎng)絡(luò)最短路徑算法的首選[10]，成為解決旅游交通中線路優(yōu)化設(shè)計(jì)的重要方法；但其在旅游業(yè)中的應(yīng)用并不完善，研究層次也較低[11]。故本文在Dijkstra算法基礎(chǔ)上進(jìn)行改進(jìn)，即先利用Dijkstra算法依次求出局部最優(yōu)解，然后整合得到全局最優(yōu)路徑，并以西安市周邊景點(diǎn)為例，結(jié)合自駕車游客的特點(diǎn)，對(duì)西安市周邊的自駕車旅游線路進(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)過頂點(diǎn)vj到達(dá)該頂點(diǎn)的路徑長(zhǎng)度中的較小者。此過程不斷重復(fù)，直到集合V中的全部頂點(diǎn)都加入到集合S中[12]。

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

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

假設(shè)集合S1存放已經(jīng)找到最短路徑的頂點(diǎn)，開始時(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)都是最小距離的旅游線路。

圖1 程序流程

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

2.1 案例背景

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

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

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

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

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

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

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

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

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

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

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

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

表2 景點(diǎn)間駕車時(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)因主觀性較大、不確定因素多、與所訪景點(diǎn)次序無(wú)關(guān)等因素而不考慮。交通費(fèi)用與公路等級(jí)、燃油費(fèi)等有關(guān)，本文按照高速公路0.6 元/車·km及燃油費(fèi)0.7 元/車·km的標(biāo)準(zhǔn)計(jì)算，同樣將無(wú)形的費(fèi)用問題轉(zhuǎn)化為具體路徑問題。首先根據(jù)景點(diǎn)間的線路分別計(jì)算出所需的交通費(fèi)用，再結(jié)合所花交通費(fèi)用最少的原則確定線路，最終得出費(fèi)用權(quán)值表(表3)。

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

3 算法應(yīng)用

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

3.1 最短路程路線

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

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

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

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

該線路行程共354.3 km。

3.2 最省時(shí)間路線

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

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

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

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

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

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

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

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

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

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

該線路駕車交通費(fèi)用為 289.7 元。

4 結(jié)語(yǔ)

將Dijkstra算法應(yīng)用到自駕游線路設(shè)計(jì)中，所設(shè)計(jì)的線路可滿足自駕車游客的需求，方法具有普適性且實(shí)現(xiàn)簡(jiǎn)單。未來(lái)應(yīng)用中，可建立全國(guó)最優(yōu)旅游路徑網(wǎng)站或旅游線路查詢決策系統(tǒng)。旅游區(qū)旅游線路的開發(fā)水平、完善程度，起到把握控制旅游流的流量、流向的作用，因此，相關(guān)結(jié)果可擴(kuò)展到區(qū)域旅游交通規(guī)劃和景區(qū)內(nèi)道路設(shè)計(jì)等實(shí)際應(yīng)用方面，可據(jù)實(shí)際需要進(jìn)行改進(jìn)，為旅游相關(guān)部門提供決策支持。據(jù)此最優(yōu)路徑制定的旅游開發(fā)戰(zhàn)略可推動(dòng)沿線地區(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)篩選組合及旅游線路的優(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] 高尚. 求解旅行商問題的模擬退火算法[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問題新方法[J].計(jì)算機(jī)應(yīng)用與軟件,2001,18(4):59-64.

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

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

[11] 吳凱. 旅游線路設(shè)計(jì)與優(yōu)化中的運(yùn)籌學(xué)問題[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