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

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

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

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

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

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

1 問(wèn)題描述

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

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

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

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

表 1 動(dòng)車組單元基本量信息Tab. 1 Basic information of EMUs

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

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

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

2.1 建模假設(shè)

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

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

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

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

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

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

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

2.2.1 符號(hào)說(shuō)明

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

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

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

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

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

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

2.2.3 約束條件

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

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

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

式中：t需滿足

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

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

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

3） 動(dòng)車所庫(kù)存能力限制約束

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

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

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

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

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

4） 動(dòng)車所庫(kù)存平衡約束

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

式 中： Γ0和 Γ1分別為計(jì)算時(shí)間段的結(jié)束和開(kāi)始時(shí)刻.

2.3 SP模型：帶維修約束的動(dòng)車組指派模型

2.3.1 符號(hào)說(shuō)明

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

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

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

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

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

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

2.3.3 約束條件

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

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

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

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

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

3.1 WP有效下界證明

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

3.2 CP模型主要步驟

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

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

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

3.3 多日計(jì)劃求解方法

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

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

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

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

若某日列車運(yùn)行圖已經(jīng)執(zhí)行了一部分時(shí)突然需要進(jìn)行調(diào)整，此時(shí)只需要在MP模型中根據(jù)已經(jīng)執(zhí)行的運(yùn)行線信息，固定對(duì)應(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)行線集合；同時(shí)c中列車車次編組需確定，即yfc,m=1且ysc,m=1 ；nτ,u,b為當(dāng)前時(shí)刻τ動(dòng)車段（所）b內(nèi)u型車輛的可用數(shù)量.

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

4 算例分析

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

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

算法框架在Visual Studio 2015環(huán)境中采用C#語(yǔ)言編程實(shí)現(xiàn)，混合整數(shù)線性規(guī)劃模型部分調(diào)用商業(yè)優(yōu)化軟件CPLEX 12.8.0進(jìn)行求解. 求解MP模型時(shí)，需使用多重可行解生成算法來(lái)生成多個(gè)備選路徑方案，可通過(guò)調(diào)用CPLEX中的populate函數(shù)實(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的取值通過(guò)與調(diào)度員商議后確定，由于篇幅限制在此并未列出. 迭代逼近算法的迭代時(shí)間、最優(yōu)間隙終止條件分別設(shè)置為不超過(guò)120 s和小于等于0.0001%，不同運(yùn)營(yíng)策略下的運(yùn)用計(jì)劃方案關(guān)鍵技術(shù)統(tǒng)計(jì)指標(biāo)見(jiàn)表3. 表中：RS和OP分別為方案使用的動(dòng)車組單元數(shù)量和動(dòng)車所外過(guò)夜的動(dòng)車組單元數(shù)量；ARL、MRL、MARL、AERL及ERL分別為方案所使用動(dòng)車組單元的平均走行距離、最小走行距離、最大走行距離、平均空駛距離以及該方案的總空駛距離；OBJ、OBJSP以及CT分別為方案的目標(biāo)函數(shù)值、對(duì)應(yīng)SP模型目標(biāo)函數(shù)值以及求解時(shí)間；策略1為沒(méi)有動(dòng)車組在運(yùn)行途中的額外改編作業(yè)，策略2為允許額外的改編作業(yè). 策略1與策略2均保證動(dòng)車所內(nèi)動(dòng)車組單元的庫(kù)存平衡. 在策略2中，規(guī)定額外的重聯(lián)作業(yè)耗時(shí)12 min、摘解作業(yè)耗時(shí)8 min，其他參數(shù)與前述保持一致.

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

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

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

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

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

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

5 結(jié) 論

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

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

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