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

李志明

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

0 引言

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

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

1 公路客運換乘網絡模型

對公路客運網絡進行合適的建模是研究乘車方案選擇算法的基礎。早期的研究多以公路區間網絡為基礎構建路網模型[6]，這種模型可用于求解最短乘車里程徑路，但因為沒有列車車次信息，所以難以用于討論換乘問題[2]。近來的研究已經注意到：換乘現象是存在于由列車及停靠站構成的邏輯網絡中的，與公路客運網絡的物理結構并無直接關系[7]，因此可以直接從列車時刻表構建公路客運換乘網絡研究乘車方案優選問題[2]。

公路客運換乘網絡可以用三元組G進行描述：

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

上述模型是一個有向無權圖模型，具有以下幾點特性：

a）任意兩頂點之間不存在重復邊；

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

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

通過采用上述數學模型描述公路客運換乘網絡，將兩站之間最少換乘次數乘車方案選擇問題，轉換為在有向無權圖中搜索兩頂點間的最短路徑問題。

2 乘車方案選擇算法

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

2.1 基本廣度優先搜索算法

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

基本廣度優先搜索算法步驟如下：

第1步：初始化，令迭代算子k＝1；輸入換乘網絡無權圖G、始發站頂點s和終點站頂點t；令s點的訪問狀態標記為Ms＝k；其余頂點i的訪問狀態標記為Mi＝0；

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

第3步：如果j＝t，則令其前驅標記Pt＝i，轉第6步，否則轉第4步；

第4步：如果j的訪問狀態標記為0，則令Mj＝k＋1，Pj＝i；

第5步：令k＝k＋1，轉第2步；

第6步：從k開始通過前驅標記Pt回溯，得到從s到t的頂點序列，即為s到t的最少換乘次數乘車方案，算法結束。

2.2 改進后的廣度優先搜索算法

在實際的客運換乘網絡中，兩站間往往存在多個換乘次數相同的乘車方案，一個完善的算法應能搜索到全部得最少換乘次數乘車方案。而基本廣度優先搜索算法只能搜索到兩點間的一條最短路徑，因此有必要對其進行改進，使之能夠搜索兩點間所有的最短路徑，這一點對于乘車方案選擇具有重要意義。

觀察基本算法，對于每一個節點，基本算法僅進行1次狀態標記，并記載其前驅，最終生成單一的路徑。如果把標記條件放寬，即節點可以被同一層次的前驅節點多次標記，并記載每個前驅，則可生成多條最短路徑。據此可以給出改進后的廣度優先搜索算法步驟。

改進廣度優先搜索算法步驟如下：

第1步：初始化，令迭代算子k＝1；輸入換乘網絡無權圖G、始發站頂點s和終點站頂點t；令s點的訪問狀態標記為Ms＝k；其余頂點i的訪問狀態標記為Mi＝0；

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

第3步：如果j＝t，則令E＝k＋1，轉第4步；

第4步：如果j的訪問狀態標記Mj＝0，則令Mj＝k＋1，n＝0，＝i；如果j的訪問狀態標記Mj＝k＋1，則令n＝n＋1，＝i；

第5步：令k＝k＋1，如果k＝E，轉第6步，否則轉第2步；

第6步：從t開始通過前驅標記Pt回溯，得到從s到t的頂點序列，即為s到t的所有最少換乘次數乘車方案，算法結束。

3 算例

本文采用文獻[3]中的算例驗證基本算法和改進算法的正確性。

設一由6個站點構成的路網，共有6趟列車開行，各列車車次和所經過的站點序列如下：

根據上述列車開行方案，生成如圖1所示的換乘網絡。現要求計算出1、3站點之間的最小換乘次數乘車方案。

圖1 換乘網絡示意圖

根據基本廣度優先搜索算法，所求最短路徑為1→4→3。表示從頂點1至3最少換乘次數乘車方案為：先乘列車V1從頂點1至頂點4，再乘列車V2從頂點4至頂點3，換乘次數為1，與文獻[3]中計算結果相同。

根據改進廣度優先搜索算法，所求最短路徑為1→4→3和1→6→3，兩者換乘次數均為1，都是換乘次數最少的乘車方案。可見，通過改進廣度優先搜索算法，可以一次搜索出換乘網絡中給定發、到站間全部的最少換乘次數乘車方案。

4 算法效率分析

公路旅客乘車方案選擇算法必須具有較高的執行效率，以適應公路客運信息查詢、計算機聯網售票等應用系統對算法響應時間的要求。本節對基本廣度優先搜索算法和改進廣度優先搜索算法的效率進行分析，并與普通最短路徑算法的執行效率進行比較。

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

為實際驗證基本廣度優先搜索算法的執行效率，用全路客運換乘網絡對其進行測試。在根據全路列車時刻表數據生成的換乘網絡中隨機挑選1000對站點，分別用基本廣度優先搜索算法和Dijkstra算法搜索兩站點間的最短路徑。算法測試的硬件平臺為Intel Centrino 1.8GHz CPU，2GB內存，編程語言為C＋＋。算法效率對比結果見圖2。

圖2 基本廣度優先搜索算法和Dijkstra算法效率對比

從圖2可以看出，基本廣度優先搜索算法執行時間與換乘次數正相關，而Dijkstra算法的執行時間與換乘次數無關。這是因為Dijkstra算法（事實上對所有單源最短路徑算法都是如此）在搜索起終點間的最短路徑時，實質上是搜索了從起點到圖中所有節點的最短路徑，因此平均搜索效率遠低于基本廣度優先搜索算法。

進一步分析改進廣度優先搜索算法的執行效率。與基本廣度優先搜索算法相比，改進廣度優先搜索算法僅多記錄了每個節點的前驅，因此算法時間復雜度仍是Θ（|V2|）。而采用K最短路算法搜索網絡中的多條最短路徑時，算法的時間復雜度是Θ（K|V2|），其中K是最短路徑的數量。同樣使用前述換乘網絡，對比測試在搜索全部最短路徑時，改進廣度優先搜索算法與K最短路算法的執行效率，結果見圖3。

圖3 改進廣度優先搜索算法和K最短路算法效率對比

從圖3可以看出，在搜索起終點間的多條最短路徑時，改進廣度優先搜索算法由于根據節點前驅回溯最短路徑的實際時間開銷增大，效率低于基本廣度優先搜索算法，但仍遠優于K最短路算法。

5 結語

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

[1]史峰，馬均培，向聯慧，等.客運中轉徑路的換乘模型及算法[J].鐵道學報，1999，21（5）：1－4.

[2]史峰，鄧連波.旅客換乘網絡優化設計[J].鐵道科學與工程學報，2004，1（1）：78－82.

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

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

[5]傅冬綿.交通系統中最少換乘算法及其實現[J].華僑大學學報：自然科學版，2001，22（4）：348－350.

[6]張彥.鐵路客票中轉換乘多徑路選擇問題的研究[J].鐵道運輸與經濟，1997，19（8）：11－13.

[7]趙偉，何紅生，林中材，等.中國鐵路客運網網絡性質的研究[J].物理學報，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.