公路旅客最少換乘次數(shù)乘車方案選擇算法

李志明

（石家莊市公路工程管理處，河北 石家莊 050011）

0 引言

公路旅客從始發(fā)站至終點(diǎn)站沿途依次乘坐的列車及換乘站序列稱為旅客乘車方案[1]。在進(jìn)一步提高公路客運(yùn)效益的研究中，不論是評價(jià)旅客列車開行方案和列車運(yùn)行時(shí)刻表對旅客需求的滿足程度，還是為旅客提供中轉(zhuǎn)換乘咨詢服務(wù)，旅客乘車方案優(yōu)化都是一個(gè)十分重要的問題[2]。旅客乘車方案選擇問題是多目標(biāo)優(yōu)化問題[3－4]，但應(yīng)注意到絕大多數(shù)旅客在選擇乘車方案時(shí)，都會優(yōu)先選擇換乘次數(shù)少的乘車方案，而后才會進(jìn)一步考慮旅行時(shí)間、票價(jià)和列車等級等因素[5]，因此旅客乘車方案優(yōu)化的關(guān)鍵，是如何在為數(shù)眾多的可能乘車方案中選出換乘次數(shù)最少的乘車方案。對于公路旅客最少換乘次數(shù)乘車方案選擇問題，目前主要有兩類解決方法。一類方法是以K最短路算法在路網(wǎng)中求解兩站點(diǎn)間的最短中轉(zhuǎn)徑路集，再從最短徑路集中篩選出換乘次數(shù)少的乘車方案[1]。這類方法的實(shí)質(zhì)是先以距離最短、再以換乘次數(shù)最少為目標(biāo)分布進(jìn)行乘車方案優(yōu)選，可能導(dǎo)致?lián)Q乘次數(shù)最少但里程較長的乘車方案落選。另一類方法是先根據(jù)列車時(shí)刻表數(shù)據(jù)構(gòu)建換乘網(wǎng)絡(luò)[2]，再采用經(jīng)典的最短路徑算法搜索發(fā)、到站之間的最短路徑[3]，但這種方法不能保證找到兩站間全部的最少換乘次數(shù)乘車方案，同時(shí)算法效率有待進(jìn)一步提高。

本文在現(xiàn)有研究基礎(chǔ)上，提出一種基于改進(jìn)廣度優(yōu)先搜索算法的公路旅客乘車方案選擇算法。該算法可以一次搜索出給定發(fā)車、到站間全部的最少換乘次數(shù)乘車方案，且具有較高的搜索效率，能夠較好地解決公路旅客乘車方案優(yōu)選問題。

1 公路客運(yùn)換乘網(wǎng)絡(luò)模型

對公路客運(yùn)網(wǎng)絡(luò)進(jìn)行合適的建模是研究乘車方案選擇算法的基礎(chǔ)。早期的研究多以公路區(qū)間網(wǎng)絡(luò)為基礎(chǔ)構(gòu)建路網(wǎng)模型[6]，這種模型可用于求解最短乘車?yán)锍虖铰?，但因?yàn)闆]有列車車次信息，所以難以用于討論換乘問題[2]。近來的研究已經(jīng)注意到：換乘現(xiàn)象是存在于由列車及停靠站構(gòu)成的邏輯網(wǎng)絡(luò)中的，與公路客運(yùn)網(wǎng)絡(luò)的物理結(jié)構(gòu)并無直接關(guān)系[7]，因此可以直接從列車時(shí)刻表構(gòu)建公路客運(yùn)換乘網(wǎng)絡(luò)研究乘車方案優(yōu)選問題[2]。

公路客運(yùn)換乘網(wǎng)絡(luò)可以用三元組G進(jìn)行描述：

其中，V為公路網(wǎng)絡(luò)中所有客運(yùn)站的集合；E為客運(yùn)站之間連接邊的集合，如果旅客可乘坐某列車從車站u直達(dá)車站v，則u、v之間存在且僅存在一條邊e；Re為邊e上的列車車次集合。

上述模型是一個(gè)有向無權(quán)圖模型，具有以下幾點(diǎn)特性：

a）任意兩頂點(diǎn)之間不存在重復(fù)邊；

b）邊沒有權(quán)值，但可以通過Re找到邊e上各車次的列車等級、票價(jià)、里程等信息；

c）如果圖是連通的，則任意兩頂點(diǎn)u、v之間至少存在一條簡單路徑，其中所經(jīng)頂點(diǎn)數(shù)目最少的路徑對應(yīng)一組換乘次數(shù)最少的乘車方案。

通過采用上述數(shù)學(xué)模型描述公路客運(yùn)換乘網(wǎng)絡(luò)，將兩站之間最少換乘次數(shù)乘車方案選擇問題，轉(zhuǎn)換為在有向無權(quán)圖中搜索兩頂點(diǎn)間的最短路徑問題。

2 乘車方案選擇算法

如果令式（1）中無權(quán)圖的所有邊權(quán)值為1，則使用任一種經(jīng)典的最短路算法（如Dijkstra算法）均可完成最短路徑搜索。但對于無權(quán)圖存在效率更高的最短路徑搜索算法，即廣度優(yōu)先搜索算法[8]。本節(jié)首先給出求解換乘網(wǎng)絡(luò)中單一最短路徑的基本廣度優(yōu)先搜索算法，再對基本廣度優(yōu)先搜索算法進(jìn)行改進(jìn)，使之能夠搜索到換乘網(wǎng)絡(luò)中的全部最短路徑。

2.1 基本廣度優(yōu)先搜索算法

廣度優(yōu)先搜索算法是無權(quán)圖最短路徑搜索的一種高效算法，其基本思想是從起點(diǎn)開始，按鄰接層次順序遍歷圖中的頂點(diǎn)直至終點(diǎn)，再從終點(diǎn)回溯即可找到起終點(diǎn)間的一條最短路徑[8]。下面針對公路換乘網(wǎng)絡(luò)搜索問題，給出具體的算法步驟。

基本廣度優(yōu)先搜索算法步驟如下：

第1步：初始化，令迭代算子k＝1；輸入換乘網(wǎng)絡(luò)無權(quán)圖G、始發(fā)站頂點(diǎn)s和終點(diǎn)站頂點(diǎn)t；令s點(diǎn)的訪問狀態(tài)標(biāo)記為Ms＝k；其余頂點(diǎn)i的訪問狀態(tài)標(biāo)記為Mi＝0；

第2步：對所有M＝k的頂點(diǎn)i，順序訪問其鄰接頂點(diǎn)j；

第3步：如果j＝t，則令其前驅(qū)標(biāo)記Pt＝i，轉(zhuǎn)第6步，否則轉(zhuǎn)第4步；

第4步：如果j的訪問狀態(tài)標(biāo)記為0，則令Mj＝k＋1，Pj＝i；

第5步：令k＝k＋1，轉(zhuǎn)第2步；

第6步：從k開始通過前驅(qū)標(biāo)記Pt回溯，得到從s到t的頂點(diǎn)序列，即為s到t的最少換乘次數(shù)乘車方案，算法結(jié)束。

2.2 改進(jìn)后的廣度優(yōu)先搜索算法

在實(shí)際的客運(yùn)換乘網(wǎng)絡(luò)中，兩站間往往存在多個(gè)換乘次數(shù)相同的乘車方案，一個(gè)完善的算法應(yīng)能搜索到全部得最少換乘次數(shù)乘車方案。而基本廣度優(yōu)先搜索算法只能搜索到兩點(diǎn)間的一條最短路徑，因此有必要對其進(jìn)行改進(jìn)，使之能夠搜索兩點(diǎn)間所有的最短路徑，這一點(diǎn)對于乘車方案選擇具有重要意義。

觀察基本算法，對于每一個(gè)節(jié)點(diǎn)，基本算法僅進(jìn)行1次狀態(tài)標(biāo)記，并記載其前驅(qū)，最終生成單一的路徑。如果把標(biāo)記條件放寬，即節(jié)點(diǎn)可以被同一層次的前驅(qū)節(jié)點(diǎn)多次標(biāo)記，并記載每個(gè)前驅(qū)，則可生成多條最短路徑。據(jù)此可以給出改進(jìn)后的廣度優(yōu)先搜索算法步驟。

改進(jìn)廣度優(yōu)先搜索算法步驟如下：

第1步：初始化，令迭代算子k＝1；輸入換乘網(wǎng)絡(luò)無權(quán)圖G、始發(fā)站頂點(diǎn)s和終點(diǎn)站頂點(diǎn)t；令s點(diǎn)的訪問狀態(tài)標(biāo)記為Ms＝k；其余頂點(diǎn)i的訪問狀態(tài)標(biāo)記為Mi＝0；

第2步：對所有M＝k的頂點(diǎn)i，順序訪問其鄰接頂點(diǎn)j；

第3步：如果j＝t，則令E＝k＋1，轉(zhuǎn)第4步；

第4步：如果j的訪問狀態(tài)標(biāo)記Mj＝0，則令Mj＝k＋1，n＝0，＝i；如果j的訪問狀態(tài)標(biāo)記Mj＝k＋1，則令n＝n＋1，＝i；

第5步：令k＝k＋1，如果k＝E，轉(zhuǎn)第6步，否則轉(zhuǎn)第2步；

第6步：從t開始通過前驅(qū)標(biāo)記Pt回溯，得到從s到t的頂點(diǎn)序列，即為s到t的所有最少換乘次數(shù)乘車方案，算法結(jié)束。

3 算例

本文采用文獻(xiàn)[3]中的算例驗(yàn)證基本算法和改進(jìn)算法的正確性。

設(shè)一由6個(gè)站點(diǎn)構(gòu)成的路網(wǎng)，共有6趟列車開行，各列車車次和所經(jīng)過的站點(diǎn)序列如下：

根據(jù)上述列車開行方案，生成如圖1所示的換乘網(wǎng)絡(luò)。現(xiàn)要求計(jì)算出1、3站點(diǎn)之間的最小換乘次數(shù)乘車方案。

圖1 換乘網(wǎng)絡(luò)示意圖

根據(jù)基本廣度優(yōu)先搜索算法，所求最短路徑為1→4→3。表示從頂點(diǎn)1至3最少換乘次數(shù)乘車方案為：先乘列車V1從頂點(diǎn)1至頂點(diǎn)4，再乘列車V2從頂點(diǎn)4至頂點(diǎn)3，換乘次數(shù)為1，與文獻(xiàn)[3]中計(jì)算結(jié)果相同。

根據(jù)改進(jìn)廣度優(yōu)先搜索算法，所求最短路徑為1→4→3和1→6→3，兩者換乘次數(shù)均為1，都是換乘次數(shù)最少的乘車方案?？梢?，通過改進(jìn)廣度優(yōu)先搜索算法，可以一次搜索出換乘網(wǎng)絡(luò)中給定發(fā)、到站間全部的最少換乘次數(shù)乘車方案。

4 算法效率分析

公路旅客乘車方案選擇算法必須具有較高的執(zhí)行效率，以適應(yīng)公路客運(yùn)信息查詢、計(jì)算機(jī)聯(lián)網(wǎng)售票等應(yīng)用系統(tǒng)對算法響應(yīng)時(shí)間的要求。本節(jié)對基本廣度優(yōu)先搜索算法和改進(jìn)廣度優(yōu)先搜索算法的效率進(jìn)行分析，并與普通最短路徑算法的執(zhí)行效率進(jìn)行比較。

根據(jù)算法復(fù)雜性理論可知[8]，如果圖采用鄰接矩陣的結(jié)構(gòu)儲存，則基本廣度優(yōu)先搜索算法在最不利情況下，時(shí)間復(fù)雜度是Θ（|V|2）。在采用同樣的儲存結(jié)構(gòu)時(shí)，單源最短路徑算法——Dijkstra算法的時(shí)間復(fù)雜度也是Θ（|V|2）。表面看來基本廣度優(yōu)先搜索算法相較Dijkstra算法在效率上并無優(yōu)勢，但實(shí)際應(yīng)用中基本廣度優(yōu)先搜索算法很少在“最不利情況”下運(yùn)行。這里的“最不利情況”是指遍歷完整個(gè)網(wǎng)絡(luò)才找到終點(diǎn)，對于全路列車構(gòu)成的換乘網(wǎng)絡(luò)而言，任意兩站之間的最小換乘次數(shù)上限是5次[7]，而實(shí)際中旅客換乘次數(shù)很少超過2次[4]，因此算法實(shí)際執(zhí)行效率還是很高的。

為實(shí)際驗(yàn)證基本廣度優(yōu)先搜索算法的執(zhí)行效率，用全路客運(yùn)換乘網(wǎng)絡(luò)對其進(jìn)行測試。在根據(jù)全路列車時(shí)刻表數(shù)據(jù)生成的換乘網(wǎng)絡(luò)中隨機(jī)挑選1000對站點(diǎn)，分別用基本廣度優(yōu)先搜索算法和Dijkstra算法搜索兩站點(diǎn)間的最短路徑。算法測試的硬件平臺為Intel Centrino 1.8GHz CPU，2GB內(nèi)存，編程語言為C＋＋。算法效率對比結(jié)果見圖2。

圖2 基本廣度優(yōu)先搜索算法和Dijkstra算法效率對比

從圖2可以看出，基本廣度優(yōu)先搜索算法執(zhí)行時(shí)間與換乘次數(shù)正相關(guān)，而Dijkstra算法的執(zhí)行時(shí)間與換乘次數(shù)無關(guān)。這是因?yàn)镈ijkstra算法（事實(shí)上對所有單源最短路徑算法都是如此）在搜索起終點(diǎn)間的最短路徑時(shí)，實(shí)質(zhì)上是搜索了從起點(diǎn)到圖中所有節(jié)點(diǎn)的最短路徑，因此平均搜索效率遠(yuǎn)低于基本廣度優(yōu)先搜索算法。

進(jìn)一步分析改進(jìn)廣度優(yōu)先搜索算法的執(zhí)行效率。與基本廣度優(yōu)先搜索算法相比，改進(jìn)廣度優(yōu)先搜索算法僅多記錄了每個(gè)節(jié)點(diǎn)的前驅(qū)，因此算法時(shí)間復(fù)雜度仍是Θ（|V2|）。而采用K最短路算法搜索網(wǎng)絡(luò)中的多條最短路徑時(shí)，算法的時(shí)間復(fù)雜度是Θ（K|V2|），其中K是最短路徑的數(shù)量。同樣使用前述換乘網(wǎng)絡(luò)，對比測試在搜索全部最短路徑時(shí)，改進(jìn)廣度優(yōu)先搜索算法與K最短路算法的執(zhí)行效率，結(jié)果見圖3。

圖3 改進(jìn)廣度優(yōu)先搜索算法和K最短路算法效率對比

從圖3可以看出，在搜索起終點(diǎn)間的多條最短路徑時(shí)，改進(jìn)廣度優(yōu)先搜索算法由于根據(jù)節(jié)點(diǎn)前驅(qū)回溯最短路徑的實(shí)際時(shí)間開銷增大，效率低于基本廣度優(yōu)先搜索算法，但仍遠(yuǎn)優(yōu)于K最短路算法。

5 結(jié)語

本文對公路旅客最少換乘次數(shù)乘車方案選擇問題進(jìn)行了研究。首先建立了描述公路客運(yùn)換乘網(wǎng)絡(luò)的有向無權(quán)圖模型，將兩站之間最少換乘次數(shù)乘車方案選擇問題，轉(zhuǎn)換為在權(quán)圖中搜索兩頂點(diǎn)間的最短路徑問題。然后給出求解換乘網(wǎng)絡(luò)中單一最短路徑的基本廣度優(yōu)先搜索算法，再對基本廣度優(yōu)先搜索算法進(jìn)行改進(jìn)，使之能夠搜索到換乘網(wǎng)絡(luò)中的全部最短路徑，并通過算例驗(yàn)證了兩種算法的正確性。通過算法效率的分析和實(shí)測，本文算法在執(zhí)行效率方面明顯優(yōu)于傳統(tǒng)的最短路算法和K最短路算法，適用于公路客運(yùn)信息查詢系統(tǒng)等應(yīng)用系統(tǒng)要求。

[1]史峰，馬均培，向聯(lián)慧，等.客運(yùn)中轉(zhuǎn)徑路的換乘模型及算法[J].鐵道學(xué)報(bào)，1999，21（5）：1－4.

[2]史峰，鄧連波.旅客換乘網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)[J].鐵道科學(xué)與工程學(xué)報(bào)，2004，1（1）：78－82.

[3]江南，史峰，盧紅巖，等.鐵路旅客乘車方案優(yōu)化決策模型研究[J].鐵道學(xué)報(bào)，2007，29（3）：13－18.

[4]崔炳謀，馬鈞培，陳光偉，等.鐵路旅客旅行換乘方案優(yōu)選算法[J].中國鐵道科學(xué)，2007，28（6）：122－127.

[5]傅冬綿.交通系統(tǒng)中最少換乘算法及其實(shí)現(xiàn)[J].華僑大學(xué)學(xué)報(bào)：自然科學(xué)版，2001，22（4）：348－350.

[6]張彥.鐵路客票中轉(zhuǎn)換乘多徑路選擇問題的研究[J].鐵道運(yùn)輸與經(jīng)濟(jì)，1997，19（8）：11－13.

[7]趙偉，何紅生，林中材，等.中國鐵路客運(yùn)網(wǎng)網(wǎng)絡(luò)性質(zhì)的研究[J].物理學(xué)報(bào)，2006，55（8）：3906－3911.

[8]Weiss M A.Data structures and problem solving with C++[M].2nd ed.New Jersey: Addison Wesley,1999.511-557.