馬靜 劉江岳

摘要：城市地鐵已經(jīng)成為許多居民出行的首選交通工具，但在一些大城市中，復(fù)雜龐大的地鐵網(wǎng)絡(luò)給出行者的線路選擇和換乘帶來了許多不便[1]。為了解決在日趨復(fù)雜的地鐵網(wǎng)中找出最優(yōu)路徑這一問題，文章介紹的項(xiàng)目基于改進(jìn)的Dijkstra算法，充分考慮了用戶需求，設(shè)計(jì)了地鐵出行線路規(guī)劃系統(tǒng)，實(shí)現(xiàn)了多種路線規(guī)劃模式，能夠科學(xué)、高效地規(guī)劃出最優(yōu)路線。

關(guān)鍵詞：改進(jìn)Dijkstra算法;軌道交通;地鐵;路線規(guī)劃;最優(yōu)路線

中圖分類號：G434 ? ? ?文獻(xiàn)標(biāo)識碼：A

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

1 引言

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

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

2.1 功能需求分析

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

2.2 可行性分析

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

2）軟件可行性分析：地鐵出行路線規(guī)劃系統(tǒng)的后臺數(shù)據(jù)，即站點(diǎn)數(shù)、站點(diǎn)名稱、站點(diǎn)坐標(biāo)、地鐵線路及其包含的各個(gè)站點(diǎn)等信息存儲于外部txt格式文件中，程序?qū)葱袕闹凶x取數(shù)據(jù)。這樣的外部存儲方式使得本系統(tǒng)有很高的靈活性和擴(kuò)展性，用戶可以自定義擴(kuò)充新的地鐵線路圖，讓程序?yàn)橛脩籼峁﹤€(gè)性化的路線規(guī)劃服務(wù)。其中地鐵站點(diǎn)坐標(biāo)取自于地鐵線路圖片上站點(diǎn)的x，y坐標(biāo)。

數(shù)據(jù)存儲方式如表1所示。

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

該系統(tǒng)的軟件程序用C++編寫而成，由GUI界面、程序算法、后臺數(shù)據(jù)三個(gè)部分組成，程序結(jié)構(gòu)如圖1所示。

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

系統(tǒng)的程序算法部分為改進(jìn)的迪杰斯特拉算法，提供少停站優(yōu)先、少換乘優(yōu)先、周游一圈這三個(gè)模式，適應(yīng)用戶的多樣化需求。

系統(tǒng)的后臺數(shù)據(jù)為擴(kuò)展文件，可從本地文件中讀取地鐵路線信息，可從中央服務(wù)器動態(tài)獲取地鐵路線信息。

3 Dijkstra算法簡介

“最短路徑算法”用于解決最短路徑問題，其原理為：首先在路線拓?fù)鋱D中找出地點(diǎn)作為結(jié)點(diǎn)，其次將節(jié)點(diǎn)編號并計(jì)算出所有結(jié)點(diǎn)間的最短路徑，最后查找線路拓?fù)渲袃蓚€(gè)目標(biāo)結(jié)點(diǎn)的最短路徑[5]。目前用于解決最短路徑問題的比較成熟的算法有Dijkstra算法、A-Star 算法、Bellman-Ford算法和Floyd算法等[2，5]。四種最短路徑算法的優(yōu)缺點(diǎn)比較如表2所示。

其中，Dijkstra 算法由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959 年提出，是在實(shí)際中應(yīng)用最多的具有代表性的最短路徑算法[3]。該算法針對具有非負(fù)權(quán)值的圖。它采用標(biāo)記法按照路徑長度遞增的順序?qū)ふ易疃搪窂?，然后通過對路徑長度迭代得到從源點(diǎn)到其他各目標(biāo)節(jié)點(diǎn)的最短路徑[7]。

Dijkstra算法的基本思想是：

1）設(shè)置兩個(gè)節(jié)點(diǎn)的集合S和T，集合S是已經(jīng)標(biāo)記節(jié)點(diǎn)集，表示已經(jīng)找到最短路徑的節(jié)點(diǎn)，集合T是未標(biāo)記節(jié)點(diǎn)集合，表示未找到最短路徑的節(jié)點(diǎn)[7]。

2）初始狀態(tài)時(shí)，集合S中只包含源點(diǎn)Vo[7]。

3）不斷從未標(biāo)記節(jié)點(diǎn)集合T中選取到節(jié)點(diǎn)Vo路徑長度最短的節(jié)點(diǎn)Vj加入集合S中，集合S每加入一個(gè)新的節(jié)點(diǎn)Vj都要比較計(jì)算更新源點(diǎn)Vo到集合T中剩余各節(jié)點(diǎn)的最短路徑長度值。不斷重復(fù)此過程，直到集合T的節(jié)點(diǎn)全部加入集合S[7]。

為了解決Dijkstra算法的時(shí)間復(fù)雜度較高的缺點(diǎn)，以及為了滿足遍歷圖中所有的點(diǎn)這一需要，本系統(tǒng)做了以下改進(jìn)：

1）系統(tǒng)使用C++語言編寫，通過C++程序運(yùn)行的高效性的特點(diǎn)來彌補(bǔ)Dijkstra算法較高的時(shí)間復(fù)雜度。

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

4 軟件功能實(shí)現(xiàn)方案

綜合以上分析，本系統(tǒng)采用Dijkstra算法進(jìn)行可靠的路徑規(guī)劃運(yùn)算，利用C++語言編程實(shí)現(xiàn)提高程序運(yùn)行效率，彌補(bǔ)Dijkstra算法時(shí)間復(fù)雜度較高的缺陷，并且根據(jù)出行者乘坐地鐵時(shí)的特殊情況進(jìn)行規(guī)劃模式上的優(yōu)化改進(jìn)。

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

1）語音功能技術(shù)難點(diǎn)分析

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

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

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

#ifdef _WIN64

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

#else

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

#endif

然后include以下幾個(gè)頭文件：

#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格式的音頻。該模塊使用了回調(diào)函數(shù)的方法：

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

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

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

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

m_soundFormat.nChannels = 1; ?//采樣聲道數(shù)

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

m_soundFormat.nAvgBytesPerSec = 22050 * 1 * 16 / 8; ? //每秒的數(shù)據(jù)率

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

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

m_soundFormat.cbSize = 0;

2）路徑規(guī)劃功能

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

實(shí)現(xiàn)這三種功能的具體步驟是：

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

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

第三步：選擇“少換乘”模式時(shí)，以整個(gè)二元組為鍵，進(jìn)行Dijkstra計(jì)算，得出起點(diǎn)與終點(diǎn)間換乘次數(shù)最少的最優(yōu)路徑;選擇“少停站”模式時(shí)，以二元組的第二元為鍵，進(jìn)行Dijkstra計(jì)算，得出起點(diǎn)與終點(diǎn)之間站點(diǎn)數(shù)量最少的最優(yōu)路徑。

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

少停站規(guī)劃模式的實(shí)現(xiàn)代碼：

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

//如果沒有設(shè)置起點(diǎn)或沒有設(shè)置終點(diǎn)，直接返回1，不繼續(xù)執(zhí)行少停站的算法

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

{

return 1;

}

//如果設(shè)置了起點(diǎn)和終點(diǎn)，繼續(xù)執(zhí)行少停站的算法

int src = this->mp[s]; //起點(diǎn)

int tar = this->mp[t]; //終點(diǎn)

//少停站模式下做dijkstra計(jì)算

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

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

return 0;

}

少換乘規(guī)劃模式的實(shí)現(xiàn)代碼：

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

//如果沒有設(shè)置起點(diǎn)或沒有設(shè)置終點(diǎn)，直接返回1，不繼續(xù)執(zhí)行少換乘的算法

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

{

return 1;

}

//如果設(shè)置了起點(diǎn)和終點(diǎn)，繼續(xù)執(zhí)行少換乘的算法

int src = this->mp[s]; //起點(diǎn)

int tar = this->mp[t]; //終點(diǎn)

//少換乘模式下做dijkstra計(jì)算

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

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

return 0;

}

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

3）軟件測試用例及測試結(jié)果

在上海地鐵地圖上，將起點(diǎn)設(shè)置為上?；疖囌?，將終點(diǎn)設(shè)置為常熟路。

如圖5所示，使用少換乘模式規(guī)劃路線時(shí)，程序計(jì)算出的規(guī)劃方案為：換乘0次、經(jīng)過6站到達(dá)目的地，程序的運(yùn)算時(shí)間為0.1秒。

如圖6所示，使用少停站模式規(guī)劃路線時(shí)，程序計(jì)算出的規(guī)劃方案為：換乘2次、經(jīng)過4站到達(dá)目的地，程序的運(yùn)算時(shí)間為0.1秒。

如圖7所示，使用少換乘模式規(guī)劃路線時(shí)，程序計(jì)算出的規(guī)劃方案為：換乘0次、經(jīng)過6站到達(dá)目的地，程序的運(yùn)算時(shí)間為0.1秒。

如圖8所示，使用少停站模式規(guī)劃路線時(shí)，程序計(jì)算出的規(guī)劃方案為：換乘2次、經(jīng)過4站到達(dá)目的地，程序的運(yùn)算時(shí)間為0.1秒。

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

如圖9所示，在蘇州地鐵地圖上，以蘇州火車站為起點(diǎn)進(jìn)行周游一圈模式的路線規(guī)劃，程序計(jì)算的規(guī)劃方案為：經(jīng)過166站，換乘10次，遍歷了所有站點(diǎn)，同樣以蘇州火車站為終點(diǎn)結(jié)束蘇州地鐵周游，程序的運(yùn)算時(shí)間為0.3秒。

結(jié)果表明，程序能夠正確且高效地遍歷地圖上所有站點(diǎn)。

5 應(yīng)用前景

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

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

6 地鐵出行線路規(guī)劃系統(tǒng)特點(diǎn)與優(yōu)勢

1）科學(xué)。本系統(tǒng)采用優(yōu)化改進(jìn)的Dijkstra算法進(jìn)行最短路線規(guī)劃運(yùn)算，程序具有科學(xué)性、可靠性。

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

3）穩(wěn)定。本系統(tǒng)不閃退、死機(jī)，加入了對于可能出現(xiàn)的錯(cuò)誤的提示反饋機(jī)制，可以連續(xù)工作，為城市出行者提供不間斷的路線規(guī)劃服務(wù)。

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

5）應(yīng)用廣泛。本系統(tǒng)通過導(dǎo)入存儲站點(diǎn)信息的本地txt文件，可以擴(kuò)展成任何公共交通系統(tǒng)的出行路線規(guī)劃工具，如公交、地鐵、電車、高鐵等，用途多樣、廣泛。

6）支持觸摸屏。本系統(tǒng)以手持設(shè)備的方法設(shè)計(jì)并實(shí)現(xiàn)了相關(guān)功能，使軟件可以在公共觸摸查詢臺上提供更人性化的服務(wù)。

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

8）研發(fā)歷程與項(xiàng)目實(shí)踐。本項(xiàng)目經(jīng)歷了超過8個(gè)月的研發(fā)與多次的測試，并在多個(gè)地鐵出入口讓路人進(jìn)行測試，目前可正式投入使用。

7 結(jié)束語

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

參考文獻(xiàn)：

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

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

[3] 江嘉健.基于改進(jìn)Dijkstra算法的地鐵線網(wǎng)應(yīng)急乘車導(dǎo)引系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].廣州：華南理工大學(xué)，2013.

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

[5] 呂瓊藝.基于改進(jìn)的Dijkstra算法的旅游規(guī)劃線路研究與實(shí)踐——以鼓浪嶼景區(qū)為例[J].柳州職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2017，17（2）：32-36.

[6] 張本俊，周海嬌，劉淑琴.改進(jìn)Dijkstra算法在公共交通出行的研究[J].物聯(lián)網(wǎng)技術(shù)，2018，8（11）：45-48.

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

[8] 魏佳.基于訊飛云的兒童語言行為發(fā)育評估系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].南寧：廣西大學(xué)，2017.

[9] 程小鳳.Dijkstra改進(jìn)算法在停車場內(nèi)部路徑引導(dǎo)中的應(yīng)用[J].交通科技與經(jīng)濟(jì)，2016，18（5）：26-29.

[10] 王維，蓋之華.基于Dijkstra算法的停車場泊車引導(dǎo)路徑設(shè)計(jì)[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2018（9）：52-53.

【通聯(lián)編輯：謝媛媛】