直通貨物列車運(yùn)行線優(yōu)化選擇問題的網(wǎng)絡(luò)圖研究

余后倫，笪翔

(1.中國鐵路設(shè)計集團(tuán)有限公司,天津300251；2.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院,四川成都 610031)

0 引言

近年來鐵路旅客運(yùn)輸穩(wěn)步發(fā)展，而鐵路貨物運(yùn)輸因貨物到達(dá)時間不能得到有效保證、貨運(yùn)周期長而飽受詬病[1-2]。列車運(yùn)行圖作為鐵路行車組織中的核心技術(shù)文件之一，是聯(lián)系鐵路內(nèi)部與社會外界的紐帶，因此理論上可以通過優(yōu)化貨物列車運(yùn)行圖改善鐵路貨物運(yùn)輸現(xiàn)狀[3-5]。在編制貨物列車運(yùn)行圖時，一般遵循先直通后管內(nèi)的原則，即優(yōu)先安排直通貨物列車的運(yùn)行線，因此，直通貨物列車運(yùn)行線的選擇對后續(xù)管內(nèi)貨物列車的運(yùn)行線安排以及整個運(yùn)行圖的編制質(zhì)量能產(chǎn)生顯著影響[6-7]。一般而言，直通貨物列車在技術(shù)站的中轉(zhuǎn)停留時間是影響列車運(yùn)行線優(yōu)化選擇的重要因素，因此壓縮直通貨物列車在技術(shù)站的中轉(zhuǎn)停留時間是優(yōu)化貨物列車運(yùn)行圖的一個重要方向[8-9]。

直通貨物列車從始發(fā)站到終到站的走行過程中在沿途技術(shù)站只進(jìn)行無改編中轉(zhuǎn)作業(yè)，不用考慮沿途技術(shù)站的貨車集結(jié)時間。貨車集結(jié)時間是指從直通貨物列車到達(dá)技術(shù)站時起，進(jìn)行無改編中轉(zhuǎn)的技術(shù)作業(yè)后至列車出發(fā)時為止的列車在站停留時間[10-11]。因此在不影響其他列車運(yùn)行線調(diào)整的情況下可通過壓縮直通貨物列車在沿途技術(shù)站的接續(xù)時間來使貨物運(yùn)到時間盡可能縮短，以此為原則優(yōu)化選擇直通貨物列車運(yùn)行線，可以確保運(yùn)行圖滿足動態(tài)運(yùn)輸市場需求并順利實(shí)施，同時保證貨物運(yùn)到期限要求[12]。

1 網(wǎng)絡(luò)圖模型的建立

在一個直線區(qū)段中，已知有e列無改編直通貨物列車需要沿下行方向通過h個技術(shù)站，一般情況下，直通貨物列車在任一技術(shù)站的停留時間不超過2 d，列車在沿途區(qū)段可以選擇的運(yùn)行線數(shù)量是相等的，直通貨物列車等級相同(運(yùn)行速度一樣)，車站能力(工作人員和到發(fā)線等設(shè)備設(shè)施的數(shù)量)充足，任一列直通列車在某個技術(shù)站的出發(fā)時刻一旦確定，則它在下一個技術(shù)站的到達(dá)時刻也就已經(jīng)確定(基本列車運(yùn)行圖中已經(jīng)鋪畫出了各技術(shù)站之間的運(yùn)行線)[13]。

圖1 基本列車運(yùn)行圖中的運(yùn)行線

假設(shè)在基本列車運(yùn)行圖中，任一技術(shù)站w(w為當(dāng)前技術(shù)站編號且w=1,2,……，h)共有p個到達(dá)運(yùn)行線(到達(dá)時刻對應(yīng)的運(yùn)行線)和q(p與q相等)個出發(fā)運(yùn)行線(出發(fā)時刻對應(yīng)的運(yùn)行線)供列車選擇(如圖1所示)[14]。

(1)

式(1)表示對任一列直通列車在技術(shù)站的停留時間不得少于該技術(shù)站的標(biāo)準(zhǔn)接續(xù)時間，當(dāng)出發(fā)運(yùn)行線與到達(dá)運(yùn)行線對應(yīng)的時刻相減所得的時間小于標(biāo)準(zhǔn)接續(xù)時間，若依然保持到達(dá)和出發(fā)運(yùn)行線不變，則這列直通列車就要在該站多停留1 d[17-18]。

直通貨物列車運(yùn)行線優(yōu)化選擇的問題實(shí)際就是在各個技術(shù)站挑選與直通列車數(shù)量相匹配且滿足標(biāo)準(zhǔn)接續(xù)時間的列車到達(dá)運(yùn)行線和出發(fā)運(yùn)行線，使直通列車在沿途所有技術(shù)站進(jìn)行接續(xù)時的總停站時間最小[19-20]。根據(jù)上述理論可構(gòu)建對應(yīng)的網(wǎng)絡(luò)圖如圖2所示。

圖2 直通列車運(yùn)行線優(yōu)化選擇容量費(fèi)用網(wǎng)絡(luò)圖

2 算法求解

該網(wǎng)絡(luò)圖模型是一個典型的流值一定的容量費(fèi)用網(wǎng)絡(luò)，當(dāng)e=1時，問題變?yōu)榍蠼饩W(wǎng)絡(luò)圖從源點(diǎn)到匯點(diǎn)最短路問題。受此啟發(fā)，可結(jié)合實(shí)際問題考慮設(shè)計這樣一種算法思路，先根據(jù)運(yùn)籌學(xué)中經(jīng)典的Dijkstra算法在網(wǎng)絡(luò)圖中算出一個從源點(diǎn)到匯點(diǎn)的最短路，將其記下并保存，然后將所得的最短路徑在原網(wǎng)絡(luò)圖上刪掉(或者屏蔽)，再開始在剩下的網(wǎng)絡(luò)圖上進(jìn)行下一個從源點(diǎn)到匯點(diǎn)的最短路徑的計算，這樣每得到一個最短路，就將其記錄下來后刪掉或者屏蔽，最后一定能得到e個這樣的路徑，借鑒最小費(fèi)用流問題中的連續(xù)最短路算法理論可知，這e個路徑分別對應(yīng)e列車的最優(yōu)運(yùn)行線選擇方案。因此，算法設(shè)計步驟可總結(jié)如下：

1)首先將各列車時刻轉(zhuǎn)化為相應(yīng)的時間[0,1440]；

3)根據(jù)Dijkstra算法求解現(xiàn)有的網(wǎng)絡(luò)圖中從源點(diǎn)vs到匯點(diǎn)vt的最短路徑并將其保存；

4)把3)所得最短路徑對應(yīng)的弧在網(wǎng)絡(luò)圖上進(jìn)行屏蔽，得到新的網(wǎng)絡(luò)圖；

5)返回到3)并重復(fù)3)、4)直至所保存的最短路徑數(shù)量與直通列車數(shù)e相等，根據(jù)得到的這e條路徑即可按照網(wǎng)絡(luò)圖中各點(diǎn)對應(yīng)關(guān)系得到這e列直通列車的運(yùn)行線最優(yōu)選擇方案。

上述算法可在MATLAB軟件中進(jìn)行編程實(shí)現(xiàn)以解決實(shí)際問題。

3 算例

3.1 背景資料

圖3 區(qū)段地理位置情況

已知某個直線區(qū)段在路網(wǎng)的情況如圖3所示，A—E分別表示5個技術(shù)站(共4個區(qū)段)，車次號分別為24001、24003、24005、24007的4列直通貨物列車需從A站無改編運(yùn)行到E站，已知每個站的無改編中轉(zhuǎn)列車的標(biāo)準(zhǔn)接續(xù)時間均為30 min，4列直通貨物列車速度等級相同，各區(qū)段運(yùn)行線的信息情況如表1所示。

表1 各區(qū)段列車運(yùn)行線信息

3.2 算例求解

根據(jù)網(wǎng)絡(luò)圖模型的算法步驟在MATLAB軟件中進(jìn)行編程實(shí)現(xiàn)，可得到路徑(各區(qū)間的運(yùn)行線)結(jié)果如表2所示。根據(jù)各運(yùn)行區(qū)段的運(yùn)行線優(yōu)選方案可得列車時刻表如表3所示，此時這4列直通貨物列車在技術(shù)站的接續(xù)總時間最短，根據(jù)MATLAB軟件求解結(jié)果可知這4列車的最小接續(xù)總時間為1 034 min。

4 結(jié)語

通過對直線區(qū)段的直通貨物列車運(yùn)行線優(yōu)化選擇的問題進(jìn)行研究，建立了以直通列車在沿途技術(shù)站的接續(xù)總時間最短為目標(biāo)的網(wǎng)絡(luò)圖模型，并通過實(shí)際算例進(jìn)行了模型驗(yàn)證，得出對直通貨物列車運(yùn)行線進(jìn)行優(yōu)化選擇的一種可行方法，旨在為貨物列車運(yùn)行圖編制和優(yōu)化提供參考，對鐵路貨物運(yùn)輸組織具有一定的參考。

表2運(yùn)行區(qū)段運(yùn)行線優(yōu)選路徑

列車車次運(yùn)行線AB段BC段CD段DE段24001771022400322692400556912400710157

表3 列車時刻表