基于多路徑優化算法的鐵路網絡分析系統開發

李向農,范丁元

(中鐵工程設計咨詢集團有限公司,北京 100055)

引言

隨著新一輪《中長期路網規劃》的實施，鐵路網絡效應將更加強化，路網結構空前復雜[1]，運量預測與鐵路網絡分析聯系緊密[2]。鐵路網絡的復雜性和抽象性，決定了利用計算機進行網絡圖形計算和分析已成必由之路[3]。目前，常用的此類計算機系統中，TransCAD系統傾向于地理信息和公路、城市道路，信息顯示和查詢不符合我國鐵路運量預測模式[4]；RGIS系統可進行鐵路網絡圖形的屏幕顯示和路網分配、數據統計和分析等功能，但主要偏向于統計分析[5]。本鐵路網絡分析系統，創新發展了大規模鐵路網多路徑計算，運量分配及動態調整，列車時刻數據提取、運輸徑路提取技術。鐵路網絡圖形呈現、車站和線路屬性編輯、運輸徑路比較、運量分配和動態調整、區段客貨流和旅客列車對數查詢、運輸路徑提取等功能于一體，并應用于鐵路前期研究和路網規劃等領域。

1 系統設計創新技術

本系統作為軟件應用系統，提供功能眾多，并采取了與既有國內外相關系統差異化、專業導向性研發思路。主要技術有：簡化路網KSP計算技術、區段運量分配及動態調整技術、統計區段運量的OD構成技術、列車時刻數據智能識別和徑路提取技術等。

1.1 簡化路網KSP計算技術

鐵路網多路徑計算(即KSP計算)是本系統其他功能(如徑路比較、路網分配及動態調整等)的基礎[6]。為使系統能夠達到即時人機交互、隨時信息反饋、所見即所得的設計目標，本系統采用了先進行全局KSP計算，再根據需要隨時提取任意節點對間徑路的設計模式。全局KSP計算復雜度和空間復雜度極高[7]。為能在普通計算機上完成計算，本系統創新研發出簡化路網KSP計算方法。設有簡化路網G(N，E)，|G|=Q，Q為網絡中真節點數，計算所有真節點之間的前K條較短路徑。將節點i和節點j間的第K條路徑Rij(k)用以下數據結構遞歸表示。

Rij(k)={ID，w，v，ID1，ID2}

(1)

式中，ID為標識數字，唯一標識真節點i到j間的某條路徑；w為該路徑長度；v為該路徑所經由的真節點；ID1標識該路徑中由真節點i到v的子路徑；ID2標識該路徑中經由真節點v到j的子路徑。以上五元組可唯一確定G中一條路徑。

具體步驟如下。

首先，對其進行初始化，記K維向量R(i，j)={Rij(k)|k=1，2，…，K}。構造矩陣Dk={R(i，j)|i=1，2，…，Q；j=1，2，…，Q} 。若真節點i和j相鄰，Rij(1).v=-1；否則Rij(1).w=∞，表示無此路徑。

其次，計算Dk，k=1，2，…，K。由Rik(k1).w和Rkj(k2).w計算Rij(kr).w，通過循環更新Dk-1，得到Dk。

該技術主要解決在大規模路網節點情況下，計算路網全部節點對大量路徑進行存儲和提取路徑的問題，對于大規模路網中每個節點對間K短路徑(K值較大)的計算復雜度和空間復雜度有明顯降低，從而提高計算該問題對一般PC機的內存適應能力及實時反應能力，而不失交通網絡信息的完整性，提高了鐵路運量預測和路網規劃效率及科學性。

1.2 區段運量分配及動態調整技術

在傳統最短路徑分配基礎上，本系統開發出分配結果的動態調整功能，即根據路段運量規模、平行徑路的平衡利用或項目要求等因素，將繁忙路段的運量動態分流到次短徑路的技術，目標函數與具體分配方法如下

(2)

關鍵技術為，對經過要調整區段的OD對排序，按最小繞行距離從小到大排序，選擇最小繞行的OD調出至空閑區段，可保證目標函數在滿足的條件下始終最小，OD調入也可根據繞行最小進行調出。經過分配調整分流，能夠模擬出現狀路網上與實際客貨流徑路最為接近的分配結果，并使研究年度路網分配更加平衡合理，滿足設計要求[8]。同時，本系統可隨時切換，按路徑長度、旅行時間、廣義費用進行分配。

1.3 統計區段運量的OD構成技術

1.4 列車時刻數據的智能識別和徑路提取技術

本系統應用人工智能的聚類分析和模式匹配，開發出可準確識別表格形式和結構，以及提取列車時刻表詳細數據的方法。關鍵技術為：首先，根據聚類分析確定表格范圍；其次，根據先驗的表頭模式、車站名模式、車次模式、時刻模式通過人工智能算法確定表格內部結構；再次，根據已掌握的表格結構提取列車時刻表詳細數據；最后，對提取的數據進行合并整理并查錯處理，發現問題及時反饋并報告有問題的工作表名、行車號及出錯類型。通過以上算法，不但可提取準確的列車時刻表數據，還能找出數據中的錯誤和可疑位置。

列車時刻數據提取后，須根據路網結構確定每一列旅客列車在路網上的運輸路徑[9]。本系統開發出根據路網節點相鄰程度、線路包含車站等圖形拓撲結構與旅客列車時刻表數據中站名比對匹配的計算方法，可準確確定每列車的運輸路徑，并將之突出顯示在鐵路網絡圖形上。

2 系統設計

2.1 系統需求

2.1.1 運輸徑路比較模塊需求

通過徑路計算和比較，可對項目功能定位、建設必要性運量構成及流向進行更好地研究和分析，其在運量預測中起著重要作用[10]。目前，路網信息識別和運輸徑路分析基本通過紙質圖形或電子圖片，經手工計算或EXCEL表格公式和數據錄入進行計算[11]。隨著鐵路網絡的進一步復雜化，鐵路網絡站點多、區段數量大，計算復雜度極高、工作量巨大。因此，快速查詢任意兩車站間距離和路徑具有重要的現實意義。

2.1.2 OD加載、運量分配、調整模塊及流量分析需求

加載OD數據后，根據時間、距離及廣義費用等因素，將OD數據間的分布交通量分配至具體徑路中[12]。可針對項目的運輸特點，分析路段運量構成，確定研究項目承擔的運量級別。針對流量分析顯示更符合實際的客流、貨流流向，便于圖形化顯示斷面流量大小，更好地進行流量分析和動態路網分配。因此，開發出可以進行OD數據加載、運量分配、運量動態調整及流量分析的網絡分析系統，對研判預測的合理性起重要作用。

2.1.3 列車時刻數據提取模塊需求

目前，旅客列車時刻表原始精確數據主要來自于鐵路局提供的EXCEL表格和鐵路12306網站的數據[13]。但鐵路局表格格式多樣，且同一車次分散存放，車站次序也有時任意排列，人工提取數據工作量巨大，且需有一定的經驗才能準確提取，對計算機數據提取技術要求較高；12306網站的列車時刻數據顯示不出運輸路徑。因此，本系統開發出可準確識別表格形式和結構，以及提取列車時刻表詳細數據的方法。

2.2 系統界面及結構

本系統的體系結構可分為三大單元：核心數據結構層、核心算法層和功能實現層[14]。基于圖形網絡數據結構、單路徑與多路徑的運輸徑路矩陣、OD向量及OD矩陣、列車時刻表矩陣和控制參數等，通過簡化路網KSP計算技術、區段運量分配及動態調整技術、統計區段運量的OD構成技術、列車時刻數據的智能識別和徑路提取技術等核心算法，最終實現12個主要系統功能。系統結構如圖1所示。

圖1 系統結構

2.3 系統功能模塊解讀

系統主要功能模塊分為12個部分：鐵路網圖形信息顯示；圖形編輯；車站、線路、中間站詳細信息及編輯；單徑路和多徑路計算；運輸徑路比較；OD加載、運量分配及調整；流量分析及圖形化顯示；旅客列車時刻表讀取；線路客車對數統計；路網信息和徑路計算結果的讀取和存儲；外部信息交換；EXCEL報表輸出等。以下對部分模塊進行重點介紹，軟件界面如圖2所示。

圖2 軟件界面

2.3.1 運輸徑路比較模塊

系統可進行自動徑路比較(通過選擇起、訖點)[15]、自定義徑路比較(通過選擇起、訖點和中間節點)[16]，可進行運輸距離、旅行時間及廣義費用比較，并在三者間隨意切換[17]。徑路比較結果均在圖形窗口和屬性窗口中反饋，運輸徑路比較結果如圖3所示。

圖3 運輸徑路比較結果

2.3.2 OD加載、運量分配、調整模塊及流量分析模塊

系統可加載483個和582個原始OD小區交流數據以及自定義的文本格式存儲的OD矩陣數據，進行運量分配[18]。獨創路網分配動態調整方法，根據多徑路計算結果，調整繁忙區段流量并圖形化顯示其運量大小，更符合鐵路實際運輸特點[19]。通過獨創的鼠標選擇上行或下行方法，可在屬性窗口選入控制區段，并在屬性窗口中顯示控制區段運量，以及每個控制區段的OD構成，同時在圖形窗口顯示運輸徑路；還可按運量大小用不同線條寬度進行徑路顯示，使之更直觀化、清晰化。OD加載分配類型、分配計算及結果、手動分配窗口及流量分析、圖形化顯示及分配結果如圖4～圖6所示。

圖4 OD加載分配類型、分配計算及結果

圖5 手動分配窗口

圖6 流量分析、圖形化顯示及分配結果

2.3.3 列車時刻數據提取模塊

系統可讀取格式多樣的鐵路局旅客列車時刻EXCEL表數據[20]，對之進行排序、整理和查錯處理，并在圖形窗口和屬性窗口中同時顯示運輸徑路。檢查時刻表的重復車次、可分配性與起終點和顯示運輸徑路如圖7和圖8所示。

圖7 檢查時刻表的重復車次、可分配性與起終點

圖8 顯示運輸徑路

3 結語

本系統是應用型軟件系統，實用性強，采用C++語言編寫，通過加載國鐵集團483個和582原始OD小區交流數據，研究鐵路局客貨運電子數據特性，更符合鐵路運輸徑路的形成機理，提高了系統對各類數據的自適應能力。系統可充分利用路網信息采用圖形表達，提供動態修改和增補路網信息功能，有比較完善的圖形編輯、鐵路車站和線路區段信息編輯功能；同時，將鐵路運輸徑路比較、原始OD讀取、路網分配、斷面流量分析和動態調整，以及列車時刻數據提取、查詢集成至系統中，對不同運輸徑路和區段運量構成均提供信息反饋和交互功能。該系統具有以下特點。

(1)首創簡化路網KSP計算技術、區段運量分配及動態調整技術、統計區段運量OD構成技術、列車時刻數據智能識別與提取、運輸徑路提取技術。

(2)優化算法減少參與計算節點規模，精簡數據結構，可滿足系統快速響應的目的。

(3)列車時刻數據處理和大規模提取，提供了網絡的快速解決方案。

(4)系統以圖形方式顯示運量及徑路，分析結果呈現直觀且清晰。

該系統應用在成達萬高鐵、沿江高鐵、通蘇嘉甬鐵路等項目，已取得良好效果。相較于傳統的手動分配法和其他軟件，分別提高100倍和5倍以上的設計工效，具有良好的經濟社會效益。