李天琦， 聶 磊， 譚宇燕

(北京交通大學(xué) 交通運(yùn)輸學(xué)院， 北京 100044)

近年來(lái)，我國(guó)高鐵路網(wǎng)規(guī)模不斷擴(kuò)大、旅客服務(wù)質(zhì)量需求逐漸提高，以高服務(wù)頻率、規(guī)律停站、便捷換乘、旅客方便記憶為特點(diǎn)的周期性列車運(yùn)行圖得到了我國(guó)鐵路運(yùn)營(yíng)管理部門的關(guān)注。由于列車開行方案呈周期性重復(fù)，高速鐵路周期性列車運(yùn)行圖與非周期性列車運(yùn)行圖差異性顯著：一是周期性列車運(yùn)行圖停站組合種類較少，在考慮保證列車旅行速度的條件下，需要設(shè)計(jì)換乘接續(xù)來(lái)滿足旅客多樣化的出行服務(wù)需求；二是受限于周期性列車運(yùn)行圖鋪畫條件，長(zhǎng)距離列車的開行數(shù)量受限制，故在列車起訖點(diǎn)選擇上，周期性列車運(yùn)行圖的可選方案明顯少于非周期性列車運(yùn)行圖，將產(chǎn)生較大數(shù)量的換乘服務(wù)需求。因此，在列車周期性開行條件下，為保障在相對(duì)少量的列車停站組合和起訖點(diǎn)種類條件下滿足多樣化的旅客出行需求，充分發(fā)揮周期性列車運(yùn)行圖便捷換乘的優(yōu)勢(shì)，需要在列車運(yùn)行圖編制過(guò)程中優(yōu)化列車接續(xù)關(guān)系。

在高鐵周期性列車運(yùn)行圖編制方面，既有研究一般建模為周期事件規(guī)劃模型(Periodic Event Scheduling Problem，PESP)[1]和圈周期模型(Cycle Periodicity Formulation，CPF)[2]。國(guó)外學(xué)者針對(duì)周期性列車運(yùn)行圖模型的諸多特性和求解算法開展了豐富的研究：模型結(jié)構(gòu)方面，文獻(xiàn)[2-5]的研究?jī)?nèi)容涉及動(dòng)車組接續(xù)的靈活性[2]、區(qū)間運(yùn)行時(shí)間的可變性[2-3]、運(yùn)行圖魯棒性[4]和結(jié)構(gòu)的對(duì)稱性[5]等多個(gè)方面，提高了模型的實(shí)用價(jià)值；求解策略方面，除使用CPLEX等整數(shù)規(guī)劃求解器直接求解外，文獻(xiàn)[5-6]探討的圈基搜索輔助求解技術(shù)已成為該問(wèn)題的主要求解方式，文獻(xiàn)[7]提出的模單純型算法進(jìn)一步提高了模型求解效率。國(guó)內(nèi)學(xué)者在借鑒國(guó)外研究經(jīng)驗(yàn)的基礎(chǔ)上，多結(jié)合我國(guó)單條高鐵線路開展研究：文獻(xiàn)[8]簡(jiǎn)化處理了 CPF模型圈基約束，高效編制了京津城際鐵路周期性列車運(yùn)行圖;文獻(xiàn)[9]與文獻(xiàn)[10]分別考慮了定序條件和可變區(qū)間運(yùn)行時(shí)間編制了京滬高速鐵路周期性列車運(yùn)行圖，文獻(xiàn)[11]探討了周期性列車運(yùn)行圖編制系統(tǒng)開發(fā)的關(guān)鍵技術(shù)。以上成果為進(jìn)一步研究周期性列車運(yùn)行圖優(yōu)化問(wèn)題打下了堅(jiān)實(shí)的基礎(chǔ)。

高鐵周期性列車運(yùn)行圖編制過(guò)程中對(duì)換乘接續(xù)問(wèn)題的考慮方面，既有研究多基于固定接續(xù)關(guān)系和不固定接續(xù)關(guān)系兩種思路?；诠潭ń永m(xù)關(guān)系的研究一般將一套確定、可靠的列車接續(xù)方案作為列車運(yùn)行圖編制模型的輸入，并以接續(xù)時(shí)間范圍約束的形式直接嵌入模型中。國(guó)外鐵路在多年周期性列車運(yùn)行圖運(yùn)用實(shí)踐中已形成了較為固定的列車接續(xù)關(guān)系，該思路在國(guó)外研究中得到了廣泛采納[2-5]。而不固定接續(xù)關(guān)系條件下，在所有可能的接續(xù)列車及對(duì)應(yīng)接續(xù)車站的基礎(chǔ)上確定備選列車接續(xù)集合，經(jīng)運(yùn)行圖驗(yàn)證最終確定接續(xù)關(guān)系。由于周期性列車運(yùn)行圖在我國(guó)尚未得到全面推廣，列車接續(xù)關(guān)系無(wú)法在列車運(yùn)行圖編制前確定，因此基于不固定接續(xù)的運(yùn)行圖編制思路更適合我國(guó)高鐵運(yùn)營(yíng)實(shí)際。文獻(xiàn)[12]提出了以換乘接續(xù)數(shù)量最少和接續(xù)服務(wù)覆蓋換乘客流量最多為優(yōu)化目標(biāo)的備選列車接續(xù)優(yōu)化模型。文獻(xiàn)[13-14]考慮了無(wú)直達(dá)服務(wù)的大節(jié)點(diǎn)客流OD換乘需求，提出了基于備選列車接續(xù)的周期性列車運(yùn)行圖編制體系。文獻(xiàn)[15]解決了周期性列車運(yùn)行圖編制過(guò)程中，同類列車間接續(xù)關(guān)系靈活選擇的問(wèn)題。基于固定和不固定接續(xù)關(guān)系兩種思路的周期性列車運(yùn)行圖編制流程見圖1。

圖1 基于固定和不固定接續(xù)關(guān)系兩種思路的周期性列車運(yùn)行圖編制流程

針對(duì)高鐵周期性列車運(yùn)行圖編制與換乘接續(xù)綜合優(yōu)化問(wèn)題，本文基于文獻(xiàn)[13-14]對(duì)以下3個(gè)方面做出改進(jìn)和完善。

(1) 僅考慮大節(jié)點(diǎn)間因無(wú)列車直達(dá)而產(chǎn)生的客流換乘服務(wù)需求，對(duì)于因列車直達(dá)服務(wù)不足而產(chǎn)生的旅客換乘需求有待進(jìn)一步考慮。本文使用換乘服務(wù)頻率量化路網(wǎng)各客流OD間的換乘服務(wù)需求，引入客流OD換乘服務(wù)頻率約束和最小化換乘服務(wù)頻率欠缺值的目標(biāo)函數(shù)，使模型不僅考慮了部分OD因無(wú)列車直達(dá)而產(chǎn)生的旅客換乘需求，同時(shí)兼顧為列車直達(dá)服務(wù)頻率不足的客流OD增加相應(yīng)需求的快速換乘服務(wù)。

(2) 在備選列車接續(xù)中事先確定了接續(xù)列車和對(duì)應(yīng)接續(xù)車站，可能造成最優(yōu)解不在備選集中。本文拓展了不固定列車接續(xù)關(guān)系的研究思路，將接續(xù)列車及對(duì)應(yīng)接續(xù)車站和接續(xù)時(shí)間3個(gè)要素全部在列車運(yùn)行圖優(yōu)化過(guò)程中動(dòng)態(tài)確定，使接續(xù)關(guān)系的選擇更加靈活。

(3) 在選擇列車接續(xù)關(guān)系的同時(shí)缺乏接續(xù)時(shí)間優(yōu)化，導(dǎo)致不必要的接續(xù)時(shí)間冗余。通過(guò)引入最小化換乘接續(xù)時(shí)間的優(yōu)化目標(biāo)和換乘接續(xù)選取與接續(xù)時(shí)間耦合關(guān)系約束，在規(guī)劃接續(xù)關(guān)系的基礎(chǔ)上進(jìn)一步優(yōu)化換乘接續(xù)時(shí)間。

1 問(wèn)題描述

一個(gè)換乘接續(xù)關(guān)系包含接續(xù)列車、接續(xù)車站以及接續(xù)時(shí)間3個(gè)基本要素。接續(xù)列車和接續(xù)車站與列車開行方案密切相關(guān)，并且共同決定了該換乘接續(xù)可以服務(wù)的客流OD集合。接續(xù)時(shí)間由列車運(yùn)行圖中前序列車到達(dá)與后續(xù)列車出發(fā)時(shí)間間隔確定，其上限不應(yīng)超出旅客可容忍的換乘等待時(shí)間，其下限應(yīng)滿足旅客換乘必要走行時(shí)間，單一換乘接續(xù)關(guān)系見圖2。

圖2 單一換乘接續(xù)關(guān)系

列車開行方案中符合一定條件的所有換乘接續(xù)關(guān)系構(gòu)成了備選換乘接續(xù)關(guān)系集合，是本文模型的輸入條件，其構(gòu)建包含換乘接續(xù)關(guān)系構(gòu)造與篩選兩個(gè)基本過(guò)程。構(gòu)造過(guò)程在遍歷全部列車組合方式的前提下，構(gòu)建所有可行的換乘接續(xù)關(guān)系，一般考慮以下基本原則：(1)前后兩列車存在公共接續(xù)車站；(2)旅客可以通過(guò)接續(xù)車站在合理接續(xù)時(shí)間內(nèi)完成換乘；(3)接續(xù)客流OD集合非空；(4)接續(xù)關(guān)系覆蓋的換乘客流OD集合對(duì)應(yīng)的客流路徑繞行里程在可接受范圍內(nèi)且無(wú)重復(fù)車站節(jié)點(diǎn)。篩選過(guò)程指根據(jù)決策者需要，在已構(gòu)建的換乘接續(xù)關(guān)系中，篩選出有利于鐵路企業(yè)運(yùn)營(yíng)組織和方便旅客出行的換乘接續(xù)關(guān)系，一般建議考慮以下4點(diǎn)原則：(1)優(yōu)先選擇前后列車特性與覆蓋換乘客流特性較匹配的換乘接續(xù)；(2)優(yōu)先選擇接續(xù)車站旅客換乘能力較大、服務(wù)水平較高、列車接續(xù)作業(yè)組織條件較好的換乘接續(xù)；(3)優(yōu)先選擇覆蓋換乘客流OD與潛在換乘客流量較大的換乘接續(xù)；(4)對(duì)運(yùn)營(yíng)實(shí)際中效果不佳的換乘接續(xù)予以刪除。

周期性列車運(yùn)行圖換乘接續(xù)優(yōu)化以向旅客提供便捷、快速的換乘服務(wù)為目標(biāo)。一方面，換乘接續(xù)服務(wù)應(yīng)盡可能滿足各客流OD間旅客的換乘出行需求，為旅客提供足夠數(shù)量的可選換乘方案。此方面可用換乘服務(wù)頻率衡量，即在規(guī)定換乘時(shí)間范圍內(nèi)通過(guò)一次換乘到達(dá)目的地可供旅客選擇的列車組合數(shù)量。另一方面，應(yīng)當(dāng)盡量縮短旅客在換乘站的中轉(zhuǎn)換乘時(shí)間，優(yōu)化旅客旅行時(shí)間。此方面可用換乘接續(xù)時(shí)間來(lái)衡量，即前序列車到達(dá)與后續(xù)列車出發(fā)的間隔時(shí)間。

周期性列車運(yùn)行圖編制過(guò)程中換乘接續(xù)人工優(yōu)化案例見圖3。

圖3 周期性列車運(yùn)行圖換乘接續(xù)優(yōu)化問(wèn)題案例

已知周期長(zhǎng)度60 min，換乘接續(xù)時(shí)間限制為15～20 min，列車3、4在車站C的出發(fā)時(shí)間分別為第13、0分，列車5的在車站D的出發(fā)時(shí)間為第36分，各列車在經(jīng)由車站均辦理旅客乘降，客流OD：A-E、B-E、A-F存在換乘服務(wù)需求，頻率為1次。為滿足A-E、B-E換乘服務(wù)需求，接續(xù)1和接續(xù)2是應(yīng)當(dāng)納入選定接續(xù)，取最短接續(xù)時(shí)間15 min。為方便對(duì)比，按各列車區(qū)間運(yùn)行和停站時(shí)間均取最小的條件推算列車1、2在車站C、D的到發(fā)時(shí)間，結(jié)果見圖3中標(biāo)識(shí)。在此條件下，備選列車接續(xù)3、4、5可用于滿足換乘服務(wù)需求A-F：對(duì)于換乘接續(xù)3，可取最短接續(xù)時(shí)間15 min；對(duì)于換乘接續(xù)4，接續(xù)時(shí)間為16 min；對(duì)于換乘接續(xù)5，接續(xù)時(shí)間為20 min。除換乘接續(xù)3外，若需進(jìn)一步優(yōu)化列車接續(xù)4、5的接續(xù)時(shí)間，則需延長(zhǎng)接續(xù)1、2的接續(xù)時(shí)間或額外附接續(xù)列車區(qū)間運(yùn)行或停站時(shí)間。基于此，若車站接續(xù)能力和列車接續(xù)數(shù)量未達(dá)瓶頸不受限制，顯然接續(xù)3為最優(yōu)方案；若假定車站C的單周期內(nèi)列車接續(xù)數(shù)量上限為2次，接續(xù)4為較優(yōu)方案；若假定列車2的接續(xù)次數(shù)限制為1次時(shí)，則僅可選擇接續(xù)5。

由此可見，周期性列車運(yùn)行圖換乘接續(xù)優(yōu)化問(wèn)題是一個(gè)復(fù)雜的系統(tǒng)優(yōu)化問(wèn)題，人工優(yōu)化難以應(yīng)用于大規(guī)模案例。本文綜合考慮周期性列車運(yùn)行圖編制約束和換乘接續(xù)相關(guān)約束，以盡量滿足換乘服務(wù)頻率需求、最小化列車總旅行時(shí)間和總換乘接續(xù)時(shí)間為優(yōu)化目標(biāo)，建立多目標(biāo)混合整數(shù)規(guī)劃模型，完成周期性列車運(yùn)行圖和接續(xù)方案的一體化編制。

2 優(yōu)化模型

2.1 相關(guān)符號(hào)定義

路網(wǎng)及周期性列車開行方案層面基礎(chǔ)要素定義如下。S：路網(wǎng)全部車站集合；L：?jiǎn)沃芷趦?nèi)全部列車集合；Sl：列車l停站車站集合；Pl：列車l經(jīng)由車站集合；Stransfer：路網(wǎng)中備選換乘接續(xù)車站集合；F：路網(wǎng)換乘客流OD集合；Z：備選列車接續(xù)集合。

對(duì)于周期性列車運(yùn)行圖，采用事件—活動(dòng)圖(Event-Activity Graph，簡(jiǎn)稱EA圖[7])描述其要素，三列車組成的EA圖，見圖4。

圖4 事件—活動(dòng)圖

定義事件—活動(dòng)圖G=(E,A)。點(diǎn)集合E中的元素e∈E稱為事件，用以表達(dá)列車到達(dá)和出發(fā)時(shí)刻，E由列車出發(fā)點(diǎn)(事件)集合Edep和列車到達(dá)點(diǎn)(事件)集合Earr兩個(gè)子集構(gòu)成。

弧集合A中的元素a∈A稱為活動(dòng)，表示列車事件間的時(shí)間間隔約束關(guān)系，可以用一對(duì)列車事件表示，以換乘接續(xù)弧為例表示為

|i,j∈L,s∈Si∩Sj∩Stransferi,j,s∈Z}

本文考慮以下4類弧集合。Adriving：運(yùn)行弧(活動(dòng))集合，表示列車在區(qū)間運(yùn)行過(guò)程中從前序車站出發(fā)與到達(dá)后續(xù)車站的時(shí)間間隔約束；Astop：停站弧(活動(dòng))集合，表示列車在站停站過(guò)程中從列車到達(dá)車站與自該站出發(fā)的時(shí)間間隔約束，當(dāng)列車不停站通過(guò)時(shí)，弧長(zhǎng)取值為0；Asafety：安全弧(活動(dòng))集合，表示同方向經(jīng)由同一區(qū)間的兩列車到達(dá)時(shí)間間隔與出發(fā)時(shí)間間隔約束；Aconnection：接續(xù)弧(活動(dòng))集合，表示接續(xù)前序列車到達(dá)與后續(xù)列車出發(fā)的時(shí)間間隔約束。

2.2 約束條件

(1) 弧約束

為保證列車安全高效運(yùn)行，列車區(qū)間運(yùn)行時(shí)間、停站時(shí)間、安全間隔時(shí)間應(yīng)限制在規(guī)定時(shí)間范圍內(nèi)；為保證旅客換乘的效率與安全，對(duì)于一個(gè)換乘接續(xù)，在換乘車站的前序列車到達(dá)時(shí)間和后續(xù)列車出發(fā)時(shí)間間隔應(yīng)保證在一定范圍內(nèi)。

la≤xa≤ua

?a∈Asafety∪Adriving∪Astop∪Aconnection

( 1 )

式中：la為弧a所代表的時(shí)間間隔取值下限；ua為弧a所代表的時(shí)間間隔取值上限。

(2) 圈基約束

圈基約束是保證列車運(yùn)行圖滿足周期性質(zhì)的約束。根據(jù)文獻(xiàn)[2]，周期性列車運(yùn)行圖的EA圖中所有圈應(yīng)當(dāng)滿足圈周期性質(zhì)，即該圈包含的順向弧取值之和與逆向弧取值之和的差值應(yīng)當(dāng)是周期的整數(shù)倍，同時(shí)證明整數(shù)變量qc的取值范圍應(yīng)滿足式( 2 )。文獻(xiàn)[5]證明圖G(E，A)中存在元素個(gè)數(shù)為(|A|-|E|+1)的圈集合B，當(dāng)該集合中的圈滿足圈周期性質(zhì)時(shí)，則圖G中的全部圈均滿足圈周期性質(zhì)，將圈集合B稱為整數(shù)圈基。文獻(xiàn)[13]將按圈基B內(nèi)的圈是否是包含接續(xù)弧將其劃分為普通圈基Btrivial和接續(xù)圈基Bconnection，普通圈基內(nèi)的圈由若干運(yùn)行弧、停站弧和安全弧組成，接續(xù)圈基內(nèi)的圈由唯一接續(xù)弧和若干運(yùn)行弧、停站弧和安全弧組成。

按照上述原理，本文所建EA圖中普通圈基和被選定的接續(xù)弧對(duì)應(yīng)的接續(xù)圈基應(yīng)當(dāng)滿足周期性質(zhì)，即：對(duì)于普通圈基中的圈應(yīng)滿足式( 3 )、接續(xù)圈基中的圈應(yīng)滿足式( 4 )、式( 5 )。式( 4 )、式( 5 )引入了松弛變量δc，當(dāng)接續(xù)弧a對(duì)應(yīng)的換乘接續(xù)關(guān)系被選擇時(shí)ta=1，對(duì)應(yīng)松弛變量δc=0，對(duì)應(yīng)接續(xù)圈滿足圈周期性質(zhì)約束；當(dāng)接續(xù)弧a對(duì)應(yīng)的換乘接續(xù)關(guān)系未被選擇時(shí)ta=0，對(duì)應(yīng)松弛變量δc可任取，松弛對(duì)應(yīng)圈約束。

c∈Btrivial∪Bconnection

( 2 )

( 3 )

( 4 )

-M(1-ta)≤δc≤M(1-ta)

c∈Bconnectiona∈Aconnection

( 5 )

式中：c+為圈c中的順向弧的集合；c-為圈c中的逆向弧的集合；Btrivial為普通圈基；Bconnection為接續(xù)圈基。

(3) 沖突消解約束

當(dāng)兩列追蹤列車的區(qū)間運(yùn)行時(shí)分之差大于到達(dá)、出發(fā)安全間隔時(shí)間之和時(shí)，將造成運(yùn)行線在區(qū)間交會(huì)，故需引入沖突消解約束。將經(jīng)由同一區(qū)間的同向列車對(duì)應(yīng)的一對(duì)運(yùn)行弧和一對(duì)安全弧組成的圈稱為沖突消解圈，見圖5，當(dāng)其順向弧取值之和與逆向弧取值之和的差值為0時(shí)，列車運(yùn)行線不會(huì)在區(qū)間交會(huì)[3]。

圖5 沖突消解圈

( 6 )

式中：Cnon-collision為EA圖中全部沖突消解圈的集合。

(4) 客流OD換乘服務(wù)頻率約束

限于周期性列車運(yùn)行圖有限的停站組合和起訖點(diǎn)種類，列車直達(dá)服務(wù)難以滿足多樣化的旅客出行需求，因此應(yīng)考慮為列車直達(dá)頻率不足的客流OD設(shè)計(jì)相應(yīng)頻率的快速換乘服務(wù)，以提高旅客出行的效率與便捷性。但嚴(yán)格限制換乘服務(wù)頻率可能會(huì)導(dǎo)致問(wèn)題無(wú)解，因此引入非負(fù)松弛變量yod，當(dāng)換乘服務(wù)頻率達(dá)到設(shè)計(jì)值時(shí)，松弛變量yod取值為0；否則松弛變量取值為正整數(shù)，該約束被松弛。

( 7 )

現(xiàn)階段我國(guó)高速鐵路主要實(shí)行非周期化運(yùn)營(yíng)，客流輸送方式以直達(dá)為主。出于實(shí)用性考慮，同時(shí)保證我國(guó)高鐵改行周期性運(yùn)行圖后各OD列車服務(wù)頻率的相對(duì)穩(wěn)定，本文參考了我國(guó)現(xiàn)行高速鐵路列車運(yùn)行圖，將各OD直達(dá)與換乘服務(wù)頻率需求總量按式( 8 )計(jì)算、換乘服務(wù)頻率需求設(shè)計(jì)值按式( 9 )計(jì)算，即

( 8 )

( 9 )

(5) 列車接續(xù)數(shù)量約束

為避免單列車接續(xù)數(shù)量過(guò)大造成嚴(yán)重的晚點(diǎn)傳播，對(duì)列車運(yùn)行調(diào)整工作造成困難，故應(yīng)限制單列車接續(xù)數(shù)量。

(10)

(6) 接續(xù)車站約束

為保證換乘接續(xù)車站可以靈活選擇，該模型將接續(xù)列車相同、接續(xù)車站不同的若干換乘接續(xù)歸為一組換乘接續(xù)。為保證規(guī)劃接續(xù)車站選擇的唯一性，每組接續(xù)關(guān)系應(yīng)當(dāng)滿足式(11)；同時(shí)受車站換乘設(shè)備和線路布局的影響，單周期內(nèi)車站內(nèi)的接續(xù)能力有限，故應(yīng)限制周期內(nèi)車站接續(xù)數(shù)量，避免車站接續(xù)能力不足、防止換乘接續(xù)過(guò)多集中于單一換乘車站，即式(12)。

(11)

(12)

(7) 接續(xù)對(duì)稱性約束

由于我國(guó)高鐵列車基本成對(duì)開行，同時(shí)換乘服務(wù)應(yīng)滿足旅客出行的往返性，故列車接續(xù)關(guān)系應(yīng)具有對(duì)稱性[14]。

ta=ta′a,a′∈Aconnection

(13)

式中：接續(xù)弧a′是接續(xù)弧a的對(duì)向接續(xù)弧。

(8) 接續(xù)選取和接續(xù)時(shí)間耦合約束

(14)

式中:M為較大常數(shù)。

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

本文將列車總旅行時(shí)間最小z1、總換乘接續(xù)時(shí)間最小z2以及各OD的實(shí)際換乘服務(wù)頻率相對(duì)于換乘服務(wù)頻率需求總欠缺值最小z3為優(yōu)化目標(biāo)。最小化列車總旅行時(shí)間不僅可提高動(dòng)車組運(yùn)用效率，還可節(jié)省旅客旅行時(shí)間；最小化總換乘接續(xù)時(shí)間使旅客換乘時(shí)間在合理?yè)Q乘接續(xù)時(shí)間范圍內(nèi)盡量少，節(jié)省了旅客換乘等待時(shí)間；最小化換乘服務(wù)頻率欠缺值，使換乘接續(xù)服務(wù)盡量滿足各客流OD換乘服務(wù)頻率需求。

(15)

(16)

(17)

采用線性加權(quán)法將多目標(biāo)規(guī)劃轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題。

minZ=α1z1+α2z2+Mz3

(18)

式中:α1，α2，M分別為三項(xiàng)目標(biāo)函數(shù)的權(quán)重系數(shù)，為優(yōu)先保證換乘接續(xù)服務(wù)盡量滿足各客流OD換乘服務(wù)頻率需求，取M?α1,α2。

2.4 模型求解

以CPF模型為基礎(chǔ)，經(jīng)線性加權(quán)法轉(zhuǎn)化為單目標(biāo)混合整數(shù)規(guī)劃模型，通過(guò)Cplex、Gurobi等整數(shù)規(guī)劃求解器可以快速求解。此問(wèn)題的一般求解流程是：在以備選列車接續(xù)和周期性列車開行方案構(gòu)建的EA圖的基礎(chǔ)上，搜索整數(shù)圈基作為模型輸入的一部分，采用整數(shù)規(guī)劃求解器求解，通過(guò)生成樹算法推算各列車事件發(fā)生時(shí)刻。問(wèn)題求解的關(guān)鍵在于分類整數(shù)圈基的構(gòu)建，優(yōu)質(zhì)圈基將極大提高模型求解效率。本文參考文獻(xiàn)[14]采用CFCB算法搜索分類整數(shù)圈基。

3 案例驗(yàn)證

本文以京滬高鐵及其部分銜接線路周期性列車運(yùn)行圖編制作為研究案例，以優(yōu)化生成的周期性列車開行方案為基礎(chǔ)，見圖6。周期為60 min。各線路區(qū)間最高運(yùn)行速度為：京滬350 km/h，鄭徐、合蚌、津秦、寧杭高鐵300 km/h，其余線路取200 km/h。最低運(yùn)行速度取最高運(yùn)行速度的0.9倍。300、350 km/h線路起車附加時(shí)分2 min、停車附加時(shí)分3 min；200 km/h線路起停車附加時(shí)分均取2 min。車站最小到達(dá)、出發(fā)時(shí)間間隔：北京南站取5 min、上海虹橋取4 min、其余車站取3 min。列車停站時(shí)間取1～4 min。備選接續(xù)車站有：天津西、天津南、濟(jì)南西、徐州東、蚌埠南和南京南。各車站周期內(nèi)最大接續(xù)數(shù)量為10次，單列車最大接續(xù)數(shù)量為2次，換乘接續(xù)時(shí)間為15～20 min。服務(wù)頻率高峰系數(shù)取為1.05。目標(biāo)函數(shù)各項(xiàng)系數(shù)出于不同考慮有多種組合方式，本案例取值為α1=1,α2=1,M=200。

使用Visual Studio 2015結(jié)合C#語(yǔ)言編程調(diào)用CPELX 12.7.1，硬件環(huán)境為Intel Xeon E5-2620 2.4 GHZ 32 G內(nèi)存。經(jīng)過(guò)1 572.97 s求解時(shí)間，得到路網(wǎng)周期性列車運(yùn)行圖及換乘接續(xù)方案。京滬高速鐵路下行方向周期性列車運(yùn)行圖見圖7。

最終選定的列車換乘接續(xù)關(guān)系見表1，接續(xù)方案見圖8。

圖6 京滬高速鐵路及部分銜接線路周期性列車開行方案

序號(hào)接續(xù)站前序列車后續(xù)列車接續(xù)時(shí)間/min序號(hào)接續(xù)站前序列車后續(xù)列車接續(xù)時(shí)間/min1濟(jì)南西G7:北京南—上海虹橋G35:濟(jì)南西—青島北192濟(jì)南西G36:青島北—濟(jì)南西G8:上海虹橋—北京南163濟(jì)南西G6:上海虹橋—北京南G16:濟(jì)南西—沈陽(yáng)北204濟(jì)南西G15:沈陽(yáng)北—濟(jì)南西G5:北京南—上海虹橋175濟(jì)南西G15:沈陽(yáng)北—濟(jì)南西G37:濟(jì)南西—青島北206濟(jì)南西G38:青島北—濟(jì)南西G16:濟(jì)南西—沈陽(yáng)北157濟(jì)南西G20:鄭州東—濟(jì)南西G35:濟(jì)南西—青島北158濟(jì)南西G36:青島北—濟(jì)南西G19:濟(jì)南西—鄭州東159南京南G1:北京南—上海虹橋G25:南京南—上海虹橋1510南京南G26:上海虹橋—南京南G2:上海虹橋—北京南1511南京南G1:北京南—上海虹橋G49:南京南—杭州東1512南京南G50:杭州東—南京南G2:上海虹橋—北京南1513南京南G5:北京南—上海虹橋G47:南京南—杭州東1514南京南G48:杭州東—南京南G6:上海虹橋—北京南1515南京南G9:北京南—杭州東G27:南京南—上海虹橋1516南京南G28:上海虹橋—南京南G10:杭州東—北京南1517南京南G17:天津西—上海虹橋G45:南京南—杭州東1518南京南G46:杭州東—南京南G18:上海虹橋—天津西1519天津西G18:上海虹橋—天津西G31:天津西—沈陽(yáng)北1520天津西G32:沈陽(yáng)北—天津西G17:天津西—上海虹橋1521徐州東G10:杭州東—北京南G41:徐州東—鄭州東1522徐州東G42:鄭州東—徐州東G9:北京南—杭州東1523徐州東G21:青島北—徐州東G39:徐州東—鄭州東1524徐州東G40:鄭州東—徐州東G22:徐州東—青島北1525徐州東G4:上海虹橋—北京南G22:徐州東—青島北1626徐州東G21:青島北—徐州東G3:北京南—上海虹橋1727徐州東G4:上海虹橋—北京南G43:徐州東—鄭州東2028徐州東G44:鄭州東—徐州東G3:北京南—上海虹橋2029徐州東G8:上海虹橋—北京南G39:徐州東—鄭州東1930徐州東G40:鄭州東—徐州東G7:北京南—上海虹橋18

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

客流OD列車服務(wù)頻率方面，周期性列車開行方案設(shè)計(jì)服務(wù)的856個(gè)京滬高鐵本跨線客流OD中，596個(gè)客流OD滿足服務(wù)頻率需求，260個(gè)客流OD服務(wù)頻率未達(dá)到設(shè)計(jì)需求值，需要補(bǔ)充換乘接續(xù)服務(wù)。換乘接續(xù)優(yōu)化后，原滿足服務(wù)頻率需求的596個(gè)客流OD中，有372個(gè)客流OD服務(wù)頻率得到提高，旅客除可通過(guò)直達(dá)出行外，還可通過(guò)設(shè)計(jì)的快速換乘接續(xù)完成出行；未滿足服務(wù)頻率需求的260個(gè)OD中，有198個(gè)客流OD通過(guò)增加快速換乘接續(xù)服務(wù)滿足服務(wù)頻率需求，該部分旅客客流通過(guò)規(guī)劃的15～20 min的快速換乘服務(wù)完成出行；最終僅剩62個(gè)客流OD無(wú)法通過(guò)規(guī)劃換乘接續(xù)或列車直達(dá)完成出行。優(yōu)化前后客流OD服務(wù)頻率變化情況見表2。

換乘接續(xù)時(shí)間方面，選定的30個(gè)換乘接續(xù)中，平均換乘接續(xù)時(shí)間16.2 min，較未考慮換乘接續(xù)時(shí)間優(yōu)化的情形下，平均減少冗余接續(xù)時(shí)間3.8 min。

圖8 列車接續(xù)方案圖

優(yōu)化前優(yōu)化后服務(wù)頻率滿足需求的客流OD數(shù)量596服務(wù)頻率原已滿足需求、優(yōu)化后提高的客流OD數(shù)量及占比服務(wù)頻率原已滿足需求、優(yōu)化后不變的客流OD數(shù)量及占比372(62%)224(38%)服務(wù)頻率未滿足需求的客流OD數(shù)量260服務(wù)頻率原不滿足、優(yōu)化后滿足需求的客流OD數(shù)量及占比仍未滿足服務(wù)頻率需求的客流OD數(shù)量及占比198(76%)62(22%)

4 結(jié)束語(yǔ)

本文建立了基于換乘接續(xù)優(yōu)化的高鐵周期性列車運(yùn)行圖多目標(biāo)混合整數(shù)規(guī)劃模型，從換乘頻率、動(dòng)態(tài)接續(xù)、換乘時(shí)間3個(gè)方面優(yōu)化設(shè)計(jì)列車換乘接續(xù)關(guān)系，較為全面考慮了周期性列車運(yùn)行圖編制和換乘接續(xù)關(guān)系設(shè)計(jì)相關(guān)約束和優(yōu)化目標(biāo)，解決了周期性列車運(yùn)行圖與列車換乘接續(xù)方案的一體化編制問(wèn)題，為周期性列車運(yùn)行圖接續(xù)優(yōu)化提供了系統(tǒng)的方法。案例涵蓋京滬高鐵及部分銜接線路，服務(wù)頻率需求參數(shù)參考了我國(guó)現(xiàn)行列車運(yùn)行圖運(yùn)營(yíng)情況，提高了案例的實(shí)用性。求解結(jié)果表明：原直達(dá)服務(wù)頻率不足260個(gè)客流OD中，76%的客流OD可以在15～20 min的換乘時(shí)間范圍內(nèi)通過(guò)規(guī)劃換乘接續(xù)滿足出行需求，驗(yàn)證了模型的有效性。此外，針對(duì)車站接續(xù)能力、列車合理接續(xù)數(shù)量以及接續(xù)魯棒性等換乘接續(xù)設(shè)計(jì)的精細(xì)化問(wèn)題有待進(jìn)一步研究。