基于Dijkstra算法的京津冀旅游交通線路優化研究

王 佳，趙宏麗

(燕山大學 a.經濟管理學院，b.校園建設管理處 河北 秦皇島 066004）

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

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

1 研究方法

1.1 Dijkstra算法

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

1.2 研究思路

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

步驟如下：

（1）給 vs以 P 標號，P(vs)=0，其余各點均給 T 標號，T(vi)=+∞。

（2）若 vi點為剛得到 P 標號的點，考慮這樣的點 vj：（vi，vj）屬于E，且vj為T標號。對vj的T標號進行更改：T(vj)=min[T(vj),P(vi)+lij]。

（3）比較所有具有T標號的點，把最小者改為P標號，即：P)=min[T(vi)]，當存在兩個以上最小者時，可同時改為標號。若全部點均為P標號則停止。否則用代vi轉回。

2 研究過程

2.1 研究的數據

本文研究的京津冀各城市以交通線路節點表示，各個節點的代碼見表1所示。各城市間的線路距離數據見表2所示：

2.2 Dijkstra算法求解節點之間的最優路線

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

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

(1)首先給 v11以 P標號，P(v11)=0，給其余所有點以 T標號。

(2)由于(v11,v10),(v11,v9),(v11,v7),(v11,v12)邊屬于 E，且 v9，v10，v7，v12為T標號，所以修改這四個節點的標號：

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

(4)v10為剛得到的P標號的點，考察邊(v10,v1),(v10,v9),(v10,v13)的端點v1,vq,v13

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

(6)v1為剛得到的P標號的點，考察邊(v1,v3),(v1,v7),(v1,v8),(v1,v9)的端點 v3，v7,v8,v9。

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

(8)v9為剛得到的P標號的點，考察邊(v9,v7),(v9,v12),(v9,v13),(v9,v8)的端點 v7,v12,v13,v8。

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

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

(12)v8為剛得到的P標號的點，考察邊(v8,v12),(v8,v13)的端點v12,v13。

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

(14)v13為剛得到的P標號的點，考察邊(v13,v2),(v13，v5)的端點v2,v5。

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

(16)v12為剛得到的P標號的點，考察邊(v12,v2),(v12，v6)的端點v2,v6。

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

(18)v6為剛得到的P標號的點，考察邊(v6,v2),(v6，v5)的端點v2,v5。

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

(20)v5為剛得到的P標號的點，考察邊（v5，v4)的端點v4。

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

(22)v3為剛得到的 P 標號的點，考察邊（v3，v2)，（v3，v4)的端點 v2，v4。

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

(24)考察 v2。

(25)因只有一個 T標號 T(v4)，令P(v4)=729，記錄路徑(v5,v4)，至此全部交通節點均為P標號，計算結束。按逆推法得到v11到 v4的最短路徑為 v11→v9→v13→v5→v4，線路長 P(v4)=729。全部計算結果見圖2，圖中粗線為v11到v4的最優路線。

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

2.3 京津冀旅游交通線路優化的建議

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

（1）構建一體化的旅游圈。構建一體化的京津冀旅游圈層結構，其中包括大旅游圈、旅游亞圈和重點旅游城市建設，使得各區域旅游業協同發展，為擴建旅游地空間結構提供條件。同時，形成合并旅游空間一體化，重塑新型旅游區域關系，實現“多贏”的區域旅游發展格局。

（2）設計合理的旅游線路。京津冀區域內旅游線路的設計應根據游客的旅游動機和切身利益來設計，同時還受到其他一些因素的影響，比如，各旅游節點之間的直接通達性、游客使用的交通工具及旅游出行規律等都會影響旅游線路的規劃和設計。因此，應根據最優化線路設計原則，統籌設計合理的旅游線路。

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

3 結論

交通網絡中的任意兩交通節點間的最優路徑都可以用Dijkstra算法求到。誠然，尋找最優的交通線路路徑主要是解決旅游交通網絡中的兩節點之間的直達路徑，若旅游組織者在組織旅游路線時倘若不考慮所經路徑內的其他節點旅游資源性質，可以完全選擇此最優路徑，節約組織成本，耗費最短時間，達到最佳旅游效果。若考慮所經路徑內的其他節點資源，就應考慮其他因素選擇最優路線。本文引入Dijkstra算法，得到了京津冀經濟圈內任意兩旅游城市的最優交通線路，為實現京津冀旅游經濟一體化、交通一體化奠定了理論上的基礎。

[1]胡運權.運籌學教程（第三版）[M].北京:清華大學出版社,2007.

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

[3]王恒，李悅錚.大連市旅游交通空間結構分析與優化[J].海洋開發與管理，2009,（9）.

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

[5]張聰，但文紅.黔東南州旅游交通通達性研究[J].重慶科技學院學報（社會科學版），2009,（1）.

[6]吳凱.旅游線路優化中的運籌學問題[D].東北財經大學碩士學位論文，2003.

[7]翁鋼民.基于SOM網絡的城市居民旅游需求區域差異研究[J].統計與決策，2007，（24）.