彭其淵，廖珮茹，何必勝，李 力

（1.西南交通大學 交通運輸與物流學院，四川 成都 611756；2.西南交通大學 綜合交通運輸智能化國家地方聯(lián)合工程實驗室，四川 成都 611756；3.深圳市城市交通規(guī)劃設(shè)計研究中心股份有限公司 佛山分院，廣東 佛山 528010）

北京奧運會、廣州亞運會期間，當?shù)氐罔F都有過短期全天候運行的嘗試。為滿足城市居民夜間出行需求，國內(nèi)部分城市正在研究軌道交通線路采用常態(tài)化全天候運行模式的可行性，如正在建設(shè)中的雄安新區(qū)地鐵R1 線等［1］。在全天候運行模式下，部分車底夜間仍需擔當運輸任務(wù)，而車底的日常檢修作業(yè)也在夜間進行，為協(xié)調(diào)車底夜間的運用與檢修作業(yè)，減少因車底集中或提前檢修造成的運營時間損失和資源浪費，有必要對車底運用計劃與檢修計劃進行綜合優(yōu)化，但目前可供借鑒的研究成果非常有限。

非全天候運行條件下，城市軌道交通車底日間行車、夜間檢修，單日車底運用相互獨立，因此既有的車底運用優(yōu)化問題研究，如文獻［2-6］，一般對運用計劃和檢修計劃進行分別優(yōu)化。車底運用與檢修計劃一體化編制的研究對象主要是鐵路系統(tǒng)的日間動車組，如文獻［7-16］，求解日間動車組運用與檢修協(xié)同優(yōu)化問題的思路大致相同，都是將問題分解為2 個子問題，先固定動車組一級檢修范圍內(nèi)的基本交路（日間交路→一級檢修），再構(gòu)建完整循環(huán)交路。實踐中動車組夜間單次運輸任務(wù)的時間跨度和運行里程分別在6 h 和2 000 km 以上，在車底的2 次一級檢修之間，同1 列動車組同1 天只可能擔當1 次夜間運輸任務(wù)。鑒于此，文獻［17］在解決高速鐵路夜行車底運用與檢修計劃一體化編制問題時，將各夜間運輸任務(wù)套跑若干個日間短交路作為夜行動車組的基本交路（單次夜間運輸任務(wù)→日間短交路→一級檢修）。

不同于高速夜行動車組，城市軌道交通車底的單次運輸任務(wù)交路和一級檢修時間均較短，全天候運行車底在完成一級檢修后還能夠繼續(xù)承擔當日夜間運輸任務(wù)，其基本交路為“日夜交路→一級檢修→日夜交路”的形式，此時車底的檢修時機會影響到后續(xù)夜間運輸任務(wù)的執(zhí)行。而基于非全天候運行條件的研究中，可供車底檢修的時間范圍寬裕，無須關(guān)注各車底檢修時間的協(xié)調(diào)。因此，既有研究無法解決全天候運行條件下的城市軌道交通車底運用與檢修協(xié)同優(yōu)化問題，有必要研究適用于全天候運行條件下的城市軌道交通車底運用與檢修協(xié)同優(yōu)化問題的方法。

本文將全天候運行條件下的城市軌道交通車底運用與檢修協(xié)同優(yōu)化問題抽象為網(wǎng)絡(luò)流問題，根據(jù)行車計劃、車底檢修修制、車場檢修能力等，先構(gòu)建城市軌道交通車底運用與檢修的接續(xù)網(wǎng)絡(luò)；再引入檢修等待時間，用于衡量受車場檢修能力限制的實際檢修時間與預分配檢修時間兩者之間的偏離，及這一偏離對運營效益的不利影響；然后以包含檢修等待時間在內(nèi)的運營總成本最少為目標，基于網(wǎng)絡(luò)弧方法構(gòu)建城市軌道交通車底運用與檢修協(xié)同優(yōu)化的網(wǎng)絡(luò)流模型；最后設(shè)計大規(guī)模鄰域搜索算法求解模型。依托以雄安新區(qū)地鐵R1線為背景的算例，證明提出模型與算法的可行性與有效性。

1 協(xié)同優(yōu)化問題分析

1.1 問題描述

將全天候運行條件下的城市軌道交通車底運用與檢修協(xié)同優(yōu)化問題表述為：在資源配置和設(shè)施設(shè)備能力能夠同時確保運營安全與全天候運行的基礎(chǔ)上，在給定符合運能的全天候行車計劃與線網(wǎng)拓撲結(jié)構(gòu)的前提下，考慮制式相同且連通的線路間運力資源共用，統(tǒng)一調(diào)配同制式線路中的所有車底及相關(guān)資源，提前根據(jù)車底的檢修地點協(xié)調(diào)其承擔的運輸任務(wù)并且分配合適的檢修時機，實現(xiàn)運營綜合效益的最大化。該問題涉及各車底從多個車場出發(fā)，連續(xù)擔當一定里程或時間的運輸任務(wù)后均須前往車場檢修，最終返回各車場的全過程，類似于多源多匯最小代價流問題。

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

結(jié)合網(wǎng)絡(luò)優(yōu)化理論，將全天候運行條件下的城市軌道交通車底運用與檢修協(xié)同優(yōu)化問題抽象為網(wǎng)絡(luò)流問題。在車底從車場出發(fā)，擔當若干個任務(wù)后返回車場的過程中，車場以及運輸任務(wù)、檢修任務(wù)等研究對象可抽象為網(wǎng)絡(luò)中的節(jié)點，網(wǎng)絡(luò)中的弧便可用來表征研究對象間的關(guān)系，且所有弧的生成必須滿足對象間接續(xù)在時間與空間上的約束條件。顯然，該過程涉及出場弧、接續(xù)弧和入場弧這3類連接關(guān)系。其中：出場弧連接始發(fā)車場與運輸任務(wù)、檢修任務(wù)與運輸任務(wù)，對應(yīng)車底在場停放或檢修后繼續(xù)擔當運輸任務(wù)的情形；接續(xù)弧連接2 個不同的運輸任務(wù)，對應(yīng)車底連續(xù)承擔運輸任務(wù)的情形；入場弧連接運輸任務(wù)與回送車場、運輸任務(wù)與檢修任務(wù)，對應(yīng)車底連續(xù)擔當一定里程或時間的運輸任務(wù)后，入場停放或檢修的狀態(tài)。

構(gòu)建某城市軌道交通線路中車底運用與檢修的接續(xù)網(wǎng)絡(luò)G=（V，A，U，F(xiàn)，W），如圖1 所示。圖中：分別為集合V，VS，VT，VO和VM中的第i個節(jié)點；V為網(wǎng)絡(luò)G中所有節(jié)點的集合，包括始發(fā)車場集合VS、回送車場集合VT、運輸任務(wù)集合VO和檢修任務(wù)集合VM，即V=VS∪VT∪VO∪VM；A為網(wǎng)絡(luò)G中所有弧的集合；aij為相繼連接節(jié)點vi和vj的弧，aij∈A；U為各弧容量上限的集合，表示各弧可容納的最大車底數(shù)；uij為弧aij的容量上限，uij∈U，uij=1；F為各弧流量的集合；0-1 變量fij為弧aij上的流量，fij∈F，若車底相繼經(jīng)過節(jié)點vi和vj則fij=1，否則fij=0；W為弧上單位流量代價的集合，wij為弧aij上單位流量的代價，wij∈W。在圖1 的接續(xù)網(wǎng)絡(luò)中，始發(fā)車場和回送車場分別為網(wǎng)絡(luò)的源節(jié)點和匯節(jié)點，各運輸任務(wù)和檢修任務(wù)均為網(wǎng)絡(luò)的中間節(jié)點。

圖1 城市軌道交通車底運用與檢修協(xié)同優(yōu)化問題的接續(xù)網(wǎng)絡(luò)

考慮到運輸任務(wù)包含始發(fā)、終到站，始發(fā)、終到時刻和運行里程等信息，檢修任務(wù)包含檢修車場和檢修開始時刻等信息，基于接續(xù)網(wǎng)絡(luò)G，可將城市軌道交通全天候運行的車底運用與檢修協(xié)同優(yōu)化問題轉(zhuǎn)化為最小代價流問題。即：每1個從車場出發(fā)、經(jīng)過各任務(wù)節(jié)點最終回到車場的可行流都是1個完整的車次鏈，代表該車場中某車底1種可能的運用檢修方案；從各車場出發(fā)按規(guī)定合作訪問完規(guī)劃周期內(nèi)全部運輸任務(wù)節(jié)點的所有流即構(gòu)成問題的1 個可行解；問題的求解目標是找到符合相關(guān)約束條件的多個流，并要求符合約束的流的總代價最小。

2 模型構(gòu)建

根據(jù)構(gòu)建的城市軌道交通車底運用與檢修的接續(xù)網(wǎng)絡(luò)，建立基于網(wǎng)絡(luò)弧方法的軌道交通車底運用與檢修協(xié)同優(yōu)化的網(wǎng)絡(luò)流線性模型，以便對全天候運行條件下的軌道交通車底及檢修設(shè)備等資源進行合理的計劃和分配。

2.1 邊界假定

結(jié)合城市軌道交通全天候運行的車底運用與檢修計劃的編制條件及要求，對問題進行一定程度的限定與簡化，做出如下模型假設(shè)。

（1）所有車底均為固定編組。

（2）所有車底均返回配屬車場進行日常檢修，不考慮車底在非配屬車場檢修產(chǎn)生的額外溝通管理費用。

（3）車底運用只圍繞列檢進行協(xié)同優(yōu)化，不考慮車底日常檢修中的雙周檢、月檢和定期檢修。

（4）所有車底的出、入場與夜間運輸任務(wù)均不產(chǎn)生沖突。

（5）嚴格按照計劃運用車底，不同動態(tài)條件不會使原運用計劃產(chǎn)生偏離，且不考慮運用計劃的調(diào)整優(yōu)化。

2.2 變量與參數(shù)定義

為方便模型構(gòu)建研究對象間的數(shù)學關(guān)系，按照下述方法對各研究對象進行編號：

2.3 約束條件

根據(jù)全天候運行條件下城市軌道交通車底運用接續(xù)、車底檢修修制和設(shè)施設(shè)備能力的制約，對城市軌道交通車底運用與檢修協(xié)同優(yōu)化模型構(gòu)造以下4類約束條件。

1）接續(xù)約束

運輸任務(wù)間以及運輸任務(wù)與檢修任務(wù)間的接續(xù)應(yīng)至少預留在2個任務(wù)地點間的走行時間。

2）檢修修制約束

國內(nèi)城市軌道交通車底檢修普遍采用日常檢修和定期檢修相結(jié)合的計劃預防修檢修制度［23］，其中車底日常檢修包括列檢、雙周檢和月檢。因為雙周檢、月檢和定期檢修的檢修周期較長，受車底運用計劃編制效果的影響較小，所以模型僅考慮車底日常檢修中的列檢，協(xié)調(diào)各車底的列檢時機，使其同時滿足列檢的修制要求與夜間行車需求。

為判斷檢修狀態(tài)，計算每項任務(wù)vj（vj∈V）完成后自上一次列檢結(jié)束以來的累計運行里程Lj，任務(wù)間的走行里程lsia，sjd和任務(wù)交路長度lj均計入累計運行里程，每完成1 次列檢vi（vi∈VM）就對其Li清零，即

式中：lk為車底k在規(guī)劃時段開始時距上次列檢結(jié)束以來的累計運行里程；對于任務(wù)vj（vj∈VVO），其起點sjd和終點sja相同，均為vj對應(yīng)的車場，且車場交路長度lj取值為0。

每項任務(wù)vj（vj∈V）都應(yīng)滿足列檢修制規(guī)定，Lj不能超過LM；同時，車底k前后2 次列檢時間間隔應(yīng)不超過TM。即

式中：Gk為車底k的列檢周期序號集合；Nk為車底k的列檢周期數(shù)；tk為規(guī)劃周期開始時車底k的上一次列檢開始時刻；為車底k在第g個列檢周期內(nèi)能完成的運輸任務(wù)集合。

3）檢修時間約束

式中：λjt和μkjt均為線性化描述模型而引入的0-1中間變量；Tkj為車底k進行列檢的時長。

4）基本約束

結(jié)合最小代價流問題的規(guī)則與經(jīng)典車輛調(diào)度優(yōu)化問題［2］的特征，沿用以下基本約束。

每個車場的出發(fā)車底數(shù)應(yīng)少于該車場存車數(shù)，即

保證每個運輸任務(wù)節(jié)點都與且只與1 個前驅(qū)和后繼節(jié)點相連，每項運輸任務(wù)由且僅由1列車底完成，即

保證每個任務(wù)節(jié)點的前驅(qū)節(jié)點和后繼節(jié)點都由同一車場發(fā)出、由同一車底接續(xù)，且存在同一車底約束，即

每列車底至多連接1 條車次鏈且均從其配屬車場出發(fā)，即

每列車底完成任務(wù)后返回其始發(fā)車場，即

其中，

每列車底均返回其配屬車場列檢，即

保證各檢修任務(wù)只與構(gòu)造它的運輸任務(wù)接續(xù)，即

2.4 目標函數(shù)

結(jié)合實際分析可知：車底運營總費用由固定運營費用和可變運營費用組成，其中固定運營費用取決于車底使用數(shù)量，可變運營費用在列車運行計劃既定的條件下，主要取決于節(jié)點間總接續(xù)時間與車底總檢修時間；因列車運行圖固定，車底使用數(shù)量與節(jié)點間總接續(xù)時間和車底總檢修時間均成正比關(guān)系，且后者在數(shù)值上遠大于前者。因此，在滿足前述約束的前提下，可將模型目標從“使城市軌道交通車底運營總費用最少”簡化為“使車底運用與檢修的接續(xù)網(wǎng)絡(luò)節(jié)點間總接續(xù)時間及車底總檢修時間（包括檢修等待時間與檢修時間）最短”。

需要說明的是，檢修等待時間會干擾到承擔全天候運行列車交路的車底的夜間行車。因此，此類列車各時段的檢修等待時間均須計算運營費用；而其余車底在非運營時段內(nèi)的檢修等待時間可不計入運營費用。相應(yīng)地，可將弧（vi，vj）上單位流量的代價wij定義為弧（vi，vj）對應(yīng)的接續(xù)時間，并說明各弧對應(yīng)的wij為

得到該問題優(yōu)化模型的目標函數(shù)Z為

3 大規(guī)模領(lǐng)域搜索算法求解

我國城市軌道交通網(wǎng)絡(luò)化運營已成趨勢，隨著列車運營交路與開行對數(shù)的不斷增加，車底運用方案數(shù)呈爆炸式增長，城市軌道交通車底運用與檢修協(xié)同優(yōu)化問題屬于大規(guī)模的組合優(yōu)化問題，如何協(xié)調(diào)車底運用與檢修，制定相應(yīng)方案是非常困難的，因此可用于求解該問題的智能優(yōu)化算法長期受到國內(nèi)外學者的廣泛關(guān)注［2，4，12-13，19-20］。

考慮到大規(guī)模鄰域搜索算法被認為是針對車底運用問題在計算時間與求解質(zhì)量之間折中的最佳選擇［2］，且兼具通用性較強、易與其他智能化算法結(jié)合的特點，本文將采用這種算法設(shè)計出合理的鄰域搜索算子，在較短時間內(nèi)尋找到該問題的滿意解。解的優(yōu)劣程度根據(jù)目標函數(shù)評價，目標函數(shù)值越低說明相應(yīng)方案越優(yōu)。

3.1 大規(guī)模鄰域搜索算法要素

3.1.1 編碼方法與編碼空間表達

為使編碼和解碼的過程更加簡便，對算法采用實數(shù)編碼，各運輸任務(wù)對應(yīng)不同的實數(shù)，則解的編碼空間可表示為不同實數(shù)與列檢任務(wù)的組合。某城市軌道交通車底運用與檢修方案的編碼空間形式見圖2。圖中：J1和J3為在對應(yīng)的車場列檢；其余數(shù)字為運輸任務(wù)的編號；每1 行對應(yīng)規(guī)劃時段內(nèi)1 列車底的運輸檢修接續(xù)方案；編碼空間中所有車底的運用共同構(gòu)成問題的1個解。

圖2 編碼空間形式

3.1.2 初始方案

安排某列車底承擔1 組運輸任務(wù)，任意運輸任務(wù)的后續(xù)運輸任務(wù)在可接續(xù)運輸任務(wù)列表中尋找。為避免算法過早停滯，以μ為選擇范圍內(nèi)的運輸任務(wù)數(shù)，在接續(xù)時間最短的前μ個運輸任務(wù)中隨機選擇1個作為后續(xù)運輸任務(wù)。當分配完該列車底的運輸任務(wù)后，依次分析各列檢任務(wù)的插入位置，車次鏈中加入列檢任務(wù)可能造成原位置附近的運輸任務(wù)不可行。針對這種情況，結(jié)合列車類型、列檢時間、交路長度、場站距離以及行車密度等信息，合理判斷車次鏈中加入列檢任務(wù)后移除運輸任務(wù)數(shù)的上限，并對修改程度接近上限的車次鏈重新安排該列檢后的運輸任務(wù)，對僅小范圍調(diào)整的車次鏈直接移除列檢后的部分運輸任務(wù)。

按此思路，繼續(xù)為車次鏈中接近列檢修制要求的運輸任務(wù)安排列檢任務(wù)，直至該車次鏈中所有列檢任務(wù)安排完畢后，再重復所有步驟，生成車底運用與檢修的初始方案P。

3.1.3 鄰域和鄰域操作規(guī)則

方案P的鄰域N(P)由破壞解方法和重建解方法隱式定義：首先根據(jù)破壞解方法，破壞當前方案P中接續(xù)時間過長的運輸任務(wù)；然后用重建解方法，將其重建為新可行方案Pnew，Pnew∈N(P)。鄰域操作規(guī)則（又稱鄰域搜索算子）為P→N(P)的映射，算子構(gòu)造的優(yōu)劣直接影響最終求解的質(zhì)量，而鄰域搜索算子的設(shè)計本質(zhì)上是對破壞解方法和重建解方法的設(shè)計，具體如下。

1）設(shè)計針對運輸任務(wù)的算子

（1）破壞解方法。根據(jù)城市軌道交通線路配屬車數(shù)和行車量等信息，計算線路運輸任務(wù)間接續(xù)時間的合理范圍，并依此設(shè)定可接受的接續(xù)時間上限Δtaccpet，破壞當前方案P各車次鏈中運輸任務(wù)間接續(xù)時間超過Δtaccpet的運輸任務(wù)，其余運輸任務(wù)均按照一定的隨機概率被破壞，從而保證以任何方案作為鄰域搜索起點時的鄰域搜索空間始終覆蓋所有可能的方案。未被破壞的運輸任務(wù)可組成當前方案P中滿意的數(shù)個片段，將這些片段各自作為1個整體，連同被破壞的運輸任務(wù)一起，按重建解方法重新生成鄰域方案。

（2）重建解方法。重建解方法與生成初始方案的方法類似，依次為各車底構(gòu)建車次鏈，當車底k連續(xù)運行至超過修制規(guī)定時，即TM（tkj為車底k在完成運輸任務(wù)前上一次列檢入場時刻）或Lj＞LM時，拒絕當前運輸任務(wù)，插入轉(zhuǎn)去車場的列檢任務(wù)，列檢結(jié)束后再繼續(xù)為其分配運輸任務(wù)，如此反復直至所有運輸任務(wù)分配完畢，列檢開始時刻的計算方法見式（7）和式（8）。圖2 中運輸任務(wù)的鄰域交換規(guī)則可表示如圖3 所示。圖中：方框內(nèi)數(shù)字為wij≤Δtaccpet的滿意片段，并被保留到鄰域解中；點劃線表示任務(wù)間的接續(xù)關(guān)系；“×”表示wij＞Δtaccpet的接續(xù)關(guān)系被破壞，需在鄰域解中重新構(gòu)建。圖3 中原3 行的示例編碼經(jīng)交換變成2行，這種交換規(guī)則不同于常用的環(huán)形交換［21-22］，后者在求解較長規(guī)劃周期內(nèi)的大規(guī)模運輸任務(wù)分配時難以符合配屬車數(shù)要求，而前者對大范圍解的調(diào)整效率更高。

圖3 針對運輸任務(wù)的鄰域交換規(guī)則

2）設(shè)計針對列檢任務(wù)的算子

求解本文問題的關(guān)鍵是確定各車底配合運輸任務(wù)合適的檢修時間，為此，對每1個經(jīng)過運輸任務(wù)鄰域交換后生成的鄰域方案，再次進行列檢任務(wù)的鄰域搜索，旨在搜索列檢時間與運輸任務(wù)更加匹配的鄰域方案。此時搜索的起始方案中各次列檢時間已經(jīng)符合集中列檢時間和車場列檢能力的要求，在各次列檢時間可行的條件下，具體的搜索規(guī)則如下。

（1）在同類車底之間交換列檢時間后，各車次鏈中列檢時間的變化均會造成部分列檢任務(wù)附近的運輸任務(wù)不可行，因此運用破壞解方法剔除這些與車次鏈中新列檢時間沖突的運輸任務(wù)，再根據(jù)重建解方法將被破壞的運輸任務(wù)插入到車次鏈中。若該算子在方案接近滿意結(jié)果時表現(xiàn)較好，可通過多次調(diào)用該算子快速尋找到問題的滿意方案（本文對任一方案P滿意程度的界定，是依據(jù)方案P的配屬車數(shù)∑k和目標函數(shù)值ZP與理論目標值下限Z0的距離ZP—Z0綜合考慮的）。

（2）針對列檢任務(wù)的鄰域搜索類似于不同車底間以環(huán)狀方式替換列檢時間及列檢任務(wù)附近的若干運輸任務(wù)，將該鄰域替換規(guī)則作用于圖2 擴充后的運輸任務(wù)可表示如圖4所示。圖中：相同顏色表示同類型且配屬車場相同的車底間列檢時間替換以及新列檢時間附近的運輸任務(wù)重構(gòu)；箭頭表示車底間替換列檢時間。

圖4 針對列檢任務(wù)的鄰域替換規(guī)則

3）2種算子適用范圍

求解模型時配合使用上述2 種算子。在算法初期，當生成的方案需要大范圍調(diào)整重組時，前者對此表現(xiàn)較好；隨著生成的方案大部分可接受時，后者在小部分任務(wù)的調(diào)整上效率更高。同時，每搜索到若干個鄰域方案，就以歷代目標函數(shù)值最優(yōu)、次優(yōu)和第三優(yōu)的3 個方案Pfirst，Psecond和Pthird，作為候選方案和新的鄰域搜索起點，并隨著鄰域方案的積累，生成方案不斷改進，適當擴大Δtaccpet，以達到逐代減少破壞任務(wù)數(shù)量、縮小重建方案范圍、加快收斂速度的目的?？紤]到前期方案更改的程度較大、獲得的鄰域方案較少，且為了探索更好的鄰域方向而頻繁調(diào)用針對運輸任務(wù)的搜索算子，后期方案調(diào)整范圍縮小且積累了一定數(shù)量的鄰域方案，調(diào)節(jié)算法控制參數(shù)，減少對運輸任務(wù)的鄰域搜索，增加列檢任務(wù)鄰域搜索算子的調(diào)用，使檢修時間匹配到合適的運輸任務(wù)。

3.1.4 解的接受規(guī)則

求解過程中生成的任何方案，必須滿足4 個條件：所有運輸任務(wù)全部完成且僅完成1次；各車底列檢遵守修制及車場列檢能力的規(guī)定；任務(wù)接續(xù)符合時間、空間上的限制；使用的車底數(shù)不超過配屬的車底數(shù)。

3.1.5 算法終止準則

參考值差準則，記方案P的目標函數(shù)值為ZP，若每經(jīng)過若干次鄰域搜索后更新的3 個滿意方案Pfirst，Psecond和Pthird的目標函數(shù)值（分別為當前候選方案中目標函數(shù)的最小、最大取值，為歷次方案的平均目標函數(shù)值，α為可接受的精度誤差），則終止迭代。

3.2 算法步驟

基于上述算法的原理及相關(guān)規(guī)則的制定，大規(guī)模鄰域搜索算法求解全天候運行條件下的城市軌道交通車底運用與檢修協(xié)同優(yōu)化模型的具體步驟如下，算法流程如圖5所示。

圖5 大規(guī)模鄰域搜索算法流程

步驟1：初始化。給定線路設(shè)施布置、列車運行計劃、車底初始運用狀態(tài)和列檢修制等信息，并對各類型車底分別構(gòu)建描述運輸任務(wù)間接續(xù)關(guān)系的矩陣，記?vi∈VO可接續(xù)的運輸任務(wù)集合為Ai，車底k在規(guī)劃周期內(nèi)的任務(wù)接續(xù)方案為Hk，Hk=?，待完成的運輸任務(wù)集合為DO，DO=VO。初始化后轉(zhuǎn)步驟2。

步驟2：生成初始方案。首先構(gòu)建車底k的運輸任務(wù)序列并寫入Hk，然后對Hk插入列檢任務(wù)確保車底k完成運輸任務(wù)，最后更新待完成的運輸任務(wù)集合DOHk∩VO。按此思路，依次對每一個k分配Hk，直至DO=?、生成的車底運用與檢修初始方案P為各車底方案Hk的并集，轉(zhuǎn)步驟3。

步驟3：針對運輸任務(wù)的鄰域搜索。對當前最優(yōu)、次優(yōu)和第三優(yōu)的3 個候選方案Pfirst，Psecond和Pthird采用運輸任務(wù)搜索算子，分別對各自的運輸任務(wù)進行若干次鄰域搜索（按對應(yīng)順序定義為I1，I2和I3），為生成的鄰域方案Pnew中各次列檢的開始時刻，每生成1個鄰域方案Pnew就轉(zhuǎn)步驟4進行h次列檢任務(wù)的鄰域交換。當(I1+I2+I3)h次鄰域搜索完成后，更新Pfirst，Psecond和Pthird，轉(zhuǎn)步驟5。

步驟4：針對列檢任務(wù)的鄰域搜索。方案Pnew同類車底之間隨機交換在同一列檢日同車場列檢的時間，再移除與交換后的各次列檢開始時刻沖突的運輸任務(wù)，最后將被移除的運輸任務(wù)重建到車次鏈中。對方案Pnew重復該步驟h次，獲得多順序下的h種鄰域方案，轉(zhuǎn)步驟5。

步驟5：若滿足算法終止準則，輸出Pfirst作為最終方案，計算結(jié)束；否則轉(zhuǎn)步驟3。

特別說明，由于承擔全天候運行的列車交路的車底夜間仍有行車需要，而車場的列檢能力有限，為了不延誤該部分車底夜間行車、避免因檢修資源未及時分配增加車底配置數(shù)量，應(yīng)優(yōu)先滿足該部分車底的列檢需要，即首先對承擔全天候運行交路的車底按步驟3 確定交換列檢時間前的車底運用方案。再在列檢能力被全天候運行的車底優(yōu)先占用的限制下，對其余車底執(zhí)行步驟3任務(wù)的分配。

4 算例分析

4.1 線路行車資料

以雄安新區(qū)地鐵R1 線為背景進行全天候運行條件下的車底運用與檢修協(xié)同優(yōu)化。線路建設(shè)前期全長125.3 km，共設(shè)3個車場，A 站往D 站方向為下行方向，初期組織大小交路套跑，其中A 站—B站開行小交路，A 站—D 站開行大交路，C 站—D站通宵運營。線路布設(shè)如圖6所示。結(jié)合國內(nèi)外組織城市軌道交通全天候運行的經(jīng)驗，并考慮線路全天候常態(tài)化運行的實際與一定的通過能力需求，可將該算例視為1個分段單線雙向全天候運行模式協(xié)同優(yōu)化車底運用與檢修計劃問題。

圖6 線路布設(shè)示意圖

分段單線雙向全天候運行模式下，全天候運行的C 站—D 站區(qū)間每側(cè)正線被劃分為若干檢修段，在檢修天窗內(nèi)各檢修段輪流檢修，在檢路段按單線雙向模式組織運行，未檢修到的線路部分按照正常雙線運行模式。此時，C 站—D 站區(qū)間在夜間0：00—6：00時段每小時開行停1站列車與站站停列車各1對，均由時速250 km 的8編列車擔當，得到某日的夜間行車計劃見表1。全線日間不同區(qū)間列車開行對數(shù)不同、擔當列車速度不同，具體的日間行車計劃因篇幅暫不展示。車底夜間集中列檢時間定為22：00至次日4：00。

表1 分段單線雙向全天候運行模式下C站—D站某日夜間運行計劃

線路場站間走行里程和走行時間見表2和表3，8 編列車的列檢時間為50 min，列檢周期的走行里程間隔為4 000 km、運用時間間隔為2 d，車場配屬車底和列檢能力見表4。

表2 始發(fā)終到站站間走行里程和運行時間

表3 始發(fā)終到站與其聯(lián)通車場間的走行里程與運行時間

表4 車場配屬車底及列檢能力（8輛編組）

4.2 車底運用與檢修協(xié)同優(yōu)化實驗

按照前文構(gòu)建的模型與設(shè)計的算法，考慮到列檢周期與運算規(guī)模，以3 d 作為規(guī)劃求解周期，對全線所有列車編制車底運用與檢修計劃。實驗利用Python 軟件開發(fā)，在處理器為AMD Ryzen 7、內(nèi)存為16.0 GB 的計算機上完成。前100 次鄰域搜索時，Δtaccpet取20 min，并將部分車次間接續(xù)時間不超過Δtaccpet的運輸片段作為1 個任務(wù)整體，以歷代最優(yōu)、次優(yōu)、第三優(yōu)的3個候選解作為搜索起點并不斷重復迭代，每代依次對各自的運輸任務(wù)進行I1=3，I2=2 和I3=1 次鄰域搜索；隨著鄰域解的不斷積累，搜索方向逐漸優(yōu)化，后期將Δtaccpet增至30 min，將I1，I2和I3分別調(diào)整為2，1 和1。直到滿足算法終止條件，α取0.003。

為了驗證算法的有效性，調(diào)用CPLEX 12.8.0求解所構(gòu)建的模型。由于CPLEX 軟件難以快速求解大規(guī)模優(yōu)化問題，對于任務(wù)數(shù)達到1 000 以上的車底運用問題失效［4］，只能求解到該算例中1 d 的最優(yōu)車底運用方案，并獲得單日車次總接續(xù)時間下限為4 637.4 min。

1）列檢能力配置不同時

對R1 線車場按表4 充分配置列檢能力和配屬車數(shù)，對比僅針對運輸任務(wù)的鄰域搜索算法（記為“LNS 算法”）、加入列檢任務(wù)搜索算子后的鄰域搜索算法（記為“改進LNS 算法”）、遺傳算法（記為“GA 算法”）、變鄰域搜索（記為“VNS 算法”）的求解效果，迭代效果如圖7所示。

圖7 迭代效果對比（列檢能力充足）

由圖7 可知：4 種算法中，LNS 算法和改進LNS 算法的迭代效果相對更好；對于僅針對運輸任務(wù)的LNS算法，求解用時1 439.2 s，得到承擔3 d內(nèi)共1 104個運輸任務(wù)滿意的車底運用與檢修方案，滿意方案對應(yīng)的接續(xù)和檢修時間之和為15 031.6 min，對比CPLEX 最優(yōu)解結(jié)果，處在總時間下限值10%的波動范圍內(nèi)，說明該滿意方案非局部最優(yōu)解，但該算法在后期已難以搜尋到更優(yōu)的方案；對于綜合運用運輸任務(wù)和列檢任務(wù)2 種搜索算子的改進LNS 算法，能夠使各方案下的列檢時間匹配到更合適的運輸任務(wù)，提高了算法整體的尋優(yōu)效率，從而更快地接近方案的目標值下限，并且最終搜尋到的車底運用與檢修方案也更優(yōu)，方案總接續(xù)和檢修時間為14 418.1 min。

設(shè)置R1 車場列檢能力緊張場景，當J1，J2 和J3 車場的列檢能力分別取3，3 和4時，各算法的迭代效果如圖8 所示?？梢钥闯?，此時改進LNS算法的尋優(yōu)效果更為顯著。

圖8 迭代效果對比（列檢能力緊張）

最終確定的滿意解中，投入運用的承擔全天候運行任務(wù)的時速250 km 8 編列車共有18 列（其中J1 車場和J3 車場各9 列），與車場配屬運用車數(shù)相符；列檢能力充足和緊張時對應(yīng)的接續(xù)和檢修時間之和分別為14 418.1 min 和14 775.9 min。這18 列列車在規(guī)劃周期內(nèi)部分時段（第2 日18：00—第3日6：00）的車底運用檢修方案見圖9。圖中：縱向?qū)?yīng)不同的車底；藍色和灰色矩形分別表示運輸任務(wù)和列檢任務(wù)；橙色矩形表示各列檢任務(wù)前的等待時間；矩形中的數(shù)字為運行區(qū)間。由圖9可知：列檢能力充足時，車底因到達車場時間早于夜間集中列檢時間而產(chǎn)生等待，合理避免了受限于車場列檢能力的檢修等待；列檢能力緊張時，因車場列檢能力緊張，部分車底受限于車場列檢能力而產(chǎn)生額外的檢修等待，如車底9 須等待車底1 和車底3 列檢完成后才能進行檢修，車底11須等待車底5等。

圖9 車底運用與檢修的部分方案

2）夜間車底運用方式不同時

繼續(xù)沿用前文列車運行計劃，當夜間車底獨立運用，即另外配置車底專用于承擔夜間運輸任務(wù)，白天在場整備停留時，夜間需額外配置4 列車底，每列車底的具體運用計劃見表5。而在本算例設(shè)計的夜間高峰小時列車開行對數(shù)和交路周轉(zhuǎn)時間均未超過日間的條件下，車底日夜套跑運用時無須額外配置運用車就可以實現(xiàn)全天候運行（如圖9所示），能夠大幅提升運營綜合效益。

表5 夜間列車獨立運用計劃

3）全天候運行條件下配屬車數(shù)變化

城市軌道交通全天候運行下，車均日走行里程增加后，隨著夜間運輸任務(wù)連日積累，當出現(xiàn)以下情況時還是需要增加配屬車數(shù)：綜合考慮各交路高峰小時的列車開行對數(shù)和周轉(zhuǎn)時間2 項指標，當夜間行車量與交路長度增加到使這2 項指標的乘積大于日間的乘積時，需增加運用車數(shù)直至滿足夜間交路高峰小時的行車需求；檢修車數(shù)的變化由車均走行里程的增加情況決定，當夜間行車量與交路長度增加到使走行里程數(shù)成為計算車底檢修工作量的決定性指標時，檢修車數(shù)與車均走行里程成正比，需增加檢修車數(shù)直至保證夜間車底始終處于良好的運用狀態(tài)。

5 結(jié)語

城市軌道交通全天候運行模式下，車底夜間檢修與運用的矛盾突出，如何協(xié)調(diào)車底的檢修與運用，減少因車底集中檢修或提前檢修造成的運營時間損失和資源浪費具有重要意義。本文考慮制式相同且連通的線路間運力資源共用，統(tǒng)一調(diào)配同制式線路中的所有車底及相關(guān)資源，將全天候運行條件下的城市軌道交通車底運用與檢修協(xié)同優(yōu)化問題抽象為網(wǎng)絡(luò)流問題。先構(gòu)建城市軌道交通車底運用與檢修的接續(xù)網(wǎng)絡(luò)，再據(jù)此建立基于網(wǎng)絡(luò)弧方法的車底運用與檢修協(xié)同優(yōu)化的網(wǎng)絡(luò)流線性模型，對軌道交通車底及檢修設(shè)備等資源進行相應(yīng)的計劃和分配；在滿足接續(xù)約束、檢修修制約束、檢修時間約束和基本約束的前提下，將模型目標從“使城市軌道交通車底運營總費用最少”簡化為“使車底運用與檢修的接續(xù)網(wǎng)絡(luò)節(jié)點間總接續(xù)時間及車底總檢修時間最短”。最后基于大規(guī)模鄰域搜索算法設(shè)計合理的鄰域搜索算子，對模型進行求解。

以雄安新區(qū)地鐵R1 線為背景算例分析表明：本文構(gòu)建的城市軌道交通車底運用與檢修協(xié)同優(yōu)化的網(wǎng)絡(luò)流線性模型和設(shè)計得到的兼顧運輸任務(wù)和列檢任務(wù)的大規(guī)模鄰域搜索算法，能夠以盡可能少的車底按照接續(xù)時空條件完成規(guī)定的所有運輸任務(wù)；同時算法的尋優(yōu)效果更為顯著，不但能夠更快地接近方案目標值下限，并且得到方案中的車底檢修符合修程修制、檢修時段和車場檢修能力的限制，有效地解決了實際城市軌道交通全天候運行下的車底運用與檢修計劃協(xié)同優(yōu)化問題；通過對比充足、緊張2 種列檢能力下求得的車底運用和檢修方案，可以發(fā)現(xiàn)車場在列檢能力緊張時會出現(xiàn)車底檢修等待時間增加和夜間車底獨立運用時配屬車數(shù)增加的情形，因此建議全天候運行條件下，車場組織日夜套跑運用時應(yīng)按全天候運行需求配置運用車底和檢修資源。