列流圖中列流線生成與排序優化算法

耿敬春，武建平，聶英杰，倪少權

（1.西南交通大學 交通運輸與物流學院，四川 成都 610031；2.中國國家鐵路集團有限公司 工程設計鑒定中心，北京 100844；3.中國鐵路經濟規劃研究院有限公司 線路站場咨詢部，北京 100844；4.中國鐵路設計集團有限公司 交通運輸規劃研究院，天津 300308；5.西南交通大學 綜合交通運輸智能化國家地方聯合工程實驗室，四川 成都 610031；6.西南交通大學 綜合交通大數據應用技術國家工程實驗室，四川 成都 610031）

列流圖是在鐵路新建、改造項目設計中展示樞紐內各種客貨列車流的種類、數量和路徑的技術文件。列流圖繪制主要包括圖形布局和列流線鋪畫。其中：圖形布局是樞紐內車站的空間布置，與樞紐內車站的相對位置及數量、鐵路線走向和列車流走向等因素相關；列流線鋪畫是反映列車流（列車種類、數量）在樞紐內走向（路徑）的靜態指標，其鋪畫過程中最為關鍵的2 個步驟是確定列流線的走向和列流線的相對位置。

針對該問題，史峰［1］提出了列流線鋪畫的左右、緊湊、分層、對稱和分類5 種排列原則及其遵循的先后順序；程學慶［2-5］設計了列流路徑尋找標號、列流線折點搜索、列流線偏移描繪、節點集合及邊集合自動生成等算法。此外，在計算機自動繪制列流圖方面［6-10］，主要從自動繪圖算法的提出、計算機程序化實現等方面進行了研究探討。這些研究成果為實現列流圖計算機自動鋪畫提供了相關技術支持。

列流圖分為客運列流圖、貨運列流圖和客貨運列流圖3 種。列流圖鋪畫的前提是根據客流分配［11］、貨運量等確定列車開行方案，其中貨物列車開行方案的確定過程還需先將貨流折算為車流，再結合編組計劃的制定將車流轉化為列流。以上內容與列流圖鋪畫工作相對獨立且專業性強，需專門研究，本文不涉及。

本文針對大型樞紐內車站數量多、車站銜接方向多、列車種類多等新特點，將銜接方向的車站按經緯向進行分割，在此基礎上提出列流線生成與排序優化算法，實現列流線的快速生成以及自動優化排序；基于該算法開發列流圖優化編制輔助設計系統；以金華鐵路樞紐為例，對算法的合理性與有效性進行驗證。

1 列流圖的布局與分解

為直觀明了地展示樞紐內的列車種類、數量和走向，列流圖中所有線條都由水平和豎直線段來描繪［1］。列流圖的圖形布局經過計算機程序開發后，可以很好地實現并通過人機交互隨時進行修改［12］；但大型樞紐內車站銜接鐵路線多，用矩形框表述車站時，同一車站的同一邊可能會銜接多條線路，會給列流線的計算機自動鋪畫增加難度。以如圖1 所示的某樞紐列流圖為例進行說明（圖中字母表示車站）。車站B 的左側邊銜接了車站A 和車站D，車站E 的上側邊銜接了車站B 和車站D。

為有效簡化該問題，根據列流圖“橫平豎直”的表現形式，理論上可將整個圖幅按經緯向進行分割，經緯分割線的位置和數量隨鐵路線的布局確定，即互相平行的2 條線路間按平行線路方向設置1 根經緯分割線。對圖1 所示的列流圖，按經緯向進行分割后如圖2 所示。圖中：紅色虛線表示經緯分割線；B'，B″和E'，E″分別表示經緯向切割后，車站B 和車站E 隨鐵路線布局分割后得到的虛擬車站；虛線框為原車站位置。

圖2 列流圖經緯分割后示意圖

按此方法不斷分割，使得同一矩形同一邊上最多只銜接1 條線路，每個矩形（虛擬車站）最多銜接4 條線路。這樣一來，車站分割會大幅降低列流線鋪畫所涉及的處理難度；所有列流線鋪畫完成后，再將之前分割的車站進行合并。根據列流線表現形式，車站內一般用虛線表示，車站間一般用實線表示，而且任意相鄰車站間的列流線均為平行線，故車站合并時只需將車站間的列流線由實線變為虛線。需要指出的是，以上車站的分割與合并均為算法邏輯，在應用到計算機程序開發時并不顯示在用戶界面上。

2 列流線生成與排序優化算法

2.1 列流線生成算法

人工梳理列流線徑路時效率較低且容易出錯，對于規模較大樞紐則更為不易，鑒于此種情況，提出列流線生成算法。該算法的總體思路為：列流圖按經緯向分割后，生成目標車站對（某條線路兩端的2 個車站組成1 個車站對）間的列車徑路備選集合，繼而通過人機交互方式由用戶確定徑路上1～2 個節點車站來最終確定列流線徑路，并將其添加到列流線待鋪畫集合中，待下一步鋪畫。在進行系統開發時，還需要通過人機交互確定列流線的屬性（如用不同顏色和線型表示不同的列車種類）。

列流線生成算法中最關鍵的步驟是目標車站對間列車徑路備選集合的生成。一般來說，最簡單的方式是在樞紐路網圖上基于廣度搜索思路進行全枚舉生成，但其算法復雜度會隨著樞紐規模的擴大呈指數增加。經研究發現，除個別列車會在樞紐內選擇指定徑路，絕大部分列車一般都會選擇最短徑路或者相近徑路走行。由此可借鑒雙重掃除算法（Double-Sweep Algorithm）［13］生成任意車站對間列車備選徑路集合［14］，具體步驟如下。

步驟1：將按經緯向分割后的樞紐網絡結合圖論［15］進行數學抽象，將所有車站視為節點，將所有線路視為連接節點的邊，形成有向網絡拓撲結構，并為每條邊賦權值為1，為每1 個節點編號。

步驟2：確定目標車站對間列車徑路備選集合規模，即備選徑路條數，記為N。

步驟3：按有向拓撲網絡的鄰接矩陣構造以N條徑路長度為元素的目標車站對的初始向量，即

步驟4：根據步驟（3）中目標車站對的初始向量，構建初始計算矩陣V0，V0中的元素為向量并根據矩陣V0生成下三角矩陣L 和上三角矩陣U，上、下三角矩陣中的空缺元素用維度相同且元素均為極大數的向量填充。

步驟5：計算車站i 至樞紐內除該站之外所有車站的N 條最短徑路長度，分別生成初始向量令其元素與矩陣V0元素一致。

步驟6：按式（2）和式（3）進行計算。

式中：r 為迭代次數。

根據式（4），可確定車站i 至車站j 的第n(n

步驟9：循環調用車站對間列車備選徑路集合生成算法，得到每一車站對間的N 條備選徑路，最終得到所有列車徑路備選集合。

根據生成的列車徑路備選集合，再結合人機交互，可確定各車站對間的列車徑路，并形成列流線待鋪畫集合。在列流圖輔助設計開發時，為減少計算機自動化編制時的無效工作，目標車站對間列車徑路備選集的規模（N 值）可由用戶根據實際需要提前設定。

2.2 列流線排序優化算法

列流線待鋪畫集合確定后，就可著手列流線的鋪畫工作。由于列流圖是以“橫平豎直”的方式進行展示，同一經緯線上不同區間內列流線的排列順序會相互影響，不同的排列順序就會形成不同的交叉形式，即不同的列流線布置形式，最終影響到列流圖的整體布局。這是列流圖繪制過程中最為關鍵的問題，也是難點。為有效解決這一難題，可將列流線的排序問題分解為以下2 步解決。第1 步，遍歷所有區間（相鄰車站構成的區間），對途徑的列流線進行相對位置排序；第2 步，根據同一經緯線上各區間的相對位置排序再進行二次排序，最終確定列流線空間位置。

2.2.1 各區間內列流線相對位置排序

1）算法步驟

列流線進入區間的形式有直向進入、左轉進入、右轉進入、區間始發以及右向后轉返回區間5 種，列流線離開區間的形式同樣有直向離開、左轉離開、右轉離開、區間終到以及右向后轉返回區間5 種，其中右向后轉返回區間形式較為特殊，無論是進入區間還是離開區間都應緊貼鐵路線布置，無須再與其他列流線形式進行位置排序，則任意區間內參與位置排序的列流線存在形式共計16 種，如圖3 所示。圖中：藍色箭頭線條表示列流線形式；G 和H 分別為某樞紐內的2 個相鄰車站；黑色線條表示連接2 個車站的鐵路線；水平虛線表示2 個車站的邊界；橙色數字為該區間內參與位置排序的列流線存在形式編號。

圖3 任意車站區間內須排序的列流線形式

在這16 種列流線存在形式中，只有區間始發且終到形式的列流線位置不會對其他區間的排序產生影響，故而在研究時可先將該種形式列流線設為自由位置，待其他列流線排序確定后，再將其按離線路及列車屬性由近及遠的方式進行插空，因此以下先對其余15 種列流線形式的排序問題進行研究。

針對任一區間，從列流線待鋪畫集合中篩選經過該區間的待鋪畫列流線，即將列流線徑路中帶有目標區間的列流線選出，并確定其在目標區間內的相對位置排序，具體步驟如下。

步驟1：初始化權重。根據列流圖的繪制思路，列流線間的交叉是由于列流線在車站進行方向轉變而形成，為了減少或避免交叉，當列流線向靠近線路方向轉向時，列流線在區間內的相對位置排序應靠近線路；當列流線向遠離線路方向轉向時，列流線在區間內的相對位置排序應遠離線路。據此思想以及鐵路左側行車規則，可根據進入區間和離開區間的方式，為列流線賦予一定的權重，即對右轉進入區間和右轉離開區間方式賦予較大權重，對左轉進入區間和左轉離開區間方式賦予較小權重，直向進入和直向離開方式賦予中間大小權重。

步驟2：權重值更新。列流線在目標區間的位置排序還會受到列流線途徑各區間相對位置排序的影響。考慮這一影響因素，延續上述思路，沿著列流線徑路向前追蹤和向后追蹤更新權重，具體如下。

（1）順著列流線方向到達下一區間，根據上述方法對列流線進行權重值更新。若其他區間權重與目標區間權重為同等數量級，則會嚴重干擾目標區間內的排序；因此，在對下一區間權重賦值時可降1 個數量級。如目標區間權重為5，則下一區間同樣形式列流線權重可賦為0.5，此時列流線在目標區間的權重更新為5.5。同理，繼續順向到再下一個區間，再降1 個數量級更新權重，直到列流線終止。

（2）逆著列流線方向回溯到達上一個區間，直到回溯到起點時終止，其權重賦值原則與順向一致。但逆向回溯時，其方向與順向相反，則權重的大小也應左右互換。

（3）按照上述（1）和（2）步完成目標區間每一列流線的權值更新。

步驟3：按照權重排序。將目標區間內各列流線最終權重按照降序排列，排序后權重越大的列流線越靠近線路，這樣就得到了目標區間內所有列流線距離線路由近及遠的相對位置。

步驟4：按步驟1—步驟3 歷遍圖中所有區間，確定各區間內列流線相對位置排序。

2）算法示例

為更清楚地理解上述算法，以圖4 所示列流線（藍色）所在區間DB″的權重更新為例進行說明。

圖4 列流線

如圖4 所示，列流線在各區間涉及進入或離開區間的方式有：區間始發、左轉離開、左轉進入、右轉離開、右轉進入以及區間終到共6 種方式。令6 種方式的權重分別為0，-4，-5，4，5和0，列流線在區間DB″的權重更新具體過程如下。

（1）在區間DB″內，列流線為右轉離開區間，初始化權重為4。

（2）進行順向追蹤。追蹤到下一區間B″E″，列流線離開區間方式為左轉離開，降1 個數量級更新權重4.0+（-0.4）=3.6；繼續順向追蹤到區間E″F，列流線終止權重為0，順向追蹤后權重更新為3.6。

（3）進行逆向回溯。回溯到上一區間DA，列流線右轉進入區間，降1 個數量級且反向，權重更新為3.6+0.5=4.1，列流線在區間DA 回溯終止，逆向追蹤后權重更新為4.1。

（4）在區間DB″內，列流線以權重4.1 進行相對位置排序。

同理，圖4 所示列流線在區間B″E″內的權重為-3.55，在區間E″F 內的權重為-0.455。

2.2.2 同一經緯線上列流線排序

1）算法步驟

根據第1 步中得到的各區間內所有列流線的相對位置排序，進行同一經緯線上所有列流線的二次排序，即實際位置排序，具體流程如下。

步驟1：確定排序標準。將同一經緯線上各區間列流線及其相對位置排序取出，并將各區間內的相對位置作為同一經緯線上列流線2 次排序的標準。

步驟2：初始化排序方案。篩選同一經緯線上各區間所取出的列流線，刪除相同列流線，并隨機生成初始位置排序方案。

步驟3：排序調整。根據從左至右順序，按照各區間內列流線相對位置順序對同一經緯線上所涉及的列流線位置排序進行檢查，若不一致則按各區間內的相對位置排序進行調換；循環往復，直到同一經緯線上的列流線位置順序與各區間內的相對位置順序全部一致時停止，并更新相關區間列流線實際位置。

步驟4：對同一經緯線上列流線位置進行檢查，若同一根列流線靠近線路一側的相鄰位置均為空閑位置，則將該列流線整體向空閑位置移動，并循環往復，直到不存在此種情況。

步驟5：檢查該經緯線上各區間是否存在區間內始發終到的列流線；如存在，則按照相對線路由近及遠的順序進行插空，并更新相關區間內列流線實際位置。

步驟6：按步驟1—步驟5 歷遍所有經緯線，得到各車站區間列流線的實際位置排序。

2）算法示例

為更清楚說明，以1 個簡單例子進行說明。根據列流圖圖形布局，同一經緯線上有2 個區間AB 和BC，區間AB 內有列流線a，b 和c，其相對位置順序為“bac”；區間BC 內有列流線b，c，其相對位置順序為“bc”，列流線d 在區間BC 內始發且終到，其位置為自由位置，具體如圖5所示。

圖5 列流線經緯向排序的初始位置

該經緯線上列流線位置排序具體步驟如下。

（1）將所有相關列流線取出進行歸并、生成初始順序，如“abc”，此時列流線d 作為自由位置不參與排序。

（2）用區間AB 內的列流線順序對初始位置進行檢查并調整，發現位置順序一致，為“bac”，再用區間BC 內的列流線順序對上述順序進行檢查并調整，得到“bac”。

（3）循環檢查發現，該順序與各區間的相對位置都一致，更新各區間位置，即區間AB 內的順序為“bac”，區間BC 內的順序為“bc”（b 與c 之間為空閑位置）。

（4）檢查發現區間BC 內存在始發且終到列流線，按照相對線路由近及遠順序進行插空，得到“bdc”。

（5）最終得到區間AB 和區間BC 內的列流線排序“bac”和“bdc”，如圖6 所示。

圖6 列流線經緯向排序后的位置

2.3 列流圖合并與調整

1）車站合并與調整

通過上述列流圖的布局與分解、列流線生成算法和列流線排序優化算法，即可得到各車站區間內的列流線位置排序，但此時的列流圖是按照前述“列流圖的布局與分解”方法分解后的圖形，因此還需要進一步合并調整。調整方法只需按照對前述的車站分割進行逆向合并即可。合并后，相應區間列流線就變成車站內列流線，但其位置排序仍保持不變。

2）列流線合并

在列流圖的繪制實踐中，為節省圖幅空間，會將具有相同起點且初始徑路區段相同的列流線，或具有相同終點且尾部徑路區段相同的列流線進行合并處理，且在匯合點或分叉點予以突出顯示，該需求可通過開發人機交互功能來實現。用戶在繪圖界面點擊任一列流線時，系統需自動識別并推送具有相同起點或終點、具有相同徑路區段以及相同屬性的列流線并按相同徑路區段長度由長至短排列；然后由用戶在推送的徑路中選擇要合并的徑路。徑路合并后，對合并區段的列車數進行求和顯示。

3 算法實現與案例應用

以金華鐵路樞紐客運列流圖鋪畫對前述算法進行實例應用及驗證。根據規劃［16］，金華鐵路樞紐連接滬昆高鐵、杭溫鐵路、金溫鐵路、金甬鐵路、金建鐵路、金臺城際、金龍城際、金衢城際、滬昆鐵路、金千鐵路、金溫貨線、金臺鐵路，共計12 條線路；銜接杭州（東、西）、衢州、溫州、建德、臺州、寧波、龍泉、天臺共9 個方向。隨著規劃線路的引入，樞紐客運系統將形成以金華站、義烏站為主要客站，金義站、金華南站為輔助客站的“2 主2 輔”客站格局。根據銜接線路所承擔客流以及金華鐵路樞紐客運需求［11］，金華鐵路樞紐規劃年度始發客車對數詳見表1，樞紐銜接16 個方向間通過客車詳見表2，規劃年度遠期客站分工及作業量［11］見表3 和表4。

表1 規劃年度始發客車對數 對·日-1

表2 規劃年度通過客車對數 對·日-1

表3 規劃年度遠期始發客車主要客站分工及作業量 對·日-1

表4 規劃年度遠期通過客車主要客站分工及作業量 對·日-1

根據表1—表4 中的數據，利用前述算法完成列流圖的鋪畫，最終得到的列流圖如圖7 所示。

對圖7 所示的列流圖經人工檢查，無列流徑路以及數據標識錯誤，說明了算法的合理性；在列流圖的生成過程中，列流線備選集合生成以及列流線的優化排序時間消耗均小于1 s，在實際應用中可以忽略不計，表明列流線生成與排序優化算法具有較強的高效性。

圖7 規劃年度客運列流圖

4 結 語

隨著近年來鐵路的快速發展，樞紐內車站作業分工以及列流分配日益復雜，為提高列流圖的鋪畫效率和質量，基于列流圖“橫平豎直”的表現形式，提出了列流線生成與排序優化算法。通過運用經緯分割線，將1 個方向上銜接多條鐵路線的車站轉化為1 個方向上銜接單條鐵路線的多個車站，將列流線的整體排序轉化為經緯向上的排序，從而化繁為簡，大大提高了列流線生成與排序的效率。下一步，需要結合列車編組計劃以及人工智能等新興技術對列流圖鋪畫進行協調聯動研究。