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

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

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

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

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

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

1 問題描述及網(wǎng)絡(luò)結(jié)構(gòu)抽象

1.1 問題描述

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

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

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

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

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

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

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

2 模型構(gòu)建

2.1 模型假設(shè)

本模型的基本假設(shè)如下：

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

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

(3) 技術(shù)站有足夠的中轉(zhuǎn)能力。

2.2 目標(biāo)函數(shù)

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

(1)

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

2.3 約束條件

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

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

w=Q-uv=L-d

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

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

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

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

(4)

(3) 完整徑路約束

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

(5)

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

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

(6)

3 算法設(shè)計

3.1 SA算法關(guān)鍵步驟設(shè)計

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

(1) 解的構(gòu)造

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

(2) 初始解的生成

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

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

采用隨機(jī)突變方法設(shè)計解的鄰域結(jié)構(gòu)。隨機(jī)選擇當(dāng)前解X的某一車站作為突變點(diǎn)，隨機(jī)選擇一條除當(dāng)前解選定的運(yùn)行線，并依此產(chǎn)生鄰域解。

(4) 冷卻過程

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

3.2 運(yùn)行圖k短路求解策略

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

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

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

3.3 基于SA的k短路算法

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

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

4 算例分析

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

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

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

表1 備選列車運(yùn)行線集

表2 運(yùn)到期限方案

5 結(jié)束語

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

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