聞克宇，何必勝，徐 林

（1. 鐵道部經(jīng)濟(jì)規(guī)劃研究院 運輸咨詢部，北京 100038；2. 北京交通大學(xué) 交通運輸學(xué)院，

北京 100044；3. 杭州杭港地鐵有限公司 運營支持室，浙江 杭州 310000）

動車組運用計劃的編制受到多種因素的影響，如高速鐵路路網(wǎng)結(jié)構(gòu)、列車運行計劃、運輸組織模式、運輸管理體制等，而編制一個適應(yīng)國情、路情的動車組運用計劃，有助于促進(jìn)我國高速鐵路運營生產(chǎn)效率的提高。動車組運用計劃編制是一種多車場的車輛調(diào)度問題，與其他運輸方式不同，動車組運用計劃還包括日常檢修計劃。國內(nèi)不少專家和學(xué)者都在動車組運用計劃領(lǐng)域進(jìn)行深入的探索，取得了一定的理論成果[1-5]。但是，隨著我國高速鐵路逐漸成網(wǎng)，動車組運用計劃優(yōu)化問題更為復(fù)雜，因而需要進(jìn)一步優(yōu)化和協(xié)調(diào)動車組運用與檢修的關(guān)系。由于成網(wǎng)條件下的動車組運用計劃與既有動車組運用計劃存在較大區(qū)別，因而結(jié)合成網(wǎng)條件下動車組運用計劃的特點和我國國情、路情，研究有效優(yōu)化方法。

1 成網(wǎng)條件下動車組運用計劃描述

在列車運行圖確定后，動車組運用計劃主要研究由哪些動車組承擔(dān)鐵路運輸任務(wù)。為了確保動車組的安全運行，動車組運用計劃需要將檢修計劃納入日常運營。因此，動車組運用計劃應(yīng)綜合考慮動車組檢修任務(wù)、動車組的種類和數(shù)量、運行圖圖定任務(wù)等因素，不斷優(yōu)化動車組運用總成本，并且保證動車組運用計劃的魯棒性和穩(wěn)定性。以我國CRH 系列動車組為例，其檢修指標(biāo)分為 5 級，如表1 所示[6]。

動車組運用可以分為固定區(qū)段和不固定區(qū)段 2種類型。固定區(qū)段的動車組運用相對比較簡單，但會增加動車組運用的成本。為此，主要研究在不固定區(qū)段使用方式下動車組的運用優(yōu)化問題，即動車組完成 1 次運輸任務(wù)后，根據(jù)一定目標(biāo)選擇接續(xù)任務(wù)。為了研究多個動車段 ( 所 ) 條件下的不固定區(qū)段動車組運用問題，通過綜合考慮動車組檢修計劃，作出以下假設(shè)：①動車組從所屬動車段 ( 所 ) 出發(fā)，在該計劃結(jié)束時必須返回原動車段 ( 所 )；②動車組使用方式為不固定區(qū)段使用；③一級檢修和二級檢修任務(wù)包含在動車組計劃內(nèi)。

2 構(gòu)建時空網(wǎng)絡(luò)

為了避免隨著運輸任務(wù)規(guī)模的增加，動車組運用計劃優(yōu)化模型的規(guī)模急劇增加，需要將動車組運用優(yōu)化問題簡化，為此引入時空網(wǎng)絡(luò)[7]。時空網(wǎng)絡(luò)將復(fù)雜的網(wǎng)絡(luò)流規(guī)劃問題的建模求解帶入由“時間”軸和“空間”軸構(gòu)成的二維空間，為動車組運用計劃優(yōu)化問題提供了一種有效的方法。

考慮以運輸任務(wù)為節(jié)點，根據(jù)相鄰運輸任務(wù)之間的函數(shù)關(guān)系ω(s，t) 在節(jié)點之間建立相應(yīng)的弧，從而構(gòu)建出時空網(wǎng)絡(luò)。根據(jù)運輸任務(wù)的屬性，通常將運輸任務(wù)分為 3 類：運輸作業(yè)、基地作業(yè)、檢修作業(yè)。同時，將函數(shù)關(guān)系分為以下 3 種情況：相鄰運輸作業(yè)之間的函數(shù)關(guān)系、運輸作業(yè)與基地作業(yè)之間的函數(shù)關(guān)系、運輸作業(yè)與檢修作業(yè)之間的函數(shù)關(guān)系。在考慮開始地點、到達(dá)地點、開始時刻、結(jié)束時刻、發(fā)生地點、持續(xù)時間、運行里程、需要的動車組數(shù)量等時空屬性后，可以根據(jù)以下步驟建立動車組運用的時空網(wǎng)絡(luò)。

步驟 1：基于給定的運輸任務(wù)集合R，對應(yīng)不同類型的運輸任務(wù)，建立與之相應(yīng)的作業(yè)節(jié)點：運輸作業(yè)節(jié)點、基地作業(yè)節(jié)點、檢修作業(yè)節(jié)點，并且對應(yīng)每一個作業(yè)開始時間、結(jié)束時間分別建立 1 對作業(yè)開始節(jié)點、作業(yè)結(jié)束節(jié)點。這 3 種作業(yè)節(jié)點的集合被記為V。

表1 CRH 系列動車組運用檢修指標(biāo)

步驟 2：根據(jù)運輸任務(wù)的類型建立以下 4 類?。孩龠\輸作業(yè)弧：動車組必須完成的運輸作業(yè)任務(wù)，包含起訖節(jié)點等信息；②接續(xù)?。簞榆嚱M完成上次運輸作業(yè)后繼續(xù)下次運輸作業(yè)過程中所走行的路徑 ( 包含等待下一作業(yè)時間 )；③出入基地?。簞榆嚱M完成任務(wù)后出入車站或動車段 ( 所 ) 產(chǎn)生的行走軌跡，其特點就是將任務(wù)節(jié)點連接起來，以使動車組在任務(wù)間轉(zhuǎn)換；④檢修作業(yè)?。簞榆嚱M必須完成的檢修作業(yè)任務(wù)，包含了起訖節(jié)點等信息。

在列車運行圖基礎(chǔ)上構(gòu)建的動車組運用時空網(wǎng)絡(luò)圖如圖 1 所示。在圖 1 中，任意 1 條從計劃開始時間到結(jié)束時間的完整的路徑即可以看作 1 個動車組的交路。

對變量定義如下。

（1）s為車站，S為車站集合，則有s∈S。不辦理始發(fā)終到作業(yè)的車站不影響動車組運用計劃。因此，該集合內(nèi)只包括辦理始發(fā)終到作業(yè)的車站。

（2）k為動車段 ( 所 )，K為動車段 ( 所 ) 集合，則有k∈K。部分車站有相鄰的動車段 ( 所 ) 用于動車組的檢修，則設(shè)sk為配備有動車段 ( 所 ) 的車站，有sk∈Sk∈S。設(shè)Ck，1為動車段 ( 所 ) 1 天的一級檢修能力，Ck，2為動車段 ( 所 ) 1 天的二級檢修能力，Nk為動車段 ( 所 ) 的動車組數(shù)量。

（3）l為運用任務(wù)，Al為運用任務(wù)集合，則有l(wèi)∈Al。l存在到達(dá)節(jié)點va，l和出發(fā)節(jié)點vd，l，其中：va，l∈Va，l，所處地點為sa，l，時間為ta，l；vd，l∈Vd，l，所處地點為sd，l，時間為td，l。l對應(yīng)成本為wl。

（4）m為檢修任務(wù)，Am為檢修任務(wù)集合，則有m∈Am。m分為一級檢修任務(wù)和二級檢修任務(wù)，則有一級檢修任務(wù)m∈Am，1二級檢修任務(wù)m∈Am，2。出入動車段 ( 所 ) 對應(yīng)有開始維修節(jié)點vb，m和結(jié)束維修節(jié)點vf，m，其中：vb，m∈Vb，m，地點為sb，m，時間為tb，m；vf，m∈Vf，m，地點為sf，m，時間為tf，m。若檢修任務(wù)m發(fā)生在動車段 ( 所 )k則有γm，k= 1，否則為γm，k= 0。m對應(yīng)成本為wm。

（5）c為接續(xù)弧，Ac為接續(xù)弧集合，則有c∈Ac。c用于連接l的任務(wù)終點和l'的任務(wù)起點，接續(xù)弧可以認(rèn)為是Ac= {(l，l')|ta，l+ε＜td，l '，l∈Al，l'∈Al}，即只要l的任務(wù)結(jié)束時間與作業(yè)時間ε之和小于任務(wù)l'的任務(wù)開始時間，2 個任務(wù)之間就可以建立接續(xù)關(guān)系，生成接續(xù)弧。其中：若sa，l=sd，l'則為本地接續(xù)，若sa，l≠sd，l'則為異地接續(xù)。動車組夜間停留在車站或動車段 ( 所 ) 可以看作是一種接續(xù)弧，都可以理解為在車站駐車。c對應(yīng)成本為wc。

（6）i，o分別表示入弧和出弧，入弧i∈Ai，出弧o∈Ao。i，o用于描述動車組進(jìn)出車場走行的情況，連接的是運用任務(wù)和檢修任務(wù)，由于只要動車組所在的車站配備有動車段 ( 所 )，動車組就能進(jìn)出動車段 ( 所 )，因而在任意sk，當(dāng)動車組需要進(jìn)行檢修時入弧即可產(chǎn)生，當(dāng)檢修完成時出弧也就產(chǎn)生。i，o對應(yīng)成本分別為wi，wo。

圖1 動車組運用時空網(wǎng)絡(luò)圖

（7）τ∈T為規(guī)劃周期，τ代表第幾天。

（8）e為動車組，Ek為動車組集合，動車段( 所 ) 都有相應(yīng)配屬的動車組，因而有e∈Ek。

（9）綜上所述，有A=Al∪Ac∪Am∪Ai∪Ao，V=Va，l∪Vd，l∪Vb，m∪Vf，m，共同構(gòu)成動車組運用時空網(wǎng)絡(luò)G= (V，A)。在第τ天內(nèi)，動車組可以分為2 類，一類是完成任務(wù)的動車組，另一類是沒有進(jìn)行任何任務(wù)的動車組。對于有任務(wù)的動車組e在G中存在可能的路徑集合為p∈Pk，即為動車組e的交路段，所有動車組可能交路段生成路徑集合Pk∈P。交路段包括列車運用任務(wù)和檢修任務(wù)，以及連接它們的接續(xù)弧、入弧和出弧。

對于 2 個同級別的相鄰的維修任務(wù)而言，中間的運行長度或時間必須小于該級別的規(guī)定，如 2 個一級檢修任務(wù)間的運行距離和時間要小于一級檢修中所規(guī)定的 4 000 km 和 48 h。因此，對路徑p中所包含的檢修弧按照時間順序進(jìn)行排序，一級檢修任務(wù)集合Am，1，p，二級檢修任務(wù)集合Am，2，p，m'為m的下一個同級檢修任務(wù)。對于路徑p中的每一個節(jié)點，還需要保存路徑的走行時長tp，v和走行距離dp，v，其中v代表節(jié)點，用于進(jìn)行檢修狀態(tài)識別。路徑p對應(yīng)的成本wp為

式中：θp，l為 0-1 變量，表示運用任務(wù)l是否在路徑p上，θp，l= 1 代表l在p上，θp，l= 0 則反之；μp，m為 0-1 變量，表示檢修任務(wù)m是否在路徑p上，μp，m= 1 代表m在p上，μp，m= 0 則反之；ηp，c為 0-1 變量，表示接續(xù)弧c是否在路徑p上，ηp，c= 1 代表c在p上，ηp，c= 0 則反之。

動車組運用時空網(wǎng)絡(luò)，需要注意以下方面。

（1）完成 1 次運用任務(wù)到達(dá)車站后，動車組必須進(jìn)行簡單整備作業(yè)才可繼續(xù)進(jìn)行下次運用任務(wù)，即接續(xù)弧的時長必須大于整備作業(yè)時間ε。

（2）時空網(wǎng)絡(luò)的優(yōu)點就是能夠減少接續(xù)弧數(shù)量。

（3）合理利用動車段 ( 所 ) 的檢修能力能夠有效減少動車組在動車段 ( 所 ) 的停留時間，進(jìn)而提高動車組的使用效率。因此，要求 1 天內(nèi)動車段 ( 所 )所進(jìn)行的檢修任務(wù)不超過動車段 ( 所 ) 的檢修能力。{m|1440τ≤tb，m≤ 1440 (τ+1)，m∈Am，1} 代表第τ天的一級檢修任務(wù)集合，{m| 1440τ≤tb，m≤1440 (τ+1)，m∈Am，2} 代表二級檢修任務(wù)集合。

（4）動車組到達(dá)車站時，可以選擇進(jìn)入動車段 ( 所 ) 或在車站等待，若直接進(jìn)入動車段 ( 所 )，出、入弧的成本均為定值，完成檢修任務(wù)時，動車組在動車段 ( 所 ) 等待運用任務(wù)開始。因此，成本應(yīng)為接續(xù)弧加上出弧的成本。

3 成網(wǎng)條件下動車組運用計劃優(yōu)化模型

以路徑費用最小為目標(biāo)函數(shù)，建立動車組運用計劃優(yōu)化模型為

式中：tm為相應(yīng)級別的檢修限制時間；dm為相應(yīng)級別檢修限制距離。

⑴式為目標(biāo)函數(shù)，該模型以動車組在運用過程中走行路徑的總費用最小為目標(biāo)。⑵式為走行費用計算方法。⑶式至⑹式為動車組的檢修要求約束，必須在運用中按照要求完成一、二級檢修，其中：⑶式為一級檢修的時間要求，⑷式為一級檢修的里程要求，⑸式為二級檢修的時間要求，⑹式為二級檢修的里程要求。⑺式為動車組運用數(shù)量上限，動車組運用數(shù)量不能超過動車段 ( 所 ) 存有的動車組數(shù)量。⑻式要求運用任務(wù)只能由 1 輛動車組完成；⑼、⑽式為動車段 ( 所 ) 一、二級檢修能力約束。⑾ 式為變量約束要求，xp為 0-1 變量。

4 算法設(shè)計

通過分析成網(wǎng)條件下動車組運用計劃的優(yōu)化問題，采用大規(guī)模鄰域搜索算法 ( Large-scale Neighborhood Search Algorithm ) 進(jìn)行求解。為了進(jìn)行鄰域搜索，運用數(shù)字串對動車組交路段進(jìn)行描述，假設(shè)動車組交路的編碼形式為eX(l，k)，其中，X= 0 或 1，X= 0 代表進(jìn)行任務(wù)作業(yè)，X= 1 代表進(jìn)出動車段 ( 所 ) 作業(yè)。

為了縮小動車組運用問題的規(guī)模，同時保持計算精度不受影響，在構(gòu)造初始解時提出班組的概念，即在給定配屬動車組數(shù)量Nk的情況下，以T為周期用n個班組周期性分配完規(guī)定的u個任務(wù)。其中n=Nk/T。例如：線路規(guī)定配屬 100 個動車組，周期為 10 天，每天 160 個任務(wù)，則需要編制 100 個動車組在 10 天內(nèi)完成 1 600 個任務(wù)的計劃。但是，如果以 10 天為周期分為 10 個班組，每個班組 10 個動車組來運行，讓動車組周期性循環(huán)套跑，則只需要安排 10 個動車組在 1 天內(nèi)完成 160 個任務(wù)的計劃，其他班組按照這個既定交路循環(huán)套跑完成1 600 個任務(wù)。所產(chǎn)生的初始解是可行的，雖然不一定是最優(yōu)解，但這將大大降低算法規(guī)模，提高求解速度，增加編制動車組運用計劃的效率，具有較好的可操作性。

按照以下步驟進(jìn)行初始可行解的構(gòu)造：①所有動車組指派空路徑；②設(shè)U為所有沒有安排的任務(wù)的集合，u為任務(wù)數(shù)量；③初始化動車組配屬數(shù)量Nk，初始化動車組運用周期T，得到班組數(shù)n=Nk/T；④將U等分為n個集合u1，u2，…，uq，…，un，每個集合任務(wù)數(shù)量為uq/n；⑤從u1，u2，…，uq，…，un里面隨機抽取1個任務(wù)；⑥將這個任務(wù)分別插入u1，u2，…，uq，…，un中能夠使目標(biāo)函數(shù)值增加最小的可行插入位置；⑦在原有路徑中刪除此任務(wù)；⑧在規(guī)定時間內(nèi)重復(fù)⑤～⑦，以盡量獲取較好的初始可行解。則最后產(chǎn)生的u1，u2，…，un即為初始路徑集合。

綜上所述，設(shè)計算法如下。

步驟 1：構(gòu)造初始可行解。

步驟 2：設(shè)定最大移出的任務(wù)數(shù)pmax，最大迭代次數(shù)Itermax，以及當(dāng)前移出任務(wù)數(shù)n= 1。

步驟 3：設(shè)定當(dāng)前迭代次數(shù)Iter= 1。

步驟 4：如果Iter＜Itermax，根據(jù)移出 ( Remove )過程，得到從當(dāng)前解S中移出n個任務(wù)后的部分解S'。

步驟 5：根據(jù)插入 ( Re-insertion ) 過程，選擇最適合的位置插回S'中，如果得到一個更優(yōu)解Sbest則令S=Sbest并轉(zhuǎn)到步驟 3；如果沒有，則返回當(dāng)前的解S，Iter=Iter+ 1 轉(zhuǎn)到步驟 6。

步驟 6：如果Iter=Itermax，則令n=n+ 1，如果n=Pmax則輸出結(jié)果，算法終止；否則轉(zhuǎn)到步驟 3。

算法結(jié)束的條件有：①迭代達(dá)到最大迭代次數(shù)或達(dá)到一定時間；②當(dāng)前解在預(yù)期值的范圍內(nèi)；③前面 2 項的組合?？梢愿鶕?jù)不同的情況選擇算法的結(jié)束。

5 算例

為了驗證該模型算法的有效性，擬采用京滬高速鐵路和滬寧高速鐵路的給定運行圖數(shù)據(jù)作為研究對象，假定初期 2 條線路并不套跑，后期為了成網(wǎng)考慮，套跑運行，以模擬成網(wǎng)條件。

依據(jù)給定的京滬、滬寧高速鐵路運行圖，京滬高速鐵路開行列車 100 對/d，滬寧高速鐵路開行列車 78 對/d。運輸組織采用本線運輸組織模式，動車組采用 CRH2 型動車組。CRH2 型動車組的立即折返時間標(biāo)準(zhǔn)為 24 min，一級檢修里程為 4 000 km、作業(yè)時間標(biāo)準(zhǔn)為 1.5 h，二級檢修里程 30 000 km、作業(yè)時間標(biāo)準(zhǔn)4 h，檢修修程波動系數(shù)為 10%。

運算結(jié)果中，運行周期分 8 個班組完成所有任務(wù)，每個班組 16 個動車組，運行周期為16 d，運用動車組總數(shù)為 128 組。動車組交路片段如圖 2 所示。

圖2 動車組交路片段

通過分析圖 2 可以發(fā)現(xiàn)該方案中有線路套跑的車次。例如：G113 是京滬高速鐵路的車次，在圖 2 的交路中，該動車組在完成了 G113 后又完成了 G7026 和 G7179 的運輸任務(wù)，而這 2 個車次屬于滬寧高速鐵路，即 2 條線路套跑，這樣的安排會降低空車走行，有利于提高動車組使用效率，同時增加車輛的平均日車公里數(shù)。通過與給定運行圖進(jìn)行比較，結(jié)果方案中這種成網(wǎng)后的優(yōu)勢體現(xiàn)得較為明顯。

為了驗證大規(guī)模鄰域搜索算法的有效性，根據(jù)模擬退火算法[8]對初始解進(jìn)行優(yōu)化，并將其結(jié)果與大規(guī)模領(lǐng)域搜索算法的優(yōu)化結(jié)果進(jìn)行比較，發(fā)現(xiàn)大規(guī)模鄰域搜索算法結(jié)果較優(yōu)，算法結(jié)果如表 2 所示。

表2 算法結(jié)果比較

6 結(jié)束語

研究成網(wǎng)條件下動車組運用計劃的優(yōu)化問題，通過引入時空網(wǎng)絡(luò)，建立成網(wǎng)條件下動車組運用計劃的優(yōu)化模型。該模型運用網(wǎng)絡(luò)流的思想，能夠更加清晰地描述動車組運用情況。結(jié)合大規(guī)模鄰域搜索算法，提出對周期性的多車場動車組運用問題的求解方法。以京滬、滬寧高速鐵路數(shù)據(jù)為例，驗證了該算法的可行性和有效性。比較大規(guī)模鄰域搜索算法與模擬退火算法的優(yōu)化結(jié)果，認(rèn)為大規(guī)模鄰域搜索算法能夠較快地獲取優(yōu)化結(jié)果，對于高速鐵路逐步成網(wǎng)后，編制和優(yōu)化動車組運用計劃具有一定的參考價值。

[1] 趙 鵬，楊 浩，胡安洲. 高速鐵路動車組的不固定區(qū)段使用問題[J]. 鐵道學(xué)報，1997，19(2)： 15-19.

[2] 趙 鵬，富井規(guī)雄. 動車組運用計劃及其編制算法[J]. 鐵道學(xué)報，2003，25(3)：1-7.

[3] 張才春. 基于均衡性的客運專線動車組運用問題研究[D].北京：北京交通大學(xué)，2010.

[4] 李 華，韓寶明，李得偉，等. 動車組運用接續(xù)網(wǎng)絡(luò)優(yōu)化方法研究[J]. 鐵道運輸與經(jīng)濟(jì)，2012，34(1)：76-79.

[5] 劉 鋼，孫晚華，韓學(xué)雷. 旅客列車車底運用優(yōu)化模型及算法[J]. 鐵道運輸與經(jīng)濟(jì)，2004，26(2)：62-64.

[6] 中華人民共和國鐵道部. 鐵路動車組運用維修規(guī)程(暫行)[M]. 北京：中國鐵道出版社，2007.

[7] 李妍峰，李 軍，高自友. 大規(guī)模鄰域搜索算法求解時變車輛調(diào)度問題[J]. 管理科學(xué)學(xué)報，2012，15(1)：22-32.

[8] 賈玉芬. 高速鐵路動車組周期性運用計劃問題研究[D]. 北京：北京交通大學(xué)，2011.