田志強(qiáng)，張小炳，郭倩倩

（西南交通大學(xué) 交通運(yùn)輸學(xué)院，四川 成都 610031）

在現(xiàn)階段我國鐵路列車運(yùn)行圖的編制工作中，貨物列車運(yùn)行線的鋪畫一般都是在旅客列車運(yùn)行線編制完成后進(jìn)行的，其始發(fā)終到時(shí)刻、區(qū)段內(nèi)會(huì)讓和待避旅客列車的情況、區(qū)段旅行時(shí)間等都受到旅客列車框架的影響。當(dāng)直通貨物列車運(yùn)行線從始發(fā)站直接向終到站鋪畫時(shí)，不同的始發(fā)點(diǎn)選擇將得到不同的運(yùn)行線方案，且鋪畫過程中可能因?yàn)槁每土熊嚳蚣艿挠绊懚鴮?dǎo)致貨物列車在沿途車站停站時(shí)間過長。因此，按照區(qū)段鋪畫貨物列車運(yùn)行線，再根據(jù)需要將各區(qū)段的運(yùn)行線接續(xù)為直通或直達(dá)貨物列車運(yùn)行線是一種較為常用的方法，且應(yīng)用該方法時(shí)區(qū)段貨物列車運(yùn)行線的鋪畫能夠在計(jì)算機(jī)編圖軟件的輔助下以較快的速度和較少的人機(jī)交互得到合理的方案[1]。由于貨物列車運(yùn)行線的編制基本上都是各鐵路局各自進(jìn)行的，因此從全路的角度來看，需要確定貨物列車運(yùn)行線接續(xù)方案的車站除各鐵路局管內(nèi)的技術(shù)站外，還包括相鄰兩鐵路局的分界口車站。

直通貨物列車運(yùn)行線接續(xù)問題的目標(biāo)一般是在滿足各項(xiàng)約束條件的基礎(chǔ)上使列車在技術(shù)站(分界口車站)的停留時(shí)間最短，同時(shí)在一定程度上保證各技術(shù)站上始發(fā)列車與直通列車的分布相對(duì)均衡，為車站工作創(chuàng)造良好的條件[2]。本文主要從接續(xù)時(shí)間的角度出發(fā)，對(duì)直通貨物列車運(yùn)行線在技術(shù)站接續(xù)方案的選擇方法進(jìn)行分析，以期為提高列車運(yùn)行圖編制水平、優(yōu)化直通貨物列車接續(xù)方案提供相應(yīng)的理論與方法支持。

1 已有模型描述

在文獻(xiàn)[2]和[3]中，均是假定技術(shù)站已經(jīng)給定，直通貨物列車的到達(dá)時(shí)刻已知，因此其接續(xù)方案選擇的實(shí)質(zhì)就是從若干個(gè)貨物列車出發(fā)時(shí)刻中選擇相應(yīng)的運(yùn)行線與之匹配，使得所有直通貨物列車在該技術(shù)站的總停留時(shí)間最短。若直通列車沿途經(jīng)過多個(gè)技術(shù)站，則只需要從始發(fā)站開始，重復(fù)應(yīng)用上述過程即可。

文獻(xiàn)[2]和[3]中建立的模型(即模型1)可描述如下：

式中：Z 表示直通貨物列車在技術(shù)站的總停留時(shí)間；nZ表示在技術(shù)站需要接續(xù)的直通列車的數(shù)目；nF表示從該技術(shù)站發(fā)出的運(yùn)行線數(shù)目；xij為0-1變量，表示到達(dá)運(yùn)行線i是否接續(xù)出發(fā)運(yùn)行線 j，當(dāng)兩者接續(xù)時(shí)取1否則取0；tij為到達(dá)運(yùn)行線i與出發(fā)運(yùn)行線 j 相接續(xù)的時(shí)間；Fj表示該站第 j 條出發(fā)運(yùn)行線的出發(fā)時(shí)刻；Di表示到達(dá)該站的第i條運(yùn)行線的到達(dá)時(shí)刻；T技為直通貨物列車在技術(shù)站的技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)。

原模型中式⑷不能包含所有情況，考慮到列車到、發(fā)時(shí)刻是在一天之內(nèi)，因此在一種較為極端的情況下(如到達(dá)列車時(shí)刻為23:59，出發(fā)列車時(shí)刻為0:05，技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)為30 min時(shí)，計(jì)算得出的接續(xù)時(shí)間tij為6 min)，該式計(jì)算出的接續(xù)時(shí)間并不能滿足技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)。因此本文將式⑷修改為：

2 直通貨物列車接續(xù)方法的擴(kuò)展

從已有方法的應(yīng)用過程可以看出，由于在每一個(gè)技術(shù)站選擇出發(fā)運(yùn)行線與到達(dá)的直通列車運(yùn)行線相匹配時(shí)，沒有考慮后續(xù)技術(shù)站運(yùn)行線的接續(xù)情況，因此并不能保證所得出的接續(xù)方案能夠使所有直通列車在各個(gè)技術(shù)站的接續(xù)時(shí)間總和最小，甚至不能保證該接續(xù)方案是各技術(shù)站所有到、發(fā)列車運(yùn)行線間接續(xù)時(shí)間最短的方案。為此，本文對(duì)直通貨物列車運(yùn)行線在技術(shù)站的接續(xù)問題進(jìn)行如下擴(kuò)展(下文中所述的原方法指文獻(xiàn)[2]和[3]中采用的方法)。

2.1 擴(kuò)展1

原方法無論對(duì)于上行列車還是下行列車，均是假設(shè)直通列車到達(dá)技術(shù)站的時(shí)刻確定、從技術(shù)站出發(fā)的時(shí)刻未定進(jìn)行討論。但實(shí)際上，以技術(shù)站直通車出發(fā)運(yùn)行線確定而為其選擇到達(dá)運(yùn)行線也是一種可行的方法。其優(yōu)化模型與模型1相差不大，在此不再贅述。

2.2 擴(kuò)展2

在某些情況下，由于受到某技術(shù)站設(shè)備、能力等條件的制約，需要優(yōu)先考慮直通列車在該站的接續(xù)方案。因此，單純應(yīng)用上述接續(xù)方法無法解決該問題，此時(shí)需要首先在能力緊張的技術(shù)站從所有到達(dá)及出發(fā)列車集合中匹配出所需數(shù)量的直通列車運(yùn)行線，使其接續(xù)方案滿足直通車在該站接續(xù)時(shí)間最短。當(dāng)該站的接續(xù)方案指定后，可向其終到方向和始發(fā)方向分別采用原方法及擴(kuò)展1方法選擇直通列車接續(xù)方案。

對(duì)于優(yōu)先考慮的車站，其接續(xù)方案模型 2為：

式中：nD表示到達(dá)該技術(shù)站的運(yùn)行線數(shù)目。

當(dāng)需要優(yōu)先考慮技術(shù)站的接續(xù)方案確定后，對(duì)該站以后的技術(shù)站采用原方法逐步向后確定接續(xù)關(guān)系，對(duì)該站以前的技術(shù)站采用擴(kuò)展方法1逐步向前確定接續(xù)關(guān)系。

2.3 擴(kuò)展3

原方法及擴(kuò)展1、2都是從局部出發(fā)設(shè)計(jì)直通列車在技術(shù)站的接續(xù)方案，并不能保證得到的方案在所有技術(shù)站的總接續(xù)時(shí)間最短。因此，若要得出在所有技術(shù)站接續(xù)時(shí)間最短的接續(xù)方案，就需要同時(shí)考慮所有技術(shù)站的接續(xù)情況。

在這種情況下，所有車站的接續(xù)情況被同時(shí)考慮，設(shè)所有直通列車共經(jīng)過m個(gè)技術(shù)站(包含始發(fā)、終到站)，由于在始發(fā)站只有始發(fā)運(yùn)行線，在終到站只有終到運(yùn)行線，從而不存在接續(xù)方案的選擇，因此只需要考慮技術(shù)站2至技術(shù)站m-1的接續(xù)情況，其接續(xù)方案的優(yōu)化模型3為：

其中：k為當(dāng)前考慮的車站編號(hào)。

2.4 擴(kuò)展4

擴(kuò)展方法3雖然以直通貨物列車在所有技術(shù)站總的接續(xù)時(shí)間最小為目標(biāo)進(jìn)行優(yōu)化，但由于各個(gè)區(qū)段內(nèi)不同貨物列車運(yùn)行線的實(shí)際鋪畫情況不同，一般也具有不同的旅行時(shí)間。因此，若僅考慮直通貨物列車在技術(shù)站的接續(xù)時(shí)間，則不能保證所得方案的總旅行時(shí)間最短。

當(dāng)以直通貨物列車旅行時(shí)間最短為目標(biāo)時(shí)，上述的擴(kuò)展方法仍不能滿足需要。此時(shí)可以將貨物列車在區(qū)段內(nèi)的旅行時(shí)間也計(jì)入考慮范圍，即同時(shí)考慮運(yùn)行線的旅行時(shí)間及其在技術(shù)站的接續(xù)時(shí)間。優(yōu)化模型4如下：

3 各擴(kuò)展問題的求解算法

針對(duì)上述提出的各個(gè)擴(kuò)展問題，討論其相應(yīng)的求解算法：

（1）擴(kuò)展1。該問題實(shí)質(zhì)上是原問題的逆向過程，因此同樣可以采用最小費(fèi)用最大流算法求解，由于始發(fā)站和終到站不需要考慮接續(xù)方案，則當(dāng)車站總數(shù)為 m 時(shí)算法應(yīng)用的次數(shù)為(m-2)。

（2）擴(kuò)展2。該問題首先考慮中間某技術(shù)站的接續(xù)方案，由于到達(dá)該技術(shù)站的運(yùn)行線數(shù)和從該技術(shù)站出發(fā)的運(yùn)行線數(shù)一般都大于或等于直通貨物列車的數(shù)量，因此不能再采用最小費(fèi)用最大流算法求解，而應(yīng)采用最小費(fèi)用流算法求解，求解時(shí)流值即為直通貨物列車的運(yùn)行線數(shù)量m直。在需要優(yōu)先考慮的技術(shù)站接續(xù)方案確定后，其余技術(shù)站采用最小費(fèi)用最大流算法求解即可。因此總的算法應(yīng)用次數(shù)為1次最小費(fèi)用流算法和(m-3)次最小費(fèi)用最大流算法。

（3）擴(kuò)展3。該問題同時(shí)考慮直通列車在所有技術(shù)站的接續(xù)方案，采用1次最小費(fèi)用流算法求解即可。

（4）擴(kuò)展4。該問題與擴(kuò)展3相比，只是增加了各相鄰技術(shù)站之間各條貨物列車運(yùn)行線的旅行時(shí)間，在網(wǎng)絡(luò)中則只是增加了區(qū)段內(nèi)的運(yùn)行線，因此也只需要采用1次最小費(fèi)用流算法求解。

直觀上看，上述4個(gè)擴(kuò)展問題分別應(yīng)用了最小費(fèi)用最大流和最小費(fèi)用流兩種算法求解，但實(shí)質(zhì)上，無論是采用最小費(fèi)用最大流算法還是采用最小費(fèi)用流算法，其流值均為m直，因此上述所有問題都可以歸結(jié)為求流值為m直的最小費(fèi)用流[4]。

4 算例分析

為了說明本文所提出的各擴(kuò)展方法在制定直通貨物列車接續(xù)方案時(shí)的應(yīng)用情況，本文設(shè)計(jì)了相關(guān)的數(shù)據(jù)進(jìn)行計(jì)算。

設(shè)有如圖1所示的運(yùn)行區(qū)段需要確定直通貨物列車在各技術(shù)站的接續(xù)方案。該圖中共包含4個(gè)技術(shù)站，3個(gè)運(yùn)行區(qū)段，在每個(gè)技術(shù)站到、發(fā)的貨物列車運(yùn)行線均為10條，列車在各個(gè)區(qū)段的發(fā)、到時(shí)刻及旅行時(shí)間如表1所示。所有區(qū)段內(nèi)運(yùn)行線編號(hào)都按照其始發(fā)時(shí)刻從18:00開始以升序排列，假設(shè)經(jīng)過所有區(qū)段的直通貨物列車為4列，在各技術(shù)站的技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)均為30 min，現(xiàn)分別根據(jù)原方法及各擴(kuò)展方法確定其在各技術(shù)站的接續(xù)方案。

圖1 直通貨物列車運(yùn)行區(qū)段示意圖

采用表1中的數(shù)據(jù)，首先按照擴(kuò)展3方法及擴(kuò)展4方法計(jì)算接續(xù)方案。然后采用擴(kuò)展3方法對(duì)應(yīng)區(qū)段1的4條運(yùn)行線為B站的到達(dá)運(yùn)行線，應(yīng)用原方法向后(始發(fā)站—終到站方向)確定接續(xù)方案。再采用擴(kuò)展3方法對(duì)應(yīng)區(qū)段3的4條運(yùn)行線為C站的出發(fā)運(yùn)行線，應(yīng)用擴(kuò)展1方法向前(終到站—始發(fā)站方向)確定接續(xù)方案。最后應(yīng)用擴(kuò)展2方法分別以B站和C站為優(yōu)先考慮對(duì)象計(jì)算接續(xù)方案，最終的接續(xù)方案及相關(guān)方案的接續(xù)和旅行時(shí)間統(tǒng)計(jì)如表2所示。

從最終的計(jì)算結(jié)果可以看出，對(duì)于同樣的區(qū)段運(yùn)行線分布，當(dāng)采用不同方法求解時(shí)得出的接續(xù)方案可能是不同的。原方法及擴(kuò)展1方法雖然應(yīng)用簡(jiǎn)便，但從表2中可以看出，這兩種方法并不能保證得到的接續(xù)方案總接續(xù)時(shí)間最短。擴(kuò)展3及擴(kuò)展4方法計(jì)算稍顯繁瑣，但能夠確保得出相應(yīng)的最優(yōu)接續(xù)方案，如本文算例中的最小接續(xù)時(shí)間和為679 min，所有直通貨物列車的最小總旅行時(shí)間和為4 217 min。擴(kuò)展方法2僅適用于中間某技術(shù)站能力緊張的情況，本文分別以B站和C站作為能力緊張的車站計(jì)算了相應(yīng)的接續(xù)方案，不難看出，雖然對(duì)于B站或C站而言，該方法能夠得到最短的接續(xù)時(shí)間，但是該方法不能縮短而是顯著增加了整個(gè)運(yùn)行區(qū)段的接續(xù)時(shí)間。

表1 各區(qū)段列車到發(fā)時(shí)刻及旅行時(shí)間

表2 各方法接續(xù)方案

5 結(jié)束語

本文研究了鐵路直通貨物列車運(yùn)行線在技術(shù)站的接續(xù)問題，分析了多種情況下的不同接續(xù)方法并建立了相應(yīng)模型，在對(duì)各模型分析的基礎(chǔ)上提出了采用最小費(fèi)用流算法進(jìn)行統(tǒng)一求解的思路。設(shè)計(jì)算例的結(jié)果表明，針對(duì)不同的優(yōu)化目標(biāo)及求解方法，其接續(xù)方案之間是存在差異的，且用本文提出的相關(guān)方法能夠得出最優(yōu)的接續(xù)方案。

文中設(shè)計(jì)的算例沒有直接涉及鐵路局分界口車站的接續(xù)情況，但實(shí)際上，對(duì)于分界口車站，只需要將技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)改為合理的接續(xù)值即可。當(dāng)各技術(shù)站技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)不一致時(shí)，也只需要重新計(jì)算各車站對(duì)應(yīng)的接續(xù)時(shí)間矩陣。另外，本文僅從接續(xù)時(shí)間的角度出發(fā)研究了接續(xù)方案的選擇方法，當(dāng)對(duì)直通貨物列車的始發(fā)終到時(shí)刻有特殊要求時(shí)，其接續(xù)方案的優(yōu)化仍需深入研究。

[1]倪少權(quán)，呂紅霞，楊明倫. 全路列車運(yùn)行圖編制系統(tǒng)設(shè)計(jì)的研究[J].西南交通大學(xué)學(xué)報(bào)，2003，38(3)：332-335．

[2]朱建梅. 基于實(shí)用的技術(shù)站直通列車接續(xù)方案計(jì)算方法研究[J]. 西南交通大學(xué)學(xué)報(bào)，1999，34(3)：365-368.

[3]彭其淵，閆海峰，石子明. 計(jì)算機(jī)編制列車運(yùn)行圖的理論與方法[M]. 成都：西南交通大學(xué)出版社，2004.

[4]謝 政，李建平. 網(wǎng)絡(luò)算法與復(fù)雜性理論[M]. 長沙：國防科技大學(xué)出版社，1995．