啟發式算法在鐵路換乘的應用

尹伊伊，王富章，單杏花，張 霞

（1.中國鐵道科學研究院，北京 100081；2.中國鐵道科學研究院 電子計算技術研究所，北京 100081）

啟發式算法在鐵路換乘的應用

尹伊伊1，王富章2，單杏花2，張 霞2

（1.中國鐵道科學研究院，北京 100081；2.中國鐵道科學研究院 電子計算技術研究所，北京 100081）

隨著中國鐵路的建設與發展，如何更加充分地利用鐵路客運能力、提高列車上座率是鐵路亟待解決的問題。本文針對復雜的客運路網下最短路徑算法計算效率低下的問題，對比分析了常用的Dijkstra算法及啟發式A*算法，擇優選取啟發式A*算法進行策略改進；并基于優化的客運路網結構及鐵路實際業務，對其進行效率優化。實驗證明，改進后的算法模型高效準確，具有明顯的現實意義。

最短路算法；鐵路換乘；Dijkstra算法；啟發式A*算法

隨著高速鐵路的快速發展，人們出行越來越依賴于鐵路，出行范圍及次數也在不斷擴增。但現有運能條件下，仍有相當一部分城市間難以實現直達或直達無票，乘客必須換乘才可到達目的地，即在現有客運條件下需要兩張（或以上）車票接續，完成旅行。對于由被動服務向主動服務角色轉變的鐵路來講，提升鐵路服務水平且在現有條件下盡可能提升客運效率，最大限度地發揮客運方便快捷的優勢，需要建立一個統一、完善、友好的鐵路聯程服務系統，引導乘客高效換乘，方便乘客出行。

1 最短路徑算法比選

1.1 算法目標

本文目標是為12306網站提供高效的算法接口，算法設計既要滿足網站的高并發性又要滿足乘客交互時效性的要求。算法需要在滿足最少換乘條件下，根據乘客個性化需求如時間短、票價低、接續列車多等要求，將旅客要求轉換為數學約束條件，高效精準地計算出可行的換乘方案。

1.2 既有技術背景

徑路搜尋分為：（1）盲目搜索，如尋址方法起始于一個頂點，繼而探索相鄰節點，遍歷直到找到目標節點獲得最短路徑；（2）啟發式搜索，即“探索”地圖，趨向于目的地方向搜索[1]。本節對比上述兩種思想的經典算法：遍歷盲搜的Dijkstra算法及啟發式搜索A*算法，分析其原理及效率性能，選取更適合鐵路最優徑路選取的算法，并根據實際需求優化。

1.2.1 Dijkstra算法

Dijkstra算法屬于盲搜算法，是一種典型的標號算法，其基本思想是以起點為中心向外層層擴展，直到搜索到目標點。該算法從未標記的點集合中不斷地找出距離起點最近的點，并把該點移動到已標記的點集合中，同時更新未標記點集合中其余各點到起點的最短距離，重復迭代，向外拓展找到目標點。Dijkstra算法遍歷時計算的點很多，但是可以算出最短路徑的最優解。

1.2.2 啟發式A*算法

A*算法是人工智能領域中典型的啟發式搜索算法[2]。啟發式搜索就是在狀態空間的搜索中，對每一個搜索位置進行評估，得到最優位置，再從這個位置進行搜索直到獲得最終目標[3]。這樣就節省了大量無謂的節點搜索，提高了效率。A*算法的核心部分就在它的估值函數：F(n) = G(n)+H(n)。其中，F(n)是當前點n的代價值；G(n)為起點到當前點n的代價值；H(n)則為當前點n到最終目的點的估計代價值，即H(n)為啟發函數，體現搜索的啟發信息，是整合函數的核心所在。當每次選擇下一個待搜索點時，從所有已探知的卻未搜索過節點中，獲取代價值最小的點展開搜索，直到算法失敗，無解而終，或者找到終點，成功獲得較優路徑。

1.3 算法比選

分析兩種經典尋路算法的中心思想可知：Dijkstra是一種成熟穩定的圖譜搜索算法，確實能保證找到一條最短路徑[4]。但Dijkstra算法在找到終點之前會拓展更多的區域，導致開銷大運行慢。啟發式A*算法采用評價函數引導求解過程，節省了冗余探索過程而大幅度提高效率。但當目標點太多，估價函數復雜，數據計算量猛增，而且A*算法可能因啟發函數的精確度計算出一條較短較優而非最短最優的徑路。

關于兩種算法的效率問題簡單地以圖1示意，其中純綠格子代表起點，純紅格子代表終點，灰色格子代表障礙物即不可達點，黃色線段代表最終得出的路徑。圖1是A*算法以常用的歐式距離作為啟發函數的探索示意圖。圖2是運用Dijkstra原理在二維地圖中進行搜索的示意圖。

藍色區域代表已探索區域，綠色部分代表待搜索節點，覆蓋范圍映射出算法的效率。比較圖1和圖2可知，兩種算法得到的黃色的最短（優）路徑相似，但很明顯，A*算法擴展的結點少，效率高于Dijkstra算法。

圖1 啟發式A*算法示意圖

圖2 Dijkstra算法示意圖

鐵路車站站點眾多，但并非所有車站均可作為換乘站。本文選取具有始發車次、具備客運組織換乘能力的大站作為換乘車站，完全可以克服A*算法多目標點而導致開銷巨大的弊端。乘客并不需要得到最短的路徑，只要是較優較近的即可，A*算法最優而非最短徑路的弊端在鐵路應用仍可通過啟發函數的約束條件權值控制來沖正。所以本文從A*算法入手，結合鐵路實際，設計精準的啟發函數，使其適用于鐵路客運路網下的高效尋址計算。

2 算法優化及實現

2.1 算法優化

2.1.1 啟發函數優化

A*算法優點是啟發方向可以根據需求可控。如果啟發函數設計的合適、恰當，它將會指引搜索過程朝最優的方向前進[5]，排除的節點越多，運行效率越高，從而快速找到最適合換乘的站點，A*算法由于此高性能而得到廣泛應用。本文的關鍵是啟發函數H(n)設計。H(n)的設計需要根據全局平衡取舍，根據乘客個性化需求，配置最合適的啟發函數。如果H(n)精確等于真實數據，F(n)的取值將一直保持最優。

對于二維網格地圖的函數H(n)，有一些眾所周知的啟發式函數：（1）曼哈頓距離，是固定直角坐標系上兩點所形成的線段對軸產生的投影距離總和[6]；（2）歐氏距離，在二維和三維空間中的歐氏距離的就是兩點之間的距離[7]。具體到鐵路路網來講，乘客在高速列車上更關心的是徑路是否可靠有效、換乘后是否繞遠、票價是否增加等，結合高鐵、動車、城際等高速鐵路的發展，部分乘客不再關心徑路長度而將重心放在了時間最短，再結合現在鐵路有全國通簽的功能，乘客考慮到換乘的靈活性，有些也會非常注重換乘站接續列車的數量，使換乘時間更加充裕。所以本文將以往A*算法常用的距離啟發轉化為多約束條件：有更多選擇的可接續車次轉換為車次權重，車次時效性轉換為時間權重，票價轉換成里程權重。針對不同需求，使用參數來調整各因素對代價函數的貢獻值，影響啟發尋址的趨向，找到滿足個性化需求的方案集，從而達到優化模型的目的。

2.1.2 換乘站點優化

鐵路網規模的擴大為換乘提供了便利條件，卻為搜索效率提出了更高的要求。最短路徑搜索算法涉及到大規模的拓撲查詢，數據處理量大。網絡數據的數據量及圖在計算機中存儲形式都會直接影響算法運行效率和響應時間。

當乘客自行選擇換乘方案時，可很快得到較為合理的連通徑路。在乘客的思考過程中，分層策略篩選出樞紐站點；方向策略驅動引導出趨向于目的車站的徑路；貪心策略會幫助選擇可靠性最大的站點。全國共有4千多個辦理客運業務的火車站，全部作為換乘車站，既不符合實際且運算量會非常龐大。而一般情況下車站規模和客流較大的地方均會作為列車的始發、終到車站，所以選取樞紐及結算站，可以保證有相對較多的票額供發售，保證換乘的可行性。

將車站站點合理分類，并且預計算所有乘車站至換乘點間的權值數據，是將徑路計算問題復雜性降低的關鍵步驟。本文根據本章節觀點，初始化并保存了乘車站與換乘站的啟發函數H(n)關系矩陣A[i] [j]，用于參與后續F(n)值的快速計算，式（1）中，i為乘車站，j為換乘站。

預先計算出乘車站到換乘站點多條件約束代價，并配置合理的結構存儲，減少每次計算H(N)的時間，算法犧牲了空間來爭取時效，從而使A*算法計算速度最優。

2.1.3 路網模型優化

關于鐵路路網抽象模型，本文不是簡單的基于現有鐵路網為線，而是抽象車次為線?？衫斫鉃椋涸O定初始路網是一個空圖，使所有列車同時從始發站出發，直至終到站，以所有列車的經停站與優化的換乘站點交集作為點，存為本文所用的鐵路乘車路網模型，這樣在保證線路連接的同時保證肯定有列車接續，從而避免鐵路網相連但可能有路無車現象的發生。

2.2 算法實現

基于Java實現鐵路換乘的A*算法：（1）從Sybase數據庫中載入原始數據，初始化乘車站、換乘站和列車等基礎信息；（2）生成并保存路網信息、乘車站與換乘站的啟發函數H(n)、關系矩陣A[i][j]，參與后續F(n)的計算；（3）基于上述數據，執行改進的A*算法，直到找到換乘站或算法失敗。在算法中，A*算法維護兩張重要表：Open待處理的站點表和Closed 已處理過的站點表。算法流程如圖3所示。

3 算法應用

本文選取3 000個乘車站，300個具有始發車次、擁有良好換乘客流交換層且具備應急及客流組織能力的車站作為換乘車站，有代表性的200個城鎮作為出發到達站，將這些數據作為樣本數據進行測試，測試內容涵蓋交通樞紐城市、省會城市、大城市與小城鎮、偏遠地區城市之間列車通行方案。計算結果關注測算數據的準確性是否滿足需求，并分析比較算法運行時間效率。其中，表1為部分發到站測試用例；表2和表3為根據表1 所示發到站，執行本文的算法模型，在多目標和約束條件下編號1和編號2的計算結果。

圖3 算法流程圖

表1 部分測試用例

由表2和表3可知：算法可依據乘客個性化需求給啟發函數加權，當時間比重優先時，優推出有高鐵、動車直達車的有效站點；而里程比重優先時，則給乘客優推出不繞行的換乘站點。此算法結果準確有效，且可根據乘客個性化需求優先推選出符合乘客意愿的換乘站供乘客參考。

表2 編號1的測試結果

表3 編號2的測試結果

圖4為算法對比圖，圖中，紅色和藍色分別代表Dijkstra及A*算法響應時間箱線圖，對比可得，A*算法平均1 ms返回乘客搜索目標的換乘站方案，比Dijkstra算法的性能提高很多。

本文模型優化了數據結構，使得推薦最優線路站點的效率不超過1 ms，為12306聯程業務提供可靠的基礎數據，結合網站既有的余票算法，可快速為乘客推薦出聯程方案。

Application of Heuristic Algorithm in railway transfer

YIN Yiyi1,WANG Fuzhang2,SHAN Xinghua2,ZHANG Xia2
（1.China Academy of Railway Sciences,Beijing 100081,China；2.Institute of Computing Technologies,China Academy of Railway Sciences,Beijing 100081,China)

With the construction and development of China railway,how to take full advantages of railway passenger transport capacity and improve occupancy rate became urgent problems,so that the research of railway transfer based on railway network was with important theoretical and practical signifcance.In order to solve the low computational effciency of common Shortest Path Algorithm,compared Dijkstra Algorithm with Heuristic A * Algorithm,this article selected the Heuristic A* Algorithm to optimize the effciency based on the optimization of the railway network and rail services.Experiments showed that the improved algorithm model was effcient,accurate,and signifcance obviously.

Shortest Path Algorithm;railway transfer;Dijkstra Algorithm;Heuristic A* Algorithm

U293.22∶TP39

A

1005-8451（2016）01-0020-05

2015-04-09

尹伊伊，在讀碩士研究生；王富章，研究員。