列流圖中列流線生成與排序優(yōu)化算法

耿敬春，武建平，聶英杰，倪少權(quán)

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

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

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

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

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

1 列流圖的布局與分解

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

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

圖2 列流圖經(jīng)緯分割后示意圖

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

2 列流線生成與排序優(yōu)化算法

2.1 列流線生成算法

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

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

步驟1：將按經(jīng)緯向分割后的樞紐網(wǎng)絡(luò)結(jié)合圖論［15］進行數(shù)學(xué)抽象，將所有車站視為節(jié)點，將所有線路視為連接節(jié)點的邊，形成有向網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并為每條邊賦權(quán)值為1，為每1 個節(jié)點編號。

步驟2：確定目標(biāo)車站對間列車徑路備選集合規(guī)模，即備選徑路條數(shù)，記為N。

步驟3：按有向拓?fù)渚W(wǎng)絡(luò)的鄰接矩陣構(gòu)造以N條徑路長度為元素的目標(biāo)車站對的初始向量，即

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

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

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

式中：r 為迭代次數(shù)。

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

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

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

2.2 列流線排序優(yōu)化算法

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

2.2.1 各區(qū)間內(nèi)列流線相對位置排序

1）算法步驟

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

圖3 任意車站區(qū)間內(nèi)須排序的列流線形式

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

針對任一區(qū)間，從列流線待鋪畫集合中篩選經(jīng)過該區(qū)間的待鋪畫列流線，即將列流線徑路中帶有目標(biāo)區(qū)間的列流線選出，并確定其在目標(biāo)區(qū)間內(nèi)的相對位置排序，具體步驟如下。

步驟1：初始化權(quán)重。根據(jù)列流圖的繪制思路，列流線間的交叉是由于列流線在車站進行方向轉(zhuǎn)變而形成，為了減少或避免交叉，當(dāng)列流線向靠近線路方向轉(zhuǎn)向時，列流線在區(qū)間內(nèi)的相對位置排序應(yīng)靠近線路；當(dāng)列流線向遠離線路方向轉(zhuǎn)向時，列流線在區(qū)間內(nèi)的相對位置排序應(yīng)遠離線路。據(jù)此思想以及鐵路左側(cè)行車規(guī)則，可根據(jù)進入?yún)^(qū)間和離開區(qū)間的方式，為列流線賦予一定的權(quán)重，即對右轉(zhuǎn)進入?yún)^(qū)間和右轉(zhuǎn)離開區(qū)間方式賦予較大權(quán)重，對左轉(zhuǎn)進入?yún)^(qū)間和左轉(zhuǎn)離開區(qū)間方式賦予較小權(quán)重，直向進入和直向離開方式賦予中間大小權(quán)重。

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

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

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

（3）按照上述（1）和（2）步完成目標(biāo)區(qū)間每一列流線的權(quán)值更新。

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

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

2）算法示例

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

圖4 列流線

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

（1）在區(qū)間DB″內(nèi)，列流線為右轉(zhuǎn)離開區(qū)間，初始化權(quán)重為4。

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

（3）進行逆向回溯?；厮莸缴弦粎^(qū)間DA，列流線右轉(zhuǎn)進入?yún)^(qū)間，降1 個數(shù)量級且反向，權(quán)重更新為3.6+0.5=4.1，列流線在區(qū)間DA 回溯終止，逆向追蹤后權(quán)重更新為4.1。

（4）在區(qū)間DB″內(nèi)，列流線以權(quán)重4.1 進行相對位置排序。

同理，圖4 所示列流線在區(qū)間B″E″內(nèi)的權(quán)重為-3.55，在區(qū)間E″F 內(nèi)的權(quán)重為-0.455。

2.2.2 同一經(jīng)緯線上列流線排序

1）算法步驟

根據(jù)第1 步中得到的各區(qū)間內(nèi)所有列流線的相對位置排序，進行同一經(jīng)緯線上所有列流線的二次排序，即實際位置排序，具體流程如下。

步驟1：確定排序標(biāo)準(zhǔn)。將同一經(jīng)緯線上各區(qū)間列流線及其相對位置排序取出，并將各區(qū)間內(nèi)的相對位置作為同一經(jīng)緯線上列流線2 次排序的標(biāo)準(zhǔn)。

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

步驟3：排序調(diào)整。根據(jù)從左至右順序，按照各區(qū)間內(nèi)列流線相對位置順序?qū)ν唤?jīng)緯線上所涉及的列流線位置排序進行檢查，若不一致則按各區(qū)間內(nèi)的相對位置排序進行調(diào)換；循環(huán)往復(fù)，直到同一經(jīng)緯線上的列流線位置順序與各區(qū)間內(nèi)的相對位置順序全部一致時停止，并更新相關(guān)區(qū)間列流線實際位置。

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

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

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

2）算法示例

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

圖5 列流線經(jīng)緯向排序的初始位置

該經(jīng)緯線上列流線位置排序具體步驟如下。

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

（2）用區(qū)間AB 內(nèi)的列流線順序?qū)Τ跏嘉恢眠M行檢查并調(diào)整，發(fā)現(xiàn)位置順序一致，為“bac”，再用區(qū)間BC 內(nèi)的列流線順序?qū)ι鲜鲰樞蜻M行檢查并調(diào)整，得到“bac”。

（3）循環(huán)檢查發(fā)現(xiàn)，該順序與各區(qū)間的相對位置都一致，更新各區(qū)間位置，即區(qū)間AB 內(nèi)的順序為“bac”，區(qū)間BC 內(nèi)的順序為“bc”（b 與c 之間為空閑位置）。

（4）檢查發(fā)現(xiàn)區(qū)間BC 內(nèi)存在始發(fā)且終到列流線，按照相對線路由近及遠順序進行插空，得到“bdc”。

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

圖6 列流線經(jīng)緯向排序后的位置

2.3 列流圖合并與調(diào)整

1）車站合并與調(diào)整

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

2）列流線合并

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

3 算法實現(xiàn)與案例應(yīng)用

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

表1 規(guī)劃年度始發(fā)客車對數(shù) 對·日-1

表2 規(guī)劃年度通過客車對數(shù) 對·日-1

表3 規(guī)劃年度遠期始發(fā)客車主要客站分工及作業(yè)量 對·日-1

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

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

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

圖7 規(guī)劃年度客運列流圖

4 結(jié) 語

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