段嘉偉， 陳秋文， 孫佩

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

0 引言

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

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

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

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

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

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

表1 貨運站節(jié)點編號

表2 路網(wǎng)文件

1.2 站名文件建立

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

表3 站名文件建立

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

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

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

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

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 算法用于求解全路任意兩貨運站之間的最短車流徑路。

表4 算法比選

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)號［7］。

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

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

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

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

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

步驟4：由最終得到的T標(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)絡(luò)圖

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

3 算法實現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

圖9 水治—安陽西最短車流徑路

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

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

圖11 盡頭站最短車流徑路

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

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

圖12 多重站點搭建最短徑路

圖13 咸陽—三民村1最短路徑生成程序截圖

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

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

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

圖15 遂寧—北碚新線

將該條線路作為添加對象添加至數(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)注格式為：“2401 2402 151”，新建線路站名文件標(biāo)注見表5。

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

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

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

5 結(jié)束語

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