李得偉，丁世順

(北京交通大學(xué) 軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京　100044)

列車運(yùn)行圖是高速鐵路行車組織的基礎(chǔ)，其編制質(zhì)量直接影響行車的安全和效率。周期性列車運(yùn)行圖是指在每個(gè)周期時(shí)段內(nèi)，列車運(yùn)行線都具有相同的模式[1]。與非周期列車運(yùn)行圖相比，周期性列車運(yùn)行圖具有便于旅客記憶、行車組織有規(guī)律、有利于合理組織列車銜接等優(yōu)點(diǎn)。因此，國(guó)外高速鐵路發(fā)達(dá)國(guó)家如日本、法國(guó)、德國(guó)等均廣泛采用周期性列車運(yùn)行圖。

國(guó)外學(xué)者對(duì)周期性列車運(yùn)行圖的編制問(wèn)題進(jìn)行了大量的研究。Serafini等[2]首次提出了周期事件規(guī)劃問(wèn)題(Periodic Event Scheduling Problem，PESP)模型，并將PESP模型應(yīng)用在機(jī)車調(diào)度等計(jì)劃的編制中。Voorhoeve[3]首先采用PESP模型解決荷蘭鐵路周期性列車運(yùn)行圖的編制問(wèn)題。Lindner[4]綜合研究了列車開(kāi)行方案和列車運(yùn)行圖編制的問(wèn)題，開(kāi)發(fā)了求解PESP模型的分支定界算法。Peeters[5]在PESP模型的基礎(chǔ)上提出CPF(Cycle Periodicity Formulation)模型，通過(guò)在CPF模型中加入車站通過(guò)能力約束，從而提高了周期性列車運(yùn)行圖的編制質(zhì)量。

國(guó)內(nèi)也有學(xué)者對(duì)編制適合我國(guó)鐵路運(yùn)營(yíng)特點(diǎn)的周期性列車運(yùn)行圖問(wèn)題進(jìn)行了研究。汪波等[6]在PESP模型的基礎(chǔ)上利用約束圖建立了周期勢(shì)差模型，并應(yīng)用周期勢(shì)差模型編制了京津城際高速鐵路不同列車開(kāi)行方案下的周期性列車運(yùn)行圖。謝美全等[7]提出定序的周期性列車運(yùn)行圖編制模型，該模型考慮了列車對(duì)到發(fā)時(shí)刻的特殊要求，使得編制的列車運(yùn)行圖的適應(yīng)性更高。聶磊等[8]研究了計(jì)算機(jī)編制周期性列車運(yùn)行圖的關(guān)鍵技術(shù)，為計(jì)算機(jī)自動(dòng)編制周期性列車運(yùn)行圖提供了技術(shù)支撐。

既有研究為解決我國(guó)鐵路周期性列車運(yùn)行圖的編制問(wèn)題奠定了基礎(chǔ)，而且基于PESP模型編制周期性列車運(yùn)行圖已經(jīng)成為業(yè)界共識(shí)。由于我國(guó)鐵路的列車數(shù)量多、運(yùn)行線路長(zhǎng)、停站多而復(fù)雜，國(guó)外的研究成果無(wú)法直接應(yīng)用到我國(guó)鐵路；而我國(guó)的既有研究大多針對(duì)的是較簡(jiǎn)單的小規(guī)模場(chǎng)景。對(duì)于求解大規(guī)模周期性列車運(yùn)行圖模型時(shí)無(wú)解的問(wèn)題，國(guó)內(nèi)外的研究還不多。作者通過(guò)研究發(fā)現(xiàn)，當(dāng)求解問(wèn)題規(guī)模較大時(shí)導(dǎo)致無(wú)解的主要原因是PESP傳統(tǒng)模型中的固定列車區(qū)間運(yùn)行時(shí)間約束較為嚴(yán)格?；谶@一發(fā)現(xiàn)，本文在PESP傳統(tǒng)模型[5]的基礎(chǔ)上，提出1種改進(jìn)的PESP模型，用于編制適合我國(guó)高速鐵路的周期性列車運(yùn)行圖。

1　PESP改進(jìn)模型

1.1　目標(biāo)函數(shù)

為了最大化企業(yè)利益，提高動(dòng)車組的運(yùn)用效率，在用于編制高速鐵路周期性列車運(yùn)行圖的PESP改進(jìn)模型中以列車的總運(yùn)行時(shí)間t總最小為目標(biāo)函數(shù)，可以表示為

(1)

1.2　約束條件

1)可變區(qū)間運(yùn)行時(shí)間約束

在PESP傳統(tǒng)模型中列車的區(qū)間運(yùn)行時(shí)間約束是嚴(yán)格的等式約束，如式(2)所示，由于解空間受限，求解大規(guī)模問(wèn)題時(shí)易出現(xiàn)無(wú)解的情況。為了解決這一問(wèn)題，本文提出可變的區(qū)間運(yùn)行時(shí)間約束，即允許列車的區(qū)間運(yùn)行時(shí)間在一定范圍內(nèi)變動(dòng)，改進(jìn)的區(qū)間運(yùn)行時(shí)間約束如式(3)所示。

i=1，2，…，N；m=2，3，…，M

(2)

i=1，2，…，N；m=2，3，…，M

(3)

其中，

i=1，2，…，N；m=2，3，…，M

(4)

2)可變停站時(shí)間約束

列車在車站的停站時(shí)間約束可以表示為

i=1，2，…，N；m=2，3，…，M-1

(5)

3)列車運(yùn)行安全間隔時(shí)間約束

當(dāng)列車在區(qū)間內(nèi)的運(yùn)行時(shí)間可變后，由于PESP傳統(tǒng)模型的列車運(yùn)行安全間隔時(shí)間約束中包含列車的區(qū)間運(yùn)行時(shí)間，因此，原有約束不再適用。為解決這一問(wèn)題，需要將PESP傳統(tǒng)模型的列車運(yùn)行安全間隔時(shí)間約束分解為2個(gè)與列車的區(qū)間運(yùn)行時(shí)間無(wú)關(guān)的約束：列車出發(fā)安全間隔時(shí)間約束和列車到達(dá)安全間隔時(shí)間約束，如式(6)和式(7)所示。

i和j=1，2，…，N；j>i；m=1，2，…，M-1

(6)

i和j= 1，2，…，N；j>i；m=1，2，…，M-1

(7)

4)同類列車服務(wù)均衡性約束

(8)

5)列車到達(dá)和出發(fā)時(shí)間范圍約束

根據(jù)運(yùn)輸組織的要求，某些列車在車站的出發(fā)和到達(dá)時(shí)間需要固定在特定的時(shí)間范圍內(nèi)，可以表示為

(9)

(10)

1.3　模型求解

本文給出的PESP改進(jìn)模型為單目標(biāo)線性混合整數(shù)規(guī)劃模型，可以利用數(shù)學(xué)優(yōu)化軟件如ILOG CPLEX進(jìn)行求解，但有以下2個(gè)關(guān)鍵問(wèn)題需要解決。

1)模型的求解效率問(wèn)題

2)模型的一般性問(wèn)題

圖1　區(qū)間運(yùn)行時(shí)間之差大于或等于

2　實(shí)例驗(yàn)證

圖2　列車開(kāi)行方案

序號(hào)區(qū)間純運(yùn)行時(shí)分/min1北京南—廊坊162廊坊—天津南133天津南—滄州西184滄州西—德州東215德州東—濟(jì)南西196濟(jì)南西—泰安137泰安—曲阜東148曲阜東—滕州東119滕州東—棗莊710棗莊—徐州東1311徐州東—宿州東1412宿州東—蚌埠南1813蚌埠南—定遠(yuǎn)1114定遠(yuǎn)—滁州1315滁州—南京南1316南京南—鎮(zhèn)江南1517鎮(zhèn)江南—丹陽(yáng)北618丹陽(yáng)北—常州北719常州北—無(wú)錫東1220無(wú)錫東—蘇州北521蘇州北—昆山南622昆山南—上海虹橋12

通過(guò)求解發(fā)現(xiàn)，使用PESP傳統(tǒng)模型無(wú)法在有限時(shí)間內(nèi)得出最優(yōu)解；然而使用本文的PESP改進(jìn)模型，能夠快速求得最優(yōu)目標(biāo)函數(shù)值為2 394 min，求解時(shí)間為305 s，求解得到的結(jié)果如圖3所示，驗(yàn)證了PESP改進(jìn)模型適用于規(guī)模較大的高速鐵路周期性列車運(yùn)行圖編制問(wèn)題。

3　靈敏度分析

圖3　京滬高速鐵路下行方向的周期性列車運(yùn)行圖

3.1　允許的區(qū)間運(yùn)行時(shí)間變化量對(duì)求解效果的影響

表的取值對(duì)模型求解結(jié)果的影響

3.2　允許的停站時(shí)間變化量對(duì)求解效果的影響

3.3　割平面對(duì)模型求解時(shí)間的影響

為了在保證求解可行性的同時(shí)提高求解效率，本文通過(guò)在求解過(guò)程中引入割平面以減小搜索空間。固定其他參數(shù)，研究加入割平面和不加入割平面時(shí)模型的求解時(shí)間，結(jié)果見(jiàn)表4。由表4可知，在求解過(guò)程中引入割平面能夠顯著縮短模型的求解時(shí)間。

表的取值對(duì)模型求解效果的影響

表4　加入割平面前后的模型求解時(shí)間對(duì)比

4　結(jié)　語(yǔ)

本文對(duì)編制周期性列車運(yùn)行圖所采用的PESP傳統(tǒng)模型進(jìn)行了改進(jìn)。在PESP改進(jìn)模型中以列車的總運(yùn)行時(shí)間最小為目標(biāo)函數(shù)，采用可變的區(qū)間運(yùn)行時(shí)間約束，并將列車運(yùn)行安全間隔時(shí)間約束分解為2個(gè)與列車的區(qū)間運(yùn)行時(shí)間無(wú)關(guān)的約束，以實(shí)現(xiàn)對(duì)大規(guī)模高速鐵路周期性列車運(yùn)行圖編制問(wèn)題的求解。通過(guò)編制京滬高速鐵路下行方向的周期性列車運(yùn)行圖驗(yàn)證了PESP改進(jìn)模型的有效性。分析PESP改進(jìn)模型中參數(shù)的取值對(duì)模型求解質(zhì)量和求解效率的影響，結(jié)果表明，隨著允許的區(qū)間運(yùn)行時(shí)間變化量和停站時(shí)間變化量的增大，PESP改進(jìn)模型的求解時(shí)間也隨之大幅增加。為此在求解模型時(shí)采用了加入割平面的方法，從而使PESP改進(jìn)模型的求解效率得到大幅度提高。

[1]楊東方. 計(jì)算機(jī)編制客運(yùn)專線周期性列車運(yùn)行圖的研究[D].北京：北京交通大學(xué)，2009.

(YANG Dongfang. Study on Computer Aided Working out Cyclic Train Timetable for Passenger Dedicated Line[D]. Beijing：Beijing Jiaotong University，2009. in Chinese)

[2]SERAFINI P，UKOVICH W. A Mathematical Model for Periodic Event Scheduling Problems[J]. SIAM Journal on Discrete Mathematics，1989，2(4)：550-581.

[3]VOORHOEVE M. Rail Scheduling with Discrete Sets[R]. Eindhoven：Eindhoven University of Technology，1993.

[4]LINDNER T. Train Schedule Optimization in Public Rail Transport[D]. Braunschweig：Technical University Braunschweig，2000.

[5]PEETERS L. Cyclic Railway Timetable Optimization[D]. Rotterdam：Erasmus University Rotterdam，2003.

[6]汪波，楊浩. 周期運(yùn)行圖編制模型與算法研究[J]. 鐵道學(xué)報(bào)，2007，29(5)：1-6.

(WANG Bo，YANG Hao. Study on Model and Algorithm of Periodic Train Diagram Generation[J]. Journal of the China Railway Society，2007，29 (5)：1-6. in Chinese)

[7]謝美全，聶磊. 周期性列車運(yùn)行圖編制模型研究[J]. 鐵道學(xué)報(bào)，2009，31(4)：7-13.

(XIE Meiquan，NIE Lei. Model of Cyclic Train Timetable[J]. Journal of the China Railway Society，2009，31(4)：7-13. in Chinese)

[8]聶磊，張淵，武鑫. 計(jì)算機(jī)編制周期性列車運(yùn)行圖關(guān)鍵技術(shù)[J]. 中國(guó)鐵道科學(xué)，2014，35(1)：114-121.

(NIE Lei，ZHANG Yuan，WU Xin. Key Technologies for Computer Generation of Cyclic Train Timetable[J]. China Railway Science，2014，35(1)：114-121. in Chinese)