余后倫，笪翔

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

0 引言

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

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

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

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

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

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

(1)

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

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

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

2 算法求解

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

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

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

4)把3)所得最短路徑對(duì)應(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)對(duì)應(yīng)關(guān)系得到這e列直通列車的運(yùn)行線最優(yōu)選擇方案。

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

3 算例

3.1 背景資料

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

已知某個(gè)直線區(qū)段在路網(wǎng)的情況如圖3所示，A—E分別表示5個(gè)技術(shù)站(共4個(gè)區(qū)段)，車次號(hào)分別為24001、24003、24005、24007的4列直通貨物列車需從A站無改編運(yùn)行到E站，已知每個(gè)站的無改編中轉(zhuǎn)列車的標(biāo)準(zhǔn)接續(xù)時(shí)間均為30 min，4列直通貨物列車速度等級(jí)相同，各區(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)選方案可得列車時(shí)刻表如表3所示，此時(shí)這4列直通貨物列車在技術(shù)站的接續(xù)總時(shí)間最短，根據(jù)MATLAB軟件求解結(jié)果可知這4列車的最小接續(xù)總時(shí)間為1 034 min。

4 結(jié)語

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

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

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

表3 列車時(shí)刻表