基于Dijkstra算法的京津冀旅游交通線路優(yōu)化研究

王 佳，趙宏麗

(燕山大學(xué) a.經(jīng)濟(jì)管理學(xué)院，b.校園建設(shè)管理處 河北 秦皇島 066004）

當(dāng)前，京津冀已成為繼“長三角”、“珠三角”之后的又一最具活力的經(jīng)濟(jì)增長極，3省市經(jīng)濟(jì)一體化進(jìn)程已不斷向縱深推進(jìn)。3省市簽署的規(guī)劃、交通、旅游一體化合作協(xié)議，打破了長期以來在上述領(lǐng)域3地各自為戰(zhàn)的格局，京津冀區(qū)域相互依存、資源共享、一體化發(fā)展取得實(shí)質(zhì)進(jìn)展，其中交通無障礙是區(qū)域旅游一體化的基礎(chǔ)和保障。

旅游交通是為旅游者由客源地到旅游目的地的往返，以及在旅游目的地各處旅游活動(dòng)而提供的交通設(shè)施及服務(wù)，其便利程度，是衡量旅游業(yè)發(fā)達(dá)程度的重要標(biāo)志，在食、住、行、游、購、娛等旅游活動(dòng)六大要素中，屬于先決條件，對(duì)旅游活動(dòng)能否順利進(jìn)行起著決定性的作用。對(duì)于游客來講，立足于最小的時(shí)間與經(jīng)濟(jì)成本獲得最多的旅游體驗(yàn)；對(duì)于旅游組織者來講，立足于最小的組織成本與最大的效益，而如何使線路通達(dá)性與組織成本之間獲得平衡，達(dá)到性價(jià)比最優(yōu)，成為旅游交通系統(tǒng)優(yōu)化的重要指標(biāo)。本文基于運(yùn)籌學(xué)中的Dijkstra算法，尋找最優(yōu)化的旅游交通線路，實(shí)現(xiàn)3省市之間交通的無縫對(duì)接與交通的無障礙，促進(jìn)旅游經(jīng)濟(jì)一體化進(jìn)程的加速。

1 研究方法

1.1 Dijkstra算法

Dijkstra(迪杰斯特拉)算法于1959年提出，是典型的單源最短路徑算法，多用于解決指定兩點(diǎn)vs，vt間的最短路，或從指定點(diǎn)vs到其余各點(diǎn)的最短路,目前被認(rèn)為是求無負(fù)權(quán)網(wǎng)絡(luò)最短路問題的最好方法。Dijkstra算法一般的表述通常有兩種方式，一種用永久性標(biāo)號(hào)P和臨時(shí)標(biāo)號(hào)T方式，一種是用OPEN,CLOSE表示的方式，本文采用永久和臨時(shí)標(biāo)號(hào)的方式。

1.2 研究思路

Dijkstra算法是基于以下原理：若序列｛vs,v1,…,,｝是從到的最短路，則序列｛vs,v1,…,vn-1｝是從到的最短路。

步驟如下：

（1）給 vs以 P 標(biāo)號(hào)，P(vs)=0，其余各點(diǎn)均給 T 標(biāo)號(hào)，T(vi)=+∞。

（2）若 vi點(diǎn)為剛得到 P 標(biāo)號(hào)的點(diǎn)，考慮這樣的點(diǎn) vj：（vi，vj）屬于E，且vj為T標(biāo)號(hào)。對(duì)vj的T標(biāo)號(hào)進(jìn)行更改：T(vj)=min[T(vj),P(vi)+lij]。

（3）比較所有具有T標(biāo)號(hào)的點(diǎn)，把最小者改為P標(biāo)號(hào)，即：P)=min[T(vi)]，當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為標(biāo)號(hào)。若全部點(diǎn)均為P標(biāo)號(hào)則停止。否則用代vi轉(zhuǎn)回。

2 研究過程

2.1 研究的數(shù)據(jù)

本文研究的京津冀各城市以交通線路節(jié)點(diǎn)表示，各個(gè)節(jié)點(diǎn)的代碼見表1所示。各城市間的線路距離數(shù)據(jù)見表2所示：

2.2 Dijkstra算法求解節(jié)點(diǎn)之間的最優(yōu)路線

表2 京津冀旅游交通線路距離矩陣 單位：（km）

下面用Dijkstra算法求解京津冀各城市間的旅游交通線路的最短路，使游客在游覽時(shí)用最少的時(shí)間，最小的成本，獲得最多的旅游體驗(yàn)；使旅游組織者花費(fèi)最少的組織成本，獲取最大的旅游利潤。下面以求v11（邯鄲）節(jié)點(diǎn)到v4（秦皇島）節(jié)點(diǎn)的最短路，即尋求v11到v4的最優(yōu)線路為例來研究本文的核心問題。

(1)首先給 v11以 P標(biāo)號(hào)，P(v11)=0，給其余所有點(diǎn)以 T標(biāo)號(hào)。

(2)由于(v11,v10),(v11,v9),(v11,v7),(v11,v12)邊屬于 E，且 v9，v10，v7，v12為T標(biāo)號(hào)，所以修改這四個(gè)節(jié)點(diǎn)的標(biāo)號(hào)：

(3)比較所有T標(biāo)號(hào)，T(v10)最小，所以令P(v10)=59。并記錄路徑(v11,v10)。

(4)v10為剛得到的P標(biāo)號(hào)的點(diǎn)，考察邊(v10,v1),(v10,v9),(v10,v13)的端點(diǎn)v1,vq,v13

(5)比較所有T標(biāo)號(hào)，T(v1)最小，所以令P(v1)=192。并記錄路徑(v10,v1)。

(6)v1為剛得到的P標(biāo)號(hào)的點(diǎn)，考察邊(v1,v3),(v1,v7),(v1,v8),(v1,v9)的端點(diǎn) v3，v7,v8,v9。

(7)全部T標(biāo)號(hào)中，T(v9)最小，所以令P(v9)=199。并記錄路徑(v11,v9)。

(8)v9為剛得到的P標(biāo)號(hào)的點(diǎn)，考察邊(v9,v7),(v9,v12),(v9,v13),(v9,v8)的端點(diǎn) v7,v12,v13,v8。

(9)比較所有T標(biāo)號(hào)，T(v7)最小，所以令P(v7)=330。并記錄路徑(v11,v7)。

(10)v7為剛得到的P標(biāo)號(hào)的點(diǎn)，考察邊(v7,v3),(v7,v12),(v7,v5),(v7,v13),(v7,v8)的端點(diǎn) v3,v12,v5,v13,v8。(11)比較所有T標(biāo)號(hào)，T(v8)最小，所以令P(v8)=342。并記錄路徑(v9,v8)。

(12)v8為剛得到的P標(biāo)號(hào)的點(diǎn)，考察邊(v8,v12),(v8,v13)的端點(diǎn)v12,v13。

(13)全部T標(biāo)號(hào)中，T(v13)最小，所以令P(v13)=461。并記錄路徑(v9，v13)。

(14)v13為剛得到的P標(biāo)號(hào)的點(diǎn)，考察邊(v13,v2),(v13，v5)的端點(diǎn)v2,v5。

(15)全部T標(biāo)號(hào)中，T(v12)最小，所以令P(v12)=481。并記錄路徑(v11，v12)。

(16)v12為剛得到的P標(biāo)號(hào)的點(diǎn)，考察邊(v12,v2),(v12，v6)的端點(diǎn)v2,v6。

(17)全部T標(biāo)號(hào)中，T(v6)最小，所以令P(v6)=537。并記錄路徑(v12，v6)。

(18)v6為剛得到的P標(biāo)號(hào)的點(diǎn)，考察邊(v6,v2),(v6，v5)的端點(diǎn)v2,v5。

(19)比較所有T標(biāo)號(hào)，T(v5)最小，所以令P(v5)=586。并記錄路徑(v13,v5)。

(20)v5為剛得到的P標(biāo)號(hào)的點(diǎn)，考察邊（v5，v4)的端點(diǎn)v4。

(21)全部T標(biāo)號(hào)中，T(v3)最小，所以令P(v3)=695。并記錄路徑(v7，v3)。

(22)v3為剛得到的 P 標(biāo)號(hào)的點(diǎn)，考察邊（v3，v2)，（v3，v4)的端點(diǎn) v2，v4。

(23)比較所有T標(biāo)號(hào)，T(v2)最小，所以令P(v2)=710。并記錄路徑(v12,v2)。

(24)考察 v2。

(25)因只有一個(gè) T標(biāo)號(hào) T(v4)，令P(v4)=729，記錄路徑(v5,v4)，至此全部交通節(jié)點(diǎn)均為P標(biāo)號(hào)，計(jì)算結(jié)束。按逆推法得到v11到 v4的最短路徑為 v11→v9→v13→v5→v4，線路長 P(v4)=729。全部計(jì)算結(jié)果見圖2，圖中粗線為v11到v4的最優(yōu)路線。

同理得到 v1到 v4的最短路徑為 v1→v7→v13→v5→v4。

2.3 京津冀旅游交通線路優(yōu)化的建議

完善的旅游交通體系是發(fā)展旅游業(yè)的必要前提?，F(xiàn)今旅游業(yè)的蓬勃發(fā)展，特別是旅游旺季，給現(xiàn)有的旅游交通帶來了一定的壓力。壓力的來源之一就是現(xiàn)有的交通線路設(shè)置不盡合理，沒有考慮到游客對(duì)旅游交通的實(shí)際需求。創(chuàng)造便于游覽、舒適、快捷、安全的旅游交通條件，以及“旅速游短，旅短游長，旅中有游，游旅結(jié)合”的旅游交通環(huán)境，滿足游客的需求，實(shí)現(xiàn)良好的社會(huì)效益。

（1）構(gòu)建一體化的旅游圈。構(gòu)建一體化的京津冀旅游圈層結(jié)構(gòu)，其中包括大旅游圈、旅游亞圈和重點(diǎn)旅游城市建設(shè)，使得各區(qū)域旅游業(yè)協(xié)同發(fā)展，為擴(kuò)建旅游地空間結(jié)構(gòu)提供條件。同時(shí)，形成合并旅游空間一體化，重塑新型旅游區(qū)域關(guān)系，實(shí)現(xiàn)“多贏”的區(qū)域旅游發(fā)展格局。

（2）設(shè)計(jì)合理的旅游線路。京津冀區(qū)域內(nèi)旅游線路的設(shè)計(jì)應(yīng)根據(jù)游客的旅游動(dòng)機(jī)和切身利益來設(shè)計(jì)，同時(shí)還受到其他一些因素的影響，比如，各旅游節(jié)點(diǎn)之間的直接通達(dá)性、游客使用的交通工具及旅游出行規(guī)律等都會(huì)影響旅游線路的規(guī)劃和設(shè)計(jì)。因此，應(yīng)根據(jù)最優(yōu)化線路設(shè)計(jì)原則，統(tǒng)籌設(shè)計(jì)合理的旅游線路。

（3）構(gòu)造一體化的京津冀交通網(wǎng)絡(luò)。原有的京津唐地區(qū)的天津到唐山的路線，需繞塘沽，加大了天津到唐山之間的交通成本和時(shí)間成本，為使津唐間的交通更便捷，必須要打通北辰到寧河間的路線；京津保地區(qū)的路線自霸州向南，依次經(jīng)過任丘、肅寧、深州、饒陽和衡水，就會(huì)加大京津的經(jīng)濟(jì)輻射作用。京津冀交通線路的優(yōu)化會(huì)使本區(qū)域內(nèi)的經(jīng)濟(jì)格局由原來的帶狀分布演變?yōu)榫W(wǎng)狀分布，從而加速了京津冀旅游經(jīng)濟(jì)一體化的進(jìn)程。

3 結(jié)論

交通網(wǎng)絡(luò)中的任意兩交通節(jié)點(diǎn)間的最優(yōu)路徑都可以用Dijkstra算法求到。誠然，尋找最優(yōu)的交通線路路徑主要是解決旅游交通網(wǎng)絡(luò)中的兩節(jié)點(diǎn)之間的直達(dá)路徑，若旅游組織者在組織旅游路線時(shí)倘若不考慮所經(jīng)路徑內(nèi)的其他節(jié)點(diǎn)旅游資源性質(zhì)，可以完全選擇此最優(yōu)路徑，節(jié)約組織成本，耗費(fèi)最短時(shí)間，達(dá)到最佳旅游效果。若考慮所經(jīng)路徑內(nèi)的其他節(jié)點(diǎn)資源，就應(yīng)考慮其他因素選擇最優(yōu)路線。本文引入Dijkstra算法，得到了京津冀經(jīng)濟(jì)圈內(nèi)任意兩旅游城市的最優(yōu)交通線路，為實(shí)現(xiàn)京津冀旅游經(jīng)濟(jì)一體化、交通一體化奠定了理論上的基礎(chǔ)。

[1]胡運(yùn)權(quán).運(yùn)籌學(xué)教程（第三版）[M].北京:清華大學(xué)出版社,2007.

[2]保繼剛，楚義芳.旅游地理學(xué)[M].北京:高等教育出版社,1999.

[3]王恒，李悅錚.大連市旅游交通空間結(jié)構(gòu)分析與優(yōu)化[J].海洋開發(fā)與管理，2009,（9）.

[4]鮑捷，陸林，吉中會(huì).基于最小生成樹Kruskal算法的皖北地區(qū)旅游交通優(yōu)化與線路組織[J].人文地理，2010,（3）.

[5]張聰，但文紅.黔東南州旅游交通通達(dá)性研究[J].重慶科技學(xué)院學(xué)報(bào)（社會(huì)科學(xué)版），2009,（1）.

[6]吳凱.旅游線路優(yōu)化中的運(yùn)籌學(xué)問題[D].東北財(cái)經(jīng)大學(xué)碩士學(xué)位論文，2003.

[7]翁鋼民.基于SOM網(wǎng)絡(luò)的城市居民旅游需求區(qū)域差異研究[J].統(tǒng)計(jì)與決策，2007，（24）.