基于貨物運到期限的列車運行線選擇優(yōu)化研究

張小炳, 李晟東，呂紅霞,3，徐長安

(1. 西南交通大學 交通運輸與物流學院，四川 成都 610031；2. 西南交通大學 全圖鐵路列車運行圖編制研發(fā)培訓中心，四川 成都 610031；3. 綜合交通運輸智能化國家地方聯(lián)合工程實驗室，四川 成都 610031)

鐵路貨物運輸在國民經(jīng)濟中占有重要地位。隨著社會經(jīng)濟的發(fā)展，高附加值、鮮活貨物等運輸穩(wěn)中有升，貨物運輸越來越表現(xiàn)出高時效性需求，貨主對運到期限的要求也越來越高。

我國傳統(tǒng)的組織型模式下[1]，編組計劃、運行圖等計劃提前制定好，致使鐵路日常產(chǎn)生的動態(tài)流與運行線匹配程度低，難以保障貨物運到期限。隨著鐵路運輸能力的提高與信息化程度的提升，使鐵路有條件實施規(guī)劃型運輸組織模式，通過收集短時(每日或幾日)的動態(tài)流，根據(jù)基本圖實現(xiàn)選線，綜合考慮機車車輛的調配，達到流線結合。從而鐵路部門可以根據(jù)運行圖，預先確定車流的掛線車次，進而確定全程貨物運輸方案。在車流始發(fā)站至終到站的運行區(qū)段中有許多條運行線，不同的運行線組合方案對應不同的運到期限，鐵路部門可以從貨主需求的角度，為貨主提供多種運到期限方案，當貨主選定某種運到期限方案后，鐵路部門也可隨之確定車流掛運方案。

國內外研究中，文獻[2]設置了違反運到期限的懲罰費用，以貨物運輸總費用最小為目標，運輸能力為約束建立了線性規(guī)劃模型；文獻[3]以車小時費用、改編費用與列車費用總和最小為目標，建立了以運輸能力、技術站改編能力和運到期限為約束的0-1規(guī)劃模型；文獻[4]考慮了列車定編及技術站改編能力等約束，確定了路網(wǎng)車流的運輸路徑以及服務列車；文獻[5-6] 將問題轉化為多商品流問題，分別構建了基于路徑的整數(shù)規(guī)劃和線性規(guī)劃模型；文獻[7]構建了單個技術站列車運行線接續(xù)優(yōu)化模型，并設計了基于網(wǎng)絡流的求解算法；文獻[8]以兩個技術站之間開行的直達列車為對象，建立了直達列車運行線選擇的0-1規(guī)劃模型，并設計了粒子群算法對模型進行求解；文獻[9-12]從統(tǒng)計概率的角度，通過統(tǒng)計分析得到貨物運輸各環(huán)節(jié)的概率分布，得到貨物運到期限及其實現(xiàn)的概率。

總體而言，既有文獻多基于預測的靜態(tài)車流，從中長期規(guī)劃的角度對問題進行研究，同時將違反運到期限作為懲罰費用進行考慮。為滿足貨主多樣化運輸需求，同時提高動態(tài)車流與運行線匹配性，為實施日貨物運輸組織提供精細化指導，本文在既有研究的基礎上，基于實施日動態(tài)車流，將列車運行線選擇問題抽象為網(wǎng)絡k短路問題，求解得到不同路徑代表不同的運行線選擇方案，以滿足貨主不同的運到期限要求。

1 問題描述及網(wǎng)絡結構抽象

1.1 問題描述

不同貨主對貨物的運到期限要求是不同的，不同的運到期限對應著不同的運輸費用，一般時間越短，運輸費用越高，貨主根據(jù)自身需求選擇某種運到期限方案來運輸貨物。因此，鐵路應提供多種運到期限方案供貨主選擇，不僅包括最短的運到期限，還應包括次短、第三短等的運到期限方案，以滿足不同貨主的需求。

當車流的始發(fā)終到站確定后，可通過在運行圖上選擇不同的運行線組合方案確定不同的運到期限。車站按技術作業(yè)可分為中間站和技術站，車流在中間站始發(fā)時，通過摘掛、小運轉列車輸送至下一臨近的技術站，繼而在該技術站通過直達、直通或區(qū)段列車輸送至下一技術站，最后再通過摘掛、小運轉列車輸送至終到中間站；或直接通過直達列車輸送至終到站。因此，在不同的區(qū)間可選擇不同列車種類所對應的運行線。

1.2 問題網(wǎng)絡抽象分析

運行圖是表示列車在區(qū)間運行及在車站到發(fā)或通過時刻的技術文件，具有空間及時間兩方面的屬性，為了更好地表示運行線之間的接續(xù)關系，對運行圖進行抽象擴展，構建時空拓撲網(wǎng)絡，見圖1。

以“列車運行弧”表示列車運行線，設置“虛擬節(jié)點”表示運行線代表的列車始發(fā)終到，當節(jié)點表示列車的始發(fā)時，稱之為“發(fā)點”；當表示列車的終到時，稱之為“到點”。為同一車站兩相鄰節(jié)點之間設置一條“車站中轉弧”，以表示運行線在技術站的接續(xù)關系。

則定義時空拓撲網(wǎng)絡G=(V,A)。V={Vf,Vd}為虛擬節(jié)點集合，Vf為發(fā)點集合，Vd為到點集合，其中Vm?Vf、Vr?Vd分別代表車流的始發(fā)點和終到點集合，如圖1中虛線框內所示。A={Ao,Ap}為弧集合，Ao為列車運行弧集合，Ap為車站中轉弧集合。

則將運行線選擇轉化為在時空拓撲網(wǎng)絡中尋找從車流始發(fā)站中某一發(fā)點至終到站中某一到點的可行路徑，每一條路徑對應一個貨物全程運輸時間，即k短路問題中的路徑長度，從而將問題轉化為多源多匯的k短路問題。

2 模型構建

2.1 模型假設

本模型的基本假設如下：

(1) 車流始發(fā)終到站、重量、換長等基本信息已知。

(2) 車流路徑、貨物列車編組計劃、列車運行圖等相關計劃已知。

(3) 技術站有足夠的中轉能力。

2.2 目標函數(shù)

以車流在途運輸時間最小構建0-1規(guī)劃模型目標函數(shù)，包括隨列車的區(qū)間運行時間和在技術站的中轉停留時間兩部分。

(1)

式中：S={1,2,…,n}為技術站集合，s∈S；E為運行線集合,l∈E;E1為E中除貨物始發(fā)終到站間的直達運行線以及從始發(fā)站發(fā)出的所有運行線，E2為E中除貨物始發(fā)終到站間的直達運行線以及到達終到站的所有運行線，E1，E2?E；rl、fl、dl分別為運行線l對應列車的運行時間、始發(fā)時刻、終到時刻；xl為0-1決策變量，當運行線l被選擇時取值為1，否則為0。

2.3 約束條件

(1) 貨物列車運輸能力約束

待掛運車流的重量加上已計劃掛運同一貨物列車的車流總重量u不能超過擔當該列貨車牽引任務的機車牽引定數(shù)Q，同時待掛運車流的換算長度加上已計劃掛運同一貨物列車的車流換算總長d不能超過鐵路規(guī)定的最大貨物列車換算長度L要求。因此考慮某貨物列車是否有足夠能力運輸該批貨物可用“剩余軸重w”及“剩余換長v”的概念為

w=Q-uv=L-d

對于不同的貨物列車，牽引機車類型、線路條件等的不同，因而其規(guī)定的總重量及總長度也有所不同。該組約束表示為

式中：δ為待掛運車流的重量；ξ為待掛運車流的換長；wl、vl分別為運行線l所對應的貨物列車的剩余軸重及剩余換長。

(2) 貨物中轉停留時間約束

對于非直達裝車的貨物，在途中需經(jīng)過技術改編，因而產(chǎn)生中轉停留時間，在運行圖上表現(xiàn)為運行線的接續(xù)時間。接續(xù)時間不能小于該技術站的中轉車平均停留時間t中，以保證車流在該技術站有足夠的時間完成從上一列車到下一列車的中轉。當技術站a的t中>t2，而t中

(4)

(3) 完整徑路約束

選擇的運行線方案應能剛好完成車流從始發(fā)站到終到站的完整運輸過程，約束為

(5)

(4) 決策變量0-1約束

式(6)是對決策變量的0-1約束，當運行線si被選擇時取值為1，否則為0。

(6)

3 算法設計

3.1 SA算法關鍵步驟設計

對于本文構建的0-1規(guī)劃模型，隨著貨物始發(fā)終到站之間的距離增加，運行線的組合方案急劇增加，難以用分支定界等傳統(tǒng)方法找到最優(yōu)解。因此針對模型特點，設計了模擬退火(SA)的啟發(fā)式算法進行求解，SA關鍵步驟設計如下。

(1) 解的構造

構建矩陣X=[C1,C2]表示運行線選擇方案，其中向量C1=[s1,s2,…,sm]T、C2=[i1,i2,…,im]T，m∈{1,2,…,n-1}為C1、C2長度。則構建的矩陣表示車站s的第i條運行線依次被選擇。

(2) 初始解的生成

SA算法求得的最終解并不十分依賴初始解，因此采用隨機方法生成初始運行線選擇組合方案。隨機性體現(xiàn)在隨機選擇某站的始發(fā)運行線，一旦選定某條運行線后，運行線接續(xù)的下一車站也隨之確定，當隨機選定的運行線對應的下一到達車站為車流終到站時，即得到完整的初始解。

(3) 鄰域解的產(chǎn)生

采用隨機突變方法設計解的鄰域結構。隨機選擇當前解X的某一車站作為突變點，隨機選擇一條除當前解選定的運行線，并依此產(chǎn)生鄰域解。

(4) 冷卻過程

對相關參數(shù)經(jīng)過多種設置方案實驗，得到較優(yōu)的設定如下。初始溫度t_s=999，終止溫度t_e=10-0.003，溫度衰減系數(shù)α=0.90，馬爾可夫鏈長度為99。當溫度低于終止溫度時，算法終止，得到最優(yōu)解。

3.2 運行圖k短路求解策略

通過在運行圖上尋找不同的運行線組合方案，滿足對貨主不同運到期限的要求，以運輸時間作為“路徑長度”，進而轉變?yōu)榍蠼舛嘣炊鄥R的k短路問題。結合文獻[13]，本文提出一種運行線選擇的k短路算法。

基于以上，可以得到運行圖中k(k≥2)短路的求解策略：

(3) 將上述(k-1)2條最短背離路徑按照運輸時間的大小排列，其中前k-1條路徑即為次短、第三短到第k短的路徑。

3.3 基于SA的k短路算法

Step1調用SA算法，求得最優(yōu)運行線組合方案，即最短路p1={e1,e2,…,em}。

Step4將這(k-1)2條最短背離路徑按權值由小到大排列，其中前k-1條路徑即為次短、第三短到第k短的路徑，此時算法結束。

4 算例分析

某批貨物欲從株洲北站(A)發(fā)往濟西站(H)，根據(jù)車流徑路以及編組計劃，查知途經(jīng)萍鄉(xiāng)(B)、向塘西(C)、阜陽北(D)、徐州北(E)、兗州東(F)以及泰山站(G)，見圖3。實施日期間，部分貨物列車運行時刻以及剩余軸重、換長等信息見表1。該批貨物裝車后的重量及換長分別為1 400 t、24.7，各技術站有調中轉時間都為540 min。

本文在MATLAB R2010b軟件編程環(huán)境下實現(xiàn)了模型與算法的求解。在設計的k短路算法中，需要多次調用SA算法求解備選路徑集的最短路徑，而SA算法易陷入局部最優(yōu)，因此在每次調用SA算法時，設置使其循環(huán)10次，取10次中最小的解作為本次調用得到的最優(yōu)解。在CPU為Inter Core i7-6700HQ，RAM為16 GB的PC機上，取k=3，耗時24 s，得到優(yōu)化結果見表2。

表2給出了3種運到期限方案可供貨主選擇，同時對于每種運到期限，給出了相對應的運行線選擇方案。在本文算例中，從車站A運往車站H的最短、第二短以及第三短運到期限分別為4 273、 4 868、4 928 min，而每個運到期限又對應多種運行線組合方案，可以滿足貨主對特殊交付、收貨時間的需求。當貨主選定某種方案后，鐵路部門可以根據(jù)相對應的運行線選擇方案來組織車流運輸，如貨主選擇方案1后，車流依次選擇A4、C2、D2和E5運行線進行掛線運輸。

表1 備選列車運行線集

表2 運到期限方案

5 結束語

在鐵路加強供給側改革，向以市場為導向的運輸組織模式轉變中，加強基于運到期限的服務及運輸組織顯得尤為關鍵。本文通過在運行圖上選擇不同的運行線作為車流的掛線車次，不同的運行線選擇方案對應不同的運到期限，進而將問題轉變?yōu)樵谶\行圖上求解多源多匯的k短路問題。這樣能夠使貨主在填寫貨票時，能夠方便清楚地了解到運到期限參考值，進而根據(jù)自身需求選擇不同的運到期限運輸方案，同時為實施日運輸組織提供指導，實現(xiàn)精細化貨物運輸組織。

本文考慮了列車運輸能力、技術站有調中轉作業(yè)時間等關鍵影響因素，構建了以貨物在途運輸時間最小為目標的0-1規(guī)劃模型。針對問題特性，設計了基于模擬退火的k短路求解算法，通過算例分析驗證了模型及算法的有效性。本文主要考慮了貨主最為關心的運輸時間，進一步可考慮運輸費用等因素，以提高方法的適用性。