多優(yōu)化目標視角下高鐵站到發(fā)線運用計劃編制

雷明，孟學雷

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

?

【交通運輸】

多優(yōu)化目標視角下高鐵站到發(fā)線運用計劃編制

雷明，孟學雷

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

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

關鍵詞：高鐵站；到發(fā)線運用；0-1整數規(guī)劃；走行距離；穩(wěn)定性

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

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

1　問題分析及符號說明

1.1高鐵站到發(fā)線運用問題分析

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

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

1.2到發(fā)線運用模型的符號說明

2　高鐵站到發(fā)線運用模型

2.1約束條件

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

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

(1)

(2)到發(fā)線占用的約束

(3)進路沖突的約束

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

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

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

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

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

2.2到發(fā)線運用目標函數

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

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

(2)

(2)到發(fā)線運用計劃的穩(wěn)定性

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

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

(3)

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

(4)

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

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

3　算例驗證

為了證明本文中提出的模型與算法的正確性，算例采用圖2所示的高鐵車站網絡進行驗算。該車站共有8條股道，4個站臺，6個站臺面，1、3、5、7道用于接發(fā)下行列車；2、4、6、8道用于接發(fā)上行列車。圖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

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

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

表1　9:00～15:00列車到發(fā)時刻

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

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

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

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

圖5　到發(fā)線運用方案Fig.5　Track utilization scheme

4　研究結論

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

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

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

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

參考文獻：

[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]史峰,陳彥,秦進,等.鐵路客運站到發(fā)線運用和接發(fā)車進路排列方案綜合優(yōu)化[ J].中國鐵道科學,2009,30 (6):108-113.

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

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

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

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

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

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

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

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

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

DOI:10.3976/j.issn.1002-4026.2016.04.013

收稿日期：2016-05-04

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

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

中圖分類號：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