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

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

1 研究目的與意義

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

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

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

2.1 研究現(xiàn)狀

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

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

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

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

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

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

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

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

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

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

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

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

3 研究展望

3.1 研究目標

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

3.2 研究內(nèi)容

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

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

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

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

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

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

3.3 研究方法

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

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

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

圖1 客運節(jié)點分解圖

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

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

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

4 結(jié)束語

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

[1] 符 卓. 旅客列車運行方案圖優(yōu)化編制方法的研究[J]. 鐵道學(xué)報，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]. 鐵道學(xué)報，1993，15(2)：71-75.

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

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

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

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

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

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

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

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

[15] 陳團生，毛保華，何宇強. 旅客列車發(fā)車時間域優(yōu)化研究[J]. 鐵道學(xué)報，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]. 北方交通大學(xué)學(xué)報，2002，26(5)：28-31.

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

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