大型鐵路客運站列車進路優(yōu)化模型與算法研究

武晉飛，王煒煒

(中國鐵道科學研究院 電子計算技術研究所，北京 100081)

大型鐵路客運站列車進路優(yōu)化模型與算法研究

武晉飛，王煒煒

(中國鐵道科學研究院 電子計算技術研究所，北京 100081)

以提高車站行車技術作業(yè)效率，保證車站行車作業(yè)安全，盡可能減少旅客站內(nèi)走行距離和時間，保證發(fā)車時間相近的兩列始發(fā)或通過列車盡量不?？客徽九_，提高車站既有行車設備利用率為優(yōu)化目標，建立大型鐵路客運站進路優(yōu)化的多目標規(guī)劃模型。運用層次分析法求出各子目標的權(quán)重，并構(gòu)建啟發(fā)式算法進行模型求解。通過對算法進行實例驗證，得到了較優(yōu)的列車進路安排方案。

客運站；進路選擇；多目標規(guī)劃；啟發(fā)式算法

我國鐵路客運站正處于大規(guī)模的建設階段。大型客運站要求銜接干線鐵路、城際鐵路、高速鐵路等線路以及機車車輛檢修基地來滿足作業(yè)需求，加之車站結(jié)構(gòu)復雜，作業(yè)繁多，必然導致列車進路交叉干擾增多。因此，對大型鐵路客運站車站接發(fā)車作業(yè)的進路分配問題進行研究，并建立接發(fā)車進路優(yōu)化問題和相應算法，最終獲得高質(zhì)量接發(fā)車方案，對鐵路客運站旅客運輸至關重要。

當前，國內(nèi)外不少學者對車站進路安排問題進行了深入研究，文獻[1]提出了咽喉區(qū)最大平行進路方法和最大概率進路緊側(cè)方法。文獻[2]通過詳細分析客運站技術作業(yè)，將到發(fā)線運用目標分為3個子目標，分別建立優(yōu)化模型并用分枝定界法進行求解。文獻[3]用二次0—1規(guī)劃法進行求解列車進路安排。文獻[4]用k-頂點圖著色法進行求解。文獻[5]用固定工件排序法進行求解。研究發(fā)現(xiàn)，上述研究在列車進路安排問題中，大多數(shù)僅局限于某項作業(yè)單獨優(yōu)化，使得結(jié)果的優(yōu)化、實用性并未達到極致，在建立模型時存在模型實用性和合理性問題，在模型求解時存在算法的有效性問題。

1 模型建立

1.1 問題描述

在車站作業(yè)中，列車（或車列）在使用到發(fā)線時，需要滿足一定的原則：對于車站的某一條到發(fā)線，它可以對一定方向一定種類的列車（或車列）進行接發(fā)車作業(yè)；而對于一列旅客列車（或車列）來說，它只能被一定類型的到發(fā)線中的一條接發(fā)，該原則成為唯一性原則[2]；此外，列車（或車列）使用到發(fā)線還須滿足到發(fā)線運用的其他約束條件，如滿足最小安全時間間隔等[2]。

1.2 變量及約束條件

記到發(fā)線集為W ，到發(fā)線個數(shù)為d，根據(jù)車站行車技術作業(yè)性質(zhì)要求以及列車運行方向要求以及偏好和其他方面作業(yè)等要求，將車站到發(fā)線分為l類，對應的到發(fā)線集W分為不同的集合Wl，對于每一類到發(fā)線集合Wl，對應的股道數(shù)目為Dt(t=1, 2, …, l)，計到發(fā)列車集為H，列車總數(shù)為n，將到發(fā)列車按上述要求分為相應的l類，即將到發(fā)列車集H分為不同的集合Ht，則每一類的列車數(shù)為Nk(k=1, 2, …, l)，上述映射關系可以形式化地表示為：φ∶H→W，且有。根據(jù)車站作業(yè)安全及規(guī)定，車站接發(fā)列車應滿足以下約束：

（1） 根據(jù)列車的去向、上下行和個人偏好等情況，將列車i分到對應的到發(fā)線集合Wi中進行接發(fā)。

當xij=1時，i列車由j股道接發(fā)，否則，xij=0，表示i列車不是由j股道接發(fā)。

（3）在一定的時間區(qū)間內(nèi)，一條到發(fā)線只能有一列車占用，記列車i占用到發(fā)線j的時間為，在該時間內(nèi)股道j不能被其他的占用，表示第k類列車中第i列是否由第t類到發(fā)線中的第j條接發(fā)，其取值為0、1變量，tj表示股道j被占用的時間；為列車i出發(fā)時刻起至該線路全部騰空且可以接入下一列車的時刻；為列車i預備進路到j股道的時刻。

（4） 進路的沖突有2種形式：a. 時間上的沖突；b. 空間上的沖突。在為兩列旅客列車安排到發(fā)線時，應該避免產(chǎn)生交叉的兩個條件同時出現(xiàn)，即：為旅客列車i安排到j到發(fā)線時，與旅客列車k安排在l到發(fā)線時，是否產(chǎn)生道岔組交叉的0、1決策變量；為旅客列車i安排到j到發(fā)線時，與旅客列車k安排在l到發(fā)線時，是否產(chǎn)生時間交叉的0、1決策變量；xij、xkl均為0、1變量。

（5）同一到發(fā)線連續(xù)接車應滿足時間間隔要求，假定相繼停在股道j的3列車依次為：i_1、i、i+1，則它們在車站的時間間隔約束應滿足：站作業(yè)最小間隔時間。

1.3 建立目標函數(shù)

本文選定以下4個優(yōu)化目標，建立多目標規(guī)劃問題對大型客運站列車進路安排進行優(yōu)化?？紤]到影響進路安排的各個目標重要程度并不相同，本文針對每個目標分別建立模型，每個模型描述一個問題，引進權(quán)值Wi，且然后通過層次分析法確定其權(quán)值大小，從而確定最終目標函數(shù)。

（1）有利于提高車站行車技術作業(yè)效率，保證車站行車作業(yè)安全。

引進權(quán)值αkitj，對其取值做如下約定：若第 k類列車中第i列由第t類到發(fā)線中的第j條接發(fā)并且符合運用方案，則αkitj=0；若第k類列車中第i列由第t類到發(fā)線中的第j條接發(fā)但不符合運用方案，則αkitj=1；若第 k類列車中第i列不由第t類到發(fā)線中的第j條接發(fā)，則αkitj=M，其中i∈(1,2,…,Nk)，j∈ (1,2,…,Dt)，M 為一個任意大的數(shù)。用xkitj表示第k類列車中第i列是否由第t類到發(fā)線中的第j條接發(fā)，其取值為0、1變量，若是，則 xkitj=1，否則xkitj=0。該優(yōu)化目標表示為：

（2） 盡可能地方便旅客乘降。

引進一個懲罰值βij用以表示用第j條到發(fā)線接發(fā)第i列車時在不方便旅客乘降方面的懲罰值，βij值越大則說明該到發(fā)線接發(fā)該列車越不方便，βij可表示為：

其中，i=1,2,…,n ；j=1,2,…,d。 Ai表示在研究時段內(nèi)車站接發(fā)的n列旅客列車中，第i列列車在該站到發(fā)旅客的平均數(shù)；Sj表示第j條到發(fā)線在接發(fā)列車時，旅客在車站內(nèi)的平均走行路程。引進一個權(quán)值wij用以表示由第j條到發(fā)線接發(fā)第i列列車時的權(quán)值，若由第j條到發(fā)線接發(fā)第 i列列車且符合到發(fā)線分類使用方案，則該權(quán)值為0，即wij=0；若由第j條到發(fā)線接發(fā)第i列列車但不符合到發(fā)線分類使用方案，則該權(quán)值為1，即wij=1；若不由第j條到發(fā)線接發(fā)第i 列列車，則該權(quán)值為一個任意大的數(shù)M，即wij=M?？蓪⒎奖懵每统私祮栴}轉(zhuǎn)換為一個指派問題，表示如下：

（3）發(fā)車時間相近的兩列始發(fā)（或通過）列車盡量不?？吭谕徽九_。

假定存在兩列先后出發(fā)的列車i,I在同一站臺出發(fā)，如果i列車運用到發(fā)線j的結(jié)束時間比u列車占用到發(fā)線v的開始時間晚，但不足20 min，且j、v兩條到發(fā)線為同一站臺，則列車 i、u就形成了一個相交時間區(qū)，即其占用到發(fā)線的時區(qū)存在時間交叉。引進權(quán)值γijuv，若i列車運用到發(fā)線j的結(jié)束時間比u列車占用到發(fā)線v的開始時間晚，但不足20 min，則γijuv=M，其中 M為一個任意大的數(shù)；若i列車運用到發(fā)線j的結(jié)束時間比u列車占用到發(fā)線v的開始時間晚，但超過20 min，則γijuv=0。引進權(quán)值δijuv，若i=j，u=v即兩列車為同一列車或占用同一到發(fā)線，則δijuv=0 ,否則，δijuv=1，其中，i、u∈ (1,2,…,Nk)，j、v ∈ (1,2,…,Dt)。得到本文模型 3，表示為：

（4） 提高車站既有行車設備利用率，實現(xiàn)到發(fā)線均衡使用。

列車占用到發(fā)線時間可表示為tij=tSi+tLi+tEi。其中，tij為第i列旅客列車從接發(fā)到到發(fā)線j的總時間；tLi為第i列旅客列車占用到發(fā)線的時間；tSi為第i列旅客列車的出發(fā)作業(yè)時間；tEi為第i列旅客列車的到達作業(yè)時間。則各股道被占用時間均勻的目標函數(shù)，即本文目標函數(shù)4，可表示為：

假設Sij表示第j股道分配給兩個相鄰列車中間的空閑時間，即表示前一列車的離開時間與后一列車到達時間的差。設股道空閑時間均勻的目標函數(shù)即本文目標函數(shù)5，可表示為：

綜上，本文建立的大型鐵路客運站列車進路優(yōu)化模型為：

目標函數(shù)中的wi代表5個子目標所占用的比重，本文采取了層次分析法確定， ∑ wi= 1。

運用層次分析法求得模型到指標權(quán)重為：

2 算例分析

某大型客運站為全路44個較大客運站中的一個以客運為主、客貨運兼營的綜合性一等車站，每日有開往北京、上海等各站的始發(fā)旅客列車39列，到達39列，通過列車12列共90列。其中，特快列車7對，均為直通特快車，快速列車為2對，均為直通快速旅客列車，普通旅客列車34對?？?個鐵路局及其以上為3對，跨2個鐵路局9對，管內(nèi)5對，普通旅客慢車直通1對，管內(nèi)8對。該客運站站內(nèi)共有4個站臺，設有上下行正線，旅客列車到發(fā)線7條、貨物列車到發(fā)線、機車走行線。日均辦理旅客乘降4萬余人，辦理行包1萬余件，年發(fā)送旅客約470萬人。車站平面簡圖如圖1所示。

圖1 某客運站平面布置簡圖

2.1 數(shù)據(jù)預處理

2.1.1 對到發(fā)線的線束進行劃分

將上行旅客列車盡量安排在1，3，4到發(fā)線，下行旅客列車安排在6，7，8，9道，可以很好地減少站場咽喉區(qū)交叉干擾，提高到發(fā)線運用能力。

2.1.2 劃分到發(fā)線等級

根據(jù)到發(fā)線距離站房的遠近，所臨靠站臺的等級，可對到發(fā)線進行劃分。得到車站線路信息表如表1所示。

表1 算例客運站線路信息表

2.1.3 劃分列車等級

根據(jù)列車的種類（特快、快速、普通等）等對列車進行分類。比如特快列車以及進京、滬、廣列車定為1級，一般快速列車定為2級，普通旅客快車定為3級，普通旅客慢車定為4級。根據(jù)劃分原則將算例車站的列車做如下劃分：N201～N276為1級，K237～K374為2級，1485～1578為3級，其它列車定為4級。

2.1.4 確定列車-到發(fā)線權(quán)值矩陣cij

對于任意的列車i，都有i∈Hl, Hl=(H1, H2,…,Hl)；同理，對于到發(fā)線j，有j∈Wl, Wl=(W1, W2,…, Wl) 。權(quán)值矩陣cij表示列車接入線路的等級權(quán)值。根據(jù)算例客運站情況，做出其對應的列車-到發(fā)線權(quán)值矩陣，如表2、表3所示。

表2 列車-到發(fā)線權(quán)值矩陣（上行）

表3 列車-到發(fā)線權(quán)值矩陣（下行）

2.1.5 確定列車占用到發(fā)線時區(qū)

j列車占用到發(fā)線時間與列車的到發(fā)時間、列車類型等有關。列車占用時間包括車底接入時間、列車停站時間和列車出站時間，具體時間標準在站細中有明確規(guī)定。對于算例中客運站，始發(fā)列車占用時間總計為48 min，其中停站時間40 min，車底轉(zhuǎn)入時間為2 min，列車出站時間為3 min。如果該始發(fā)列車的出發(fā)時刻為19：28，則它占用到發(fā)線的（[]）為（18：39，19：31）。終 到旅客列車占用時間為41 min，其中列車進站時間為6 min，車底轉(zhuǎn)出時間為3 min，停站時間為31 min，如果終到列車的到達時刻為19：28，則它占用到發(fā)線的（[]）為（19：22，20： 03）。通過列車（）可以根據(jù)列車出站和進站時間得出。

2.2 列車進路優(yōu)化方案計算

本文用C#語言編制了WinForm程序進行模型求解，其中，進路優(yōu)化方案求解界面如圖2所示。

圖2 列車進路分配方案求解

在本文模型及參數(shù)設定下，程序運行282.850 s，即4.7 min，考慮計算數(shù)據(jù)量即處理流程，與預期結(jié)果基本吻合。將得到的到發(fā)線運用方案整理，如表4所示。

表4 列車到發(fā)線安排順序

表4數(shù)據(jù)表明：上行旅客列車大多安排在上行場1、3、4道，下行旅客列車大多安排在下行場6、7、8、9道，以盡量減少咽喉區(qū)的進路交叉。N、K字頭的始發(fā)或終到旅客列車（列車等級高，上、下旅客多，行包量大）大多安排在1道或離基本站臺近的股道，說明子目標函數(shù)2、3在起作用；7條到發(fā)線的占用時間基本上均等，說明是子函數(shù)4和5在起作用。例如，2023次列車和4527次列車為在一個時區(qū)的始發(fā)列車，分別安排到了7道和9道，2023次列車旅客在3站臺上車，4527次列車旅客在4站臺上車。這樣就避免了一個站臺旅客人數(shù)較多的情況。說明子函數(shù)3在起作用。

2.3 方案評價

表5 某站近期到發(fā)線固定使用方案

表5為算例客運站近期實際站調(diào)編制的到發(fā)線運用計劃。其進入上行場的下行列車相對較多，即進路橫切正線情況較多。而一些行包量較大的列車沒有接發(fā)在靠近基本站臺的1道。例如，7163次列車和6041次列車屬于同一時區(qū)的始發(fā)列車卻分別安排到了9道和8道，那么必然會有4站臺同時有較多的旅客上車，有可能會造成客運站工作組織的混亂。而在本文模型求解的方案表中（表4），子目標函數(shù)2很好地發(fā)揮了作用，將7163次列車和6041次列車分別安排在了7道和8道，使兩列車的旅客分別從3站臺和4站臺上車，這樣有利于有序的組織旅客按時上車，避免一些旅客上錯車的現(xiàn)象，同時也避免了同一站臺旅客人數(shù)多、壓力大的情況。表4和表5比較說明，算法生成的到發(fā)線運用計劃優(yōu)化效果明顯。

3 結(jié)束語

大型鐵路客運站列車進路安排是一個繁瑣而復雜的過程。論文綜合考慮保證列車的進出站作業(yè)完成、發(fā)車時間相近的兩列始發(fā)（或通過）列車盡量不?？吭谕徽九_、線路使用均衡和減少旅客站內(nèi)的走行距離4個優(yōu)化目標，建立了基于多目標非線性整數(shù)規(guī)劃的高速鐵路到發(fā)線運用模型，并以某大型鐵路客運站為實際背景，采用C#對算法進行了實現(xiàn)，得到了到發(fā)線運用方案。結(jié)果表明，所建模型很好地體現(xiàn)了到發(fā)線運用的各種要求，得到了比較均衡的、方便旅客乘降的到發(fā)線運用方案，與傳統(tǒng)的手工經(jīng)驗計算編制方法相比更優(yōu)化、更高效，為優(yōu)化列車進路，實現(xiàn)自動編制到發(fā)線運用計劃提供了技術手段。

[1] 史 峰，謝楚農(nóng)，于桂芳. 鐵路車站咽喉區(qū)進路排列優(yōu)化方法[J] ．鐵道學報，2004，26 （4）：5-9．

[2] 謝楚農(nóng)，黎新華. 鐵路客運站到發(fā)線運用優(yōu)化研究[J]．中國鐵道科學，2004，25（5）：130-133．

[3] 龍建成，高自友，馬建軍，等. 鐵路車站進路選擇優(yōu)化模型及求解算法的研究[J]．鐵道學報，2007，29 （5）：7-14．

[4] D. D.L. Cardillo, M. Nicola. K L-list coloring of graphs [J].European Journal of Operational Research, 1998, 106(1): 160-164.

[5] 徐 杰，杜 文，李宗平，等. 基于模擬退火算法和圖著色的調(diào)車機車安排研究[J]．鐵道學報，2003，25（3）：24-30．

[6] 高世蕊. 客運專線車站通過能力計算方法的研究[J]．鐵道運輸與經(jīng)濟，2005，27（10）：92-94．

[7] 張惟皎，史天運，陳 彥. 動車運用所存車線運用方案優(yōu)化模型與算法[J]．中國鐵道科學，2013， 34（1）：21-125．

責任編輯 楊利明

Research on optimizing model and algorithm of train route for large-scale railway passenger station

WU Jinfei, WANG Weiwei
( Institute of Computing Technologies, China Academy of Railway Sciences, Beijing 100081, China )

The paper built the multi-goal programming model of utilization of arrival and departure track at the large-sized railway passenger station by taking utilization of arrival and departure track and safety assurance for both train operation and technical operation as the target which included reducing the running distance and time for passengers to go into the station or get out of the station, any two departure or nonstop trains whose departure times were close won’t stay in the same platform as possible as they could, and effective utilization of the existed technical equipment for train operation at station such as balance the occupied and free time of every track. It was obtained each weight by ahp to optimization objective of model. The Heuristic Algorithm was selected to solve the model in this paper. The better application scheme of arriving-departure tracks was obtained under the real-life case of a large-sized railway passenger station.

passenger station； selection of train route；multi-objective planning；Heuristic Algorithm

U291.6∶TP39

A

1005-8451（2014）05-0001-05

2013-12-06

武晉飛，研究實習員；王煒煒，助理研究員。