鐘慶偉 ，張永祥 ，王 典 ，殷 勇 ，閆 旭 ，彭其淵

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

動車組作為重要的移動設(shè)備資源，是執(zhí)行列車運(yùn)行圖的最終載體. 動車組主要由動車段及其下屬的動車運(yùn)用所負(fù)責(zé)管理，通常情況下其運(yùn)用計劃等由動車調(diào)度員進(jìn)行編制. 隨著我國高速鐵路路網(wǎng)規(guī)模的擴(kuò)大，動車段（所）及動車組的數(shù)量也不斷增加，如何合理地使用動車組資源成為了鐵路公司關(guān)注的一個科學(xué)難題[1]. 目前，現(xiàn)場動車調(diào)度員先根據(jù)發(fā)布的運(yùn)行圖編制動車組交路計劃（即一組有序列車車次的集合），然后以固定的動車組交路計劃為基礎(chǔ)，在考慮不同等級維修限制的條件下編制動車組運(yùn)用計劃（即運(yùn)用計劃與檢修計劃的協(xié)同編制）. 當(dāng)下，全國正在推廣實施列車運(yùn)行圖的“一日一圖”編制方法[2]，動車組運(yùn)用的相關(guān)計劃也將隨之進(jìn)行動態(tài)調(diào)整. 在復(fù)雜高鐵網(wǎng)絡(luò)背景下，人工經(jīng)驗編制方法難以滿足時效性要求，且編制的計劃質(zhì)量及各計劃間的協(xié)調(diào)程度也難以得到保證. 因此，有必要借助數(shù)學(xué)優(yōu)化方法對日益復(fù)雜的高速鐵路動車組運(yùn)用問題進(jìn)行研究.

過去數(shù)十年，動車組運(yùn)用計劃的編制得到了國內(nèi)外學(xué)者的廣泛關(guān)注. 文獻(xiàn)[3]以早高峰時期的座位短缺最少為優(yōu)化目標(biāo)，研究了動車組的分配問題；文獻(xiàn)[4-5]引入了動車組的改編作業(yè)；文獻(xiàn)[6-7]以固定的動車組交路計劃為基礎(chǔ)，通過對動車組交路計劃的調(diào)整，引入動車組的距離維修約束. 類似的研究還有文獻(xiàn)[8-9]，在交路調(diào)整過程中加入了時間和距離維修約束；文獻(xiàn)[10]以動車組可行運(yùn)用計劃為決策變量，以最大化待檢動車組檢修前的累計運(yùn)行里程為目標(biāo)，建立了檢修計劃優(yōu)化模型，并設(shè)計了分支定價算法求解；文獻(xiàn)[11-12]研究了動車組的運(yùn)用與檢修計劃的優(yōu)化編制方法，從接續(xù)網(wǎng)絡(luò)和離散處理的角度分別構(gòu)建了0-1整數(shù)規(guī)劃模型，并設(shè)計了基于粒子群算法的求解策略；文獻(xiàn)[13]以復(fù)合網(wǎng)絡(luò)（hypergraphs）為基礎(chǔ)描述動車組運(yùn)用問題，并考慮了動車組運(yùn)用的時間和距離維修約束.

文獻(xiàn)[3, 8-12]未考慮動車組的重聯(lián)和摘解作業(yè)；文獻(xiàn)[3-4]未考慮動車組的維修限制；文獻(xiàn)[6-7, 9-12]僅考慮了車輛的距離檢修約束，與目前動車組的實際運(yùn)用條件有所差異；文獻(xiàn)[9]未對動車組進(jìn)行分類；文獻(xiàn)[4-5, 10-12]中考慮的路網(wǎng)結(jié)構(gòu)較為簡單；文獻(xiàn)[3-5, 10-12]在進(jìn)行動車組運(yùn)用計劃的編制時，均以動車組交路計劃作為已知輸入，這種做法適合長期的周期性運(yùn)行圖，能夠計算一段時間內(nèi)的動車組運(yùn)用計劃方案，當(dāng)列車運(yùn)行圖臨時更換或調(diào)整時，對應(yīng)的交路方案也將發(fā)生變化，從而影響上述文獻(xiàn)中根據(jù)固定交路計劃編制的運(yùn)用計劃的可行性；文獻(xiàn)[8-9]與本文的出發(fā)點(diǎn)相似，都沒有使用固定的動車組交路計劃作為輸入，不同之處在于文獻(xiàn)[8-9]采用啟發(fā)式方法生成交路段，然后進(jìn)行交路段的重新組合，而本文則是在考慮多個實際運(yùn)營約束的條件下基于列車車次生成可改編路徑；文獻(xiàn)[13]在求解實際規(guī)模的問題時需要耗費(fèi)較長時間.

綜上，既有研究文獻(xiàn)有待完善之處主要體現(xiàn)在：1） 問題設(shè)定的條件較為簡單，如僅考慮單方面的動車組維修約束、路網(wǎng)結(jié)構(gòu)簡單及無改編作業(yè)等；2） 多將動車組交路計劃作為已知輸入，不能很好地適應(yīng)運(yùn)行圖臨時更換或調(diào)整的情況；3） 未對動車組進(jìn)行類別劃分或僅以動車組類別為研究單元來添加維修約束，不能精確地描述不同類型的單個動車組在執(zhí)行任務(wù)前的初始狀態(tài)；4） 模型和算法復(fù)雜，實際應(yīng)用的計算時間較長. 因此，本文針對運(yùn)行圖臨時更換或調(diào)整的情況，研究包含多動車（段）所、多車種的高速鐵路網(wǎng)絡(luò)中帶時間和距離日常檢修限制的動車組運(yùn)用計劃編制問題. 與基于固定交路段的研究不同，本文基于列車車次進(jìn)行建模，能夠靈活地應(yīng)對運(yùn)行圖臨時更換或調(diào)整. 為提高求解效率，還設(shè)計了一個基于路徑生成的迭代逼近算法框架. 最后，文中所建立的模型能夠靈活地控制動車組的改編策略，更加適合未來的動車組靈活編組模式[14-15].

1 問題描述

在實際生產(chǎn)運(yùn)營過程中，當(dāng)列車運(yùn)行圖臨時更換或調(diào)整時，相應(yīng)動車段（所）的動車調(diào)度員就需要基于當(dāng)前的動車組配屬、運(yùn)用及檢修等情況，結(jié)合列車運(yùn)行圖要求，快速地制定短期的動車組運(yùn)用計劃（通常為動車組運(yùn)用日計劃）. 如前文所述，此時就需要進(jìn)行動車組交路計劃、日常檢修計劃及運(yùn)用計劃的協(xié)同優(yōu)化編制.

以包含5個車站、1個動車運(yùn)用所、14條列車運(yùn)行線以及2種不同類型動車組所構(gòu)成的高速鐵路網(wǎng)絡(luò)為例進(jìn)行說明，如圖1所示. 圖中：s1～s5為車站，綠色虛線為動車所銜接站，配有長度為15 km的出入線，其他車站為藍(lán)色實線；1～14為列車運(yùn)行線編號；Ⅰ、Ⅱ分別代表一列8編組和一列重聯(lián)16編組的動車組，動車組的數(shù)量由列車運(yùn)行線的預(yù)測客流量決定；“1-Ⅱ”代表列車車次1需要一列重聯(lián)16編組的動車組擔(dān)當(dāng)，其余類推；運(yùn)營時間段為06：00—24：00. 原則上所有的動車組在運(yùn)營時段結(jié)束后返回動車所進(jìn)行相應(yīng)的檢修作業(yè). 實際運(yùn)營中，由于某些運(yùn)行線的走行距離較長，可能會出現(xiàn)動車組在配屬所外過夜的情況. 兩種類型的動車組服務(wù)于該路網(wǎng)，動車組單元類型、累積運(yùn)行時間、運(yùn)行里程等基本信息如表1所示. 其中AL類動車組一旦出所其編組保持不變，A類動車組能夠在配備動車所連接線的車站返回到動車所進(jìn)行改編. 同種類型的動車組之間能夠進(jìn)行改編.

圖1 列車時刻表及站間距信息Fig. 1 Information of timetable and interval of stations

根據(jù)圖1中列車運(yùn)行圖要求以及動車組單元的初始狀態(tài)，在不違反日常檢修規(guī)定（即動車組單元累積運(yùn)行時間不超過2 d，且累積運(yùn)行里程不超過5000 km）時，可獲得多種動車組運(yùn)用計劃. 以列車運(yùn)行線為節(jié)點(diǎn)、列車運(yùn)行線間的可行接續(xù)關(guān)系為弧，將運(yùn)行圖抽象為動車組接續(xù)網(wǎng)絡(luò)圖，基于該接續(xù)網(wǎng)絡(luò)的3種可行計劃方案如圖2所示. 圖中：D為動車段（所）；中括號中的路徑為對應(yīng)各動車組單元的路徑詳情；各方案的空駛線、動車所連接線、段外過夜線有多種顏色，以區(qū)分不同的路徑.

表 1 動車組單元基本量信息Tab. 1 Basic information of EMUs

圖2 3種可行的動車組運(yùn)用計劃方案示例Fig. 2 Three kinds of possible train-set scheduling

以圖2（a）中路徑D—1—9—D為例，該路徑表示從D出發(fā)，完成運(yùn)行線1和運(yùn)行線9然后返回D，由于運(yùn)行線1和運(yùn)行線9的始發(fā)/終到車站都沒有動車所連接線，因此該路徑包含部分空駛. 根據(jù)動車組單元的自身初始狀態(tài)，可由1號與2號動車組單元重聯(lián)完擔(dān)當(dāng)該路徑任務(wù). 對于包含多動車段（所）、多車種的復(fù)雜高速鐵路網(wǎng)絡(luò)而言，由運(yùn)行圖中運(yùn)行線任務(wù)可產(chǎn)生數(shù)萬種可行的動車組路徑方案，再結(jié)合各動車組的初始狀態(tài)及維修限制條件，調(diào)度員很難憑借經(jīng)驗在短時間內(nèi)編制一個高質(zhì)量的動車組運(yùn)用計劃，由此說明了本文研究的必要性.

2 基于列車車次的優(yōu)化模型建立

在復(fù)雜高鐵網(wǎng)絡(luò)下，考慮運(yùn)行時間和距離維修約束且包含改編作業(yè)的動車組運(yùn)用優(yōu)化問題是一類較為復(fù)雜的組合優(yōu)化問題[11,14]. 為了降低問題的求解難度，在此將整個問題（whole problem，WP）分解為主問題（master problem，MP）模型和子問題（subproblem，SP）模型兩部分. 其中，MP是基于多商品網(wǎng)絡(luò)流理論建立的混合整數(shù)線性規(guī)劃模型，其目的是生成多種備選的可改編動車組路徑方案. SP是動車組可行路徑分配模型，其作用主要是根據(jù)動車組的運(yùn)行時間和距離維修約束來檢驗和挑選備選路徑方案中的合理路徑. MP模型和SP模型之間以特定的過程進(jìn)行迭代，逼近全局最優(yōu)解，見第3節(jié)的迭代算法框架.

2.1 建模假設(shè)

便于問題的建模及描述，進(jìn)行以下假設(shè)：

假設(shè)1列車運(yùn)行線及其對應(yīng)的預(yù)測客流量大小由列車運(yùn)行圖確定，其中客流量大小轉(zhuǎn)換為符合運(yùn)營規(guī)定的動車組編組方式.

假設(shè)2動車組可在具備條件的特定車站停放過夜，過夜停留時間均為6 h，由調(diào)度員給出可行的備選過夜運(yùn)行線集合.

假設(shè)3動車組采用不固定區(qū)段的運(yùn)營模式，空車調(diào)撥可在動車所之間、從動車所始發(fā)以及終到動車所時進(jìn)行. 空駛運(yùn)行線集合根據(jù)運(yùn)行線可行接續(xù)關(guān)系提前生成.

假設(shè)4每個動車所都能進(jìn)行不同種類的動車組改編作業(yè)，動車組從動車所始發(fā)或終到動車所時需要進(jìn)行相應(yīng)的改編作業(yè).

假設(shè)5研究過程中僅考慮動車組的日常檢修限制條件，具體維修作業(yè)細(xì)節(jié)不作研究.

2.2 MP模型：可改編路徑方案生成模型

2.2.1 符號說明

定義集合及索引：B、b分別為動車所集合和索引，b∈B；U、u分別為動車組型號集合和索引，u∈U；M、m分別為動車組編組方式集合和索引，m∈M；T、t分別為列車運(yùn)行線集合和索引，t∈T；Tf、Te、Tn分別為圖定列車運(yùn)行線集合、可用空駛運(yùn)行線集合、可用過夜運(yùn)行線集合，Tf∪Te∪Tn=T；C、c分別為所有可行的列車運(yùn)行線接續(xù)組合集合和索引，c∈C.

定義參數(shù)：Γ、τ分別為計算時間范圍和時刻；fc、sc分別為c中的第1個和第2個列車運(yùn)行線；Zc,m,m′為c對應(yīng)的所有可能動車組編組方式，其中m和m′分別 為 組合c中fc和sc的編 組 方式；Nu,b,1、Nu,b,2分別為運(yùn)營開始前和運(yùn)營結(jié)束后b中u型號動車組的數(shù)量；αc,m,m′為c中從m改編為m′所產(chǎn)生的費(fèi)用；βt,m為t上使用m的費(fèi)用； ε、ξ、ζ分別為動車所存車數(shù)偏離期望、總空駛里程以及總過夜時間的懲罰參數(shù)；Nu,m,m′,1、Nu,m,m′,2分別為從m改編為m′時重聯(lián)和摘解的u型號動車組數(shù)量；ηc、μc分別為c中摘解完畢時刻和重聯(lián)完畢時刻；lt、At、Dt、ρt分別為t的運(yùn)行距離、終到車站、始發(fā)車站和過夜時間；Nm為m中需要的動車組單元數(shù)量；eu,b為b中u型號動車組的容量限制.

定義變量：yt,m為0-1決策變量，若t的編組方式為m，值取1，否則取0；Ju,b為整數(shù)變量，代表b在運(yùn)營時間段結(jié)束后u類型動車組偏離期望的數(shù)量；Fc,m,m′為0-1決策變量，若m和m′分別為c中fc和sc的編組方式，值取1，否則取為非負(fù)整數(shù)變量，分別代表c中u類型動車組重聯(lián)和摘解的數(shù)量；qb,c,u、gb,c,u為0-1決策變量，分別代表c中重聯(lián)和摘解的u類型動車組是否來自b，若是，值取1，否則取0；wτ,u,b為非負(fù)整數(shù)變量，代表在時刻τ動車所b內(nèi)u型號動車組的數(shù)量；σ 、 λ為整數(shù)輔助變量 ，分別為動車組總空駛里程及動車組總過夜時間.

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

如式（1）所示，MP模型目標(biāo)函數(shù)為最小化動車組運(yùn)行成本、改編成本，并通過降低動車組非生產(chǎn)使用時間的占比（減少動車組的總空駛里程）來提高運(yùn)用效率. 此外，對動車組在動車所外過夜及動車所庫存不均衡的情況進(jìn)行懲罰. 為了統(tǒng)一目標(biāo)函數(shù)各部分的單位，通過設(shè)置懲罰參數(shù)將總空駛里程等轉(zhuǎn)化為綜合運(yùn)營費(fèi)用. 總空駛里程和總過夜時間可根據(jù)最終使用的運(yùn)行線進(jìn)行計算.

式中：zMP為MP模型的目標(biāo)函數(shù)；σ 和 λ可根據(jù)最終使用的運(yùn)行線進(jìn)行計算[16].

2.2.3 約束條件

1） 運(yùn)行線擔(dān)當(dāng)唯一性約束

定義第1天和第2天需要完成的列車運(yùn)行線集合分別為T1和T2，第1天需要完成的列車運(yùn)行線t∈T1，對應(yīng)第2天列車運(yùn)行線t′∈T2. 為了完成一天內(nèi)列車運(yùn)行圖中所有需要擔(dān)當(dāng)?shù)牧熊囘\(yùn)行線，T1∪T2中相互對應(yīng)的列車運(yùn)行線有且只有某一動車組擔(dān)當(dāng)，即

空駛列車運(yùn)行線以及過夜運(yùn)行線在運(yùn)營過程中至多被使用一次，即

式中：t需滿足

2） 動車組接續(xù)平衡約束

為了保證動車組運(yùn)用的接續(xù)平衡關(guān)系，需要滿足式（4）、（5）.

式（4）、（5）中：t需滿足At,Dt?B；式（4）中c需滿足fc=t，同時其第1個和第2個列車運(yùn)行線的編組方式組合為可行的組合，即 (m,m′)∈Zc,m,m′；同理，式（5）中c需滿足

3） 動車所庫存能力限制約束

動車組在動車所內(nèi)庫存數(shù)量的變化與動車組的改編作業(yè)相關(guān)，列車運(yùn)行線接續(xù)組合中某類型動車組重聯(lián)和摘解的數(shù)量分別為

式（6）、（7）中：c需滿足(m,m′)∈Zc,m,m′.

動車所b內(nèi)在時刻τ的u型動車組單元數(shù)量為

式中：c1～c4為C的索引，用不同符號以示區(qū)分；c1需滿足Dfc1=b且 ηc1≤τ；c2需滿足Asc2=b且 μc2≤τ；c3需滿足fc3,sc3∈Tf且 μc3≤τ；c4需滿足fc4,sc4∈Tf，且

式（8）中使用的動車組單元被分成僅在動車所始發(fā)、終到時進(jìn)行改編作業(yè)的動車組單元和包含額外改編作業(yè)的動車組單元. 動車所內(nèi)某類型動車組單元的容量限制為

4） 動車所庫存平衡約束

任一動車所b內(nèi)某類型的動車組單元偏離期望值的數(shù)量為

式 中： Γ0和 Γ1分別為計算時間段的結(jié)束和開始時刻.

2.3 SP模型：帶維修約束的動車組指派模型

2.3.1 符號說明

定義集合及索引：R、r分別為動車組單元集合和索引，r∈R；Pr、p分別為r的所有路徑集合和索引，p∈Pr.

定義參數(shù)：ar為r的啟動費(fèi)用，根據(jù)每個動車組單元根據(jù)的自身狀態(tài)不同設(shè)置相應(yīng)不同的啟動費(fèi)用；kr、lr分別為r的初始累積運(yùn)行時間和初始累積運(yùn)行距離，需在完成檢修后重置；ur、br分別為r的類型和初始停放動車所；up、bp、hp分別為p所要求的動車組類型、始發(fā)動車所和運(yùn)行時間；mt為t的圖定動車組編組要求；ot,p為0-1參數(shù)，當(dāng)t是p的一部分時，值取1，否則取0.

定義變量：xp,r為0-1變量，若r擔(dān)當(dāng)路徑p時，值取1，否則取0.

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

在SP模型目標(biāo)函數(shù)中引入一個虛擬啟動費(fèi)用，并規(guī)定啟用新的動車組單元（剛完成一級維修的動車組單元）有更高的啟動費(fèi)用. 通過最小化動車組的虛擬啟動費(fèi)來充分使用動車組，即

式中：zSP為SP模型的目標(biāo)函數(shù).

2.3.3 約束條件

包含列車運(yùn)行線覆蓋、路徑唯一性、時間和距離維修限制約束3類約束，如式（12）～（15）.

式（12）滿足每個列車運(yùn)行線的編組要求；式（13）保證一個動車組單元最多分配一條可行路徑；式（14）和式（15）分別保證每一個動車組單元在執(zhí)行任務(wù)的過程中均滿足其日常檢修的時間和距離維修約束，其中r和p需滿足

3 基于路徑生成的迭代逼近算法

算法框架包含3部分，除了上述已經(jīng)介紹的MP模型和SP模型部分，還有一個連接（connection part，CP）模型部分. CP是基于深度搜索的路徑生成模型，目的是將MP模型生成的每種備選動車組路徑方案中的路徑轉(zhuǎn)換為單個動車組單元的可行路徑集合. 整個迭代算法的框架如圖3所示，圖中：n為迭代循環(huán)次數(shù)；M為1次迭代過程中MP模型產(chǎn)生的備選交路計劃方案數(shù)（解池填充次數(shù)）；U0為整個問題的上界值.

圖3 基于路徑生成的迭代逼近算法流程Fig. 3 Flow chart of iterative gap reducing algorithm

3.1 WP有效下界證明

圖3中MP模型可以為WP提供下界L0，而在MP模型產(chǎn)生的可行解集合中能夠通過SP模型檢驗的可行解為WP提供上界U0，從而算法框架可以通過不斷地更換上、下界之間的最優(yōu)間隙W0，迫使產(chǎn)生更接近于下界的新可行解. 定義zWP為 WP模型目標(biāo)函數(shù)，為MP模型的任一可行解為不考慮維修限制的WP（稱為RWP）的任一可行解，為WP的任一可行解. 不難理解，若松弛SP模型中的維修限制條件，則通過CP模型轉(zhuǎn)換后都是松弛維修限制后的SP模型的可行解，此時；若SP模型中保留維修限制條件，則MP模型獲得的可行解集合中通過CP模型轉(zhuǎn)換后能夠通過SP模型檢驗的可行解才是WP的可行解不難推出，WP的解空間屬于MP模型的解空間，即由于WP是求目標(biāo)函數(shù)值最小的優(yōu)化問題，所以此時MP模型的最優(yōu)解就是WP的下界.

3.2 CP模型主要步驟

步驟1根據(jù)MP模型決策變量取值Fc,m,m′明確列車車次之間的接續(xù)關(guān)系及其動車組編組方式，以動車所為起點(diǎn)、終點(diǎn)搜索獲得的路徑集合F.

步驟2將獲得的路徑集合F分為兩部分，即僅在動車所始發(fā)、終到時產(chǎn)生改編作業(yè)的路徑集合F1（如圖2中的路徑D—3—5—12—14—D）和包含額外改編作業(yè)的路徑集合F2（如圖2中的路徑D—3—5—7—8—11—13—D）. 以運(yùn)行線編號索引為點(diǎn)V，列車運(yùn)行線接續(xù)組合為邊E，構(gòu)建有向圖G=(V,E) . 對任一f1∈F1，根據(jù)MP的變量yt,m提供的運(yùn)行線動車組編組方式，將f1分解為單個動車組單元的路徑p1，并得到路徑集合P1. 對任一f2∈F2，根據(jù)MP模型變量qb,c,u、gb,c,u獲取額外改編作業(yè)對應(yīng)的動車所相關(guān)信息，然后向G中添加新的有向邊.以動車所為起點(diǎn)和終點(diǎn)，采用改進(jìn)的深度搜索算法搜尋路徑p2，并得到路徑集合P2.

步驟3對路徑集合P0=P1∪P2中的路徑進(jìn)行統(tǒng)一編號，構(gòu)建新的有向圖G′=(V′,E′) ，其中點(diǎn)V′為路徑的索引，邊E′為路徑之間可行接續(xù). 以動車所為起點(diǎn)和終點(diǎn)，采用改進(jìn)的深度搜索算法搜尋完整路徑集合Pr.

3.3 多日計劃求解方法

多日計劃有以下兩種方法可以實現(xiàn)：

1） 在MP模型中導(dǎo)入多日的運(yùn)行圖數(shù)據(jù). 在CP模型生成路徑集合時，根據(jù)計算周期及對應(yīng)的維修等級，向每條路徑添加可行的維修弧，然后更改對應(yīng)SP模型中的維修約束進(jìn)行計算.

2） 選取獲得的任一可行運(yùn)用計劃中的動車組路徑集合，將該路徑集合作為固定動車組交路，然后更改SP模型的維修限制條件（需增加新的累積變量和可行維修弧）進(jìn)行計算. 此方法類似人工編制的流程，即先確定交路計劃，然后在考慮相應(yīng)等級維修限制的情況下進(jìn)行長時間段的動車組運(yùn)用計劃編制.

3.4 計劃調(diào)整優(yōu)化方法

若某日列車運(yùn)行圖已經(jīng)執(zhí)行了一部分時突然需要進(jìn)行調(diào)整，此時只需要在MP模型中根據(jù)已經(jīng)執(zhí)行的運(yùn)行線信息，固定對應(yīng)的決策變量Fc,m,m′和wτ,u,b的取值，即

式（16）、（17）中：c為已執(zhí)行列車運(yùn)行線構(gòu)成的接續(xù)組合，即fc,sc∈Tfix，Tfix為已經(jīng)執(zhí)行的列車運(yùn)行線集合；同時c中列車車次編組需確定，即yfc,m=1且ysc,m=1 ；nτ,u,b為當(dāng)前時刻τ動車段（所）b內(nèi)u型車輛的可用數(shù)量.

通過添加式（16）、（17）來固定已經(jīng)執(zhí)行的運(yùn)行線及已使用的動車組單元，然后基于未執(zhí)行運(yùn)行線信息、線路結(jié)構(gòu)信息（可添加的空車調(diào)配線信息等）以及實時可用動車組單元信息（現(xiàn)有各車的狀態(tài)信息及可啟用的備用車狀態(tài)等）重新計算.

4 算例分析

以鄭州局集團(tuán)有限公司所轄動車組開行的高鐵路網(wǎng)為算例背景，該路網(wǎng)包含36個主要車站及2個動車所，其結(jié)構(gòu)如圖4所示. 選取兩套列車運(yùn)行圖實際數(shù)據(jù)作為臨時更換后的運(yùn)行圖，其對應(yīng)各動車所不同類型的動車組單元保有量信息（每個動車組單元的初始狀態(tài)由于篇幅所限未列出）如表2所示，表中：數(shù)據(jù)1為2017年9月某日至2018年7月某日的實際圖，包含159條運(yùn)行線（均為集成運(yùn)行線，如昆明到鄭州東只算1條運(yùn)行線，下同）；數(shù)據(jù)2為2018年8月某日至2019年7月某日的實際圖，包含212條運(yùn)行線. 在統(tǒng)計可添加的人工空駛運(yùn)行線和過夜運(yùn)行線后，數(shù)據(jù)1總共包含377條運(yùn)行線，數(shù)據(jù)2總共包含490條運(yùn)行線.

可用4種類型的動車組，其中380AL類型在擔(dān)當(dāng)運(yùn)輸任務(wù)的中途不能改編（只有16編一種方式），其他3種類型的動車組列車則可在滿足條件的情況下進(jìn)行改編（有8編和16編）.

算法框架在Visual Studio 2015環(huán)境中采用C#語言編程實現(xiàn)，混合整數(shù)線性規(guī)劃模型部分調(diào)用商業(yè)優(yōu)化軟件CPLEX 12.8.0進(jìn)行求解. 求解MP模型時，需使用多重可行解生成算法來生成多個備選路徑方案，可通過調(diào)用CPLEX中的populate函數(shù)實現(xiàn)，其中求解強(qiáng)度參數(shù)（pool intensity）設(shè)置為3，初始最優(yōu)間隙（absolutely gap）W0設(shè)置為10000000，解池填充次數(shù)（populate times）M設(shè)置為50，其他參數(shù)均為默認(rèn)值. 算法框架每一次從解池M中選取的備選路徑方案F設(shè)定為10. 此外，式（1）中的懲罰參數(shù) ε、ξ 和 ζ 的取值分別設(shè)置為100000、1和4；αc,m,m′及 βt,m的取值通過與調(diào)度員商議后確定，由于篇幅限制在此并未列出. 迭代逼近算法的迭代時間、最優(yōu)間隙終止條件分別設(shè)置為不超過120 s和小于等于0.0001%，不同運(yùn)營策略下的運(yùn)用計劃方案關(guān)鍵技術(shù)統(tǒng)計指標(biāo)見表3. 表中：RS和OP分別為方案使用的動車組單元數(shù)量和動車所外過夜的動車組單元數(shù)量；ARL、MRL、MARL、AERL及ERL分別為方案所使用動車組單元的平均走行距離、最小走行距離、最大走行距離、平均空駛距離以及該方案的總空駛距離；OBJ、OBJSP以及CT分別為方案的目標(biāo)函數(shù)值、對應(yīng)SP模型目標(biāo)函數(shù)值以及求解時間；策略1為沒有動車組在運(yùn)行途中的額外改編作業(yè)，策略2為允許額外的改編作業(yè). 策略1與策略2均保證動車所內(nèi)動車組單元的庫存平衡. 在策略2中，規(guī)定額外的重聯(lián)作業(yè)耗時12 min、摘解作業(yè)耗時8 min，其他參數(shù)與前述保持一致.

圖4 測試的高鐵路網(wǎng)絡(luò)結(jié)構(gòu)Fig. 4 Tested high-speed railway network

表2 各動車所不同類型的動車組單元保有量信息Tab. 2 Information of EMUs for different depots 組

由表3可以看到：數(shù)據(jù)1中兩種策略下的算法方案均能夠在120 s內(nèi)求得最優(yōu)解. 需要注意，數(shù)據(jù)1中策略1的算法方案與下界方案并不是同一方案，雖然兩個方案大部分關(guān)鍵指標(biāo)一致，但OBJSP有差異，表示兩種方案使用的具體動車組單元并不相同.說明通過文中的方法能夠在短時間內(nèi)縮小求解空間，迫使其不斷尋求更接近下界的優(yōu)質(zhì)解. 數(shù)據(jù)2能在120 s內(nèi)獲得接近下界方案目標(biāo)函數(shù)值的高質(zhì)量解，其兩種策略下算法方案的目標(biāo)值收斂過程如圖5所示，圖5中兩種策略下的最終目標(biāo)值與下界值之間的差值均小于0.01%.

與人工方案相比，數(shù)據(jù)1和數(shù)據(jù)2算法方案的動車組總空駛距離的平均下降值分別為38%和9%，動車組單元平均空駛距離的平均下降值分別為32%和3%. 兩組數(shù)據(jù)結(jié)果上的差異主要來自數(shù)據(jù)2中動車組單元初始停放位置的調(diào)整（如表2所示）. 數(shù)據(jù)1和數(shù)據(jù)2中算法方案的動車組單元平均走行距離的平均上升值分別為7.9%和6.4%. 總空駛距離的下降及平均走行距離的上升，都從側(cè)面反映出動車組單元使用效率的提升. 同時，從表3中能夠看出，算法方案相比人工方案更能夠節(jié)省動車組單元的使用，且算法方案的目標(biāo)函數(shù)值更?。ㄟ\(yùn)營成本降低）.此外，不難發(fā)現(xiàn)允許額外改編作業(yè)的方案能夠進(jìn)一步節(jié)省動車組單元的使用數(shù)量并降低綜合運(yùn)營成本. 所有方案的動車所外過夜的動車組單元數(shù)量相同，說明所外過夜是不可避免的，如：鄭州（東）至昆明南、鄭州（東）至廈門北等. 綜上，通過上述多組實驗數(shù)據(jù)分析表明，相比于人工方案，算法方案結(jié)果中的動車組綜合運(yùn)營成本平均下降10.5%、總空駛里程平均減少23%.

表 3 不同策略下各案例的動車運(yùn)用計劃關(guān)鍵技術(shù)指標(biāo)Tab. 3 Key statistics of train-set scheduling cases under different scenarios

圖5 不同策略下目標(biāo)函數(shù)值收斂過程示意Fig. 5 Convergence process of objective function value process under different scenarios

5 結(jié) 論

1） 本文在包含多動車段（所）、多類型動車組的復(fù)雜高速鐵路網(wǎng)絡(luò)背景下，以最小化綜合運(yùn)營成本和總空駛里程為優(yōu)化目標(biāo)，考慮動車組運(yùn)營安全、動車所庫存能力、動車組日常維修限制等約束條件，建立了基于列車車次的可改編動車組運(yùn)用優(yōu)化混合整數(shù)線性規(guī)劃模型，并設(shè)計了一個基于路徑生成的迭代逼近算法框架.

2） 所提出的模型和算法能夠快速地編制滿足日常維修限制的動車組運(yùn)用計劃，其合理性與有效性在以鄭州局為實例背景的算例中得到驗證，相比已有的研究更加適應(yīng)列車運(yùn)行圖更換或臨時調(diào)整的情況.

3） 未來可對算法框架進(jìn)行改進(jìn)，以提高求解效率；此外，還將對某些特殊場景（如突發(fā)自然災(zāi)害或人為破壞等）下的動車組運(yùn)用計劃實時調(diào)整做進(jìn)一步探討.