注：本文為期刊公眾號簡版，完整版已發(fā)群內(nèi)自取。

段嘉偉，廣州東華職業(yè)學(xué)院

陳秋文，廣州東華職業(yè)學(xué)院

孫佩，西安交通工程學(xué)院

0?引言

我國從上世紀(jì)90年代開始運用優(yōu)化算法研究車流徑路問題，鐵路車流徑路選取對鐵路行車運輸組織十分重要，也是鐵路運輸部門高效銜接組織生產(chǎn)的有利基礎(chǔ)。車流徑路問題貫穿于列車運行圖、貨物列車運輸計劃、車站作業(yè)階段計劃等運輸計劃編制過程中，為充分利用路網(wǎng)有限資源，應(yīng)合理有效選取車流徑路。最短車流徑路算法目前比較成熟，其中趙娟根據(jù)車流組織模式對鐵路車流徑路進(jìn)行優(yōu)化，建立線性0-1規(guī)劃模型；高明瑤等以車流總走行費用最小為目標(biāo)函數(shù)，構(gòu)建基于改進(jìn)點-弧模型的鐵路網(wǎng)車輛徑路優(yōu)化模型，采用Lingo軟件求解；溫旭紅以多商品網(wǎng)絡(luò)流理論為基礎(chǔ)，構(gòu)建鐵路網(wǎng)車流分配與樹狀徑路綜合問題的混合整數(shù)規(guī)劃模型。

綜上分析，既有文獻(xiàn)對鐵路最短車流徑路的研究，多聚焦于部分路網(wǎng)中指定兩站的最短車流徑路求解，求解結(jié)果具有一定局限性，且路網(wǎng)簡單導(dǎo)致算法優(yōu)勢體現(xiàn)不明顯。因此編制全路任意發(fā)到站的最短車流徑路算法具有一定實踐意義。通過對既有最短徑路算法進(jìn)行比較，確定采用Dijkstra算法來實現(xiàn)鐵路貨運節(jié)點站間最短車流徑路、非節(jié)點站間最短車流徑路、支線上盡頭站間最短車流徑路、多重站點最短車流徑路，并提供路網(wǎng)數(shù)據(jù)維護(hù)功能。

1?路網(wǎng)數(shù)學(xué)描述

根據(jù)我國《鐵路技術(shù)管理規(guī)程》規(guī)定，路網(wǎng)中銜接3個及其以上方向的車站、技術(shù)站稱為節(jié)點站，辦理少量客貨運業(yè)務(wù)或供列車會讓及越行的車站皆為中間站，線路兩端盡頭處設(shè)置的車站皆為盡頭站。節(jié)點站采用G=（V，E，W）表示，V是路網(wǎng)中節(jié)點站編號在所建網(wǎng)絡(luò)中節(jié)點的集合，E為網(wǎng)絡(luò)中邊的集合，E=｛eij|路網(wǎng)中節(jié)點站i與j相連｝，W為網(wǎng)絡(luò)中邊的長度。我國鐵路網(wǎng)共有中間站5600多個，中間站車站位置由該車站節(jié)點編號與兩端節(jié)點站對應(yīng)節(jié)點編號之間的里程所確定，支線上的盡頭站位置由該車站節(jié)點編號距一端節(jié)點站節(jié)點編號之間的里程確定。綜上所述，將節(jié)點站的節(jié)點編號編制形成路網(wǎng)文件，以表述兩節(jié)點站之間的里程。路網(wǎng)上節(jié)點站、中間站、盡頭站的車站名用下述數(shù)學(xué)描述形成站名文件，利用路網(wǎng)文件搭建鐵路貨運路網(wǎng)，借助站名文件搜索路網(wǎng)文件中節(jié)點編號對應(yīng)的車站名，從而建立整個鐵路計算機路網(wǎng)。

1.1 節(jié)點站路網(wǎng)文件?

以“2020全國鐵路貨運營業(yè)站示意圖”為基本路網(wǎng)結(jié)構(gòu)，該鐵路網(wǎng)結(jié)構(gòu)圖G是1個連通圖，頂點數(shù)量繁多，大部分的頂點度數(shù)相對來說比較小，以二度頂點數(shù)目居多。由于繁多的頂點數(shù)在利用計算機求解最短車流徑路時所消耗的時間過長，因此采用節(jié)點站作為路網(wǎng)骨架，由此可見節(jié)點站在路網(wǎng)中占據(jù)重要地位。選取商丘—南京東的部分路網(wǎng)（見圖1）并對節(jié)點站進(jìn)行節(jié)點編號，形成路網(wǎng)文件步驟如下：

步驟1：對路網(wǎng)貨運節(jié)點站進(jìn)行節(jié)點編號（見表1）。

步驟2：對節(jié)點站進(jìn)行命名（見表2），所有節(jié)點站通過節(jié)點編號命名方法形成路網(wǎng)文件（見圖2）。

1.2 站名文件建立?

在路網(wǎng)中，站名文件是通過賦予節(jié)點站、盡頭站 特殊站名命名規(guī)則，并根據(jù)中間站基于距該條線路兩端節(jié)點站的距離來確定并建立。站名文件建立見表3。

根據(jù)站點在路網(wǎng)中的所處位置以及對應(yīng)的站點命名方式對所有站點進(jìn)行命名，形成站名文件，站名文件生成程序截圖見圖3。

基于上述2種文件，通過輸入輸出流讀文件的方式建立路網(wǎng)，如建立從商丘—南京東的路網(wǎng)圖（見圖4）。

2?算法描述

2.1 最短路徑算法比選?

目前簡單路網(wǎng)中常用的2類算法是Dijkstra和Floyd算法（見表4），其中Floyd算法在求解最短車流徑路時，需構(gòu)造數(shù)據(jù)矩陣，計算復(fù)雜，不適用于復(fù)雜路網(wǎng)計算；Dijkstra較Floyd算法求解時間快，且精確度高。我國鐵路網(wǎng)具有節(jié)點站基數(shù)大、路網(wǎng)構(gòu)造復(fù)雜且路權(quán)沒有負(fù)值等特點，計算復(fù)雜度較高，因此宜選擇Dijkstra算法用于求解全路任意兩貨運站之間的最短車流徑路。

2.2?Dijkstr算法程序步驟

Dijkstra算法基本思想是：設(shè)定2個標(biāo)號，一個P標(biāo)號，一個T標(biāo)號，P標(biāo)號為點標(biāo)號，是永久性標(biāo)號，P（Vi）表示起點到該點的最短路權(quán)值。T標(biāo)號為邊標(biāo)號，是臨時性標(biāo)號，初始定義一個最大鄰接標(biāo)號值∞，表示起點到該點的路權(quán)為∞，最終目標(biāo)是將邊∞不斷縮小，最終達(dá)到所有的T標(biāo)號改為P標(biāo)號。

2.3?路網(wǎng)拆分與重構(gòu)

在2條干線之間新建1條線路，屬于路網(wǎng)中間站之間的1條鐵路新線，對原有路網(wǎng)進(jìn)行拆分和重構(gòu)，將新建線路融入既有鐵路路網(wǎng)中，形成新路網(wǎng)。例如：現(xiàn)需在路網(wǎng)中的牡丹江—下城子、牡丹江—林口2條線路之間新建1條德惠—地中的鐵路線路（見圖5）。

從圖5可知，路網(wǎng)文件中格式為：節(jié)點編號19→牡丹江，節(jié)點編號20→下城子，節(jié)點編號31→林口。牡丹江距離下城子98km，牡丹江距離林口110km。假設(shè)從施工隊可知，德惠距離牡丹江48km，距離下城子50km。地中距離牡丹江50km，距離林口60km。因為路網(wǎng)中最大節(jié)點編號為2400，因此德惠與地中2節(jié)點站的編號分別為2401、2402。德惠—地中之間有1個中間站為天中，天中距離德惠70km，天中距離地中60km。

由于德惠—地中新建線路的加入，原路網(wǎng)文件與站名文件需進(jìn)行部分更新。路網(wǎng)文件中19→20→98與19→20→110這2條線路數(shù)據(jù)刪除，新增4條線路，19→2401→48與2401→30→50，19→2402→50與2402→31→60。站名文件增加1個車站的命名為2401→70→2402→60天中。

3?算法實現(xiàn)

3.1?節(jié)點站間最短車流徑路求解

鐵路網(wǎng)中，選取發(fā)站西安西，到站蘭州北，調(diào)用Dijkstr算法程序得到最短車流徑路。因此，從西安西站發(fā)一批貨物至蘭州北站，經(jīng)由該最短車流徑路，走形公里數(shù)為686km。

3.2 非節(jié)點站間最短車流徑路求解?

通過對所建網(wǎng)絡(luò)得到的數(shù)據(jù)文件進(jìn)行處理，可得路網(wǎng)中共有站點6241個，其中節(jié)點站673個（中間站與盡頭站共5568個），節(jié)點站最大節(jié)點編號為2400。

3.3 支線上盡頭站間最短車流徑路?

盡頭站點路網(wǎng)見圖6，在站名文件中對圖10中車站名進(jìn)行檢索可知，該路網(wǎng)中所有站點歸中國鐵路武漢局集團(tuán)有限公司管轄。胡家營、厲山、西齋在站名文件中為節(jié)點站，部營、丹江、宜昌在站名文件中為盡頭站。其中，丹江表示格式為“83446-10”，含義是丹江距834號節(jié)點站老河口東46km，屬于胡家營、厲山兩節(jié)點站之間干線上的一條支線。宜昌車站表示格式為“84437-10”，含義是宜昌距844號節(jié)點站鴉鵲嶺37km，屬于荊門、西齋兩節(jié)點站之間干線上的一條支線。通過調(diào)用Dijkstr算法程序，得到丹江—宜昌兩盡頭站間最短車流徑路和最短里程（見圖7）。

3.4 多重站點最短車流徑路求解?

通過站名文件發(fā)現(xiàn)某些貨運站點在路網(wǎng)中重復(fù)出現(xiàn)，比如三民村貨運站。在圖8中，從戶縣發(fā)一批貨物至三民村或者從咸陽發(fā)一批貨物至三民村，確定最短徑路為走行徑路的方法為：新建一個三民村1節(jié)點站，節(jié)點編號2405，將圖中2個三民村與三民村1相連，里程設(shè)置為0，此時便可保證從咸陽或者戶縣發(fā)一批貨物至三民村，走行徑路為最短徑路，經(jīng)由的三民村是最短徑路上的三民村，生成程序截圖見圖9、圖10。

4?路網(wǎng)數(shù)據(jù)維護(hù)

“2020全國鐵路貨運營業(yè)站示意圖”是一個動態(tài)網(wǎng)絡(luò)圖，隨著路網(wǎng)規(guī)模的不斷擴(kuò)大，數(shù)據(jù)文件也隨之不斷更新。例如：遂渝線上的遂寧—北碚新線（見圖11）是后期投入所建，數(shù)據(jù)文件中并沒有該條線路信息。

將該條線路作為添加對象添加至數(shù)據(jù)文件中，其他新建線路添加方法相同，添加思路如下：

（1）通過對現(xiàn)有中國鐵路成都局集團(tuán)有限公司路網(wǎng)及原有站名文件進(jìn)行檢查發(fā)現(xiàn)，遂渝線上遂寧東接蓬溪中間站，西接遂寧西中間站；北碚北接磨心坡，南接團(tuán)結(jié)村；遂寧—北碚之間所有的站點在站名文件中均無記錄，因此將遂寧—北碚線作為新線加入路網(wǎng)文件與站名文件中。

（2）路網(wǎng)文件標(biāo)注方法：新增1條線路，起點為遂寧，節(jié)點編號為2401，終點為北碚，節(jié)點編號為2402。路網(wǎng)文件標(biāo)注格式為：“24012402151”，新建線路站名文件標(biāo)注見表5。

（3）在路網(wǎng)文件與站名文件中完成新線標(biāo)注，運行最短車流徑路算法程序，得到最短里程151km，經(jīng)由徑路為：遂寧→遂寧南→三星→潼南→下太和→渭沱→合川→石子山→北碚（見圖12）。

5?結(jié)束語

通過介紹路網(wǎng)中節(jié)點站、中間站、盡頭站在數(shù)據(jù)文件中的命名方法，在計算機內(nèi)建立鐵路貨運路網(wǎng)，應(yīng)用Dijkstr算法編制鐵路貨運最短車流徑路算法程序，分析了多種情況下的發(fā)站、到站最短車流徑路求解思路。但僅分析了鐵路貨運最短車流徑路，而沒有考慮鐵路貨運最短車流徑路是否滿足超限貨物運輸需求。得到的最短車流徑路如果加入貨車在沿途技術(shù)站的解編時間，列車是否按照求得的最短車流徑路繼續(xù)走行等問題，還需進(jìn)一步開展相關(guān)研究。

來源：《中國鐵路》編輯部