雷明，孟學(xué)雷

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院，甘肅 蘭州 730070)

?

【交通運(yùn)輸】

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

雷明，孟學(xué)雷

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院，甘肅 蘭州 730070)

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

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

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

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

1　問題分析及符號說明

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

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

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

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

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

2.1約束條件

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

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

(1)

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

(3)進(jìn)路沖突的約束

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

圖1　進(jìn)路沖突示意圖Fig.1　Illustration of access routes conflict

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

(4)接發(fā)車進(jìn)路與到發(fā)線關(guān)聯(lián)約束

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

2.2到發(fā)線運(yùn)用目標(biāo)函數(shù)

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

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

(2)

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

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

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

(3)

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

(4)

根據(jù)不同優(yōu)化目標(biāo)的重要程度，給出系數(shù)λ1,λ2,λ3分別代表3個(gè)不同目標(biāo)函數(shù)的重要程度。將3個(gè)優(yōu)化目標(biāo)的重要性調(diào)查問卷分別發(fā)給鐵路技術(shù)部門和調(diào)度生產(chǎn)部門，然后收回匯總，根據(jù)問卷結(jié)果確定λ1,λ2,λ3的值。其中0<λ1,λ2,λ3<1且λ1+λ2+λ3=1。經(jīng)過上面的分析后，構(gòu)建該問題的0-1整數(shù)規(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)檢驗(yàn)了運(yùn)行圖的正確性，確保列車到發(fā)時(shí)刻滿足車站作業(yè)基礎(chǔ)。式(7)是道岔占用的約束，式(8)和式(9)用來判別列車t和t′是否前后緊接續(xù)占用同一條股道，其中M為一個(gè)較大的數(shù)。約束條件(10)和(11)說明，當(dāng)接車進(jìn)路確定后其相應(yīng)的到發(fā)線以及發(fā)車進(jìn)路也就確定了。需要注意的是，當(dāng)列車在某一時(shí)刻密集到達(dá)時(shí)，該模型可能存在無法為某些列車安排進(jìn)路及到發(fā)線的情況，因此此處假設(shè)列車密集到達(dá)時(shí)不超過車站的接發(fā)車能力。同時(shí)加權(quán)系數(shù)λ1,λ2,λ3的確定會(huì)影響解的實(shí)用性，在結(jié)論處進(jìn)行討論。

3　算例驗(yàn)證

為了證明本文中提出的模型與算法的正確性，算例采用圖2所示的高鐵車站網(wǎng)絡(luò)進(jìn)行驗(yàn)算。該車站共有8條股道，4個(gè)站臺(tái)，6個(gè)站臺(tái)面，1、3、5、7道用于接發(fā)下行列車；2、4、6、8道用于接發(fā)上行列車。圖3為該車站的候車大廳布局圖，該候車大廳有4個(gè)檢票口，每個(gè)檢票口跟不同站臺(tái)相連。檢票口1、檢票口2同時(shí)和站臺(tái)1、站臺(tái)2相連；同理檢票口3、檢票口4同時(shí)和站臺(tái)3、站臺(tái)4相連，檢票口與站臺(tái)相連但是走行的通道路程不同。

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

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

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

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

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

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

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

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

圖4　使用Lingo程序計(jì)算的結(jié)果Fig.4　Computational results with Lingo program

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

4　研究結(jié)論

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

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

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

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

參考文獻(xiàn)：

[1]賈文崢,毛保華,何天健,等.大型客運(yùn)站股道分配問題的模型與算法[J].鐵道學(xué)報(bào),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ìn),等.鐵路客運(yùn)站到發(fā)線運(yùn)用和接發(fā)車進(jìn)路排列方案綜合優(yōu)化[ J].中國鐵道科學(xué),2009,30 (6):108-113.

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

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

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

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

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

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

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

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

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

DOI:10.3976/j.issn.1002-4026.2016.04.013

收稿日期：2016-05-04

基金項(xiàng)目：國家自然科學(xué)基金(61263027)

作者簡介：雷明(1992-)，男，碩士研究生，研究方向?yàn)檫\(yùn)輸組織優(yōu)化。

中圖分類號：U291

文獻(xiàn)標(biāo)識碼：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