基于Dijkstra算法的地鐵出行路線規劃系統的設計與實現

馬靜 劉江岳

摘要：城市地鐵已經成為許多居民出行的首選交通工具，但在一些大城市中，復雜龐大的地鐵網絡給出行者的線路選擇和換乘帶來了許多不便[1]。為了解決在日趨復雜的地鐵網中找出最優路徑這一問題，文章介紹的項目基于改進的Dijkstra算法，充分考慮了用戶需求，設計了地鐵出行線路規劃系統，實現了多種路線規劃模式，能夠科學、高效地規劃出最優路線。

關鍵詞：改進Dijkstra算法;軌道交通;地鐵;路線規劃;最優路線

中圖分類號：G434 ? ? ?文獻標識碼：A

文章編號：1009-3044（2022）13-0058-05

1 引言

最短路徑問題在計算機科學、運籌學、地理信息科學等領域中是一個研究熱點，并占有極其重要的地位[2]。隨著經濟的發展，越來越多的城市建設了地鐵作為緩解交通壓力的重要公共交通設施。但是，對于外來出行者來說，面對自己不熟悉的城市和復雜的城市地鐵線路網，乘坐地鐵會是一個難題;對于城市的本地居民來說，如何選擇最佳的地鐵乘車方案來節約寶貴的時間資源也是一個難題。明確地指引乘客乘車，有效地疏導客流在地鐵的日常運營中是十分重要的。在大城市地鐵線路網絡龐大復雜的情況下，解決上述問題的關鍵在于如何根據用戶的需求，快速且明確地指引乘客選擇最佳出行線路[3]，因此在地鐵出行路線規劃的情景下研究最短路徑算法是非常有必要的。本研究基于改進的Dijkstra算法，設計并實現了能在多種情形下查詢地鐵最優路線的地鐵出行路線規劃系統。

2 地鐵出行路線規劃軟件功能需求與可行性分析

2.1 功能需求分析

現在國內市場上不乏出行路線規劃軟件，它們有的是針對某一個城市的地鐵路線的，有的地鐵、公交等多種公共交通工具。其中它們多數為移動端應用或網頁，它們幾乎都包含了以下相似的基本模塊：1）地鐵線路圖：該模塊提供各個線路的信息，方便乘客對單條線路進行研究、查詢，同時提供高清晰的地鐵線路圖以及線路圖的放大縮小功能[4];2）乘車查詢功能：乘車查詢功能要求在眾多可行路線方案中默認提供到達目的地的最優路線方案，并將查詢結果以多媒體的方式呈現，操作程序需簡潔明了易上手[4]。該功能還包括豐富多樣的站點輸入方式，多種線路方案的選擇。

2.2 可行性分析

1）硬件可行性分析：硬件配置需求：計算機選型為配備觸摸屏的一體機，具有網絡接口、麥克風和音響設備。CPU至少為1.8GHz Intel處理器，內存至少為1GB，硬盤具有30MB以上空余。其安裝的操作系統最低為64位的Windows 7系統，并且.Net framework的版本最低為4.5.1。

2）軟件可行性分析：地鐵出行路線規劃系統的后臺數據，即站點數、站點名稱、站點坐標、地鐵線路及其包含的各個站點等信息存儲于外部txt格式文件中，程序將按行從中讀取數據。這樣的外部存儲方式使得本系統有很高的靈活性和擴展性，用戶可以自定義擴充新的地鐵線路圖，讓程序為用戶提供個性化的路線規劃服務。其中地鐵站點坐標取自于地鐵線路圖片上站點的x，y坐標。

數據存儲方式如表1所示。

文件名：城市名英文-subway.txt

該系統的軟件程序用C++編寫而成，由GUI界面、程序算法、后臺數據三個部分組成，程序結構如圖1所示。

該系統的前端包含語音輸入功能，包含路線查詢結果的語音播放功能，該功能調用了科大訊飛智能語音平臺，能夠在線使用語音輸入和語音播放，界面支持多種語言。如圖2所示，前端界面顯示了高清地鐵地圖，操作方式為手持觸屏的方式，可直接在地圖上通過單擊站點的方式設置起點與終點;可移動、放大、縮小地圖;具有語音輸入、語音播放的按鈕;當前版本有三種路徑規劃方式可選，路線規劃結果能夠詳細地列在輸出框內，同時地圖上也會直觀地用標記出規劃好的最佳路線。

系統的程序算法部分為改進的迪杰斯特拉算法，提供少停站優先、少換乘優先、周游一圈這三個模式，適應用戶的多樣化需求。

系統的后臺數據為擴展文件，可從本地文件中讀取地鐵路線信息，可從中央服務器動態獲取地鐵路線信息。

3 Dijkstra算法簡介

“最短路徑算法”用于解決最短路徑問題，其原理為：首先在路線拓撲圖中找出地點作為結點，其次將節點編號并計算出所有結點間的最短路徑，最后查找線路拓撲中兩個目標結點的最短路徑[5]。目前用于解決最短路徑問題的比較成熟的算法有Dijkstra算法、A-Star 算法、Bellman-Ford算法和Floyd算法等[2，5]。四種最短路徑算法的優缺點比較如表2所示。

其中，Dijkstra 算法由荷蘭計算機科學家狄克斯特拉于1959 年提出，是在實際中應用最多的具有代表性的最短路徑算法[3]。該算法針對具有非負權值的圖。它采用標記法按照路徑長度遞增的順序尋找最短路徑，然后通過對路徑長度迭代得到從源點到其他各目標節點的最短路徑[7]。

Dijkstra算法的基本思想是：

1）設置兩個節點的集合S和T，集合S是已經標記節點集，表示已經找到最短路徑的節點，集合T是未標記節點集合，表示未找到最短路徑的節點[7]。

2）初始狀態時，集合S中只包含源點Vo[7]。

3）不斷從未標記節點集合T中選取到節點Vo路徑長度最短的節點Vj加入集合S中，集合S每加入一個新的節點Vj都要比較計算更新源點Vo到集合T中剩余各節點的最短路徑長度值。不斷重復此過程，直到集合T的節點全部加入集合S[7]。

為了解決Dijkstra算法的時間復雜度較高的缺點，以及為了滿足遍歷圖中所有的點這一需要，本系統做了以下改進：

1）系統使用C++語言編寫，通過C++程序運行的高效性的特點來彌補Dijkstra算法較高的時間復雜度。

2）拓展Dijkstra算法的思路，從解決兩點之間最短路徑的問題拓展到解決遍歷圖中的所有點的問題。遍歷地圖中所有站點的基本思路為，首先預處理任意兩站點間的最短距離，然后每次選擇一個尚未走過的站點，從當前點以最短路徑走到選中的這個尚未走過的站點。在選站點時需要注意在當前站點和選中站點之間不能有其他的未選站點。

4 軟件功能實現方案

綜合以上分析，本系統采用Dijkstra算法進行可靠的路徑規劃運算，利用C++語言編程實現提高程序運行效率，彌補Dijkstra算法時間復雜度較高的缺陷，并且根據出行者乘坐地鐵時的特殊情況進行規劃模式上的優化改進。

本系統還增添了多媒體接口，用戶能夠在線使用語音輸入和語音播放的功能。該語音功能采用了業界領先的科大訊飛智能語音平臺。

1）語音功能技術難點分析

語音功能部分分為三個模塊：訊飛云模塊、語音錄入模塊、語音播放模塊。

訊飛開放平臺是開放的智能交互技術服務平臺，提供了語音識別、聲紋識別、自然語言處理等多項服務，讓應用產品具備 “聽說讀寫”的功能[8]。

在訊飛云模塊，首先通過引入訊飛SDK的lib文件來間接調用語音函數：

#ifdef _WIN64

#pragma comment（lib，"../libs/msc_x64.lib"） //x64

#else

#pragma comment（lib，"../libs/msc.lib"） //x86

#endif

然后include以下幾個頭文件：

#include "qisr.h"

#include "qtts.h"

#include "msp_cmn.h"

#include "msp_errors.h"

SoundPlayer^ player = （gcnew SoundPlayer（text））;//音頻播放器

player->SoundLocation = text;

player->Load（）;

player->Play（）;

m_soundFormat.cbSize = 0;

waveInOpen（&m_hWaveIn， WAVE_MAPPER， &m_soundFormat， （DWORD_PTR）（waveInProc）， 0， CALLBACK_FUNCTION）;

在語音錄入模塊，首先采集PCM音頻流，再將其封裝為wav格式的音頻。該模塊使用了回調函數的方法：

該模塊采集音頻的格式為：

在語音播放模塊，直接使用了System：：Media命名空間下的類SoundPlayer：

memset（&m_soundFormat， 0， sizeof（m_soundFormat））; ?//設置聲音格式

m_soundFormat.wFormatTag = WAVE_FORMAT_PCM; ?//聲音格式為裸流PCM

m_soundFormat.nChannels = 1; ?//采樣聲道數

m_soundFormat.nSamplesPerSec = 22050; ? //采樣率 22050次/秒

m_soundFormat.nAvgBytesPerSec = 22050 * 1 * 16 / 8; ? //每秒的數據率

m_soundFormat.nBlockAlign = 1 * 16 / 8; ? //一個塊的大小

m_soundFormat.wBitsPerSample = 16; ?//采樣比特

m_soundFormat.cbSize = 0;

2）路徑規劃功能

本地鐵路徑規劃系統有三種路徑規劃方式，分別是少換乘、少停站和周游一圈。

實現這三種功能的具體步驟是：

第一步：把一條地鐵線路上相鄰兩站點之間的邊設為二元組，并且這兩個站點之間用（0，1）的邊相連。

第二步：把n條地鐵線路交叉產生的一個站點看作是n個位置重合的站點，并且這些站點之間用（1，0）的邊相連。

第三步：選擇“少換乘”模式時，以整個二元組為鍵，進行Dijkstra計算，得出起點與終點間換乘次數最少的最優路徑;選擇“少停站”模式時，以二元組的第二元為鍵，進行Dijkstra計算，得出起點與終點之間站點數量最少的最優路徑。

選擇“周游一圈”模式時，首先預處理任意兩點間的最短距離，然后每次選擇一個尚未走過的點，從當前點以最短路徑走到選中的這個尚未走過的點。在選點時需要注意在當前點和選中點之間不能有其他的未選點。

少停站規劃模式的實現代碼：

int do_lessstop （std：：string s， std：：string t） {

//如果沒有設置起點或沒有設置終點，直接返回1，不繼續執行少停站的算法

if （this->mp.find（s） == this->mp.end（） || this->mp.find（t） == this->mp.end（））

{

return 1;

}

//如果設置了起點和終點，繼續執行少停站的算法

int src = this->mp[s]; //起點

int tar = this->mp[t]; //終點

//少停站模式下做dijkstra計算

PA &tmp = this->bfs（src， tar， planMode：：pm_Short）;

this->print_plan（tmp）; //輸出方案

return 0;

}

少換乘規劃模式的實現代碼：

int do_lesstrans（std：：string s， std：：string t） {

//如果沒有設置起點或沒有設置終點，直接返回1，不繼續執行少換乘的算法

if （this->mp.find（s） == this->mp.end（） || this->mp.find（t） == this->mp.end（））

{

return 1;

}

//如果設置了起點和終點，繼續執行少換乘的算法

int src = this->mp[s]; //起點

int tar = this->mp[t]; //終點

//少換乘模式下做dijkstra計算

PA &tmp = this->bfs（src， tar， planMode：：pm_convi）;

this->print_plan（tmp）; //輸出方案

return 0;

}

程序路徑規劃功能模塊的UML類圖如圖4所示。

3）軟件測試用例及測試結果

在上海地鐵地圖上，將起點設置為上海火車站，將終點設置為常熟路。

如圖5所示，使用少換乘模式規劃路線時，程序計算出的規劃方案為：換乘0次、經過6站到達目的地，程序的運算時間為0.1秒。

如圖6所示，使用少停站模式規劃路線時，程序計算出的規劃方案為：換乘2次、經過4站到達目的地，程序的運算時間為0.1秒。

如圖7所示，使用少換乘模式規劃路線時，程序計算出的規劃方案為：換乘0次、經過6站到達目的地，程序的運算時間為0.1秒。

如圖8所示，使用少停站模式規劃路線時，程序計算出的規劃方案為：換乘2次、經過4站到達目的地，程序的運算時間為0.1秒。

結果表明，使用二元組改進的Dijkstra算法能夠正確地且高效地計算出少換乘和少停站模式下的最優路線。

如圖9所示，在蘇州地鐵地圖上，以蘇州火車站為起點進行周游一圈模式的路線規劃，程序計算的規劃方案為：經過166站，換乘10次，遍歷了所有站點，同樣以蘇州火車站為終點結束蘇州地鐵周游，程序的運算時間為0.3秒。

結果表明，程序能夠正確且高效地遍歷地圖上所有站點。

5 應用前景

本系統當前應用于地鐵出行的路線規劃，也可以擴展成任何公共交通系統的出行路線規劃工具，如公交、地鐵、電車、高鐵等等。只要用戶按照存儲地鐵信息的外部txt文件的格式導入新的公共交通系統地圖，即可讓該系統提供更多的最優路線規劃服務，從而應用在更多的公共交通情景下。

本系統擴展自定義地圖后，還可以應用于停車場空車位的最優路線導航[9]，找出最優泊車路徑， 從而大大提高停車效率，改善泊車感受[10]。本系統甚至可以應用在景區、大商場、博物館中，提供“周游一圈”的服務，讓游客能夠游覽全部景點、門店或文物展品。

6 地鐵出行線路規劃系統特點與優勢

1）科學。本系統采用優化改進的Dijkstra算法進行最短路線規劃運算，程序具有科學性、可靠性。

2）高效。程序采用C++語言編寫，運行效率高，少換乘、少停站兩種規劃模式的運算均可在0.1秒完成。在具有大量站點的密集地鐵網絡中（如上海地鐵，共329站）使用周游一圈模式遍歷所有站點時，程序的運算可在10秒內完成。這說明程序在大量數據集下依舊有良好的表現，具有推廣到城市公交等大型公交網絡線路的潛力。

3）穩定。本系統不閃退、死機，加入了對于可能出現的錯誤的提示反饋機制，可以連續工作，為城市出行者提供不間斷的路線規劃服務。

4）便捷。本系統加入了多媒體接口，用戶可實現語音輸入，對于已完成規劃的路線，不僅可以在地圖上用圖例展現出具體路線方案，還可以聲音輸出具體的路線方案。本系統還可通過接入硬按鍵，捕獲用戶按下的快捷鍵來實現對應的語音輸入功能、路線規劃功能、語音播放功能等等，進而為盲人等弱勢群體提供便捷、可靠的出行路線規劃服務。

5）應用廣泛。本系統通過導入存儲站點信息的本地txt文件，可以擴展成任何公共交通系統的出行路線規劃工具，如公交、地鐵、電車、高鐵等，用途多樣、廣泛。

6）支持觸摸屏。本系統以手持設備的方法設計并實現了相關功能，使軟件可以在公共觸摸查詢臺上提供更人性化的服務。

7）功能齊全。本系統提供三種路線規劃模式，少換乘、少停站和周游一圈。其中周游一圈模式可供出行者城市觀光時使用。

8）研發歷程與項目實踐。本項目經歷了超過8個月的研發與多次的測試，并在多個地鐵出入口讓路人進行測試，目前可正式投入使用。

7 結束語

本系統通過對Dijkstra算法的合理利用與改進，將Dijkstra算法引入了地鐵查詢領域，實現了科學、穩定、高效的路線規劃功能，并且根據地鐵出行用戶的特殊需求提供了三種不同的路徑規劃模式，能夠有效節約地鐵出行者的時間資源，助力低碳出行。系統還提供了語音輸入和語音播放功能，使地鐵線路查詢變得更加智能化、人性化。該項目參加了2018年的iTeach全國大學生數字化教育創新大賽，并獲得一等獎。

參考文獻：

[1] 陳東銀，宋艷敏.Dijkstra算法在地鐵換乘中的應用[J].信息系統工程，2012（10）：83-84，108.

[2] 花玲玲.基于GIS空間分布特征的Dijkstra最短路徑算法研究[D].重慶：重慶大學，2007.

[3] 江嘉健.基于改進Dijkstra算法的地鐵線網應急乘車導引系統的設計與實現[D].廣州：華南理工大學，2013.

[4] 苑禹晨，李巖，陳琪晟，等.基于Dijkstra優化算法的多媒體地鐵綜合信息查詢系統[J].鐵路通信信號工程技術，2013，10（3）：44-48.

[5] 呂瓊藝.基于改進的Dijkstra算法的旅游規劃線路研究與實踐——以鼓浪嶼景區為例[J].柳州職業技術學院學報，2017，17（2）：32-36.

[6] 張本俊，周海嬌，劉淑琴.改進Dijkstra算法在公共交通出行的研究[J].物聯網技術，2018，8（11）：45-48.

[7] 韓慧玲，胡紅萍.Dijkstra算法在公交換乘最短路徑中的應用[J].硅谷，2011，4（21）：111，126.

[8] 魏佳.基于訊飛云的兒童語言行為發育評估系統的設計與實現[D].南寧：廣西大學，2017.

[9] 程小鳳.Dijkstra改進算法在停車場內部路徑引導中的應用[J].交通科技與經濟，2016，18（5）：26-29.

[10] 王維，蓋之華.基于Dijkstra算法的停車場泊車引導路徑設計[J].網絡安全技術與應用，2018（9）：52-53.

【通聯編輯：謝媛媛】