王 典，趙 軍，鐘慶偉，彭其淵

(1.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 611756；2.西南交通大學(xué) 綜合交通智能化國家地方聯(lián)合工程實(shí)驗(yàn)室，四川 成都 611756)

本文研究城市軌道交通線路車底全日出入場(chǎng)走行安排中的關(guān)鍵環(huán)節(jié)，即運(yùn)營時(shí)段前車底集中空駛出場(chǎng)路徑與時(shí)刻表綜合編制問題。城市軌道交通線路在運(yùn)營時(shí)段初開行多列列車，它們始發(fā)于不同的車站，由于可供車底接續(xù)不同列車的時(shí)間有限，使得其中幾乎所有的列車都需由車場(chǎng)發(fā)出的車底擔(dān)當(dāng)。由此，運(yùn)營時(shí)段前大量車底集中從車場(chǎng)出發(fā)，根據(jù)指定的物理路徑和時(shí)刻表，直接空駛至其擔(dān)當(dāng)列車的始發(fā)站。車底集中空駛出場(chǎng)安排比較靈活，每個(gè)車底既可選擇從其始發(fā)車場(chǎng)到其擔(dān)當(dāng)列車始發(fā)站的直達(dá)路徑，也可選擇從其始發(fā)車場(chǎng)經(jīng)1個(gè)甚至多個(gè)折返站再到其擔(dān)當(dāng)列車始發(fā)站的折返路徑。然而，為確保整個(gè)出場(chǎng)活動(dòng)的安全可行以及列車正點(diǎn)開車，必須保證每個(gè)車底的出場(chǎng)路徑和時(shí)刻表與其他車底的時(shí)空無沖突，車場(chǎng)和車站能力滿足要求，且出場(chǎng)過程需在其擔(dān)當(dāng)列車開車時(shí)刻之前完成。

目前國內(nèi)外在城市軌道交通線路列車運(yùn)行圖和車底運(yùn)用計(jì)劃編制方面開展了一定工作。運(yùn)行圖編制方面，更關(guān)注時(shí)變和隨機(jī)客流需求下的動(dòng)態(tài)和魯棒運(yùn)行圖編制模型與算法，見文獻(xiàn)[1-4]。對(duì)于車底運(yùn)用問題，文獻(xiàn)[5-6]考慮列車編組、車底解編、車底空駛和客流需求等情況，建立車底運(yùn)用計(jì)劃魯棒優(yōu)化模型。文獻(xiàn)[7]分別建立具有多交路共線運(yùn)行的線路在獨(dú)立和套跑運(yùn)用條件下的車底運(yùn)用計(jì)劃編制模型。文獻(xiàn)[8]提出運(yùn)營時(shí)段前車底集中空駛出場(chǎng)路徑優(yōu)化問題，最小化總空駛距離，構(gòu)建0-1線性規(guī)劃模型。第三項(xiàng)相關(guān)研究是公交車配屬問題，為公交車指派車場(chǎng)，以滿足車場(chǎng)能力和路線車數(shù)需求。文獻(xiàn)[9]考慮總空駛距離最小和最大空駛距離最小目標(biāo)，提出非支配排序多目標(biāo)優(yōu)化算法。文獻(xiàn)[10]考慮配屬唯一性，提出幾個(gè)啟發(fā)式算法。文獻(xiàn)[11]引入車場(chǎng)運(yùn)用均衡性和運(yùn)營費(fèi)用目標(biāo)，設(shè)計(jì)遺傳算法。文獻(xiàn)[12]考慮分時(shí)段車場(chǎng)能力和路線車數(shù)需求，構(gòu)建多階段配屬模型。

綜上，城市軌道交通線路車底集中空駛出場(chǎng)路徑與時(shí)刻表綜合編制尚未獲得學(xué)術(shù)界高度關(guān)注。既有列車運(yùn)行圖編制研究通常提前固定列車在線路正線上的運(yùn)行路徑，基于此側(cè)重于優(yōu)化運(yùn)營時(shí)段內(nèi)列車在線路正線給定運(yùn)行路徑上途經(jīng)車站的到發(fā)時(shí)刻，忽略列車所需車底的出入場(chǎng)走行過程及其出入場(chǎng)路徑的多樣性(直達(dá)路徑和折返路徑)，且未全面考慮車場(chǎng)檢修和出車能力及折返站能力的限制，難以用于確定運(yùn)營時(shí)段前車底集中出場(chǎng)路徑與時(shí)刻表。既有車底運(yùn)用計(jì)劃研究往往設(shè)定車底出入場(chǎng)選擇直達(dá)路徑，主要勾畫運(yùn)營時(shí)段內(nèi)的車底交路，不能保證每條獲得交路上的車底均可在運(yùn)營時(shí)段前通過直達(dá)路徑完成出場(chǎng)。文獻(xiàn)[8]與本文研究相似，但其只優(yōu)化運(yùn)營時(shí)段前車底集中出場(chǎng)路徑，簡單以給定時(shí)間內(nèi)可發(fā)出或折返的最大車底數(shù)來刻畫車場(chǎng)和折返站的能力，未嚴(yán)格滿足車底出場(chǎng)時(shí)刻表的編制要求，注意，只確定車底出場(chǎng)路徑難以確保后續(xù)可勾畫出時(shí)空無沖突且高質(zhì)量的車底出場(chǎng)時(shí)刻表。公交車配屬的既有研究一般規(guī)定車輛在車場(chǎng)與路線始發(fā)/終到站間按指定路徑運(yùn)行，假設(shè)車輛在運(yùn)行途中無時(shí)空沖突，且忽略車場(chǎng)和車站能力，不適用于城市軌道交通線路的車底出場(chǎng)安排。

鑒于此，本文根據(jù)城市軌道交通線路的運(yùn)營特點(diǎn)，在文獻(xiàn)[8]的基礎(chǔ)上，對(duì)運(yùn)營時(shí)段前車底集中空駛出場(chǎng)路徑與時(shí)刻表進(jìn)行綜合優(yōu)化，同時(shí)確定運(yùn)營時(shí)段前車底從其配屬車場(chǎng)到其列車始發(fā)站的時(shí)空無沖突的出場(chǎng)路徑與時(shí)刻表，通過引入時(shí)刻表約束更為準(zhǔn)確地描述車場(chǎng)的出車能力及車站的接發(fā)車能力和折返能力，從而獲得更具有運(yùn)營可行性的車底出場(chǎng)方案。

1 問題定義

1.1 問題描述

城市軌道交通線路運(yùn)營時(shí)段前車底空駛出場(chǎng)路徑與時(shí)刻表綜合優(yōu)化包含路徑與時(shí)刻表優(yōu)化兩個(gè)子問題：給定線路運(yùn)營時(shí)段內(nèi)的列車運(yùn)行圖和車底交路，路徑問題在于指派運(yùn)營時(shí)段初各列車需要車底的配屬車場(chǎng)及運(yùn)營時(shí)段前從車場(chǎng)到列車始發(fā)站的出場(chǎng)路徑；給定出場(chǎng)路徑，時(shí)刻表問題在于確定各車底在選擇路徑上途經(jīng)各車場(chǎng)、中間站和折返站的到發(fā)時(shí)刻。鑒于現(xiàn)場(chǎng)存在多種運(yùn)營條件的城市軌道交通線路，不失一般性，本文針對(duì)復(fù)雜的具有多車場(chǎng)、多車型和多列車交路的線路開展研究，該線路可約簡為更為簡單的線路。

以包含6個(gè)車站(含4個(gè)折返站)和2個(gè)車場(chǎng)的線路為例進(jìn)行問題描述，如圖1所示，其中車站沿下行方向從s1到s6依次編號(hào)，車場(chǎng)類似編號(hào)為j1和j2，其所在站分別為車站s2和s5。線路沿線設(shè)置4個(gè)折返站，分別為s1，s3，s5和s6。車站s1為單向站后折返站，可將車底由上行折返為下行。車站s3為雙向站前折返站，可折返兩個(gè)方向車底。車站s5為單向站后折返站，可將車底由下行折返為上行，該站連接車場(chǎng)，通常運(yùn)營時(shí)段前不辦理折返作業(yè)。車站s6為單向站前折返站，可將車底由下行折返為上行，下行車底直接接入上行正線進(jìn)行折返。

線路運(yùn)營2條列車交路，第一條的端點(diǎn)為車站s1和s6，第二條的為車站s3和s6。線路在6：30開始運(yùn)營，根據(jù)提前編制的運(yùn)營時(shí)段內(nèi)的車底交路計(jì)劃，運(yùn)營時(shí)段初下行列車i1和上行列車i2和i3需由在運(yùn)營時(shí)段前空駛出場(chǎng)的車底擔(dān)當(dāng)，列車i1屬于第二條列車交路，列車i2和i3屬于第一條列車交路?，F(xiàn)需為擔(dān)當(dāng)該3列列車的車底指派配屬車場(chǎng)、出場(chǎng)路徑及時(shí)刻表(統(tǒng)稱出場(chǎng)方案)，在滿足各種運(yùn)營和能力要求的條件下，減少車底總空駛距離和總空駛時(shí)間。

圖2提供一些候選車底空駛出場(chǎng)方案，可以看出，若忽略車場(chǎng)檢修及出車能力、車站和折返站能力，根據(jù)車場(chǎng)和折返站位置以及列車始發(fā)站和發(fā)車方向，可確定任意列車的所有可行車底出場(chǎng)路徑。列車i1的可行車底出場(chǎng)路徑有4條，編號(hào)為p1～p4，其中，路徑p1為直達(dá)路徑，其他為折返路徑，需在途中折返一次，以滿足列車的發(fā)車方向。簡便起見，圖2分別僅給出列車i2和i3的最短車底出場(chǎng)路徑p5和p6。注意，車站s6為站前折返站，下行車底進(jìn)站時(shí)直接接入上行正線折返，由此使得列車i3的車底只能在列車i2發(fā)車后才能開始辦理接車作業(yè)。此外，理論上存在多次折返出場(chǎng)路徑，如路徑p7，采用該路徑的車底需先后在車站s3和s6折返，但通常其空駛距離較長且額外占用折返站能力，實(shí)際運(yùn)營中不予采納。

圖1 線路示意

圖2 車底空駛出場(chǎng)示意

車底同時(shí)遵循時(shí)空可行的路徑和時(shí)刻表出場(chǎng)，各條路徑的始發(fā)車場(chǎng)、途經(jīng)車站和折返站存在差異，產(chǎn)生不同空駛距離。直達(dá)路徑往往具有較小空駛距離，但受車場(chǎng)檢修及出車能力、車站通過能力、折返站折返能力等限制，直達(dá)路徑并非總是可行。同時(shí)，車站一般不設(shè)置到發(fā)線，車底到達(dá)所擔(dān)當(dāng)列車始發(fā)站后需停留在正線待發(fā)，使得后續(xù)同方向車底不能通過該車站，部分車底不得不采用折返路徑迂回出場(chǎng)，增加空駛距離。為確保運(yùn)行安全，必須保證任意兩車底出場(chǎng)時(shí)在時(shí)空上不存在沖突。受列車發(fā)車時(shí)刻的影響，在一些出場(chǎng)路徑上，車底不能在運(yùn)營開始時(shí)到達(dá)所擔(dān)當(dāng)列車的始發(fā)站，如路徑p6，車底不能與運(yùn)營時(shí)段內(nèi)的列車存在時(shí)空沖突。即使采用相同的出場(chǎng)路徑，不同的車場(chǎng)發(fā)車時(shí)刻將導(dǎo)致車底空駛時(shí)間存在差異，例如，路徑p5和p6途經(jīng)相同車場(chǎng)和車站，但前者在車場(chǎng)發(fā)車時(shí)刻更早，需要更長的空駛時(shí)間。為節(jié)約運(yùn)營成本，在不增加車底總空駛距離的同時(shí)應(yīng)盡量減少總空駛時(shí)間。車底空駛出場(chǎng)一般不需要在中間站停車，但因線路能力有限總會(huì)產(chǎn)生車站等待時(shí)間，在相同的等待時(shí)間下可能有許多等價(jià)的停站方案，若這些時(shí)間隨機(jī)分布到沿途中間站，將導(dǎo)致額外起停車作業(yè)，增加中間站工作負(fù)擔(dān)，故實(shí)際運(yùn)營中應(yīng)盡量減少車底出場(chǎng)在途經(jīng)中間站的停留時(shí)間，讓其快速運(yùn)行至擔(dān)當(dāng)列車始發(fā)站待發(fā)。

綜上，本文問題可描述為：給定線路布置及能力，車場(chǎng)布置及能力、折返站布置及能力以及需由運(yùn)營時(shí)段前集中空駛出場(chǎng)的車底擔(dān)當(dāng)?shù)牧熊嚨刃畔?，確定所有列車所需車底的配屬車場(chǎng)、出場(chǎng)路徑及時(shí)刻表，使得任意列車由適當(dāng)車底擔(dān)當(dāng)，所有車場(chǎng)檢修及出車能力、所有車站和折返站能力均不違背，任意車底和列車在時(shí)空上不沖突，且車底出場(chǎng)總空駛距離和總空駛時(shí)間最小，并盡量保證車底在所擔(dān)當(dāng)列車始發(fā)站集中待發(fā)。

1.2 問題假設(shè)

城市軌道交通線路車底全日出入場(chǎng)走行過程可分為3個(gè)階段，包括運(yùn)營時(shí)段前集中出場(chǎng)，運(yùn)營時(shí)段內(nèi)分散出入場(chǎng)和運(yùn)營時(shí)段后集中入場(chǎng)。3個(gè)階段相互聯(lián)系，共同影響車底運(yùn)用效率，求解車底全日出入場(chǎng)走行方案的理想策略應(yīng)是集成3個(gè)階段進(jìn)行協(xié)調(diào)優(yōu)化，然而這樣的策略對(duì)于具有多車場(chǎng)、多車型和多列車交路的線路研究難度大。鑒于車底在運(yùn)營時(shí)段內(nèi)分散出入場(chǎng)可視為普通列車，允許載客，不產(chǎn)生空駛，同時(shí)在運(yùn)營時(shí)段后集中入場(chǎng)不需要占用車站正線待發(fā)，安排難度和空駛距離降低顯著，本文研究第一階段的運(yùn)營時(shí)段前車底集中空駛出場(chǎng)路徑與時(shí)刻表綜合編制。為便于后續(xù)方法闡述，提出以下假設(shè)：

(1)線路運(yùn)營時(shí)段內(nèi)的列車運(yùn)行圖和車底交路計(jì)劃已完成編制。

(2)不考慮需在沿途折返2次及其以上的復(fù)雜車底出場(chǎng)路徑。

(3)為將車場(chǎng)開始上班時(shí)間設(shè)置在合理水平，引入車場(chǎng)最早允許出車時(shí)刻，規(guī)定任意車場(chǎng)向兩個(gè)方向發(fā)出車底的時(shí)刻不能早于其最早允許出車時(shí)刻。

(4)鑒于城市軌道交通線路車底起停車附加時(shí)間較短，同時(shí)為增加車底集中空駛出場(chǎng)的靈活性，無論車底是否在中間站停車，規(guī)定各區(qū)間運(yùn)行時(shí)分均包括起停車附加時(shí)間。

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

2.1 網(wǎng)絡(luò)抽象

將研究的城市軌道交通線路抽象為有向網(wǎng)絡(luò)，基于此，提前生成各列需要由車場(chǎng)發(fā)出的車底進(jìn)行擔(dān)當(dāng)?shù)牧熊嚨乃锌尚谐鰣?chǎng)路徑。

以圖1所示線路為例，其抽象網(wǎng)絡(luò)如圖3所示。頂點(diǎn)集由三部分構(gòu)成，包括車站正線頂點(diǎn)1～11，折返線頂點(diǎn)12和13，車場(chǎng)頂點(diǎn)14和15。各車站下行和上行正線一般情況下各設(shè)置1個(gè)頂點(diǎn)，各折返站根據(jù)其配線情況設(shè)置頂點(diǎn)。車站s1為單向站后折返站，車站s3為雙向站前折返站，這兩類車站同時(shí)設(shè)置正線和折返線，接發(fā)車和折返允許部分平行作業(yè)，前行列車進(jìn)折返線停穩(wěn)后可辦理后行列車接車進(jìn)路，前行列車出清折返線后可辦理后行列車進(jìn)折返線進(jìn)路。因此，在車站s1和s3分別設(shè)置1個(gè)折返線頂點(diǎn)。車站s6為單向站前折返站，在這類車站不設(shè)置折返線，下行車底依次接入上行正線辦理折返作業(yè)，前行列車需出清車站后才可辦理后行列車接車進(jìn)路。由此，只為車站s6設(shè)置上行正線頂點(diǎn)6，不設(shè)置下行正線頂點(diǎn)16和折返線頂點(diǎn)17?，F(xiàn)場(chǎng)折返站還存在站后雙折返線折返和站前雙渡線折返等配線設(shè)置形式，技術(shù)上可交替進(jìn)行兩列車底的折返，但為避免進(jìn)路沖突，確保作業(yè)安全，現(xiàn)場(chǎng)一般只固定使用其中的1條站后折返線或1條站前單渡線來辦理折返作業(yè)。為此，對(duì)這兩種類型的復(fù)雜折返站，本文參照其對(duì)應(yīng)的簡單折返站(即圖1中的車站s1和s6)在抽象網(wǎng)絡(luò)中設(shè)置頂點(diǎn)。各車場(chǎng)分別設(shè)置1個(gè)頂點(diǎn)，可向兩個(gè)方向發(fā)車。

圖3 網(wǎng)絡(luò)抽象示意

弧集包含四部分，分別為區(qū)間弧、入折返線弧、出折返線弧和出場(chǎng)弧。區(qū)間弧表示車底在區(qū)間運(yùn)行，基本位于同方向兩相鄰車站正線頂點(diǎn)間。在折返站s6，下行列車直接接入上行正線折返，車站s5和s6間的下行區(qū)間以從車站s5下行正線頂點(diǎn)5到車站s6上行正線頂點(diǎn)6的弧表示。折返線弧表示車底在折返站正線與折返線間的走行過程，在各折返站，折返線弧根據(jù)其折返方向進(jìn)行設(shè)置，入折返線弧連接接車正線頂點(diǎn)與折返線頂點(diǎn)，出折返線弧連接折返線頂點(diǎn)與發(fā)車正線頂點(diǎn)。折返站s3可辦理兩個(gè)方向車底的折返作業(yè)，盡管任意方向的車底折返物理上不占用相應(yīng)的車站正線，但此時(shí)該正線不能用于接車，即任意方向的車底折返對(duì)同方向車站正線構(gòu)成間接占用，為此，每個(gè)折返方向分別引入1條入折返線弧和1條出折返線弧。出場(chǎng)弧表示車底從車場(chǎng)到銜接車站正線的走行過程，在各車場(chǎng)，出場(chǎng)弧根據(jù)其發(fā)車方向進(jìn)行設(shè)置，對(duì)各發(fā)車方向，車場(chǎng)頂點(diǎn)通過1條出場(chǎng)弧連接可達(dá)的銜接車站正線頂點(diǎn)。為各弧引入長度和時(shí)間屬性，表示車底在該弧對(duì)應(yīng)物理路徑上的走行距離和時(shí)間。出場(chǎng)弧的屬性取為車底從車場(chǎng)到銜接車站的走行距離和時(shí)間，區(qū)間弧的屬性取為區(qū)間長度和運(yùn)行時(shí)間，入/出折返線弧的屬性取為車底入線/出線走行距離和時(shí)間。

將研究線路基于上述規(guī)則抽象為有向網(wǎng)絡(luò)后，任意列車所需車底的可行出場(chǎng)路徑等價(jià)于抽象網(wǎng)絡(luò)中從具備檢修功能車場(chǎng)對(duì)應(yīng)的頂點(diǎn)到該列車始發(fā)車站對(duì)應(yīng)正線頂點(diǎn)的路徑。分別生成每列列車的所有可行車底出場(chǎng)路徑，以保證每條出場(chǎng)路徑獨(dú)立，對(duì)應(yīng)唯一的列車和途經(jīng)頂點(diǎn)集合。所有可行出場(chǎng)路徑可在抽象網(wǎng)絡(luò)中采用深度優(yōu)先或廣度優(yōu)先等搜索算法確定，便于實(shí)施，可先忽略可行性生成所有的出場(chǎng)路徑，然后從中刪除途經(jīng)多個(gè)折返站或折返線長度小于車底長度的不可行路徑。前文已述，運(yùn)營時(shí)段內(nèi)有部分列車始發(fā)時(shí)刻在線路運(yùn)營開始時(shí)刻之后，但需要運(yùn)營時(shí)段前從車場(chǎng)發(fā)出的車底擔(dān)當(dāng)，例如圖2中的列車i3，這些列車的車底需同時(shí)與運(yùn)營時(shí)段前的出場(chǎng)車底和運(yùn)營時(shí)段初的載客列車時(shí)空不沖突。為此，將研究時(shí)段結(jié)束時(shí)刻從運(yùn)營開始時(shí)刻(圖2中為06：30)推遲為列車的最晚始發(fā)時(shí)刻(圖2中為Te)。同時(shí)，將各列車的可行車底出場(chǎng)路徑拓展為兩部分：一部分在抽象網(wǎng)絡(luò)中生成，從該路徑的始發(fā)車場(chǎng)對(duì)應(yīng)的頂點(diǎn)到列車始發(fā)站對(duì)應(yīng)的正線頂點(diǎn)，稱為可變部分，車底在這部分路徑上途經(jīng)頂點(diǎn)的到發(fā)時(shí)刻有待決策；另一部分根據(jù)運(yùn)營時(shí)段內(nèi)的運(yùn)行圖生成，從該路徑列車始發(fā)站對(duì)應(yīng)的正線頂點(diǎn)到研究時(shí)段結(jié)束時(shí)刻列車途經(jīng)的最后一個(gè)車站對(duì)應(yīng)的正線頂點(diǎn)，稱為固定部分，車底在這部分路徑上途經(jīng)頂點(diǎn)的到發(fā)時(shí)刻由運(yùn)行圖給定，是需要滿足的時(shí)空約束。

以圖2中的列車i1為例，假設(shè)車場(chǎng)j1可對(duì)該列車的車底進(jìn)行檢修，且運(yùn)營時(shí)段內(nèi)的運(yùn)行圖規(guī)定研究時(shí)段結(jié)束時(shí)刻該列車運(yùn)行至車站s4，則路徑p1為其可行車底出場(chǎng)路徑，在圖3中表示為(14，2，3，4)，其中頂點(diǎn)14到3的路徑基于圖3的抽象網(wǎng)絡(luò)生成，為可變部分，頂點(diǎn)3到4的路徑由運(yùn)行圖給定，為固定部分。類似地，對(duì)于列車i3，假設(shè)該列車的車底可在車場(chǎng)j2檢修，且研究時(shí)段結(jié)束時(shí)刻該列車正好在其始發(fā)站出發(fā)，則其可行車底出場(chǎng)路徑p6在圖3中表示為(15，5，6)，其中可變部分為頂點(diǎn)15到6，固定部分只含頂點(diǎn)6。

2.2 符號(hào)說明

為便于模型構(gòu)建，首先對(duì)將使用的集合、參數(shù)和變量進(jìn)行定義，見表1。

表1 集合、參數(shù)及變量定義

表1(續(xù))

表1(續(xù))

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

日常運(yùn)營中，車底在運(yùn)營時(shí)段前集中出場(chǎng)一般不允許載客運(yùn)行，需快速運(yùn)行至所擔(dān)當(dāng)列車始發(fā)站。為降低運(yùn)營成本，提高車底運(yùn)用效率，應(yīng)最小化車底出場(chǎng)總空駛距離。同時(shí)，在出場(chǎng)路徑確定后，車底出場(chǎng)時(shí)刻雖不會(huì)增加空駛距離，但對(duì)車底空駛時(shí)間產(chǎn)生影響。不合理的出場(chǎng)時(shí)刻可能使得車底過早出場(chǎng)，在途經(jīng)車站或所擔(dān)當(dāng)列車始發(fā)站等待較長時(shí)間，延長相關(guān)人員工作時(shí)間，增加運(yùn)營成本，故還需最小化車底總空駛時(shí)間。通?？s短總空駛距離能直接減少運(yùn)營成本，屬于主要目標(biāo)，模型引入車場(chǎng)最早允許出車時(shí)刻可在一定程度上控制車底空駛時(shí)間處于合理范圍，故總空駛時(shí)間為次要目標(biāo)。復(fù)合目標(biāo)函數(shù)表示為

(1)

2.4 約束條件2.4.1 路徑唯一性

為保證運(yùn)營時(shí)段初所有考慮列車正常發(fā)車，任意列車的車底必須且只能從其候選可行出場(chǎng)路徑集中選擇1條路徑出場(chǎng)，該約束可表示為

(2)

2.4.2 時(shí)刻表可行性

各車底在其出場(chǎng)路徑上的各頂點(diǎn)和各弧需分別滿足最小停站時(shí)間和走行時(shí)間，即

zps′=yps+tss′·xp?p∈P；s∈Sp{op}

(3)

yps-zps≥bps·xp?p∈P；s∈Sp{wp}

(4)

T·xp≤ypwp≤M1·xp?p∈P

(5)

(6)

(7)

式(3)為車底在出場(chǎng)、區(qū)間運(yùn)行、入/出折返線過程中的走行時(shí)間應(yīng)等于規(guī)定作業(yè)時(shí)間標(biāo)準(zhǔn)。式(4)為車底在途經(jīng)車站正線、折返線的停站時(shí)間不小于規(guī)定的最小時(shí)間，該約束隱含車底在任意頂點(diǎn)的出發(fā)時(shí)刻不早于相應(yīng)到達(dá)時(shí)刻。式(5)左半部分為任意車底在車場(chǎng)的發(fā)車時(shí)刻不早于該車場(chǎng)規(guī)定的最早允許出車時(shí)刻，右半部分與式(2)和式(3)共同保證式(1)中車底出場(chǎng)時(shí)刻計(jì)算的正確性，若路徑p未用于車底出場(chǎng)，其在途經(jīng)所有頂點(diǎn)s的到發(fā)時(shí)刻包括在車場(chǎng)的發(fā)車時(shí)刻均等于0，其中M1取為路徑p對(duì)應(yīng)車場(chǎng)在運(yùn)營時(shí)段內(nèi)首列車底的出場(chǎng)時(shí)刻減去對(duì)應(yīng)出車間隔。式(6)、式(7)為車底在路徑p固定部分途經(jīng)各頂點(diǎn)的到發(fā)時(shí)刻等于圖定時(shí)刻。

2.4.3 車場(chǎng)檢修能力

城市軌道交通線路的車底一般只有一種，但可配置不同的編組輛數(shù)，并在線路上混跑，例如4編/6編混跑，6編/8編混跑等，這里將車底根據(jù)其編組輛數(shù)進(jìn)行分類。為確保車底運(yùn)用安全，現(xiàn)場(chǎng)建立嚴(yán)格的車底檢修制度，修程包括列檢、月檢、定修、架修和大修等，規(guī)定車底每運(yùn)營一定時(shí)間或里程后需開展相應(yīng)修程的檢修，其中，車底的列檢和月檢等日常檢修作業(yè)通常固定在其配屬車場(chǎng)進(jìn)行。受場(chǎng)站功能和規(guī)模設(shè)計(jì)的影響，各車場(chǎng)對(duì)各類型車底的日常檢修能力是有限的，一般情況下，較短編組的車底可在容納較長編組車底的停車線上駐留并進(jìn)行日常檢修，反之則不能。因此，在確定車底出場(chǎng)方案時(shí)，需滿足配屬于各車場(chǎng)的各類型車底數(shù)不能超過該車場(chǎng)對(duì)該類型車底的可用檢修能力，可表示為

?j∈J；f∈F

(8)

式中：左半部分表示車場(chǎng)實(shí)際配屬的各類型車底數(shù)；右半部分表示該車場(chǎng)對(duì)該類型車底的可用檢修能力，等于該車場(chǎng)對(duì)該車型的總檢修能力減去用于檢修更長車型占用的能力。

2.4.4 車場(chǎng)出車能力

研究線路的車場(chǎng)與其銜接站間通常分別設(shè)置1條出場(chǎng)和1條入場(chǎng)聯(lián)絡(luò)線，運(yùn)營時(shí)段前兩條聯(lián)絡(luò)線均只供車底出場(chǎng)使用，為避免進(jìn)路沖突，兩出車方向各占用1條。盡管如此，兩條聯(lián)絡(luò)線共用同一個(gè)咽喉區(qū)與車場(chǎng)相連，受場(chǎng)站布置和信號(hào)設(shè)備的影響，兩相鄰?fù)较蚝头捶较虻能嚨组g都需滿足必要的安全出車間隔。車場(chǎng)在最早允許出車時(shí)刻規(guī)定下只有有限的出車時(shí)段，與出車間隔共同限制其出車能力，該約束可表示為

?j∈J；p，p′∈Bj|p≠p′

(9)

(10)

(11)

?j∈J；p，p′∈Bj|p≠p′

(12)

2.4.5 車站能力

城市軌道交通線路一般采用基于通信的列車控制系統(tǒng)(CBTC)，實(shí)現(xiàn)移動(dòng)自動(dòng)閉塞行車，基于此車底可以足夠小的距離追蹤運(yùn)行。然而，車底在車站到發(fā)和通過需辦理一系列技術(shù)作業(yè)，包括辦理進(jìn)路、進(jìn)/出站等，兩相鄰?fù)较虻牧熊囋谲囌拘铦M足一定的到達(dá)和出發(fā)間隔，由于列車運(yùn)行速度是一樣的，不存在區(qū)間越行，這里只考慮到達(dá)間隔。同樣的，車底在車站折返也存在辦理進(jìn)路、入/出折返線等技術(shù)作業(yè)過程，兩相鄰辦理同方向折返的車底間也需滿足必要的到達(dá)間隔。由列控系統(tǒng)引起的車站能力約束表示為

?p，p′∈P|p≠p′；s∈Sp∩Sp′且s?J

(13)

式中：M3可取為路徑p和p′所對(duì)應(yīng)列車始發(fā)時(shí)刻的較大值。此外，研究線路的車站一般不設(shè)置到發(fā)線，車底在車站到發(fā)和通過只能占用正線，同時(shí)，車底在車站折返除需占用正線以外，還需占用折返線。各車站的各條正線和折返線同一時(shí)間最多只允許1個(gè)車底占用，要求途經(jīng)同一條車站正線或折返線的兩相鄰車底應(yīng)滿足必要的發(fā)到間隔，即

?p，p′∈P|p≠p′；s∈Sp∩Sp′且s?J

(14)

s∈Sp∩Sp′且s?J

(15)

s∈Sp∩Sp′且s?J

(16)

?p，p′∈P|p≠p′；s∈Sp∩Sp′且s?J

(17)

2.5 兩階段算法

綜上，車底空駛出場(chǎng)路徑與時(shí)刻表綜合優(yōu)化問題可構(gòu)建為

M式(1)

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

簡單的車底空駛出場(chǎng)路徑問題可約簡為具有頂點(diǎn)約束的多商品網(wǎng)絡(luò)流問題，后者已被證明為NP-hard問題[8]，由此原問題本質(zhì)上是NP-hard的。然而，模型M為混合整數(shù)線性規(guī)劃模型，利用主流商業(yè)優(yōu)化軟件(CPLEX，GUROBI等)即可快速獲得中小規(guī)模問題的最優(yōu)解。通常研究線路的車場(chǎng)和折返站數(shù)量較少，且運(yùn)營時(shí)段初需要從車場(chǎng)發(fā)出車底進(jìn)行擔(dān)當(dāng)?shù)牧熊嚁?shù)量也不多，使得所有可行車底出場(chǎng)路徑的條數(shù)有限，原問題的規(guī)模是可控的。同時(shí)，線路上的非車場(chǎng)銜接站、非折返站和非列車始發(fā)站對(duì)車底出場(chǎng)方案無實(shí)質(zhì)影響，提前約簡這部分車站不會(huì)漏掉最優(yōu)出場(chǎng)路徑，并可進(jìn)一步減小原問題規(guī)模。此外，原問題為戰(zhàn)術(shù)層面決策，對(duì)模型求解無實(shí)時(shí)性要求，在合理時(shí)間內(nèi)求得最優(yōu)解即可。因此，借助于所提出的線性模型M，本文直接采用商業(yè)優(yōu)化軟件求解原問題。

3 案例分析

以某城市軌道交通線網(wǎng)中最繁忙線路實(shí)際數(shù)據(jù)為例，驗(yàn)證所提出方法的有效性。采用MATLAB 2015b編程所提出優(yōu)化方法，并調(diào)用CPLEX 12.6求解其中的優(yōu)化模型。所有計(jì)算在CPU為Inter Core i5-4590 3.3 GHz，內(nèi)存為16 GB的64位個(gè)人電腦上執(zhí)行。

3.1 案例描述

測(cè)試線路全長54 km，設(shè)車站39座，如圖4所示，2015年日均客流量達(dá)69.8萬乘次，全年客流量超2.5億乘次。全線分別在車站s3和s28附近設(shè)置車場(chǎng)j1和j2，車場(chǎng)信息見表2，其中前者只可檢修6編組車底，后者可檢修6編組和8編組車底。全線沿線共設(shè)置8個(gè)折返站，折返站信息見表3，所有折返站均為單向折返，其中可將車底從上行折返為下行的折返站3個(gè)，將車底從下行折返為上行的折返站5個(gè)，目前日常運(yùn)輸組織中啟用6個(gè)折返站，剩下2個(gè)備用。車站s11和車站s32設(shè)有渡線，可在特殊情況下分別發(fā)揮上行和下行折返站作用。折返站s28為車場(chǎng)銜接站，運(yùn)營時(shí)段前只用于車底出場(chǎng)，不辦理車底折返。

圖4 測(cè)試線路

表2 車場(chǎng)信息

表3 折返站信息

測(cè)試線路06：30開始運(yùn)營，選擇該線路某工作日的分號(hào)列車運(yùn)行圖進(jìn)行案例分析。運(yùn)行圖里共有31列列車(編號(hào)為1～31)需由運(yùn)營時(shí)段前從車場(chǎng)始發(fā)的車底擔(dān)當(dāng)，車底出場(chǎng)路徑與時(shí)刻表有待確定。同時(shí)，由問題定義研究時(shí)段結(jié)束時(shí)刻Te取為最晚的列車4的始發(fā)時(shí)刻06：43：55，在線路運(yùn)營開始時(shí)刻與研究時(shí)段結(jié)束時(shí)刻間，還有5列列車(編號(hào)為32～36)直接從車場(chǎng)始發(fā)，這些列車在車場(chǎng)的發(fā)車時(shí)刻及其至研究時(shí)段結(jié)束時(shí)刻的運(yùn)行路徑和途經(jīng)車站的到發(fā)時(shí)刻由運(yùn)行圖給定，是在安排前31列列車車底出場(chǎng)方案時(shí)需遵守的時(shí)空約束。

對(duì)于測(cè)試案例，現(xiàn)行基于經(jīng)驗(yàn)編制的車底出場(chǎng)方案如圖5所示，結(jié)合現(xiàn)場(chǎng)習(xí)慣，不展示車底在車場(chǎng)發(fā)車和在折返線作業(yè)的過程及到發(fā)時(shí)刻，同時(shí)，簡便起見，忽略研究時(shí)段結(jié)束時(shí)刻之后不屬于研究范疇的運(yùn)行線?，F(xiàn)行車底出場(chǎng)方案的統(tǒng)計(jì)信息見表4，其中，第1列為列車編號(hào)，第2～4列分別為列車始發(fā)站、始發(fā)方向及始發(fā)時(shí)刻，第5列為擔(dān)當(dāng)車底在車場(chǎng)的發(fā)車時(shí)刻，第6列為空駛距離，注意，后續(xù)計(jì)算結(jié)果只對(duì)前31列列車進(jìn)行統(tǒng)計(jì)和分析。設(shè)兩車場(chǎng)最早允許出車時(shí)刻為05：00，已知車站到達(dá)間隔和發(fā)到間隔分別為2.5 min和1.5 min，編號(hào)為20、26和31的列車需要8編組車底，其余列車需要6編組車底。

圖5 現(xiàn)行車底出場(chǎng)方案

表4 現(xiàn)行車底出場(chǎng)方案的統(tǒng)計(jì)

由圖5和表4可知，由經(jīng)驗(yàn)方法編制的車底出場(chǎng)方案中，車場(chǎng)j1和j2分別辦理9列和22列車底出場(chǎng)作業(yè)，其中，共14列車底采用折返路徑出場(chǎng)，17列車底采用直達(dá)路徑出場(chǎng)。車底總空駛距離為487 143 m，總空駛時(shí)間為1 256.58 min，車場(chǎng)發(fā)出首列車底出車時(shí)刻為5：19：10。因車場(chǎng)出車能力及車站能力限制，列車4需由配屬于車場(chǎng)j2的車底采用折返路徑出場(chǎng)擔(dān)當(dāng)，產(chǎn)生較長空駛距離和空駛時(shí)間。

3.2 計(jì)算結(jié)果

使用兩階段算法求解測(cè)試案例，尋找高質(zhì)量的車底出場(chǎng)方案，共生成車底出場(chǎng)路徑173條，從中剔除不合理路徑后，剩余可行出場(chǎng)路徑110條。所提出算法共耗時(shí)1 607 s收斂，其中第一和第二階段分別耗時(shí)1 604 s和3 s。優(yōu)化車底出場(chǎng)方案如圖6所示，相應(yīng)的統(tǒng)計(jì)信息見表5，簡便起見，表5僅給出前31列列車的車底出場(chǎng)方案。

圖6 優(yōu)化車底出場(chǎng)方案

表5 優(yōu)化車底出場(chǎng)方案的統(tǒng)計(jì)

由圖6和表5可知，從統(tǒng)計(jì)結(jié)果來看，優(yōu)化后，車場(chǎng)j1共辦理8列車底出場(chǎng)作業(yè)，車場(chǎng)j2共辦理23列車底出場(chǎng)作業(yè)，其中，共14列車底采用折返路徑出場(chǎng)，17列車底采用直達(dá)路徑出場(chǎng)。車底總空駛距離為465 933 m，總空駛時(shí)間為1 038.83 min，車場(chǎng)開始辦理車底出車作業(yè)的時(shí)刻為5：28：30。相比于現(xiàn)行方案，優(yōu)化出場(chǎng)方案中每日車底總空駛距離縮短21 210 m，縮短率為4.35%，預(yù)計(jì)全年空駛距離節(jié)省量將超過7 700 km，同時(shí)，車底總空駛時(shí)間節(jié)省217.75 min，節(jié)省率為17.33%，車場(chǎng)可推遲9.33 min開始辦理出車作業(yè)。

車底出場(chǎng)路徑方面，與現(xiàn)行方案比較，優(yōu)化方案在所有列車中僅對(duì)列車4、5、8、11、14和30的車底出場(chǎng)路徑進(jìn)行了調(diào)整。列車4、8和14的車底出場(chǎng)路徑由原來的折返路徑調(diào)整為直達(dá)路徑，共縮短空駛距離29 021 m。列車4的車底出場(chǎng)路徑由原始發(fā)于車場(chǎng)j2的折返路徑調(diào)整為始發(fā)于車場(chǎng)j1的直達(dá)路徑，空駛距離縮短13 875 m，占總空駛距離縮短量的65.4%，效果顯著。列車8和14的車底出場(chǎng)路徑由原始發(fā)于車場(chǎng)j1的折返路徑調(diào)整為始發(fā)于相同車場(chǎng)的直達(dá)路徑，空駛距離均縮短7 573 m。列車5、11和30的車底出場(chǎng)路徑由原來的直達(dá)路徑調(diào)整為折返路徑，共增加空駛距離7 811 m。列車30的車底出場(chǎng)路徑由原始發(fā)于車場(chǎng)j1的直達(dá)路徑調(diào)整為始發(fā)于相同車場(chǎng)的折返路徑，空駛距離增加7 573 m，變化明顯，但好處在于使得列車4可由更近車場(chǎng)j1的車底采用直達(dá)路徑進(jìn)行擔(dān)當(dāng)，縮短了總空駛距離。列車5和11原由始發(fā)于車場(chǎng)j1的車底通過直達(dá)路徑進(jìn)行擔(dān)當(dāng)，但空駛距離均較長，盡管優(yōu)化方案將這兩列列車的車底出場(chǎng)路徑都調(diào)整為始發(fā)于車場(chǎng)j2的折返路徑，但代價(jià)較小，空駛距離均只增加119 m。

從計(jì)算時(shí)間來看，第一階段模型的求解占據(jù)絕大多數(shù)時(shí)間，給定第一階段的最優(yōu)解，第二階段的輔助模型可極快求解。雖然所提出算法求解時(shí)間稍長，但原問題為戰(zhàn)術(shù)層面非實(shí)時(shí)決策問題，算法求解時(shí)間處于合理范圍。因此，所提出優(yōu)化方法能在合理時(shí)間內(nèi)獲得實(shí)際可行的車底出場(chǎng)方案，具有優(yōu)良的求解效果，優(yōu)于目前現(xiàn)場(chǎng)經(jīng)驗(yàn)方法，可用于輔助現(xiàn)場(chǎng)提高城市軌道交通線路運(yùn)營時(shí)段前車底出場(chǎng)方案的質(zhì)量，從而減輕工作負(fù)擔(dān)，節(jié)約運(yùn)營成本。

3.3 靈敏度分析

測(cè)試案例兩個(gè)車場(chǎng)的出車間隔有較大不同，使得這兩個(gè)車場(chǎng)可發(fā)出的車底數(shù)存在較大差異，由此可能導(dǎo)致部分列車因車場(chǎng)出車能力不足需由較遠(yuǎn)車場(chǎng)的車底進(jìn)行擔(dān)當(dāng)，增加總空駛距離和總空駛時(shí)間。此外，案例中有2個(gè)折返站未啟用，可能使得部分車底需去較遠(yuǎn)的折返站辦理折返?，F(xiàn)采用靈敏度分析方法探討可能進(jìn)一步縮短總空駛距離和總空駛時(shí)間的措施，分別為通過技術(shù)改造縮短車場(chǎng)出車間隔和啟用備用折返站。

3.3.1 縮短車場(chǎng)出車間隔

首先探討車場(chǎng)出車間隔對(duì)車底總空駛距離和總空駛時(shí)間的影響。測(cè)試案例中車場(chǎng)j2的出車間隔小，理論上已難以進(jìn)一步壓縮，因此，考慮只縮短車場(chǎng)j1的出車間隔，同時(shí)固定車場(chǎng)j2的出車間隔。根據(jù)測(cè)試線路信號(hào)部門的反饋意見，車場(chǎng)j1的出車間隔共設(shè)計(jì)以下四種情況：同向12 min，反向6 min；同向9 min，反向4.5 min；同向6 min，反向3 min；同向4 min，反向1.5 min。對(duì)于各種情況，保持其他參數(shù)設(shè)置不變，依次求解優(yōu)化模型，結(jié)果如圖7所示，其中，[12，6]表示同向和反向出車間隔分別為12 min和6 min的情況，縮短率和節(jié)省率分別表示總空駛距離和總空駛時(shí)間相對(duì)經(jīng)驗(yàn)方案的改進(jìn)比例。

(a)總空駛距離

(b)總空駛時(shí)間

由圖7可知，隨著車場(chǎng)出車間隔的減少，該車場(chǎng)出車能力逐漸增大，更多始發(fā)站在附近的列車可由該車場(chǎng)的車底擔(dān)當(dāng)，從而可縮短總空駛距離和總空駛時(shí)間。當(dāng)出車間隔由[12，6]縮短為[9，4.5]時(shí)，總空駛距離縮短率增量較為顯著，由4.35%增加為5.93%，總空駛時(shí)間節(jié)省率增量較為平緩。當(dāng)出車間隔由[6，3]進(jìn)一步縮短為[4，1.5]時(shí)，總空駛距離縮短率維持不變，而總空駛時(shí)間節(jié)省率增量較為明顯，由20.43%增長為27.67%。所有情況中兩個(gè)車場(chǎng)的檢修能力均存在富余?？傻贸鼋Y(jié)論，車場(chǎng)出車能力對(duì)車底總空駛距離和總空駛時(shí)間具有較大影響，在一定范圍內(nèi)縮短車場(chǎng)出車間隔能減少總空駛距離和總空駛時(shí)間。

車場(chǎng)出車間隔由車場(chǎng)的線路布置、信號(hào)條件及行車組織方法等因素決定，縮短車場(chǎng)出車間隔可采用許多技術(shù)改造和技術(shù)組織措施，不同的措施具有特有的技術(shù)條件要求、工程投資和適應(yīng)性，建議相關(guān)部門在設(shè)計(jì)車場(chǎng)出車間隔縮短方案時(shí)，先對(duì)候選方案進(jìn)行技術(shù)經(jīng)濟(jì)綜合比選，評(píng)估各候選方案的技術(shù)可行性、所需工程投資、以及縮短總空駛距離和總空駛時(shí)間所獲得的運(yùn)營節(jié)省，再從中選擇合理的方案。

3.3.2 啟用備用折返站

現(xiàn)探討啟用備用折返站對(duì)車底出場(chǎng)方案的影響。測(cè)試線路有兩個(gè)備用折返站s18和s35，均可將下行方向車底折返為上行。分析以下4種情況：不啟用備用折返站；啟用車站s18；啟用車站s35；啟用車站s18和s35。對(duì)于各種情況，不改變其他參數(shù)，求解優(yōu)化模型，結(jié)果如圖8所示，其中，{-}表示未啟用備用折返站，{s18}表示啟用折返站s18。

(a)總空駛距離

(b)總空駛時(shí)間

由圖8可以看出，單獨(dú)啟用折返站s35可在優(yōu)化方案基礎(chǔ)上進(jìn)一步縮短總空駛距離和總空駛時(shí)間，且對(duì)前者的優(yōu)化效果更為顯著，其增量達(dá)到8.24%。單獨(dú)啟用折返站s18不能進(jìn)一步縮短總空駛距離和總空駛時(shí)間，盡管同時(shí)啟用兩個(gè)備用折返站可進(jìn)一步提高出場(chǎng)方案質(zhì)量，但其優(yōu)化效果是由開通折返站s35所獲得的。由此可判斷，單獨(dú)啟用折返站s35能進(jìn)一步改善運(yùn)營時(shí)段前車底出場(chǎng)方案，考慮到開通備用折返站可能存在技術(shù)改造和費(fèi)用支出，建議相關(guān)部門在進(jìn)行技術(shù)經(jīng)濟(jì)比選后考慮是否啟用部分備用折返站。

4 結(jié)束語

本文提出城市軌道交通線路運(yùn)營時(shí)段前車底空駛出場(chǎng)路徑與時(shí)刻表綜合優(yōu)化方法。通過提前生成所有可行車底出場(chǎng)路徑，以車底出場(chǎng)總空駛距離和總空駛時(shí)間最小為目標(biāo)，滿足若干運(yùn)營和能力要求，構(gòu)建混合整數(shù)線性規(guī)劃模型。設(shè)計(jì)兩階段算法，以最小化車底在途總停站時(shí)間為目標(biāo)，對(duì)所得最優(yōu)解進(jìn)行二次優(yōu)化，盡量減少車底在途不必要的起停車作業(yè)，以提高獲得車底出場(chǎng)方案的實(shí)際可操作性。實(shí)際案例分析結(jié)果表明，所提出優(yōu)化方法可在合理時(shí)間內(nèi)獲得比現(xiàn)場(chǎng)經(jīng)驗(yàn)方法更優(yōu)的車底出場(chǎng)方案，可用于輔助實(shí)際決策。若技術(shù)經(jīng)濟(jì)條件允許，適當(dāng)提高瓶頸車場(chǎng)出車能力或者啟用備用折返站可進(jìn)一步提高車底出場(chǎng)方案的質(zhì)量。

本文致力于對(duì)運(yùn)營時(shí)段前車底空駛出場(chǎng)路徑與時(shí)刻表進(jìn)行綜合優(yōu)化，所提出模型對(duì)于大規(guī)模實(shí)際案例需要花費(fèi)相對(duì)較長的時(shí)間，未來有必要研究更有效的優(yōu)化算法，以進(jìn)一步加快尋找高質(zhì)量車底出場(chǎng)方案的效率。其次，論文研究宏觀的車底空駛出場(chǎng)路徑與時(shí)刻表問題，以正線和折返線集計(jì)表達(dá)車站級(jí)的基礎(chǔ)設(shè)施，下一步可以軌道電路為單元更為細(xì)致地建模車站的基礎(chǔ)設(shè)施，進(jìn)而研究微觀的車底出場(chǎng)路徑與時(shí)刻表綜合優(yōu)化方法。此外，勾畫完整的車底交路計(jì)劃需協(xié)調(diào)安排車底在運(yùn)營時(shí)段前集中出場(chǎng)、運(yùn)營時(shí)段內(nèi)分散出入場(chǎng)和運(yùn)營時(shí)段后集中入場(chǎng)3個(gè)走行過程，運(yùn)營時(shí)段內(nèi)考慮車底分散出入場(chǎng)走行的車底交路計(jì)劃問題以及集成全日車底出入場(chǎng)走行的車底交路計(jì)劃問題也是將來研究的方向。