城軌線路運營時段前車底空駛出場路徑優(yōu)化

鐘慶偉， 趙 軍， 文 超， 彭其淵(西南交通大學 交通運輸與物流學院， 四川 成都 610031)

車底運用計劃是城市軌道交通線路的基礎行車組織計劃之一，主要為提前繪制的運行圖中的列車指派車底。城市軌道交通線路通常設置多個車場(包括車輛段和停車場)，并運行多條列車交路，列車的始發(fā)和終到站不一定為車場所在站，使得車底在全日存在出入場運行，包括運營時段前集中出場、運營時段內(nèi)分散出入場和運營時段后集中入場。全日車底出入場運行不僅對運營時段內(nèi)列車運行造成干擾，還在非運營時段特別是運營時段前產(chǎn)生大量的空駛距離。確定全日車底出入場運行路徑及其在路徑上的運行線是城市軌道交通線路車底運用計劃編制的關鍵問題，目前現(xiàn)場計劃編制人員往往憑借經(jīng)驗解決該問題，計劃編制效率低下，且難以確保車底運用計劃的質(zhì)量。鑒于此，本文探討城市軌道交通線路運營時段前車底集中空駛出場路徑問題。

目前，國內(nèi)外尚未關注過城市軌道交通線路在運營時段前的車底空駛出場路徑問題，只在相關的運營時段內(nèi)列車運行圖和車底運用計劃編制方面開展過一定工作。列車運行圖編制方面，國外多考慮基于動態(tài)需求的城市軌道交通線路列車運行圖編制。文獻[1-2]以實際擁擠區(qū)段為對象，研究滿足客流需求動態(tài)變化及車底快速周轉的運行圖編制模型與算法。文獻[3]采用列車運行等效時間間隔概念，從3個不同的角度分別建立需求驅動運行圖模型。文獻[4-5]以旅客平均等待時間最小為目標，提出動態(tài)需求環(huán)境下的運行圖編制模型與算法。國內(nèi)對于城市軌道交通線路列車運行圖編制的研究并不多。文獻[6]以車場設置地點為核心，提出兩站圖及三站圖理論并以此構建運行圖通用數(shù)學模型。文獻[7]重點研究共線交路運行圖中車底運用、列車開行間隔等問題，并對其鋪畫流程和方法進行探討。文獻[8]基于現(xiàn)行運行圖編制理論與方法，構建了共線交路運行圖編制的雙層規(guī)劃模型。

第二項前期研究為車底運用計劃編制，其與車底空駛出場路徑問題關系更為密切。國外方面，文獻[9-11]在考慮列車編組、車底解編、車底空駛和客流需求等的情況下，研究車底運用計劃魯棒性編制問題，以綜合作業(yè)成本最低為目標建立車底運用優(yōu)化模型，并采用Bender分解法求解模型。國內(nèi)方面，文獻[12]歸納共線交路的4種基本形式，分別建立車底獨立與套跑運用條件下的優(yōu)化模型，并開發(fā)通用的車底運用優(yōu)化工具。文獻[13]基于圖論思想研究網(wǎng)絡化運營條件下車底運用計劃編制問題，并設計混合列生成算法求解所建立的車底運用優(yōu)化模型。文獻[14]建立了更為具體的車底運用優(yōu)化模型，并根據(jù)模型特點開發(fā)并行禁忌搜索算法。

綜上，未見文獻探討過城市軌道交通線路運營時段前車底空駛出場路徑的優(yōu)化方法。既有運行圖編制的研究通常只側重于優(yōu)化運營時段內(nèi)的運行線，即使理論上可將其拓展于編制運營時段前的車底空駛出場運行線，但由于其忽略多交路、多車場和集中出場等實際情況，難以獲得運營時段前高質(zhì)量甚至可行的車底出場運行線。同時，既有車底運用計劃編制研究往往提前設定車底從車場到車站的出入路徑，著重優(yōu)化運營時段內(nèi)的車底交路，未考慮運營時段前車底集中出場以及直達和折返兩種靈活的出場路徑，由車底交路勾畫的出場路徑很容易導致后續(xù)不能繪制出可行的車底出場運行線。因此，為提高城市軌道交通線路全日車底運用計劃的編制質(zhì)量，本文研究基礎的運營時段前車底空駛出場路徑優(yōu)化方法，著重探討具有多交路、多車場和多車型的車底空駛出場路徑問題。

1 問題定義

1.1 問題描述

以含6個車站、2個車場和4個折返站的城市軌道交通線路為例，對所研究問題進行描述。如圖1所示，車站沿上行方向依次編號為s1～s6。車站s2和s5分別為車場d1和d2所在站，區(qū)間A1為車場d1的后方，區(qū)間A2和A3為車場d1的前方，同理，區(qū)間A1和A2為車場d2的后方，區(qū)間A3為車場d2的前方。車站s1、s2、s4和s6為折返站，其中，車站s1和s2為上行折返站(可將列車由下行折返為上行)，車站s4和s6為下行折返站(可將列車由上行折返為下行)。假設線路采用2條列車交路l1和l2，交路l1的端點分別為車站s1和s4，交路l2的端點分別為車站s2和s6。線路6:30開始運營，運營時段初有2列列車i1和i2需要由車場始發(fā)的車底來擔當。列車i1為下行列車，屬于交路l1，分別始發(fā)和終到于車站s4和s1。列車i2為上行列車，屬于交路l2，受運營開始時刻的限制，只始發(fā)于車站s3，并終到于車站s6?，F(xiàn)需為該2列列車的車底指派配屬車場及其對應的出場路徑，以獲得最小的空駛距離。

從圖1可看出，若忽略車場與折返站的能力，則列車i1的車底可有3條空駛出場路徑，如圖中粗虛線所示。路徑r1中，車底從車場d2出發(fā)，經(jīng)出場線至所在站s5后，運行至列車i1的始發(fā)站s4，由于車站s5至s4的運行方向與列車i1的相同，無需折返。路徑r2中，車底從車場d1出發(fā)，經(jīng)出場線至所在站s2后，運行至列車i1的始發(fā)站s4，并在此從上行折返為下行，以滿足列車i1的運行方向要求。路徑r3中，車底從車場d2出發(fā)，經(jīng)出場線至所在站s5后，首先運行至車站s6，在此折返后，再運行至列車i1的始發(fā)站s4。將路徑r1稱為直達路徑，路徑r2和r3稱為折返路徑。類似地，列車i2的車底也有3條空駛出場路徑，分別為直達路徑r4，折返路徑r5和r6，如圖中粗實線所示。車場的出車距離不同，折返站的折返距離也不同，使得各條出場路徑可產(chǎn)生不同的空駛距離。直達路徑的空駛距離往往比折返路徑小，但受能力限制，直達路徑并非總可行，為應對能力緊張，不得不采用折返路徑。

綜上，給定車場布置及能力、折返站布置及能力、以及運營時段初需要車底的列車，城市軌道交通線路運營時段前車底空駛出場路徑問題可描述為：指派列車所需車底的配屬車場和空駛出場路徑(可為直達或折返路徑)，以使得所有列車所需的車底得到滿足，所有車場的檢修及出車能力、以及所有折返站的折返能力不違背，且總空駛距離最小。

1.2 問題假設

具有多交路、多車場和多車型的城市軌道交通線路全日車底出入場運行線編制比較復雜，為獲得理論最優(yōu)的結果，理想的求解策略應將運營時段前車底集中出場、運營時段內(nèi)車底分散出入場和運營時段后車底集中入場過程進行綜合優(yōu)化，但該策略對于復雜的城市軌道交通線路建模和求解難度較大。在假定運營時段內(nèi)列車運行圖和車底交路計劃給定的前提下，本文著重探討運營時段前車底集中空駛出場路徑優(yōu)化問題。為對所研究問題做出更為清楚的界定，特制定以下假設：

假設1 城市軌道交通線路普遍對車底采用“從哪兒出回哪兒去”的運用規(guī)則，由此，車底在運營時段內(nèi)的分散出入場安排在一定程度上受其在運營時段前集中出場路徑的影響，但與集中出場情況不同，分散出入場發(fā)生在運營時段內(nèi)，一般允許載客且不會產(chǎn)生空駛距離，故暫不考慮運營時段內(nèi)車底分散出入場路徑及其對應運行線的編制。

假設2 車底在運營時段后的集中入場安排同時受其在運營時段前集中出場和在運營時段內(nèi)分散出場路徑的影響，在單獨優(yōu)化運營時段前集中出場路徑時，難以直接對運營時段后集中入場路徑進行綜合優(yōu)化；同時，運營時段后車底一旦擔當完最后一列列車，只需在終到站直接順向或經(jīng)折返后逆向返回其配屬車場，相比于運營時段前集中出場過程，空駛距離節(jié)約顯著，故暫不考慮運營時段后車底集中入場路徑及其對應運行線的編制。

假設3 假設在所研究的線路上各車場只與1個端點站或中間站接軌，注意，本文方法可容易地拓展來描述兩站接軌、區(qū)間接軌等更復雜的車場與其所在站間的接軌方式。

假設4 車底在運營時段前集中出場時一般不允許沿途逗留，且需在線路運營開始時刻前運行至擔當列車的始發(fā)站，由此出場路徑是車底出場運行安排的關鍵決策，給定出場路徑，車底在其路徑上的可行出場運行線可采用簡單規(guī)則確定，故暫不考慮運營時段前車底集中出場運行線的編制。為了在獲得出場路徑后可勾畫出高質(zhì)量的出場運行線，特別是控制車場和折返站的最早工作時刻，特約定車場在線路運營開始時刻前只有有限的時間可用于往兩個方向發(fā)出車底，同時，折返站也只能在線路運營開始時刻前給定的可用時間內(nèi)對車底進行折返。

2 數(shù)學模型

2.1 符號說明

為便于模型構建，對需要使用的符號進行定義和說明：

定義集合如下：S為城市軌道交通線路上的車站集合，沿上行方向從前往后編號，s∈S；D為車場集合，d∈D；K為折返站集合，k∈K；I為運營時段初需由車場的車底通過空駛出場進行擔當?shù)牧熊嚰?，i∈I，根據(jù)給定的車底交路計劃確定；W為運行方向集合，W={0，1}，w=0表示上行方向，w=1表示下行方向；V為按編組輛數(shù)進行區(qū)分的車底類型集合，v∈V，按編組輛數(shù)由少到多編號；Id={i∈I|bodqi=ui}?I，表示可由車場d的車底采用直達出場路徑進行擔當?shù)牧熊嚰?；Vd?V，表示車場d所能(日常)檢修的車底類型集合；Di={d∈D|bodqi=ui}?D，表示發(fā)出的車底可對列車i采用直達出場路徑進行擔當?shù)能噲黾?；Kid={(k∈K)|bodpk=1-ui,bpkqi=ui}?K，表示列車i所需車底從車場d始發(fā)并采用折返出場路徑對應的折返站集合。

定義常數(shù)如下：lss′為車站s和s′之間的距離，等于其包含區(qū)間的距離之和；bss′為車底從車站s至s′的運行方向，根據(jù)定義，bss′等于0或1；od為車場d所在的車站；gdv為每日車場d可(日常)檢修的類型為v的最大車底數(shù)量;adv為運營時段內(nèi)需由車場d類型為v的車底擔當?shù)牧熊嚁?shù)量，由車底交路計劃進行確定；edw為運營時段前車場d可向方向w發(fā)出的最大車底數(shù)量，可根據(jù)給定的可用出車時間和單向出車間隔進行估算；nd為運營時段前車場d可向兩個運行方向總共發(fā)出的最大車底數(shù)量，可根據(jù)給定的可用出車時間和雙向出車間隔進行估算；fdw為向方向w發(fā)出的車底從車場d至該車場所在站的走行距離；pk為折返站k對應的車站。rkw為運營時段前折返站k可將運行方向從1-w折返為w的最大車底數(shù)量，可根據(jù)給定的可用折返時間和單向折返間隔進行估算；hkw為在折返站k，車底的運行方向從1-w折返為w的走行距離；qi為列車i的始發(fā)站；ui為列車i的運行方向；ti為列車i所需車底的類型。

定義變量如下：xid為0-1變量，若列車i由車場d的車底采用直達路徑進行擔當，取為1，否則為0；yidk為0-1變量，若列車i由車場d的車底采用經(jīng)折返站k的折返路徑進行擔當，取為1，否則為0；cid為連續(xù)變量，表示車底從車場d至所擔當列車i始發(fā)站的空駛出場距離。

2.2 目標函數(shù)

車底在運營時段前集中出場沿途不允許載客，需快速運行至所擔當列車的始發(fā)站。為降低運輸成本，提高車底運用效率，應最小化車底出場總空駛距離，即

( 1 )

式中:cid為車底從車場d至擔當列車i始發(fā)站的空駛出場距離，其取值依賴于車底的出場路徑、車場的出車距離、折返站的折返距離以及站間距離，可采用下式進行計算

cid=(fdui+lodqi)·xid+

( 2 )

式中：當列車i所需車底從車場d始發(fā)并采用直達路徑出場(即xid=1)時，空駛出場距離cid等于車場d在列車i運行方向上的出車距離fdui與車場d所在站至列車i始發(fā)站的距離lodqi之和。當列車i所需車底從車場d始發(fā)并采用經(jīng)折返站k*的折返路徑出場(即yidk*=1)時，空駛出場距離cid由4部分組成：車場d在列車i相反運行方向上的出車距離fd,1-ui、車場d所在站至折返站k*的距離lod,pk*、折返站k*在列車i運行方向上的折返距離hk*,ui、折返站k*至列車i始發(fā)站的距離lpk*,qi。

2.3 約束條件

車底空駛出場路徑優(yōu)化問題還需滿足一系列運營和能力約束。

(1) 路徑唯一性約束

為獲得符合現(xiàn)場實際的運營時段前車底集中出場路徑，任意列車所需的車底必須且只能選擇一條始發(fā)于可檢修其車底類型的車場的直達或折返路徑出場即

?i∈I

( 3 )

(2) 路徑可行性約束

城市軌道交通線路通常只設置2條正線，上下行方向各占用1條，除折返站和車場所在站外，普通車站一般不設置配線，使得不是所有車場和所有列車間同時存在可行的直達和折返出場路徑。給定列車i和車場d，根據(jù)列車i的運行方向、列車i始發(fā)站和車場d所在站的相對位置，有4種可行的車底出場路徑，見圖2。

如圖2(a)所示，列車i為上行列車，若車場d所在站沿著上行方向在列車i始發(fā)站的后方，則列車i可由車場d的車底采用直達出場路徑進行擔當；反之，列車i與車場d間不存在可行的直達出場路徑，即若d?Di，必存在xid=0。

如圖2(b)所示，列車i為下行列車，若車場d所在站在列車i始發(fā)站的后方，則列車i不能由車場d的車底采用直達出場路徑進行擔當，即若d?Di，必存在xid=0。

如圖2(c)所示，列車i為上行列車，若車場d所在站在列車i始發(fā)站的后方，且在車場d所在站的后方存在合適的折返站Kid，則列車i可由車場d的車底采用經(jīng)Kid中任意站的折返出場路徑進行擔當，在圖中以虛實線表示；反之，若車場d所在站在列車i始發(fā)站的前方，且在車場d所在站的后方可找到合適的折返站Kid，則列車i與車場d間同樣存在經(jīng)Kid中任意站的折返出場路徑，如圖中粗實線所示。換言之，對于列車i和車場d，若Kid=?，可令yidk=0。

如圖2(d)所示，列車i為下行列車，無論車場d所在站在列車i始發(fā)站的前方還是后方，只要在車場d所在站的前方不存在折返站Kid，則列車i不能由車場d的車底采用經(jīng)Kid的折返出場路徑進行擔當，即若Kid=?，可令yidk=0。

(3) 車場檢修能力約束

城市軌道交通線路通常只配備1種車底，但可采用不同的編組輛數(shù)，基于此，本文將車底按編組輛數(shù)進行分類，典型的有4編車底、6編車底和8編車底等。為確保行車安全，車底具有嚴格的檢修制度，包括列檢、月檢、定修、架修和廠修等修程，在每運營一定時間或里程后需開展相應修程的檢修，其中，列檢和月檢等日常檢修作業(yè)通常固定在配屬車場進行。受場站特別是停車庫和列檢/月檢庫設計的限制，各車場對各類型的車底只有有限的日常檢修能力，需要指出的是，短編車底可在檢修長編車底的車場進行日常檢修。因此，在確定運營時段前車底空駛出場路徑時，需滿足配屬于各車場的各類型車底數(shù)(含該類型車底編組長度以下的短編車底數(shù))不能超過該車場對該類型車底的最大日常檢修能力。

同時，根據(jù)實際運營情況，除了檢修車底和備用車底以外，車場停留的運用車底實際上由兩部分構成，一部分為運營時段前集中出場以為運營時段初列車服務的車底，另一部分為運營時段內(nèi)分散出場以為平高峰過渡期間高峰列車服務的車底。因此，在表達運營時段前車場的檢修能力約束時，應扣除被運營時段內(nèi)分散出場車底占用的能力，即

( 4 )

(4) 車場出車能力約束

城市軌道交通線路的車場與其所在站間通常設置有2條聯(lián)絡線，分別為出場線和入場線，運營時段前，2條聯(lián)絡線都作為出場線使用，但兩出車方向往往各自占用1條。同時，受車場信聯(lián)閉設備的限制，為確保車底運行安全，不僅兩相鄰同方向車底間需滿足必要的出車間隔，兩相鄰反方向車底間也需滿足安全的出車間隔。另一方面，現(xiàn)場規(guī)定車場只能在最早工作時刻之后出車，且車底必須在線路運營開始時刻之前到達所擔當列車的始發(fā)站，使得車場在運營時段前的可用出車時間是有限的。因此，運營時段前，受出車時間和出車間隔的限制，各車場在各運行方向上只有有限的出車能力為

?d∈Dw∈W

( 5 )

同時，各車場在兩個運行方向上的總出車能力也是有限的為

?d∈D

( 6 )

(5) 折返站能力約束

為便于日常運營組織和調(diào)度指揮，城市軌道交通線路通常在其端點和沿線設置若干折返站，利用站前或站后渡線將車底從一個運行方向折返為另一個運行方向。在實際情況中，大多數(shù)折返站只具備1個方向的折返能力，只有少部分折返站可同時折返兩個方向的車底。由于車底在折返站轉向需走行一段距離，且對折返站接發(fā)車作業(yè)造成較大干擾，為確保折返站作業(yè)安全，在現(xiàn)有的信聯(lián)閉條件下，兩相鄰折返車底間需滿足安全的時間間隔。同時，折返站在開始工作至線路開始運營之間只有有限的折返時間可用。因此，運營時段前，在各折返站各運行方向上折返的車底數(shù)不能大于該站在該方向上的最大能力，即

?k∈Kw∈W

( 7 )

(6) 變量取值約束

xid={0,1} ?i∈Id∈Di

( 8 )

yidk={0,1} ?i∈Id∈Dk∈Kid

( 9 )

2.4 整體模型

綜上，城市軌道交通線路運營時段前車底空駛出場路徑問題可構建為

(M)式( 1 )

s.t. 式( 2 )～式( 9 )

車底空駛出場路徑問題可約簡為具有頂點能力約束的整數(shù)多商品網(wǎng)絡流問題，后者已被證明為NP-hard問題[15]，因此，原問題本質(zhì)上是NP-hard的。由既有算法理論可知，對于NP-hard問題，一般難以開發(fā)精確算法，可在多項式時間內(nèi)找到最優(yōu)解，甚至是可行解。然而，所構建模型(M)為混合整數(shù)線性規(guī)劃模型，還可進一步表達為純0-1線性規(guī)劃模型，該模型最壞情況下包含|D|×|K|×|I|個變量和|I|+|D|×|V|+|D|×|W|+|D|+|K|×|W|個約束，模型規(guī)模隨車場、折返站和列車的數(shù)量呈多項式增長。初步計算測試結果表明，基于該模型，當前諸多主流商業(yè)優(yōu)化軟件(例如CPLEX、GUROBI)只需在普通計算機上便可將大規(guī)模切實算例快速求解到最優(yōu)。因此，借助于線性模型(M)，本文直接采用商業(yè)優(yōu)化軟件求解所提出的車底空駛出場路徑優(yōu)化問題。

3 算例分析

3.1 算例描述

以某城市軌道交通線網(wǎng)中最繁忙線路為背景，如圖3所示，對所提出方法進行驗證。測試線路全長54 km，設車站39座，平均站間距1 421.1 m，2015年日均客流量達69.8萬乘次，全年客流量超2.5億乘次。線路配備六編和八編兩種車底，運營3條列車交路，第1條交路的端點為車站s1和s26，第2條交路的為車站s12和s32，第3條交路的為車站s12和s39。線路6:30開始運營，22:30結束運營。全線在中部和接近端點處分別設置大型車場d1和小型車場d2，車場d1可同時檢修六編和八編車底，車場d2只可檢修六編車底，兩車場在運營時段前的可用出車時間為60 min，兩個運行方向的出車間隔和距離相同，車場其他基本信息見表1。全線在沿線較為均勻地設置折返站10個，其中，上行折返站6個，下行折返站4個，目前在日常運營組織中只啟用折返站6個，剩下4個備用，所有折返站只能往1個運行方向對車底進行折返，且運營時段前的可用折返時間為60 min，折返站其他基本信息見表2。

表1 車場基本信息

選擇測試線路2015年工作日的分號列車運行圖進行算例分析。在編制完測試運行圖的車底交路計劃后，測試線路運營時段初共有29列列車需由車場d1和d2始發(fā)的車底進行擔當，其基本信息見表3。其中，第1～3列表示列車的信息，第4～7列表示由計劃編制人員憑借經(jīng)驗確定的列車所需車底的空駛出場路徑相關信息，后7列含義與前7列相同。同時，測試線路在運營時段內(nèi)需要車場d1發(fā)出6列六編車底和9列八編車底、車場d2發(fā)出8列六編車底，意味著運營時段前車場d1和d2的實際檢修能力分別為37列八編車底和13列六編車底。

表2 折返站基本信息

注：折返站k4對應的車站s12同時為車場d1所在的車站，運營時段前只供車底出場，不供車底折返。

表3 列車基本信息

注：列車16和20需要八編車底進行擔當，其余列車需要六編車底進行擔當。

3.2 計算結果

采用IBM ILOG CPLEX OPL編程所提出的優(yōu)化方法，并調(diào)用CPLEX 12.5.1求解所構建的優(yōu)化模型(M)。將CPLEX的相關參數(shù)取為默認值，并基于其內(nèi)嵌的集成分支定界和割平面算法的分支切割算法將模型(M)求解到最優(yōu)。所有計算在CPU為Inter Core i7-4700MQ 2.40 GHz，內(nèi)存為8 GB，操作系統(tǒng)為Windows 10-64位的普通計算機上運行。

對測試算例，運用上述優(yōu)化方法，耗時不到1 s，獲得車底空駛出場路徑見表4，其中，距離縮短率為優(yōu)化結果相比于經(jīng)驗方法的空駛出場距離縮短率，增加為正值，縮短為負值。從表4可看出，受車場位置和能力的影響，21列列車(含全部的13列上行列車和8列下行列車)的車底從位于線路中部的大型車場d1始發(fā)，只有剩下8列下行列車的車底從靠近線路端部的小型車場d2始發(fā)。同時，為最小化車底總空駛距離，只有11列列車(包括6列上行列車和5列下行列車)的車底選擇折返路徑出場，剩下18列列車的車底選擇直達路徑出場。

將表3與表4進行對比可發(fā)現(xiàn)，與現(xiàn)場計劃編制人員的經(jīng)驗方法相比，所提出的優(yōu)化方法未顯著改變列車所需車底的空駛出場路徑，只有2列列車所需車底的出場路徑從原來的直達路徑調(diào)整為折返路徑，空駛距離有所延長，但與此同時，4列列車所需車底的出場路徑從原來的折返路徑調(diào)整為直達路徑，空駛距離大為縮短。最終，優(yōu)化方法經(jīng)過簡單的調(diào)整將總空駛距離從原來的473.388 km減小為444.697 km，總空駛距離縮短28.691 km，占原總空駛距離的6.1%，年總空駛距離預計可縮短超1萬km。因此，優(yōu)化方法既具有較好的求解效果，又具有非?？斓那蠼馑俣?，完全可用于提高運營時段前車底空駛出場路徑的質(zhì)量。

基于表4還可統(tǒng)計車場和折返站的能力占用情況，該信息有助于識別能力瓶頸，從而為進一步縮短車底總空駛距離提供有效提示。車場的能力占用情況見表5，其中，第6列、第7列分別為上行和下行發(fā)出的車底數(shù)，第8列～第11列分別為車場檢修能力的占用率、上行、下行和雙向出車能力的占用率。從表5可見，兩車場的檢修能力占用率低于65%，反映該算例中車場的檢修能力對車底的空駛出場路徑無實質(zhì)性影響。然而，車場1的下行和雙向出車能力全部占用，車場2的下行出車能力也全部占用，意味著車場的出車能力顯著影響車底的空駛出場路徑。折返站的能力占用情況見表6，其中第1列為折返站編號。由表6可得，只有3個折返站存在列車折返，且其折返能力占用率低于50%，說明折返站的能力不影響車底的空駛出場路徑。

表4 基于優(yōu)化方法的車底空駛出場路徑

表5 車場能力占用

表6 折返站能力占用

3.3 縮短總空駛距離的措施

本節(jié)采用靈敏度分析方法探求可進一步縮短車底總空駛距離的有效措施。根據(jù)測試算例的現(xiàn)狀及其車場和折返站在優(yōu)化后的能力占用情況，考慮2個有望縮短車底總空駛距離的措施，一個為開放未啟用的折返站，另一個為延長車場的可用出車時間。

(1) 開放未啟用的折返站

首先評估開放未啟用的折返站對車底總空駛距離的影響。如3.1節(jié)所述，測試線路共設置10個折返站，有6個折返站{1，4，5，7，9，10}已啟用，還有4個折返站{2，3，6，8}未啟用。對于未啟用的折返站，設計16種折返站開放方案，靈敏度分析結果如圖4所示。其中，橫軸表示折返站的開放方案，最左邊方案為基本方案，只包含已啟用的6個折返站，后續(xù)方案為待評估的方案，其括號內(nèi)數(shù)字表示在基本方案的基礎上新開放的折返站。左縱軸表示各方案對應的總空駛距離，以柱形圖表示，最上方的水平虛線表示經(jīng)驗方法對應的總空駛距離。右縱軸表示各方案相比于經(jīng)驗方法的總空駛距離縮短率，以折線圖表示。

從圖4可看出，若考慮只新開放1個折返站，開放折返站2或3均可明顯縮短車底的總空駛距離，且開放折返站3的效果更好。若考慮新開放2個折返站，開放折返站2或3的方案優(yōu)于其他方案，同時開放折返站2和3的方案效果最好。若考慮新開放3個折返站，同時開放折返站2和3的方案比其他方案更優(yōu)。總的來看，同時開放折返站2和3的四個方案為最優(yōu)方案，車底總空駛距離為385.082 km，與經(jīng)驗方法相比，總空駛距離縮短88.306 km，縮短率達18.7%。鑒于折返站2和3比較接近，建議新開放折返站3，此時，車底總空駛距離為 398.585 km，相對于經(jīng)驗方法，總空駛距離縮短74.803 km，縮短率為15.8%，只比最優(yōu)方案少2.9%。綜上，開放未啟用的折返站是縮短車底總空駛距離的有效措施，但是，該措施將增加設備維護和人力資源等費用，在實際應用時需通過技術經(jīng)濟比較加以確定。

(2) 延長車場的可用出車時間

其次評估延長車場的可用出車時間對車底總空駛距離的影響。3.2節(jié)已指出，車場的出車能力非常緊張，制約著車底出場路徑的優(yōu)化，對此，可嘗試提高車場的出車能力，以進一步縮短車底的總空駛距離。車場的出車能力等于出車時間除以出車間隔，因此，為提高車場的出車能力，既可延長出車時間，也可縮短出車間隔。此處考慮前項措施，將車場的出車時間從當前的60 min逐步延長至 81 min，步長為3 min，設計8種出車時間方案，靈敏度分析結果如圖5所示。其中，橫軸為出車時間方案，各方案的數(shù)字表示其對應的出車時間。左縱軸為各方案對應的總空駛距離，以柱形圖表示，同樣在最上方以水平虛線標記經(jīng)驗方法對應的總空駛距離。右縱軸為各方案相對于經(jīng)驗方法的總空駛距離縮短率，以折線圖表示。

圖5顯示，當車場出車時間從當前的60 min延長至72 min時，車底總空駛距離有所縮短，但當車場出車時間繼續(xù)延長時，車底總空駛距離保持不變。在其他條件保持現(xiàn)狀的前提下，將車場出車時間延長12 min，可獲得最優(yōu)的車底出場路徑，總空駛距離為437.229 km，相比于經(jīng)驗方法縮短36.159 km，縮短率為7.6%。利用表5的車場能力占用統(tǒng)計情況可對圖5中的變化規(guī)律進行解釋。當出車時間取為72 min時，車場1的雙向出車能力為25列，小于其實際檢修能力，同時，車場2的雙向出車能力為13列，正好等于其實際檢修能力。因此，當出車時間小于72 min時，兩車場的出車能力為瓶頸，此時延長出車時間有利于縮短車底總空駛距離。然而，當出車時間大于72 min時，車場2的檢修能力將成為瓶頸，此時繼續(xù)延長出車時間不能改進車底運用效率。綜上，當車場出車能力緊張而檢修能力富余時，延長車場出車時間有機會進一步縮短車底總空駛距離，然而，當車場出車能力比檢修能力富余時，需同時提升車場的出車和檢修能力才可能取得好的。

4 結論

運營時段前車底集中空駛出場路徑優(yōu)化是城市軌道交通線路全日車底出入場運行線以及車底運用計劃編制的重要決策，但目前該問題并未獲得企業(yè)界和學術界的廣泛關注，且在現(xiàn)場主要由工作人員憑借經(jīng)驗編制，解的質(zhì)量難以得到保證。在分析城市軌道交通線路運營時段前車底集中出場過程的基礎上，以總空駛距離最小為目標，考慮諸多的實際運營和能力約束，為具有多交路、多車場和多車型的車底空駛出場路徑問題，構建混合整數(shù)線性規(guī)劃模型，該模型的規(guī)模對于車場、折返站和列車的數(shù)量多項式有界。計算結果表明，所提出的模型可幫助主流商業(yè)優(yōu)化軟件在普通計算機上將大規(guī)模問題快速求解到最優(yōu)，所提出的優(yōu)化方法在解的質(zhì)量上優(yōu)于現(xiàn)場采用的經(jīng)驗方法。另外，若技術經(jīng)濟條件允許，可通過開放未啟用的折返站或延長車場的可用出車時間，以進一步縮短車底集中出場的總空駛距離。

作為全日車底出入場運行線編制的重要決策之一，本文問題具有研究難度和改進空間，可在以下幾個方面作進一步拓展。首先，可將所提出的模型應用于解決更多或更復雜的實際問題，以評估該模型對實際問題的求解能力，并分析繼續(xù)開發(fā)更有效求解算法的必要性。其次，實際情況中，城市軌道交通線路的車底在運營時段前需按運行線而不只是路徑集中空駛出場，未來有必要將所提出的出場路徑方法拓展來解決出場運行線編制問題。另外，城市軌道交通線路的車底在運營時段前集中出場、運營時段內(nèi)分散出入場以及運營時段后集中入場，如何在已存在大量列車運行線的運行圖空隙中插入全日車底出入場運行線(即綜合解決全日車底出入場運行線編制問題)也是下一步值得開展的工作。

參考文獻：

[1] NIU H, ZHOU X. Optimizing Urban Rail Timetable under Time-dependent Demand and Oversaturated Conditions[J]. Transportation Research Part C：Emerging Technologies, 2013, 36(11):212-230.

[2] NIU H, ZHOU X, GAO R. 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.

[3] SUN L, JIN J G, LEE D H, et al. Demand-driven Timetable Design for Metro Services[J]. Transportation Research Part C：Emerging Technologies, 2014, 46:284-299.

[4] BARRENA E, CANCA D, COELHO L C, et al. Exact Formulationsand Algorithm for the Train Timetabling Problem with Dynamic Demand[J]. Computers & Operations Research, 2014, 44(3):66-74.

[5] BARRENA E, CANCA D, COELHO L C, et al. Single-Line Rail Rapid Transit Timetablingunder Dynamic Passenger Demand[J]. Transportation Research Part B：Methodological, 2014, 70(C):134-150.

[6] 許紅,馬建軍,龍建成,等. 城市軌道交通列車運行圖編制的數(shù)學模型及方法[J]. 北京交通大學學報, 2006, 30(3):10-14.

XU Hong, MA Jianjun, LONG Jiancheng, et al. Study on Model and Method of Train Working Diagram of Urban Rail Transit[J]. Journal of Beijing Jiaotong University, 2006, 30(3):10-14.

[7] 江志彬,徐瑞華,吳強,等. 計算機編制城市軌道交通共線交路列車運行圖[J]. 同濟大學學報(自然科學版), 2010, 38(5):692-696.

JIANG Zhibin, XU Ruihua, WU Qiang, et al. Shared-path Routing Timetable Computer Designing in Rail Transit System[J]. Journal of Tongji University (Natural Science), 2010, 38(5):692-696.

[8] 王媛媛. 城市軌道交通列車運行圖編制理論與方法研究[D]. 成都:西南交通大學, 2013.

[9] CADARSO L, MARIN A. Robust Rolling Stock in Rapid Transit Networks[J]. Computers & Operations Research, 2011, 38(8):1131-1142.

[10] CADARSO L, MARIN A. Robust Routing of Rapid Transit Rolling Stock[J]. Public Transport, 2010, 2(1):51-68.

[11] CADARSO L, MARIN A. Improving Robustness of Rolling Stock Circulations in Rapid Transit Networks[J]. Computers & Operations Research, 2014, 51(3):146-159.

[12] 江志彬,徐瑞華,吳強,等. 多交路共線運行的城市軌道交通車輛運用優(yōu)化[J]. 同濟大學學報(自然科學版), 2014, 42(9):1333-1339.

JIANG Zhibin, XU Ruihua, WU Qiang, et al. Optimal Model for Using of Transit Unit Based on Shared-path Rail Transit Route[J]. Journal of Tongji University (Natural Science), 2014, 42(9):1333-1339.

[13] 何必勝,宋瑞,何世偉,等. 城市軌道交通車底運用計劃編制優(yōu)化模型求解的混合列生成算法[J]. 中國鐵道科學, 2014, 35(1):122-129.

HE Bisheng, SONG Rui, HE Shiwei,et al. A Hybrid Column Generation Approach for Solving Rolling Stock Assignment Optimization Model of Urban Rail Transit[J]. China Railway Science, 2014, 35(1):122-129.

[14] 鄭鋰,宋瑞,肖赟,等. 網(wǎng)絡化運營下城市軌道交通列車車底運用計劃編制的優(yōu)化方法[J]. 中國鐵道科學, 2014, 35(2):104-110.

ZHENG Li, SONG Rui, XIAO Yun, et al. Optimization Method for Working Out Vehicle Scheduling Plan of Urban Rail Transit under Network Operation[J]. China Railway Science, 2014, 35(2):104-110.

[15] EVEN S, ITAI A, SHAMIR A. On the Complexity of Time Table and Multi-commodity Flow Problems[C]//16th Annual Symposium on Foundations of Computer Science. New York:IEEE,1975:184-193.