多優化目標視角下高鐵站到發線運用計劃編制

雷明，孟學雷

(蘭州交通大學交通運輸學院，甘肅 蘭州 730070)

?

【交通運輸】

多優化目標視角下高鐵站到發線運用計劃編制

雷明，孟學雷

(蘭州交通大學交通運輸學院，甘肅 蘭州 730070)

摘要：在給定列車運行圖和車站候車廳布局的前提下，研究高速鐵路車站到發線運用問題。以股道和道岔的相容性約束作為前提，分析檢票口附近固定座位數量和檢票口與站臺的通道距離，以增強車站作業計劃穩定性、列車站內走行距離最短和最大化滿足候車廳布局為3個優化目標，建立了到發線運用的0-1整數規劃模型。針對模型特點，采用Lingo編程進行求解，最后通過某客運站為例證明該模型的有效性。結果表明，該模型能準確描述實際問題，適用于大型高鐵站的股道分配問題。

關鍵詞：高鐵站；到發線運用；0-1整數規劃；走行距離；穩定性

高速鐵路車站到發線運用計劃包括為列車分配到發線和安排合適的接發車進路，到發線運用優化是一類綜合優化問題。賈文崢等[1]將股道分配問題(track allocation problem，TAP)的約束分為軟約束和硬約束，建立了CP模型，采取含有沖突識別、值排序和Backtracking搜索3個步驟的算法對問題求解。Kroon等[2]指出車站作業計劃可歸結為集合配置問題(set packing problem) ，并證明當列車有3 條可選路徑時，車站作業計劃將成為NP-Complete問題。史峰等[3]選取到發線運用效用最大化和列車等級權重最大化為雙層優化目標，建立了0-1規劃模型，在Kroon等[2]算法的基礎上提出了極大列車進路方案及其k剔除領域系概念，進而設計了模擬退火算法進行問題的求解。陳彥等[4]在史峰等[3]優化模型的基礎上，調整了優化目標，以文獻[3]的算法為基礎，使用了改進的模擬退火算法進行模型求解。張英貴等[5]使用現代排序論，以總費用最小和股道均衡使用為目標，建立了多目標窗時排序模型，最后以人機交互會話的方式進行求解。龍建成等[6]引入銜接點和承載點的概念，以作業總晚點時間最短及各進路走行時間最短為目標，建立了車站進路選擇模型，在模擬退火算法的基礎上，提出了復合優化算法進行求解。喬瑞軍等[7]以列車站內走行時間之和最小和到發線均衡使用為優化目標建立了到發線運用多目標模型，以協調優化的思想求解。趙金觀等[8]在編組站到發線排序的基礎上，建立了到發線和調機運用模型，以可行性安排為實現目標并設計了相應的啟發式算法。苗建瑞等[9]從提高穩定性的角度出發，以車站資源運用最小為目標，建立了整數規劃模型，采取了基于蟻群算法的求解方法。賈文崢等[10]采用Petri網技術，探討了求解股道分配問題方法的強壯性。周妍[11]在運行圖需要調整的情況下，用計算機重新編制了運行圖，在此條件下進行車站徑路問題與運行圖協同編制的研究。曹巖等[12]采用差分算法，以運行晚點時間最小和編制高質量的運行計劃為目標，建立了高速鐵路列車運行調整模型。

一個良好的到發線運用計劃應具有良好的穩定性，抗干擾能力強，考慮車站候車廳布局情況能得到使乘客的便利性提高的到發線運用計劃。本文在站內走行消耗的總費用最小的優化目標的基礎上，提出了增強車站到發線運用計劃穩定性和最大化滿足候車廳布局的優化目標。該方法解決了優化目標的單一性，突出了優化的全面性。

1　問題分析及符號說明

1.1高鐵站到發線運用問題分析

高速鐵路列車具有行車密度大、追蹤間隔時間短的特點。良好的車站作業計劃能增加運輸組織效率，列車在車站內的作業包括為列車安排接發車進路及到發線，到發線運用計劃是高鐵站作業計劃的重要組成部分。從進站段咽喉區進入到發線的通道稱為接車進路，從到發線到達出站端咽喉區的通道稱為發車進路。

列車對到發線的使用與列車運行圖密不可分，運行圖規定了任意一列車到達和離開某車站的時刻。當運行圖給定時，車站要為所有列車安排無沖突的接發車進路和到發線。實質上，當接車進路確定后，相應的到發線也就確定了。在列車接車進路分配時，必須滿足一些約束，如到發線占用的約束、進路沖突的約束等等，在滿足約束的基礎上考慮優化目標。首先，為列車安排站內走行距離最短的接發車進路可使鐵路部門消耗的總費用最小；此外，列車在運行過程中會受到各種各樣的擾動，車站作業計劃的抗干擾能力是衡量車站作業計劃優劣的一項指標，文中使用控制相鄰兩列車之間的緩沖時間來提高作業計劃穩定性。候車廳布局在到發線運用的研究中極少涉及，本文以滿足候車廳布局為一個新的角度來考慮第三個目標函數。分析檢票口附近固定座位的數量和檢票口與站臺之間的通道距離，將候車廳布局與到發線使用進行結合，這樣能制定滿足更多目標的到發線運用計劃。綜上所述，客運站到發線運用問題是在滿足約束條件的基礎上，盡可能地滿足優化目標。

1.2到發線運用模型的符號說明

2　高鐵站到發線運用模型

2.1約束條件

(1)到發線使用最小間隔時間的約束

先后占用同一股道的兩列車必須滿足最小時間間隔才可以確保安全。對于希望占用同一到發線d(?d∈D)的先后兩列車t和t′(t,t′∈T)，只有前一趟列車t的尾部離開股道并釋放相應的道岔后，才可以對后行列車t′進行接車作業。那么兩者的到達出發時間必須滿足式(1)，

(1)

(2)到發線占用的約束

(3)進路沖突的約束

在車站作業中，有兩項作業產生敵對進路時必須保證兩項作業在使用道岔時沒有沖突，也即同一道岔在同一時間段內只能有一列車占用。進路沖突如圖1所示。

圖1　進路沖突示意圖Fig.1　Illustration of access routes conflict

在3股道的列車從A端發車，其使用的道岔集合為{11，9，5，3}。現有一列車從A端接入I股道，其使用的道岔集合為{1，5，9}，在道岔9的使用上有沖突。

(4)接發車進路與到發線關聯約束

當某列車的接車進路確定后，其相應的道岔、到發線及發車進路也就確定下來，兩者之間存在關聯的邏輯約束，記wtr表示列車t(?t∈T)使用接車進路r(?r∈R)的0-1變量，若使用為1，否則為0；wtq表示列車t(?t∈T)使用發車進路r(?q∈Q)的0-1變量，若使用為1，否則為0。

2.2到發線運用目標函數

(1)列車在站內走行距離最少

列車選擇不同的到發線，其走行的距離不一樣，當選擇走行距離較短的到發線時，車站的接車作業時間縮短，耗費的資源減小，鐵路部門的花費也就越少。對列車t(?t∈T)，給出t選擇某條接車進路r時所需的費用為Cr。t選擇某條發車進路q時所需的費用為Cq,所走的路徑越短，經過的道岔越少時，Cr和Cq就越小。那么該目標函數可以用下式表示，

(2)

(2)到發線運用計劃的穩定性

列車在運行過程中受到擾動是不可避免的，列車到發線運用計劃對擾動的抵抗能力越強說明其質量越好。通過分析同一條軌道區段相鄰兩次占用的時間間隔是判斷抗干擾能力的一個方法，時間間隔適當增加會提升抗干擾能力。到發線運用計劃的穩定性對車站作業組織的穩定大有益處。

對于兩列車t和t′(?t,t′∈T)，給出ztt′表示列車t和t′是否鄰接占用同一條股道的0-1變量，若t′為第一個與t列車有鄰接占用關系的列車時，ztt′為0，否則為1。在滿足第一個目標的基礎上，兩列車緩沖時間適當增大會提高車站作業計劃的穩定性，增強其抗干擾能力。定義一個分段函數g(ztt′,σtt′)，σtt′表示兩列車到達時間的差值即σtt′=at′-at。列車在高速鐵路車站的技術作業時間短，運輸組織效率高，為將該目標量化，參考了文獻[9]中的穩定性評價的規則，將兩列車到達時間間隔以5 min為步長劃分，給出g(ztt′,σtt′)的分段情況及目標函數。

(3)

(3)滿足候車廳布局及乘客便利性

(4)

根據不同優化目標的重要程度，給出系數λ1,λ2,λ3分別代表3個不同目標函數的重要程度。將3個優化目標的重要性調查問卷分別發給鐵路技術部門和調度生產部門，然后收回匯總，根據問卷結果確定λ1,λ2,λ3的值。其中0<λ1,λ2,λ3<1且λ1+λ2+λ3=1。經過上面的分析后，構建該問題的0-1整數規劃模型：

min Z=λ1f1+λ2f2+λ3f3，

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

xtd,ytv,ztt′,wtr,wtq=0,1，?t,t′∈T,?d∈D,?v∈V。

(13)

約束條件式(6)檢驗了運行圖的正確性，確保列車到發時刻滿足車站作業基礎。式(7)是道岔占用的約束，式(8)和式(9)用來判別列車t和t′是否前后緊接續占用同一條股道，其中M為一個較大的數。約束條件(10)和(11)說明，當接車進路確定后其相應的到發線以及發車進路也就確定了。需要注意的是，當列車在某一時刻密集到達時，該模型可能存在無法為某些列車安排進路及到發線的情況，因此此處假設列車密集到達時不超過車站的接發車能力。同時加權系數λ1,λ2,λ3的確定會影響解的實用性，在結論處進行討論。

3　算例驗證

為了證明本文中提出的模型與算法的正確性，算例采用圖2所示的高鐵車站網絡進行驗算。該車站共有8條股道，4個站臺，6個站臺面，1、3、5、7道用于接發下行列車；2、4、6、8道用于接發上行列車。圖3為該車站的候車大廳布局圖，該候車大廳有4個檢票口，每個檢票口跟不同站臺相連。檢票口1、檢票口2同時和站臺1、站臺2相連；同理檢票口3、檢票口4同時和站臺3、站臺4相連，檢票口與站臺相連但是走行的通道路程不同。

圖2　某高鐵站平面圖Fig.2　2-D figure of a high-speed railway station

圖3　高鐵站候車廳布局Fig.3　Waiting hall layout of the high-speed railway station

根據模型定義，由于高鐵站作業效率要求較高，接發列車按上下行進行區分，上行的列車只能接到上行方向的到發線，同理下行列車只能接到下行方向的到發線。

根據該高鐵站旅客列車運行圖，選取該高鐵站9:00～15:00的42列列車的到發時刻見表1。表1中下標為奇數的列車為下行列車，下標為偶數的列車為上行列車。表1中若某列車只有出發時刻則說明該車站為始發站，同樣若只有到達時刻則表明該站為終到站。

表1　9:00～15:00列車到發時刻

需要指出的是，運行圖到達時刻指列車在股道上停穩后的時刻，出發時間是指列車從股道上開始移動的時刻。根據車站作業標準，列車通過車站咽喉停穩在到發線上的時間大致為2 min，同樣列車從到發線出發到達另一端咽喉區的時間也大致為2 min。由于模型中的決策變量均為0-1變量，是一個LP問題。Lingo在線性規劃問題的求解中表現良好，因此本問題在計算的可行性上沒有問題。通過Lingo軟件進行編程求解時，由于目標函數值的單位不一致，仍然采用類似建立第三個目標函數時采用的離差標準化方法進行處理。最后求解得到上述列車占用到發線順序如圖4所示。Value值為1表示占用，為0表示不占用。

根據Lingo計算得到的到發線占用的結果，還原出到發線運用方案，繪制出該車站所有停站列車的到發線運用方案，如圖5所示。

從圖5中可以看出，該模型為通過并在該車站停留的列車分配了無沖突的進路。由于不停站通過列車的到發時刻在運行圖上一致，其在到發線運用方案圖中是一個點，于是將到發線1、2分配給上下行不停站通過列車，因此到發線運用方案中不再顯示1、2道。當兩列車先后占用同一股道時，為了增強到發線運用方案的穩定性，兩列車占用同一股道相隔時間較長；有些如t11,t15,t30等停站時間較長的列車，為減少后續停站列車的走行距離，這些列車被分配到遠離正線的到發線上，增強了后續列車的穩定性及靈活性。

圖4　使用Lingo程序計算的結果Fig.4　Computational results with Lingo program

圖5　到發線運用方案Fig.5　Track utilization scheme

4　研究結論

(1)候車廳布局在車站到發線運用的研究中尚未涉及，本文以候車廳布局情況為一個新的角度，同時考慮了列車走行距離最短以及車站作業計劃的穩定性，為得到合理、優化的到發線運用計劃奠定了基礎。

(2)Lingo軟件能夠較快求解該到發線運用模型。通過Lingo的計算結果而還原的到發線運用方案符合實際情況，能夠給該車站提供一個到發線運用方案。

(3)文中目標函數的加權系數λ1,λ2,λ3的確定非常重要，加權系數會影響到解的實用性、合理性。本文根據該車站的情況，采用調查問卷的形式對車站工作人員的意見進行搜集，確定加權系數。針對不同的車站，需要重新確定加權系數。

(4)本文研究高鐵站到發線運用計劃時以給定的列車運行圖作為前提，但列車在區間運行時會受到各種突發事件的干擾，當干擾較大時，車站到發線使用計劃需要更新。因此，如何在列車運行調整的基礎上進行車站到發線運用計劃的編制是下一步研究的重點。

參考文獻：

[1]賈文崢,毛保華,何天健,等.大型客運站股道分配問題的模型與算法[J].鐵道學報,2010,32(2):8-13.

[2]KROON L G，ROMEIJN H E，ZWANEVELD P J. Routing trains through railway stations:complexity issues[J]. European Journal of Operational Research,1997,98(3): 485-498．

[3]史峰,陳彥,秦進,等.鐵路客運站到發線運用和接發車進路排列方案綜合優化[ J].中國鐵道科學,2009,30 (6):108-113.

[4]陳彥,史峰,秦進,等.旅客列車過站徑路優化模型與算法[J].中國鐵道科學,2010,31(2):101-107.

[5]張英貴,雷定猷,劉明翔.鐵路車站股道運用排序模型與算法[J].中國鐵道科學,2010,31(2):96-100.

[6]龍建成,高自友,馬建軍,等.鐵路車站進路選擇優化模型及求解算法的研究[J].鐵道學報,2007,29(5):7-14.

[7]喬瑞軍,朱曉寧,張天偉,等.客運專線車站到發線運用多目標優化模型[J].北京交通大學學報,2012,36(3):57-64.

[8]趙金觀,朱志國.編組站到解作業計劃自動化編制研究[J].鐵道科學與工程學報,2015,12(4):962-966.

[9]苗建瑞,于勇,孟令云,等.面向穩定性的高速鐵路車站作業計劃優化方法[J].交通運輸系統工程與信息,2012,12(3):115-121.

[10]賈文崢,毛保華,何天鍵,等.基于Petri網的車站股道分配方案瓶頸識別[J].交通運輸系統工程與信息,2009,9(6):136-141.

[11]周妍.高速鐵路列車運行圖與車站徑路計劃協同編制理論與方法研究[D].北京：北京交通大學，2013.

[12]曹巖,孟學雷.基于改進差分算法的高速列車運行調整研究[J].鐵道科學與工程學報,2014,11(6):102-108.

DOI:10.3976/j.issn.1002-4026.2016.04.013

收稿日期：2016-05-04

基金項目：國家自然科學基金(61263027)

作者簡介：雷明(1992-)，男，碩士研究生，研究方向為運輸組織優化。

中圖分類號：U291

文獻標識碼：A

文章編號：1002-4026(2016)04-0060-08

Track utilization planning of high-speed railway station with multi-objective optimization

LEI Ming，MENG Xue-lei

(School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China)

Abstract∶We address track utilization of high-speed railway station for a definite train diagram and station hall layout. We analyze the number of ticket entrance nearby fixed seats and passage distance between ticket entrance and platform with compatible constraint of tracks and turnouts as a premise. We further construct a 0-1 integer programming model for arrival and departure track utilization with stability increase of station operational plan, shortest walk distance in a station and maximal station hall layout as optimization goals. Based on its characteristics, we solve it with Lingo programming.We eventually demonstrate its effectiveness with a high-speed railway station as an instance. Results show that it can accurately indicate practical issues, so it is suitable for track allocation issue of large high-speed railway station.

Key words∶high-speed railway station;track utilization;0-1 integer programming; walking distance; stability