旅客列車始發(fā)方案研究綜述

陳釘均，倪少權(quán)，呂紅霞，呂苗苗

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

1 研究目的與意義

作為鐵路旅客運(yùn)輸組織的基礎(chǔ)，旅客列車運(yùn)行圖是對旅客列車運(yùn)行時間、空間關(guān)系的圖解表示，是旅客列車在區(qū)間運(yùn)行及在車站到發(fā)或通過時刻的技術(shù)文本，是受多種因素制約、技術(shù)性強(qiáng)的綜合運(yùn)輸計(jì)劃。在鋪畫旅客列車運(yùn)行圖前，無論是手工鋪畫還是計(jì)算機(jī)鋪畫，首先需要確定各旅客列車運(yùn)行線的始發(fā)點(diǎn)，即各次旅客列車的始發(fā)時刻。只要旅客列車在始發(fā)站或終到站的出發(fā)或到達(dá)時刻確定了，整個旅客列車運(yùn)行圖的骨架也就隨之確定[1]。

旅客列車始發(fā)方案主要解決旅客列車運(yùn)行線布局問題，是編制旅客列車運(yùn)行圖的重要前提，也是旅客列車運(yùn)行圖的骨架和核心，直接影響旅客列車運(yùn)行圖質(zhì)量。同時，合理的旅客列車始發(fā)方案不僅能夠滿足旅客對出行時間和服務(wù)質(zhì)量的要求，提升鐵路旅客運(yùn)輸?shù)氖袌龈偁幜?，也能夠充分利用現(xiàn)有客運(yùn)站設(shè)備和客車整備所設(shè)施，提高客運(yùn)站作業(yè)組織的質(zhì)量和效率。提高旅客運(yùn)輸效率可以節(jié)約運(yùn)營成本，增加運(yùn)營收入?？傊?，合理的旅客列車始發(fā)方案能夠同時兼顧鐵路部門和旅客的利益，提高鐵路旅客運(yùn)輸組織水平，具有重要的理論意義及現(xiàn)實(shí)意義。

2 國內(nèi)外研究現(xiàn)狀及存在問題

2.1 研究現(xiàn)狀

對于旅客列車始發(fā)方案的研究，由于路情的不同，國外的研究主要集中在時刻表 ( 運(yùn)行圖 ) 的編制方面[2-5]，單獨(dú)對旅客列車運(yùn)行圖編制的初始階段——旅客列車始發(fā)方案的研究還比較少。目前，國內(nèi)外對該領(lǐng)域的研究主要集中在以下方面。

（1）無約束條件的列車始發(fā)方案研究。符卓通過定量化方法將旅客列車運(yùn)行方案圖編制問題轉(zhuǎn)化為一個多目標(biāo)優(yōu)化問題，運(yùn)用分層序列法解決問題的思路，按照各目標(biāo)的重要性程度進(jìn)行求解，并且給出了第一層優(yōu)化目標(biāo)——方便旅客出行的啟發(fā)式算法。其具體通過定義合理始發(fā)時間范圍、合理終到時間范圍、合理到發(fā)時間范圍、合理始發(fā)區(qū)間等概念，將定量與定性相結(jié)合，運(yùn)用匈牙利算法，提出方便旅客出行的列車出發(fā)點(diǎn)優(yōu)化方法[1]。郭富娥通過討論列車會讓、樞紐站行車間隔、列車運(yùn)行線調(diào)整等處理方法，提出人機(jī)相結(jié)合編制旅客列車運(yùn)行方案圖，并開發(fā)了計(jì)算機(jī)輔助編制旅客列車運(yùn)行方案的軟件，得到了相應(yīng)的運(yùn)用[6]。符卓針對只將 24 小時分為合理和不合理到發(fā)時間的范圍過寬情況，結(jié)合每個時間段列車到發(fā)對旅客方便程度不同的特點(diǎn)，將 24 小時劃分為多個方便程度不同的時間段，將方便旅客出行問題轉(zhuǎn)化為指派問題，對列車的到發(fā)點(diǎn)進(jìn)行整體優(yōu)化[7]。

（2）經(jīng)濟(jì)合理使用車底的列車始發(fā)方案優(yōu)化方法研究。經(jīng)濟(jì)合理使用客車車底是編制旅客列車運(yùn)行方案圖時需要考慮的主要目標(biāo)之一。符卓通過對該問題的分析和歸納，提出基于啟發(fā)式算法的合理使用車底的到發(fā)區(qū)間組合中的始發(fā)區(qū)間；基于指派問題的合理始發(fā)區(qū)間的全局優(yōu)化，得到滿意始發(fā)區(qū)間；基于指派問題的滿意始發(fā)區(qū)間所對應(yīng)的所有合理終到區(qū)間組合進(jìn)行全局優(yōu)化，得到所有的最優(yōu)到發(fā)區(qū)間組合[8]。王慈光應(yīng)用同余理論，分別對旅客列車無約束條件的合理發(fā)車范圍、照顧途中大站的合理發(fā)車范圍、考慮客車車底折返情況的合理發(fā)車范圍、既考慮車底折返又考慮途中大站的合理發(fā)車范圍 4 種情況，提出了運(yùn)用代數(shù)方法計(jì)算旅客列車合理發(fā)車范圍[9-10]。張玉召等通過概括旅客列車始發(fā)時間范圍的影響因素，分析車底需要數(shù)量與列車始發(fā)時間范圍之間的關(guān)系，提出以客運(yùn)站始發(fā)旅客列車車底在配屬站和折返站停留時間之和最少為目標(biāo)的旅客列車始發(fā)時間域數(shù)學(xué)優(yōu)化模型，并給出了傳統(tǒng)方法與啟發(fā)式方法相結(jié)合的算法求解模型[11]。潘鋒討論了影響客車運(yùn)用效率的主要因素，分析了車底需要數(shù)量與車底在站停留時間之間的關(guān)系，提出了優(yōu)化客車使用的多種措施，同時討論了提高動車組運(yùn)用效率問題[12]。

（3）方便換乘的列車始發(fā)方案優(yōu)化研究。陳玲玲等針對旅客換乘的需要，為使各方向旅客列車的到達(dá)時刻相互銜接以減少旅客中轉(zhuǎn)換乘時間，分析了兩列不同方向的旅客列車到達(dá)途中換乘站時間的相互關(guān)系；以先到達(dá)途中換乘站的列車發(fā)車時刻為基點(diǎn)，應(yīng)用同余理論，用代數(shù)方法計(jì)算出后到達(dá)列車的發(fā)車時刻，進(jìn)而求得可行解[13]。徐瑞華等在討論首末班列車協(xié)調(diào)必要性的基礎(chǔ)上，以多線換乘接續(xù)的可達(dá)性和合理性，建立多向列車換乘銜接模型，并依據(jù)早晚間客流的特點(diǎn)，提出首末班列車發(fā)車時間域的計(jì)算方法；該模型和方法為旅客列車運(yùn)營組織提供必要的決策依據(jù)[14]。

（4）客運(yùn)站設(shè)備能力約束下的列車發(fā)車時間域研究。陳團(tuán)生等在基于大量問卷調(diào)查的基礎(chǔ)上，確定了旅客出行在各發(fā)車時間域的方便系數(shù)，并運(yùn)用目標(biāo)規(guī)劃原理，以方便旅客出行程度最大為目標(biāo)，并構(gòu)造了三級控制策略；考慮客運(yùn)站到發(fā)線發(fā)車能力和旅客列車必須在合理的時間范圍發(fā)車等約束條件，建立了旅客列車發(fā)車時間域的目標(biāo)規(guī)劃模型[15]。倪少權(quán)等建立了以到發(fā)線、客車整備線能力為約束，車底使用數(shù)最少為目標(biāo)的數(shù)學(xué)優(yōu)化模型，討論了運(yùn)行區(qū)段內(nèi)旅客列車的始發(fā)時間范圍問題，并設(shè)計(jì)了啟發(fā)式遺傳算法對模型進(jìn)行求解[16]。

（5）旅客對列車發(fā)車時間的偏好選擇研究。馬建軍等以基于網(wǎng)狀線路高中速列車行車組織模式為前提，利用計(jì)算機(jī)仿真技術(shù)研究了跨線中速列車在既有線始發(fā)、終到時間域的計(jì)算方法[17]。史峰等通過分析不同旅客對列車始發(fā)時間分布的需求，同時考慮列車能力對客流分布的作用及旅客群體選擇行為，設(shè)計(jì)了基于旅客列車始發(fā)時間分布的旅客出行選擇網(wǎng)絡(luò)，提出以旅客出行總費(fèi)用最少為優(yōu)化目標(biāo)，并建立了旅客列車始發(fā)時間分布的雙層規(guī)劃模型，同時給出了模擬退火啟發(fā)式算法對模型進(jìn)行求解[18]。

（6）天窗條件下列車始發(fā)方案研究。張玉召等通過分析既有線旅客列車合理發(fā)車范圍確定方法，詳細(xì)分析了客運(yùn)專線開設(shè)垂直矩形天窗條件下跨線旅客列車的合理發(fā)車域的確定方法，應(yīng)用同余理論，討論了上線列車、下線列車、既上線又下線列車、多次上線和下線列車等情況下，列車的合理始發(fā)范圍確定方法[19]。

2.2 有關(guān)研究存在的問題

從旅客列車始發(fā)方案編制問題的有關(guān)研究成果來看，國內(nèi)外專家學(xué)者對旅客列車始發(fā)方案問題的模型及求解算法進(jìn)行了有益的探索，但是仍存在以下主要問題。

（1）研究成果的適用性。國外鐵路線路能力及車站能力均比較充裕，研究主要集中在方便旅客及方便換乘等方面，因此國外的研究成果不完全適用于我國國情。目前，旅客列車始發(fā)時間主要由編圖人員憑經(jīng)驗(yàn)采用試探的方法在較寬的時間窗里尋找，直到結(jié)果滿意為止，沒有考慮整體優(yōu)化始發(fā)時間點(diǎn)以供編圖人員選擇，影響了編圖質(zhì)量；并且對列車運(yùn)行圖的編制與優(yōu)化，大多只考慮區(qū)間運(yùn)行情況，較少考慮客運(yùn)站設(shè)備能力，特別是未考慮始發(fā)、終到站的客車整備線能力的影響。

（2）模型的可行性。目前，有關(guān)研究主要從旅客方便性 ( 合理始發(fā)、終到時間 ) 和企業(yè)經(jīng)濟(jì)性( 節(jié)約車底 ) 兩方面確定旅客列車始發(fā)方案，沒有考慮我國大型客運(yùn)站因政治、經(jīng)濟(jì)原因需開行大量列車而造成客運(yùn)站設(shè)備能力，尤其是到發(fā)線能力、客車整備線能力相對緊張的實(shí)際情況，易造成旅客列車始發(fā)方案難以實(shí)施。

（3）求解算法的有效性。實(shí)際規(guī)模的旅客列車始發(fā)方案問題是一個大型的組合優(yōu)化問題，并且基于客運(yùn)站到發(fā)線與客車整備線協(xié)調(diào)使用的旅客列車始發(fā)方案問題是一個復(fù)雜度很高的NP ( Nondeterministic Polynomial ) 問題。對于 NP 問題的求解，學(xué)術(shù)界至今還沒有成熟的理論和方法。因此，有必要對旅客列車始發(fā)方案的求解算法進(jìn)行深入研究。

3 研究展望

3.1 研究目標(biāo)

旅客列車始發(fā)方案的編制需要綜合考慮客流需求、車底運(yùn)用、客運(yùn)站到發(fā)線能力、客車整備線能力、路網(wǎng)天窗設(shè)置等因素，在旅客列車開行方案及各車站線路相關(guān)數(shù)據(jù)已確定的基礎(chǔ)上，實(shí)現(xiàn)旅客列車始發(fā)時間與客運(yùn)站設(shè)備能力協(xié)調(diào)的優(yōu)化編制。依據(jù)不同情況，具體實(shí)現(xiàn)以下目標(biāo)：旅客列車始發(fā)時間域的優(yōu)化編制；既有線旅客列車始發(fā)方案的優(yōu)化編制；高速鐵路旅客列車始發(fā)方案的優(yōu)化編制。

3.2 研究內(nèi)容

針對已有研究存在的不足，在現(xiàn)有相關(guān)研究工作的基礎(chǔ)上，綜合考慮方案的方便性、經(jīng)濟(jì)性和可行性，對旅客列車始發(fā)方案編制問題作進(jìn)一步的研究。

（1）考慮客運(yùn)站設(shè)備能力條件下旅客列車始發(fā)方案的編制問題。為提高旅客列車服務(wù)質(zhì)量和吸引客流，需要將列車始發(fā)、終到時間安排在“黃金時段”，這將形成旅客列車在某一時間段密集到發(fā)，造成客運(yùn)站接發(fā)車能力與區(qū)間通過能力緊張。另外，旅客列車的始發(fā)終到時刻影響動車組及車底的接續(xù)關(guān)系，進(jìn)而決定運(yùn)載工具的運(yùn)用效率。因此，合理編制旅客列車始發(fā)方案對于充分發(fā)揮我國鐵路技術(shù)與經(jīng)濟(jì)效益有重要影響。

（2）考慮天窗開設(shè)條件下旅客列車始發(fā)方案的編制問題。除客運(yùn)站設(shè)備能力影響旅客列車始發(fā)方案的可行性外，天窗的開設(shè)對旅客列車的運(yùn)行及線路的通過能力都有一定的影響。因此，天窗開設(shè)與旅客列車始發(fā)方案編制的協(xié)同優(yōu)化是值得研究的問題。

（3）高速鐵路動車組列車始發(fā)方案的編制問題。高速鐵路動車組列車與既有線旅客列車有很大的區(qū)別，高速鐵路一般采用公交化的周期運(yùn)行圖，旅客對出行時間也有更高的要求，加之目前高速鐵路的快速發(fā)展，動車組列車始發(fā)方案的編制問題也是值得研究的重要內(nèi)容。

（4）從旅客列車始發(fā)方案到運(yùn)行圖優(yōu)化的過渡問題。旅客列車始發(fā)方案編制的研究只解決了列車運(yùn)行線的整體布局，未考慮旅客列車在區(qū)間運(yùn)行時可能產(chǎn)生的沖突，并且未對旅客列車途經(jīng)大站占用到發(fā)線等問題給予討論，這在一定程度上將影響旅客列車始發(fā)方案的可行性。因此，有必要對旅客列車始發(fā)方案到運(yùn)行圖的過渡問題進(jìn)行研究。

（5）基于穩(wěn)定性的旅客列車始發(fā)方案編制問題。旅客列車始發(fā)方案的編制需要提高旅客列車運(yùn)營組織的可靠性和保障列車的安全正點(diǎn)運(yùn)行。目前，旅客列車開行數(shù)量眾多，尤其是高峰時期，列車密度很大，容易形成前行列車晚點(diǎn)造成后行列車的連帶晚點(diǎn)。因此，有必要討論穩(wěn)定性旅客列車始發(fā)方案編制問題。

3.3 研究方法

鐵路旅客列車始發(fā)方案的優(yōu)化編制問題是一個約束復(fù)雜的多目標(biāo)決策問題，由于問題的組合優(yōu)化特性，隨著開行列車數(shù)量的增多，問題的求解難度也逐步增加。針對問題的特點(diǎn)，擬采用以下思路加以解決。

（1）簡化思想。旅客列車始發(fā)方案的編制涉及列車運(yùn)行計(jì)劃和客運(yùn)站技術(shù)作業(yè)兩方面，而列車運(yùn)行計(jì)劃的編制本身就是一個影響因素眾多的復(fù)雜問題，加上客運(yùn)站能力、路網(wǎng)天窗設(shè)置等，問題規(guī)模更加龐大，很難找到問題的解。而該問題實(shí)質(zhì)上是編制列車運(yùn)行圖的骨架，應(yīng)盡可能提高其可行性。因此，考慮列車始發(fā)、終到站之間旅行時間確定的情況，而不考慮列車在各區(qū)間的運(yùn)行情況，可簡化問題的復(fù)雜性，使問題的求解變得可行。

（2）降維思想。針對鐵路網(wǎng)客運(yùn)站數(shù)量較多、開行的旅客列車數(shù)量龐大的特點(diǎn)，若對所有旅客列車始發(fā)方案同時優(yōu)化編制，將是一個非常復(fù)雜的問題。因此，將客運(yùn)節(jié)點(diǎn)站按照一定方法進(jìn)行重要度排序，逐次優(yōu)化各節(jié)點(diǎn)站旅客列車始發(fā)方案，將客運(yùn)節(jié)點(diǎn)“多對多”列車始發(fā)方案問題轉(zhuǎn)化為多個“一對多”問題。以 4 個客運(yùn)節(jié)點(diǎn)為例，其轉(zhuǎn)化思想如圖 1 所示。

圖1 客運(yùn)節(jié)點(diǎn)分解圖

其中，←→表示客運(yùn)站之間有互發(fā)旅客列車，若客運(yùn)節(jié)點(diǎn)站重要度排序?yàn)镾1、S2、S3、S4，則首先編制S1與S3、S4之間互開旅客列車的始發(fā)方案，其次編制S2與S3之間互開旅客列車的始發(fā)方案，最后編制S3與S4之間互開旅客列車的始發(fā)方案。

（3）協(xié)同思想。旅客列車始發(fā)方案的編制受旅客列車開行方案、客運(yùn)站設(shè)備能力和客車整備所整備能力三者的影響。因此，運(yùn)用協(xié)同思想使旅客列車始發(fā)時間與客運(yùn)站設(shè)備能力、客車整備所整備能力協(xié)調(diào)，得出可行的旅客列車始發(fā)方案。

（4）啟發(fā)式智能算法。針對旅客列車始發(fā)方案模型的特點(diǎn)，綜合運(yùn)用模糊集理論、運(yùn)籌學(xué)、組合數(shù)學(xué)、最優(yōu)化理論和現(xiàn)代優(yōu)化算法等相關(guān)理論，依照循序漸進(jìn)的思路，設(shè)計(jì)高效的啟發(fā)式算法，深入研究我國鐵路旅客列車始發(fā)方案編制理論與方法。

4 結(jié)束語

旅客列車始發(fā)方案的編制是一個復(fù)雜的優(yōu)化問題，針對有關(guān)研究存在的不足，需要綜合考慮方案的方便性、經(jīng)濟(jì)性和可行性，為我國鐵路旅客列車運(yùn)行圖的編制提供必要的理論支持，成為計(jì)算機(jī)編制旅客列車運(yùn)行圖的有效輔助手段。

[1] 符 卓. 旅客列車運(yùn)行方案圖優(yōu)化編制方法的研究[J]. 鐵道學(xué)報(bào)，1996，18(4)：10-17.

[2] Senzana M. Heuristic Approach to Train Rescheduling[J].Journal of Operation：Research，2007(7)：9-29.

[3] Vromans，M.J.C.M. Reliability of Railway Systems [D].Rotterdam：Erasmus University，2005.

[4] Alberto Caprara，Michele Monaci，Paolo Toth. A Lagrangian Heuristic Algorithm for A Realworld Train Timetabling Problem[J]. Discrete Applied Mathematics，2006，154(5)：738-753.

[5] Herrmann，T.M.Stability of Timetables and Train Routings through Station Regions[D]. Zurich： Swiss Federa Institute of Technologyzurich，2006.

[6] 郭富娥. 利用計(jì)算機(jī)編制旅客列車運(yùn)行方案[J]. 鐵道學(xué)報(bào)，1993，15(2)：71-75.

[7] 符 卓. 方便旅客旅行的列車到發(fā)點(diǎn)優(yōu)化確定方法[J]. 長沙鐵道學(xué)院學(xué)報(bào)，1998，16(3)：30-33.

[8] 符 卓. 優(yōu)化車底使用數(shù)的客車運(yùn)行方案圖編制方法[J]. 鐵道學(xué)報(bào)，1996，18(6)：6-13.

[9] 王慈光. 確定旅客列車合理開車范圍的代數(shù)方法[J]. 西南交通大學(xué)學(xué)報(bào)，1998(2)：70-78.

[10] 王慈光. 運(yùn)輸模型及優(yōu)化[M]. 北京：中國鐵道出版社，2004.

[11] 張玉召，張紅偉，文娟娟. 車底需要數(shù)最少的旅客列車始發(fā)范圍優(yōu)化模型[J]. 鐵道工程學(xué)報(bào)，2011(4)：111-114.

[12] 潘 鋒. 提高客車運(yùn)用效率的研究[D]. 成都：西南交通大學(xué)，2005.

[13] 陳玲玲，王慈光. 基于旅客列車合理接續(xù)條件的發(fā)車時刻確定方法[J]. 西南交通大學(xué)學(xué)報(bào)，2007，42(2)：234-237.

[14] 徐瑞華，張 銘，江志彬. 基于線網(wǎng)運(yùn)營協(xié)調(diào)的城市軌道交通首末班列車發(fā)車時間域研究[J]. 鐵道學(xué)報(bào)，2008，30(2)：7-11.

[15] 陳團(tuán)生，毛保華，何宇強(qiáng). 旅客列車發(fā)車時間域優(yōu)化研究[J]. 鐵道學(xué)報(bào)，2006，28(4)：12-16.

[16] Ni Shaoquan，Chen Dingjun，Lv Miaomiao. Research on Optimization Model of Initial Schedule of Passenger Trains based on Improved Genetic Algorithm[C]. //IEEE Computer Society. 2009 International Coference on Intelligent Computing Technology and Automation. Los Alamitos：IEEE Computer Society Publications，2009：273-276.

[17] 馬建軍，胡思繼，周 曦，等. 京滬高速鐵路高中速列車到發(fā)時間域的計(jì)算方法[J]. 北方交通大學(xué)學(xué)報(bào)，2002，26(5)：28-31.

[18] 史 峰，黃錚誠，周文梁，等. 基于用戶平衡分析的旅客列車始發(fā)時間分布優(yōu)化[J]. 鐵道科學(xué)與工程學(xué)報(bào)，2008，5(6)：69-75.

[19] 張玉召，嚴(yán)余松. 客運(yùn)專線跨線列車合理始發(fā)范圍的確定方法研究[J]. 蘭州交通大學(xué)學(xué)報(bào)，2010(3)：79-82.