鐵路貨運(yùn)最短車流徑路算法與實(shí)現(xiàn)

段嘉偉， 陳秋文， 孫佩

（1.廣州東華職業(yè)學(xué)院 管理學(xué)院，廣東 廣州 510000；2.西安交通工程學(xué)院 交通運(yùn)輸學(xué)院，陜西 西安 710300）

0 引言

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

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

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

根據(jù)我國(guó)《鐵路技術(shù)管理規(guī)程》規(guī)定，路網(wǎng)中銜接3個(gè)及其以上方向的車站、技術(shù)站稱為節(jié)點(diǎn)站，辦理少量客貨運(yùn)業(yè)務(wù)或供列車會(huì)讓及越行的車站皆為中間站，線路兩端盡頭處設(shè)置的車站皆為盡頭站。節(jié)點(diǎn)站采用G=（V，E，W）表示，V是路網(wǎng)中節(jié)點(diǎn)站編號(hào)在所建網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，E為網(wǎng)絡(luò)中邊的集合，E=｛eij|路網(wǎng)中節(jié)點(diǎn)站i與j相連｝，W為網(wǎng)絡(luò)中邊的長(zhǎng)度［5］。我國(guó)鐵路網(wǎng)共有中間站5 600 多個(gè)，中間站車站位置由該車站節(jié)點(diǎn)編號(hào)與兩端節(jié)點(diǎn)站對(duì)應(yīng)節(jié)點(diǎn)編號(hào)之間的里程所確定，支線上的盡頭站位置由該車站節(jié)點(diǎn)編號(hào)距一端節(jié)點(diǎn)站節(jié)點(diǎn)編號(hào)之間的里程確定。

綜上所述，將節(jié)點(diǎn)站的節(jié)點(diǎn)編號(hào)編制形成路網(wǎng)文件，以表述兩節(jié)點(diǎn)站之間的里程。路網(wǎng)上節(jié)點(diǎn)站、中間站、盡頭站的車站名用下述數(shù)學(xué)描述形成站名文件，利用路網(wǎng)文件搭建鐵路貨運(yùn)路網(wǎng)，借助站名文件搜索路網(wǎng)文件中節(jié)點(diǎn)編號(hào)對(duì)應(yīng)的車站名，從而建立整個(gè)鐵路計(jì)算機(jī)路網(wǎng)。

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

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

圖1 商丘—南京東部分路網(wǎng)圖

步驟1：對(duì)路網(wǎng)貨運(yùn)節(jié)點(diǎn)站進(jìn)行節(jié)點(diǎn)編號(hào)（見(jiàn)表1）。步驟2：對(duì)節(jié)點(diǎn)站進(jìn)行命名（見(jiàn)表2），所有節(jié)點(diǎn)站通過(guò)節(jié)點(diǎn)編號(hào)命名方法形成路網(wǎng)文件（見(jiàn)圖2）。

圖2 路網(wǎng)文件生成程序截圖

表1 貨運(yùn)站節(jié)點(diǎn)編號(hào)

表2 路網(wǎng)文件

1.2 站名文件建立

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

表3 站名文件建立

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

圖3 站名文件生成程序截圖

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

圖4 商丘—南京東路網(wǎng)圖

2 算法描述

2.1 最短路徑算法比選

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

表4 算法比選

2.2 Dijkstr算法程序步驟

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

數(shù)學(xué)描述如下：

用Wij表示Vi-Vj之間的路權(quán)，兩站相鄰，路權(quán)為實(shí)際里程，兩點(diǎn)不相鄰時(shí)，路權(quán)Wij=∞，步驟如下：

步驟1：給起點(diǎn)V1標(biāo)上永久性標(biāo)號(hào)，記為P（V1）=0，其余節(jié)點(diǎn)初始化為∞，記為T（Vj）=∞，若起點(diǎn)與該點(diǎn)直接相鄰，T（Vj）=Wij，否則等于∞。

步驟2：所有T標(biāo)號(hào)中選擇最小的，更新為P標(biāo)號(hào)，判斷表達(dá)式T（Vj）=min｛T（Vj），T（Vj）+Wij｝，更新T標(biāo)號(hào)。

步驟3：在所有的T標(biāo)號(hào)中選擇最小的T標(biāo)號(hào)作為P標(biāo)號(hào)繼續(xù)勘測(cè)，直到所有的標(biāo)號(hào)全部為P標(biāo)號(hào)。

步驟4：由最終得到的T標(biāo)號(hào)點(diǎn)起，從后往前搜索最短車流徑路。

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

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

圖5 新建線路網(wǎng)絡(luò)圖

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

由于德惠—地中新建線路的加入，原路網(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 個(gè)車站的命名為2401→70→2402→60天中。

3 算法實(shí)現(xiàn)

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

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

圖6 西安西—蘭州北最短車流徑路

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

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

3.2.1 不同區(qū)間中間站最短車流徑路求解

最短車流徑路算法程序中，路網(wǎng)節(jié)點(diǎn)站因在路網(wǎng)文件中具有其對(duì)應(yīng)的節(jié)點(diǎn)編號(hào)，因此可以得到任意兩節(jié)點(diǎn)站之間的最短車流徑路。但如果中間站沒(méi)有節(jié)點(diǎn)編號(hào)，在求不同區(qū)段內(nèi)兩中間站之間的最短車流徑路時(shí)，則需要將中間站添至路網(wǎng)，中間站到路網(wǎng)兩端節(jié)點(diǎn)站的里程與站名文件中該站節(jié)點(diǎn)編號(hào)至兩端節(jié)點(diǎn)編號(hào)的里程等價(jià)。

假設(shè)需要求解黃土店—安定的最短車流徑路，通過(guò)站名文件搜索可知，黃土店是位于沙河—雙橋兩節(jié)點(diǎn)站之間車流徑路上的中間站；安定是位于黃村—漢溝鎮(zhèn)兩節(jié)點(diǎn)站之間車流徑路上的中間站。求解思路是將黃土店與安定變?yōu)楣?jié)點(diǎn)站，節(jié)點(diǎn)編號(hào)分別為2407、2408（見(jiàn)圖7）。通過(guò)調(diào)用Dijkstr 算法程序，黃土店—安定最短車流徑路在中間站被添加至路網(wǎng)前后的最短車流徑路分別見(jiàn)圖8（a）、圖8（b）。

圖7 不同區(qū)間中間站未添至路網(wǎng)前的最短車流徑路

圖8 最短車流徑路生成程序截圖

3.2.2 同一區(qū)間內(nèi)中間站求解最短車流徑路

通過(guò)搜索站名文件發(fā)現(xiàn)水治與安陽(yáng)西屬于石澗—安陽(yáng)兩節(jié)點(diǎn)站之間的中間站，在站名文件中，兩中間站與路網(wǎng)中兩節(jié)點(diǎn)站的站點(diǎn)信息格式為：899→900→25→石澗至安陽(yáng)；899→7→900→18→水冶；899→18→900→7→安陽(yáng)西。水治—安陽(yáng)西最短車流徑路見(jiàn)圖9，水治—安陽(yáng)西最短車流徑路里程為11 km。

圖9 水治—安陽(yáng)西最短車流徑路

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

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

圖11 盡頭站最短車流徑路

3.4 多重站點(diǎn)最短車流徑路求解

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

圖12 多重站點(diǎn)搭建最短徑路

圖13 咸陽(yáng)—三民村1最短路徑生成程序截圖

圖14 戶縣—三民村1最短徑路生成程序截圖

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

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

圖15 遂寧—北碚新線

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

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

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

表5 新建線路站名文件標(biāo)注

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

圖16 新加線路生成最短徑路程序截圖

5 結(jié)束語(yǔ)

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