考慮旅客需求的停站方案與列車運(yùn)行圖一體化模型與算法

劉璐，孟令云，李新毅，劉崗

?

考慮旅客需求的停站方案與列車運(yùn)行圖一體化模型與算法

劉璐1，孟令云1，李新毅1，劉崗2

(1. 北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044；2. 天津南環(huán)鐵路維修有限責(zé)任公司，天津 300381)

考慮高速鐵路旅客出行的時(shí)空敏感性較高的特點(diǎn)，將旅客運(yùn)輸狀態(tài)引入運(yùn)輸時(shí)空網(wǎng)絡(luò)，構(gòu)建三維的時(shí)間-空間-狀態(tài)網(wǎng)絡(luò)，提出基于旅客需求的停站方案與列車運(yùn)行圖綜合優(yōu)化0-1 整數(shù)規(guī)劃模型，實(shí)現(xiàn)旅客分配、停站方案與列車運(yùn)行圖編制的一體化。設(shè)計(jì)拉格朗日松弛求解算法，將復(fù)雜的列車間強(qiáng)耦合問(wèn)題分解為單列車的最短路徑子問(wèn)題集合，從而降低模型求解難度。以京滬高鐵北京南-曲阜東區(qū)段為背景進(jìn)行驗(yàn)證和分析，結(jié)果表明模型不僅實(shí)現(xiàn)了較低的運(yùn)營(yíng)成本，還能夠有效滿足旅客需求，實(shí)現(xiàn)客流分配、停站方案與列車運(yùn)行圖編制的有機(jī)聯(lián)動(dòng)。

鐵路運(yùn)輸；列車運(yùn)行圖編制；拉格朗日松弛算法；綜合優(yōu)化；時(shí)空狀態(tài)網(wǎng)絡(luò)；旅客需求

列車運(yùn)行圖是鐵路行車組織的基礎(chǔ)，編制和優(yōu)化運(yùn)行圖是鐵路運(yùn)輸組織領(lǐng)域的經(jīng)典問(wèn)題。高速鐵路的不斷發(fā)展和社會(huì)生活水平的不斷提高，旅客對(duì)時(shí)空的敏感性需求以及對(duì)鐵路系統(tǒng)服務(wù)水平的要求不斷增加，鐵路部門需要通過(guò)考慮旅客需求來(lái)提高旅客服務(wù)水平，以提升在各種交通方式競(jìng)爭(zhēng)下行業(yè)競(jìng)爭(zhēng)力。此時(shí)考慮旅客需求的列車運(yùn)行圖編制顯得尤為重要。大多數(shù)學(xué)者從鐵路運(yùn)營(yíng)的角度出發(fā)，以鐵路效益最大[1?3]、列車總旅行時(shí)間最小[4]、列車運(yùn)行圖的均衡性[4]等為目標(biāo)，對(duì)列車開(kāi)行方案或列車運(yùn)行圖進(jìn)行獨(dú)立優(yōu)化，少量學(xué)者從旅客的角度，考慮旅客的時(shí)變需求、擁擠狀態(tài)[5]、時(shí)間敏感度[3]等因素，以旅客總等待時(shí)間最小化[5]、旅客總旅行時(shí)間最小化[6]、旅客滿意度最大化[3]等為目標(biāo)函數(shù)，對(duì)列車運(yùn)行圖進(jìn)行優(yōu)化。少量學(xué)者對(duì)開(kāi)行方案和列車運(yùn)行圖進(jìn)行綜合優(yōu)化，周文梁等[7?9]結(jié)合基于旅客彈性需求的列車開(kāi)行方案優(yōu)化和定序優(yōu)化的列車運(yùn)行圖優(yōu)化，將列車開(kāi)行方案和列車運(yùn)行圖作為整體構(gòu)建雙層規(guī)劃模型，進(jìn)行綜合優(yōu)化。既有考慮旅客需求的研究，大多將開(kāi)行方案與列車運(yùn)行圖的優(yōu)化進(jìn)行割裂考慮，采取分階段或獨(dú)立優(yōu)化的方法，容易造成優(yōu)化目標(biāo)和約束的不協(xié)調(diào)等問(wèn)題?？紤]綜合優(yōu)化的復(fù)雜性，本文考慮旅客需求的停站方案與列車運(yùn)行圖一體化優(yōu)化問(wèn)題。基于Mahmoudi 等[10]提出的VRPPDTW(Vehicle Routing Problems With Pickup And Delivery With Time Windows)問(wèn)題，將旅客運(yùn)輸狀態(tài)引入時(shí)空網(wǎng)絡(luò)，構(gòu)建三維的時(shí)間?空間?狀態(tài)網(wǎng)絡(luò)，實(shí)現(xiàn)旅客分配、停站方案與列車運(yùn)行圖編制的綜合優(yōu)化。設(shè)計(jì)拉格朗日松弛求解算法，將復(fù)雜的列車間強(qiáng)耦合問(wèn)題分解為單列車的最短路徑子問(wèn)題集合，從而降低模型求解難度。最后以京滬高鐵北京南?曲阜東下行的列車運(yùn)行圖編制為例進(jìn)行案例分析。

1 運(yùn)輸時(shí)空狀態(tài)網(wǎng)絡(luò)

1.1 運(yùn)輸時(shí)空網(wǎng)絡(luò)的構(gòu)建

圖1 4個(gè)物理節(jié)點(diǎn)的簡(jiǎn)易鐵路線路

構(gòu)建時(shí)間?空間網(wǎng)絡(luò)，將時(shí)間劃分成均等的時(shí)間間隔，每個(gè)時(shí)間間隔具有相同的時(shí)間長(zhǎng)度。設(shè)旅客1的期望出發(fā)和到達(dá)時(shí)間窗分別是[3,6]和[11,14]；旅客2期望出發(fā)和到達(dá)時(shí)間窗分別是[6,8]，[12,15]。對(duì)于列車，設(shè)其最早離開(kāi)起始站時(shí)間為1，最晚到達(dá)終到站時(shí)間為20。最短路徑時(shí)空網(wǎng)絡(luò)圖如圖2所示。

在此二維時(shí)空網(wǎng)絡(luò)中，設(shè)定：1) 任何列車可處于任何物理節(jié)點(diǎn)或虛擬節(jié)點(diǎn)。2) 任意列車只能在其允許運(yùn)行時(shí)間窗內(nèi)運(yùn)行。3) 乘客只能在其期望出發(fā)時(shí)間窗內(nèi)上車，也只能在其期望到達(dá)時(shí)間窗內(nèi) 下車。

圖2 最短路徑時(shí)空網(wǎng)絡(luò)圖

1.2 運(yùn)輸狀態(tài)的引入、表達(dá)與傳遞

表1 時(shí)空狀態(tài)網(wǎng)中相關(guān)參數(shù)及含義

(a) 時(shí)空狀態(tài)網(wǎng)絡(luò)上的最短路；(b) 簡(jiǎn)易路網(wǎng)

將旅客組的運(yùn)輸狀態(tài)引入時(shí)空網(wǎng)絡(luò)后，二維時(shí)空網(wǎng)絡(luò)由此轉(zhuǎn)變?yōu)槿S時(shí)空狀態(tài)網(wǎng)絡(luò)。三維時(shí)空狀態(tài)網(wǎng)絡(luò)中，每個(gè)點(diǎn)可表示為(,,)。簡(jiǎn)易線路下的三維時(shí)空狀態(tài)網(wǎng)絡(luò)上的最短路如圖3所示。

2 數(shù)學(xué)模型

2.1 模型假設(shè)

1) 不考慮車底的運(yùn)用、車站進(jìn)路排列和到發(fā)線的運(yùn)用；假定列車數(shù)量足夠。

2) 列車均在雙線鐵路上運(yùn)行，且只考慮單向行駛。

3) 自動(dòng)閉塞區(qū)段，列車采用按閉塞分區(qū)追蹤運(yùn)行的行車組織方式運(yùn)行。

4) 不考慮旅客的換乘行為。

2.2 列車停站方案與列車運(yùn)行圖綜合優(yōu)化數(shù)學(xué)模型

2.2.1 模型參數(shù)

模型參數(shù)及其含義見(jiàn)表2。

表2 模型參數(shù)及其含義

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

在空間?時(shí)間?狀態(tài)三維網(wǎng)絡(luò)中，列車可從點(diǎn)(,,)通過(guò)弧(,,,,,′)到達(dá)點(diǎn)(,,′)。引入0-1變量(,,,,,,′)表示列車是否使用弧(,,,,,′)。(,,,,,,′)表示列車在弧(,,,,,,′)上的花費(fèi)，定義其與列車運(yùn)行時(shí)分成正比。本研究考慮的目標(biāo)函數(shù)是最大限度減少列車花費(fèi)，實(shí)現(xiàn)運(yùn)營(yíng)總費(fèi)用最小化。定義列車在弧(,,,,,′)上的運(yùn)營(yíng)費(fèi)用為(,,,,,,′)，令該費(fèi)用與旅行時(shí)間成正比。目標(biāo)函數(shù)如下：

2.2.3 約束條件

第Ⅰ組約束：網(wǎng)絡(luò)節(jié)點(diǎn)流量平衡約束

保證在任何時(shí)刻，每個(gè)節(jié)點(diǎn)上的列車流平衡，例如，假設(shè)在中間節(jié)點(diǎn)，任意列車在由時(shí)空網(wǎng)絡(luò)上表示為(′,′,′)的點(diǎn)到達(dá)節(jié)點(diǎn)(,,)后，則此列車必有由節(jié)點(diǎn)(,,)到節(jié)點(diǎn)(′,′,′)的流動(dòng)過(guò)程。因流平衡在始發(fā)節(jié)點(diǎn)、終到節(jié)點(diǎn)和中間節(jié)有所不同，對(duì)其進(jìn)行如下約束。

1) 列車在始發(fā)車站的流量平衡約束：

2) 列車在終到車站的流量平衡約束：

3) 列車在中間節(jié)點(diǎn)的流量平衡約束：

列車在物理節(jié)點(diǎn)上需同時(shí)滿足進(jìn)出服務(wù)弧、等待弧與物理弧守恒。

第Ⅱ組約束：旅客需求約束

4) 約束滿足所有旅客均能在其起點(diǎn)搭乘列車，且均能搭乘列車到達(dá)終點(diǎn)：

5) 同一旅客的接客和落客由同一列車承擔(dān)：

第Ⅲ組約束：列車運(yùn)行約束

6) 區(qū)間運(yùn)行時(shí)分約束、停站時(shí)間約束。列車在區(qū)間運(yùn)行應(yīng)大于列車在區(qū)間運(yùn)行的最小運(yùn)行時(shí)間；將虛擬的接客服務(wù)弧和落客服務(wù)弧以及與其相對(duì)應(yīng)的物理節(jié)點(diǎn)與旅客虛擬節(jié)點(diǎn)相連的物理弧花費(fèi)的最小時(shí)間作為列車停站時(shí)間：

7) 追蹤間隔時(shí)間約束。

約束表示在同一車站的某一時(shí)刻以及與其相隔最小發(fā)車時(shí)間間隔(,)內(nèi)，最多有1列車出發(fā)；同一車站的某一時(shí)刻以及與其相隔最小到達(dá)時(shí)間間隔(,)內(nèi)，最多有1列車到達(dá)；且當(dāng)發(fā)車時(shí)間間隔不滿足臨界發(fā)車間隔時(shí)，列車通過(guò)等待弧等待，直到滿足條件，以保證列車在區(qū)間的行車 安全：

3 求解算法

Mahmoudi等[10]指出，模型中決策變量為多維變量時(shí)，此問(wèn)題在現(xiàn)實(shí)中為較復(fù)雜問(wèn)題，經(jīng)證實(shí)，拉格朗日松弛算法可用來(lái)尋求較好的解。

目標(biāo)函數(shù)為：

通過(guò)對(duì)式(13)進(jìn)行恒等變換，可得到：

(14)

松弛后的目標(biāo)函數(shù)式(12)可以分解為一個(gè)常數(shù)項(xiàng)與所有列車LR之和，如式(13)。式(13)中的LR由2部分組成，一部分為時(shí)間價(jià)格，表示列車占用時(shí)空資源的代價(jià)；另一部分為旅客上車約束、列車追蹤間隔時(shí)間約束的拉格朗日乘子之和，可以看作列車不滿足以上松弛約束時(shí)的懲罰值。由于約束(5)，(10)和(11)被松弛，剩余約束均作用于單個(gè)列車，消除了各旅客組均需要被列車接送導(dǎo)致的列車間的相互影響，打破了各列車在占用行車資源時(shí)的關(guān)聯(lián)關(guān)系，因此，該問(wèn)題在數(shù)學(xué)規(guī)劃中可以被分解為多個(gè)相互獨(dú)立的列車子問(wèn)題。該問(wèn)題的目標(biāo)函數(shù)是所有列車時(shí)空路徑的目標(biāo)函數(shù)LR之和，實(shí)質(zhì)上是列車時(shí)空路徑的最短路問(wèn)題。因此，通過(guò)構(gòu)建符合約束的時(shí)空狀態(tài)網(wǎng)絡(luò)，然后通過(guò)最短路算法即可求得該子問(wèn)題的最優(yōu)解。

上述松弛問(wèn)題的解為原問(wèn)題的下界，為了使其盡可能接近原問(wèn)題的最優(yōu)解需要求解以下拉格朗日松弛對(duì)偶問(wèn)題：

對(duì)于拉格朗日對(duì)偶問(wèn)題，需要找到合適的拉格朗日乘子的值，使松弛問(wèn)題的解盡可能接近原問(wèn)題的最優(yōu)解。采用迭代的方法，利用次梯度法迭代更新拉格朗日乘子，迭代公式如下：

式(16)表示約束(5)的拉格朗日乘子與當(dāng)前的拉格朗日乘子以及本次迭代求解得到的旅客組的列車訪問(wèn)次數(shù)有關(guān)；約束(11)的拉格朗日乘子與當(dāng)前的拉格朗日乘子以及本次迭代求解得到的列車對(duì)時(shí)空資源的占用次數(shù)有關(guān)。因此，在求解過(guò)程中根據(jù)當(dāng)前拉格朗日乘子、列車對(duì)旅客組的訪問(wèn)次數(shù)和對(duì)時(shí)空資源的占用次數(shù)更新對(duì)應(yīng)的拉格朗日乘子。

步驟2 求解拉格朗日松弛問(wèn)題。

步驟2.1遍歷每列待規(guī)劃列車，對(duì)每列待規(guī)劃列車執(zhí)行以下步驟：

步驟2.1.1根據(jù)約束條件構(gòu)建時(shí)空狀態(tài)網(wǎng)絡(luò)；

步驟2.1.2求解列車從起始站到終點(diǎn)站在時(shí)空狀態(tài)網(wǎng)絡(luò)中的最短路徑(參考文獻(xiàn)[3]的基于動(dòng)態(tài)規(guī)劃的時(shí)空狀態(tài)網(wǎng)絡(luò)最短路算法)，對(duì)列車訪問(wèn)的節(jié)點(diǎn)進(jìn)行標(biāo)記；

其中：LB為第次迭代松弛問(wèn)題的下界值

步驟2.3次梯度法更新拉格朗日乘子。

步驟2.3.1根據(jù)式(18)更新旅客組的列車訪問(wèn)次數(shù)

步驟2.3.2根據(jù)式(19)更新節(jié)點(diǎn)的列車訪問(wèn)次數(shù)

步驟2.4清空時(shí)空狀態(tài)網(wǎng)絡(luò)中的節(jié)點(diǎn)占用標(biāo)記；

步驟3 求解可行解。

步驟3.1根據(jù)式(21)按照各列車涉及的拉格朗日乘子和LRP將各列車從大到小排序；

步驟3.2遍歷排序后的每列待規(guī)劃列車，按照LRP從大到小的順序?qū)γ苛写?guī)劃列車執(zhí)行以下步驟：

步驟3.2.1根據(jù)約束條件及節(jié)點(diǎn)占用標(biāo)記構(gòu)造時(shí)空狀態(tài)網(wǎng)絡(luò)；

步驟3.2.2求解列車從起始站到終點(diǎn)站在時(shí)空狀態(tài)網(wǎng)絡(luò)中的最短路徑(參考文獻(xiàn)[3]的基于動(dòng)態(tài)規(guī)劃的時(shí)空狀態(tài)網(wǎng)絡(luò)最短路算法)，對(duì)列車訪問(wèn)的節(jié)點(diǎn)進(jìn)行標(biāo)記；

步驟3.4清空時(shí)空狀態(tài)網(wǎng)絡(luò)中的節(jié)點(diǎn)占用 標(biāo)記；

4 案例分析

本文以京滬高鐵北京南?曲阜東區(qū)段(選用8座車站：北京南、廊坊、天津南、滄州西、德州東、濟(jì)南西、泰安和曲阜東)為例進(jìn)行案例分析。根據(jù)實(shí)際的京滬高鐵運(yùn)行圖，算例截取區(qū)間最小運(yùn)行時(shí)分、最小停站時(shí)分(1 min)、列車最小發(fā)車間隔(3 min)、列車最小到達(dá)間隔(3 min)。列車定員為1 000人，有取舍的分別設(shè)立90個(gè)旅客組。設(shè)定時(shí)間鋪劃單位為1 min，時(shí)間長(zhǎng)度為180 min。

為了驗(yàn)證數(shù)學(xué)模型是否能有效的滿足旅客需求，算例分別設(shè)置2個(gè)數(shù)據(jù)集：數(shù)據(jù)集①是基于現(xiàn)實(shí)鐵路客票系統(tǒng)售票數(shù)據(jù)的旅客數(shù)據(jù)；數(shù)據(jù)集②是均衡旅客流數(shù)據(jù)。基于上述數(shù)據(jù)集，設(shè)置兩組對(duì)照試驗(yàn)：

對(duì)照試驗(yàn)1：對(duì)比數(shù)據(jù)集①和數(shù)據(jù)集②下得出的列車運(yùn)行圖對(duì)旅客需求的滿足程度及其隨旅客需求的變化。

對(duì)照試驗(yàn)2：對(duì)比按階段編制得出的列車運(yùn)行圖目標(biāo)函數(shù)值與模型求解得出的目標(biāo)函數(shù)值(采用數(shù)據(jù)集①)。

數(shù)據(jù)集①和②下得出的列車運(yùn)行圖如圖4~5所示；按階段編制列車運(yùn)行圖如圖6所示；不同情形目標(biāo)函數(shù)值的對(duì)比如圖7所示。

圖4 基于現(xiàn)實(shí)鐵路客票系統(tǒng)售票數(shù)據(jù)下編制的列車運(yùn)行圖

圖5 均衡客流數(shù)據(jù)下編制的列車運(yùn)行圖

由求解結(jié)果可做出如下分析：

1) 模型求解得到的列車時(shí)刻表與運(yùn)輸狀態(tài)相對(duì)應(yīng)，在鐵路花費(fèi)較小的目標(biāo)函數(shù)下，數(shù)據(jù)集①和②下的算例結(jié)果顯示旅客的需求得到滿足，模型的有效性得到證明。

2) 2個(gè)數(shù)據(jù)集下得到的列車運(yùn)行圖中，列車開(kāi)行的疏密程度、列車停站方案均與旅客需求相對(duì)應(yīng)：說(shuō)明本研究中的列車運(yùn)行圖編制模型能夠根據(jù)旅客需求數(shù)據(jù)靈活的設(shè)立列車停站模式和鋪畫列車時(shí)刻表。

3) 由對(duì)照實(shí)驗(yàn)2的結(jié)果(圖6)可以看出，一體化編制模型下的目標(biāo)函數(shù)與按階段編制的目標(biāo)函數(shù)相比，目標(biāo)函數(shù)值降低了9.5%，證明一體化編制模型在求解時(shí)刻表問(wèn)題上具有良好的適用性，也體現(xiàn)了一體化編制對(duì)比分階段編制所呈現(xiàn)出的優(yōu)勢(shì)。

圖6 按階段編制列車運(yùn)行圖

圖7 不同情況下的目標(biāo)函數(shù)值對(duì)比

5 結(jié)論

1) 考慮高速鐵路旅客出行的時(shí)空敏感性較高的特點(diǎn)，通過(guò)將旅客運(yùn)輸狀態(tài)引入時(shí)空網(wǎng)絡(luò)，構(gòu)建三維的時(shí)間?空間?狀態(tài)網(wǎng)絡(luò)，運(yùn)用網(wǎng)絡(luò)流理論，實(shí)現(xiàn)了旅客分配、停站方案與列車運(yùn)行圖的一體化優(yōu)化。通過(guò)設(shè)計(jì)拉格朗日松弛求解算法，將復(fù)雜的列車間強(qiáng)耦合問(wèn)題分解為單列車的最短路徑子問(wèn)題集合，降低了模型求解難度。

2) 對(duì)比非均衡客流與均衡客流數(shù)據(jù)下的模型結(jié)果，證實(shí)了模型不僅能夠滿足旅客需求，而且能夠在線路花費(fèi)較小的前提下，根據(jù)客流需求密度的變化，實(shí)現(xiàn)停站方案、列車運(yùn)行圖一體化優(yōu)化；對(duì)比分階段編制列車運(yùn)行圖模型與一體化編制列車運(yùn)行圖模型得到的目標(biāo)函數(shù)值，體現(xiàn)了一體化編制的適用性及優(yōu)勢(shì)。

3) 本文的研究仍然具有一定的可擴(kuò)展性。在旅客需求方面，需要進(jìn)一步考慮各種交通方式背景下的旅客自主選擇。在求解方面，對(duì)于大規(guī)模的問(wèn)題需要進(jìn)一步改進(jìn)算法來(lái)提高求解速度。

[1] 史峰, 黃錚誠(chéng), 周文梁, 等. 基于用戶平衡分析的旅客列車始發(fā)時(shí)間分布優(yōu)化[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2008, 5(6): 69?75. SHI Feng, HUANG Zhengcheng, ZHOU Wenliang, et al. Optimization of passenger train origin time distribution based on user equilibrium analysis[J]. Journal of Railway Science and Engineering. 2008, 5(6): 69?75.

[2] 黃鑒, 彭其淵. 基于分時(shí)客運(yùn)需求的客運(yùn)專線列車運(yùn)行圖優(yōu)化[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2012, 9(6): 66?71. HUANG Jian, PENG Qiyuan. Passenger dedicated line operation diagram optimization based on timeshare passenger demand[J]. Journal of Railway Science and Engineering, 2012, 9(6): 66?71.

[3] Robenek T, Maknoon Y, Azadeh S S, et al. Passenger centric train timetabling problem[J]. Transportation Research Part B: Methodological, 2016, 89: 107?126.

[4] 黃鑒. 基于旅客動(dòng)態(tài)調(diào)整的客運(yùn)專線網(wǎng)絡(luò)列車開(kāi)行方案優(yōu)化研究[D]. 成都: 西南交通大學(xué), 2013. HUANG Jian. Research on optimization of passenger dedicated line network train operation plan based on passenger flow dynamic adjustment[D]. Chengdu: Southwest Jiaotong University, 2013.

[5] NIU H, ZHOU X, GAO R, et al. Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints[J]. Transportation Research Part B: Methodological, 2015, 76: 117?135.

[6] Kaspi M, Raviv T. Service-oriented line planning and timetabling for passenger trains[J]. Transportation Science, 2013, 47(3): 295?311.

[7] 周文梁, 秦進(jìn), 鄧連波, 等. 城市軌道網(wǎng)絡(luò)列車運(yùn)行計(jì)劃實(shí)施效果綜合評(píng)價(jià)[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2014, 11(1): 118?125. ZHOU Wenliang, QIN Jin, DENG Lianbo, et al. Comprehensive evaluation of implementation effect of urban rail transit network train operation plan[J]. Journal of Railway Science and Engineering, 2014, 11(1): 118? 125.

[8] 周文梁. 客運(yùn)專線網(wǎng)絡(luò)列車開(kāi)行方案與運(yùn)行圖綜合優(yōu)化模型及算法[D]. 長(zhǎng)沙: 中南大學(xué), 2010. ZHOU Wenliang. Comprehensive optimization model and algorithm of train operation plan and operation diagram for passenger dedicated line[D]. Changsha: Central South University, 2010.

[9] 周文梁, 史峰, 陳彥, 等. 客運(yùn)專線網(wǎng)絡(luò)列車開(kāi)行方案與運(yùn)行圖綜合優(yōu)化方法[J]. 鐵道學(xué)報(bào), 2011, 33(2): 1?7. ZHOU Wenliang, SHI Feng, CHEN Yan, et al. A comprehensive optimization method for operation plan and operation diagram of passenger dedicated line network[J]. Journal of the China Railway Society, 2011, 33(2): 1?7.

[10] Mahmoudi M, ZHOU X. Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state-space-time network representations[J]. Transportation Research Part B: Methodological, 2016, 89: 19?42.

Integrated optimization of stopping pattern and train timetable for passenger demand

LIU Lu1, MENG Lingyun1, LI Xinyi1, LIU Gang2

(1. School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China; 2. Tianjin Nanhuan Railway Maintenance Co., Ltd, Tianjin 300381, China)

Considering the space-time sensitivity of high-speed railway passengers, we introduced a passenger carrying state to expand the two-dimensional transport space-time network into a three-dimensional network which is called space-time-state network. An integrated optimization model of stopping pattern and train timetable for passenger demand was proposed to realize the integration of passenger distribution, stopping pattern selection and train timetabling. The Lagrange relaxation algorithm was designed to decompose the complex train coupling problem into the shortest path sub-problem of a single train, so as to reduce the difficulty of solving the model. Computational experiments were performed on a realistic case study based on a heavily used part of the Beijing-Shanghai high-speed railway. The results provide evidence that the integrated optimization model not only get a low operational cost, but also realize the integration of passenger distribution, stopping pattern selection and train timetabling.

railway transportation; train timetabling; Lagrangian relaxation algorithm; integrated optimization; space-time-state network; passenger demand

10.19713/j.cnki.43?1423/u.2019.02.031

U292.41

A

1672 ? 7029(2019)02 ? 0518 ? 10

2018?03?16

國(guó)家自然科學(xué)基金面上資助項(xiàng)目(71571012)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2017JBM029)；大型樞紐機(jī)場(chǎng)旅客捷運(yùn)系統(tǒng)關(guān)鍵技術(shù)研究與應(yīng)用(民航科技項(xiàng)目任務(wù)-編號(hào)：201501)

孟令云(1983?)，男，河北遷安人，副教授，博士，從事列車運(yùn)行圖編制等研究；E?mail：lymeng@bjtu.edu.cn

(編輯 陽(yáng)麗霞)