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

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

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

2 模型構(gòu)建

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

2.1 邊界假定

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

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

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

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

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

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

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

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

2.3 約束條件

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

1）接續(xù)約束

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

2）檢修修制約束

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

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

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

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

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

3）檢修時(shí)間約束

式中：λjt和μkjt均為線性化描述模型而引入的0-1中間變量；Tkj為車底k進(jìn)行列檢的時(shí)長(zhǎng)。

4）基本約束

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

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

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

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

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

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

其中，

每列車底均返回其配屬車場(chǎng)列檢，即

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

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

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

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

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

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

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

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

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

3.1.1 編碼方法與編碼空間表達(dá)

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

圖2 編碼空間形式

3.1.2 初始方案

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

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

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

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

1）設(shè)計(jì)針對(duì)運(yùn)輸任務(wù)的算子

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

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

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

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

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

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

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

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

3）2種算子適用范圍

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

3.1.4 解的接受規(guī)則

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

3.1.5 算法終止準(zhǔn)則

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

3.2 算法步驟

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

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

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

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

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

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

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

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

4 算例分析

4.1 線路行車資料

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

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

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

表1 分段單線雙向全天候運(yùn)行模式下C站—D站某日夜間運(yùn)行計(jì)劃

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

表2 始發(fā)終到站站間走行里程和運(yùn)行時(shí)間

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

表4 車場(chǎng)配屬車底及列檢能力（8輛編組）

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

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

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

1）列檢能力配置不同時(shí)

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

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

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

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

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

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

圖9 車底運(yùn)用與檢修的部分方案

2）夜間車底運(yùn)用方式不同時(shí)

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

表5 夜間列車獨(dú)立運(yùn)用計(jì)劃

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

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

5 結(jié)語

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

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