基于改進的PESP模型編制高速鐵路周期性列車運行圖的研究

李得偉，丁世順

(北京交通大學(xué) 軌道交通控制與安全國家重點實驗室，北京　100044)

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

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

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

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

1　PESP改進模型

1.1　目標函數(shù)

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

(1)

1.2　約束條件

1)可變區(qū)間運行時間約束

在PESP傳統(tǒng)模型中列車的區(qū)間運行時間約束是嚴格的等式約束，如式(2)所示，由于解空間受限，求解大規(guī)模問題時易出現(xiàn)無解的情況。為了解決這一問題，本文提出可變的區(qū)間運行時間約束，即允許列車的區(qū)間運行時間在一定范圍內(nèi)變動，改進的區(qū)間運行時間約束如式(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)可變停站時間約束

列車在車站的停站時間約束可以表示為

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

(5)

3)列車運行安全間隔時間約束

當列車在區(qū)間內(nèi)的運行時間可變后，由于PESP傳統(tǒng)模型的列車運行安全間隔時間約束中包含列車的區(qū)間運行時間，因此，原有約束不再適用。為解決這一問題，需要將PESP傳統(tǒng)模型的列車運行安全間隔時間約束分解為2個與列車的區(qū)間運行時間無關(guān)的約束：列車出發(fā)安全間隔時間約束和列車到達安全間隔時間約束，如式(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)列車到達和出發(fā)時間范圍約束

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

(9)

(10)

1.3　模型求解

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

1)模型的求解效率問題

2)模型的一般性問題

圖1　區(qū)間運行時間之差大于或等于

2　實例驗證

圖2　列車開行方案

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

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

3　靈敏度分析

圖3　京滬高速鐵路下行方向的周期性列車運行圖

3.1　允許的區(qū)間運行時間變化量對求解效果的影響

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

3.2　允許的停站時間變化量對求解效果的影響

3.3　割平面對模型求解時間的影響

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

表的取值對模型求解效果的影響

表4　加入割平面前后的模型求解時間對比

4　結(jié)　語

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

[1]楊東方. 計算機編制客運專線周期性列車運行圖的研究[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]汪波，楊浩. 周期運行圖編制模型與算法研究[J]. 鐵道學(xué)報，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]謝美全，聶磊. 周期性列車運行圖編制模型研究[J]. 鐵道學(xué)報，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]聶磊，張淵，武鑫. 計算機編制周期性列車運行圖關(guān)鍵技術(shù)[J]. 中國鐵道科學(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)