考慮檢修能力約束的動(dòng)車(chē)組交路計(jì)劃優(yōu)化模型與算法

江政杰, 聶 磊，賀振歡，童佳楠

（1.北京交通大學(xué)?交通運(yùn)輸學(xué)院，北京?100044；2.中鐵二院工程集團(tuán)有限責(zé)任公司?土木建筑設(shè)計(jì)????研究二院，四川?成都?610036）

考慮檢修能力約束的動(dòng)車(chē)組交路計(jì)劃優(yōu)化模型與算法

江政杰1, 聶 磊1，賀振歡1，童佳楠2

（1.北京交通大學(xué)?交通運(yùn)輸學(xué)院，北京?100044；2.中鐵二院工程集團(tuán)有限責(zé)任公司?土木建筑設(shè)計(jì)????研究二院，四川?成都?610036）

我國(guó)高速鐵路動(dòng)車(chē)段所數(shù)量較少且分布較為集中，動(dòng)車(chē)組一級(jí)檢修能力成為編制動(dòng)車(chē)組交路計(jì)劃的重要制約條件。鑒于此，對(duì)動(dòng)車(chē)組交路計(jì)劃編制問(wèn)題建立考慮動(dòng)車(chē)段所一級(jí)檢修能力約束的多目標(biāo)整數(shù)規(guī)劃模型。首先，依據(jù)動(dòng)車(chē)組交路接續(xù)規(guī)則和一級(jí)檢修條件構(gòu)造交路備選集，并將交路計(jì)劃編制問(wèn)題表達(dá)為集合劃分問(wèn)題；其次，采用基于重要性分級(jí)的分層序列法求解模型，即多目標(biāo)模型被分解為主目標(biāo)“動(dòng)車(chē)組運(yùn)用數(shù)量最小”，以及次目標(biāo)“檢修次數(shù)最少”的?2?個(gè)單目標(biāo)整數(shù)規(guī)劃模型，并采用傳統(tǒng)的精確算法求解；最后，通過(guò)算例分析驗(yàn)證了模型與算法的有效性，為動(dòng)車(chē)組交路計(jì)劃的優(yōu)化編制提供依據(jù)。

高速鐵路；動(dòng)車(chē)組交路；分層序列法；多目標(biāo)整數(shù)規(guī)劃

0引言

隨著我國(guó)高速鐵路的快速成網(wǎng)，動(dòng)車(chē)組列車(chē)開(kāi)行數(shù)量不斷增加，動(dòng)車(chē)組的運(yùn)用和檢修是否合理在很大程度上影響鐵路部門(mén)的運(yùn)營(yíng)成本，動(dòng)車(chē)段所的一級(jí)檢修能力已經(jīng)成為動(dòng)車(chē)組列車(chē)開(kāi)行的重要制約條件。因此，優(yōu)化動(dòng)車(chē)組交路計(jì)劃，節(jié)省動(dòng)車(chē)組運(yùn)用數(shù)量，降低動(dòng)車(chē)組檢修成本，成為高速鐵路運(yùn)輸組織面臨的重要現(xiàn)實(shí)問(wèn)題和技術(shù)難題。

在既有的研究中，我國(guó)大多數(shù)學(xué)者通過(guò)整數(shù)規(guī)劃模型對(duì)動(dòng)車(chē)組交路計(jì)劃進(jìn)行建模，并分別以動(dòng)車(chē)組數(shù)量最少和動(dòng)車(chē)組檢修次數(shù)最少為優(yōu)化目標(biāo)；求解算法則有分枝定價(jià)算法等精確算法，以及粒子群算法、蟻群算法等智能算法。在精確算法方面，王瑩等[1-2]通過(guò)研究動(dòng)車(chē)組運(yùn)用規(guī)程的特點(diǎn)，構(gòu)建接續(xù)網(wǎng)絡(luò)模型，并采用分支定價(jià)算法進(jìn)行求解；LU C等[3]基于貪婪算法構(gòu)造接續(xù)網(wǎng)絡(luò)，并采用分支定界算法進(jìn)行求解。在智能算法方面，李華等[4]、ZHOU Y等[5]基于給定成對(duì)列車(chē)運(yùn)行圖建立多目標(biāo)整數(shù)規(guī)劃模型，并采用改進(jìn)的蟻群算法進(jìn)行求解；王忠凱[6]將動(dòng)車(chē)組交路計(jì)劃抽象為帶狀態(tài)約束的旅行商問(wèn)題，構(gòu)建相應(yīng)的接續(xù)網(wǎng)絡(luò)，并且采用蟻群算法進(jìn)行求解；李華等[7]、李建等[8]則主要基于列車(chē)運(yùn)行圖構(gòu)造動(dòng)車(chē)組交路網(wǎng)絡(luò)，采用粒子群優(yōu)化算法進(jìn)行求解；苗建瑞等[9]將動(dòng)車(chē)組交路計(jì)劃歸結(jié)為帶補(bǔ)給的多旅行商問(wèn)題，采用分層優(yōu)化啟發(fā)式算法進(jìn)行求解；黃興亮[10]分析影響動(dòng)車(chē)組交路計(jì)劃編制的因素，構(gòu)建動(dòng)車(chē)組交路計(jì)劃編制與列車(chē)運(yùn)行圖協(xié)調(diào)優(yōu)化的模型，并且采用改進(jìn)的蟻群算法進(jìn)行求解；陳然等[11]針對(duì)動(dòng)車(chē)組列車(chē)網(wǎng)絡(luò)化運(yùn)行條件下的復(fù)雜情況，將編制動(dòng)車(chē)組運(yùn)用計(jì)劃的經(jīng)驗(yàn)加入專(zhuān)家系統(tǒng)，通過(guò)設(shè)計(jì)基于專(zhuān)家系統(tǒng)指導(dǎo)的最大最小蟻群算法對(duì)模型進(jìn)行求解；余曉園等[12]分析高速鐵路列車(chē)開(kāi)行模式對(duì)動(dòng)車(chē)組運(yùn)用的影響，提出基于列車(chē)接續(xù)網(wǎng)絡(luò)的動(dòng)車(chē)組交路計(jì)劃優(yōu)化模型，并運(yùn)用 Cplex 軟件進(jìn)行求解。

既有研究中大都以動(dòng)車(chē)組數(shù)量和檢修次數(shù)的線(xiàn)性加權(quán)最小為目標(biāo)函數(shù)，但目標(biāo)權(quán)重系數(shù)依賴(lài)于決策者的主觀(guān)判斷，在實(shí)際應(yīng)用中難以客觀(guān)地確定；并且對(duì)于2個(gè)定位不同的目標(biāo)，加權(quán)目標(biāo)實(shí)際意義不明確。因此，首先基于王昕[13]提出的思路，通過(guò)分析交路生成的可行性和合理性約束，建立動(dòng)車(chē)組交路備選集，從而將問(wèn)題通過(guò)多目標(biāo)整數(shù)規(guī)劃建模；進(jìn)而，基于重要性將目標(biāo)函數(shù)進(jìn)行分級(jí)，并通過(guò)分層序列法對(duì)模型進(jìn)行求解；最后通過(guò)算例驗(yàn)證模型的有效性。

圖1　動(dòng)車(chē)組交路計(jì)劃示例

1問(wèn)題描述

定義動(dòng)車(chē)組交路段為單個(gè)動(dòng)車(chē)組或重聯(lián)動(dòng)車(chē)組擔(dān)當(dāng)?shù)牧熊?chē)或列車(chē)組合；動(dòng)車(chē)組交路則由單個(gè)或若干個(gè)動(dòng)車(chē)組交路段組成，在動(dòng)車(chē)組列車(chē)運(yùn)營(yíng)過(guò)程中周期性地重復(fù)執(zhí)行。動(dòng)車(chē)組交路計(jì)劃示例如圖 1 所示。在同一個(gè)交路中，2 個(gè)相鄰交路段中前一交路段的終到站必須與后續(xù)交路段的始發(fā)站一致；交路中最后 1 個(gè)交路段的終到站必須與第 1 個(gè)交路段的始發(fā)站一致。在圖1中，動(dòng)車(chē)組 L1 所擔(dān)當(dāng)交路段 1 的始發(fā)、終到站一致，因而交路段 1 構(gòu)成單日交路；而交路段 2 的始發(fā)站和交路段 3 的終到站一致，并且交路段 2 和交路段 3 符合相鄰的接續(xù)關(guān)系，因而交路段 2 和交路段 3 組成 1 個(gè)雙日交路。動(dòng)車(chē)組交路計(jì)劃是根據(jù)動(dòng)車(chē)組管理和檢修規(guī)程規(guī)定、動(dòng)車(chē)組配屬情況，以及給定的列車(chē)運(yùn)行圖任務(wù)，制訂需要完成的列車(chē)擔(dān)當(dāng)任務(wù)和動(dòng)車(chē)組一級(jí)檢修任務(wù)的動(dòng)車(chē)組運(yùn)用計(jì)劃。

1.1動(dòng)車(chē)組交路的數(shù)學(xué)描述

1.2構(gòu)建動(dòng)車(chē)組交路的約束條件

動(dòng)車(chē)組交路計(jì)劃是高速鐵路/客運(yùn)專(zhuān)線(xiàn)的基本運(yùn)輸計(jì)劃之一，編制過(guò)程中的影響因素很多。為簡(jiǎn)化問(wèn)題，主要考慮以下約束條件。

（1）接續(xù)條件。由同一動(dòng)車(chē)組擔(dān)當(dāng)?shù)南噜?2 個(gè)交路段的間隔時(shí)間必須大于動(dòng)車(chē)組在車(chē)站進(jìn)行接續(xù)作業(yè)需要的最小時(shí)間；由同一動(dòng)車(chē)組擔(dān)當(dāng)?shù)南噜?2個(gè)交路段中，前一交路段的終點(diǎn)必須和后一交路段的起點(diǎn)相同。假定 Rh1, w1和 Rh2, w2為符合接續(xù)條件的任意 2 個(gè)交路段，tmin為最小接續(xù)時(shí)間，則有

（2）一級(jí)檢修條件。根據(jù)動(dòng)車(chē)組檢修規(guī)程，由同一動(dòng)車(chē)組擔(dān)當(dāng)?shù)慕宦范沃?，列?chē)的累計(jì)走行里程不能超過(guò)規(guī)定的一級(jí)檢修累計(jì)里程 (一般為4 000 km，允許上下浮動(dòng)各 10%)；同時(shí)，列車(chē)的累計(jì)運(yùn)行時(shí)間不能超過(guò)規(guī)定的一級(jí)檢修累計(jì)運(yùn)行時(shí)間 48 h。以給定的 2 d 列車(chē)運(yùn)行圖為基礎(chǔ)構(gòu)造的動(dòng)車(chē)組交路段必然滿(mǎn)足規(guī)定的一級(jí)檢修累計(jì)運(yùn)行時(shí)間約束，因而只需滿(mǎn)足一級(jí)檢修累計(jì)里程約束。

2動(dòng)車(chē)組交路計(jì)劃優(yōu)化模型

定義動(dòng)車(chē)組交路備選集合為 Rf；cr為擔(dān)當(dāng)動(dòng)車(chē)組交路 r 的動(dòng)車(chē)組數(shù)量，組，r?∈?Rf；xr為 0-1 決策變量，如果動(dòng)車(chē)組交路被選擇，則 xr= 1，否則為 xr= 0；Q 為動(dòng)車(chē)段所集合；bq, r表示交路 r 在動(dòng)車(chē)段所 q 占用的一級(jí)檢修能力，組，q?∈?Q；nq表示動(dòng)車(chē)段所 q 的一級(jí)檢修能力，組；L 為給定運(yùn)行圖中的所有運(yùn)行線(xiàn)的集合；δl, r為 0-1 變量，表示交路 r 是否覆蓋列車(chē)任務(wù) l，l?∈?L，如果覆蓋則 δl, r= 1，否則為 δl, r= 0；nr表示動(dòng)車(chē)組交路 r 的檢修次數(shù)，如果交路里程超過(guò)一級(jí)檢修里程，則檢修次數(shù)為 2 次，否則為 1 次。

以動(dòng)車(chē)組數(shù)量最少為主要優(yōu)化目標(biāo)、以檢修次數(shù)最少為次要優(yōu)化目標(biāo)構(gòu)建多目標(biāo)整數(shù)規(guī)劃模型。

（1）以動(dòng)車(chē)組數(shù)量最少為主要優(yōu)化目標(biāo)建立整數(shù)規(guī)劃模型 (以下簡(jiǎn)稱(chēng)“M-1 模型”)。

式中：公式 ⑷ 為目標(biāo)函數(shù)，表示以交路方案的動(dòng)車(chē)組數(shù)量最少為目標(biāo)；公式 ⑸ 為動(dòng)車(chē)段所檢修能力約束；公式 ⑹ 為列車(chē)任務(wù)覆蓋約束，要求每個(gè)列車(chē)任務(wù)必須被覆蓋，并且只覆蓋 1 次。

（2）從 M-1 模型可以求出當(dāng)前動(dòng)車(chē)組交路方案下所需的最少動(dòng)車(chē)組數(shù)量，以此為約束，以動(dòng)車(chē)組檢修次數(shù)最少為目標(biāo)建立整數(shù)規(guī)劃模型 (以下簡(jiǎn)稱(chēng)“M-2 模型”)。

式中：公式 ⑺ 表示所選擇交路方案的總檢修次數(shù)最少；公式 ⑻ 表示當(dāng)前選擇的交路方案所需的動(dòng)車(chē)組數(shù)量不能超過(guò) M-1 模型求解得到的最少動(dòng)車(chē)組數(shù)量；公式 ⑼ 和 ⑽ 與模型 M-1 的約束定義一致。

3動(dòng)車(chē)組交路計(jì)劃優(yōu)化模型求解

3.1交路備選集構(gòu)造算法

交路備選集是指具有實(shí)際開(kāi)行可能的、合理的動(dòng)車(chē)組交路集合，它是以列車(chē)運(yùn)行圖為輸入，以動(dòng)車(chē)組一級(jí)檢修里程和時(shí)間規(guī)定、動(dòng)車(chē)段所檢修能力為約束條件得到的備選交路集合。以 2 d 列車(chē)運(yùn)行圖為基礎(chǔ)構(gòu)造交路備選集，則擔(dān)當(dāng)任意可行交路的列車(chē)?yán)塾?jì)運(yùn)行時(shí)間滿(mǎn)足一級(jí)檢修時(shí)間周期約束。交路備選集構(gòu)造算法的流程如下。

（1）以單條運(yùn)行線(xiàn)構(gòu)造交路段，得到單條運(yùn)行線(xiàn)構(gòu)成的交路段集合 R1，置迭代次數(shù) n = 1。

（2）逐層進(jìn)行廣度優(yōu)先搜索過(guò)程，即以 n 條運(yùn)行線(xiàn)構(gòu)成的可行交路段集合 Rn構(gòu)造 ( n + 1) 條運(yùn)行線(xiàn)的可行交路段集合 Rn+1：遍歷可行交路段集合 Rn，任取 Rn中的第 i 個(gè)交路段 Rn, i，再遍歷集合 R1的任意交路段 R1,j，如果滿(mǎn)足公式 ⑴ 和公式 ⑵ 的約束條件，則將交路段 R1,j拼接到交路段 Rn, i之后，構(gòu)成 ( n + 1) 條運(yùn)行線(xiàn)組成的可行交路段，并添加到集合 Rn+1。

（3）對(duì)于 ( n + 1) 條運(yùn)行線(xiàn)構(gòu)成的可行交路段集合 Rn+1，如果交路段的始發(fā)和終到站一致，則該交路段為合理交路，將該交路添加到交路備選集 Rf中。如果存在里程超過(guò)一級(jí)檢修里程的交路，則進(jìn)行超修程交路的修正，將該交路的檢修次數(shù)增加1 次，并將該交路分解為不超修程的 2 個(gè)交路段，擔(dān)當(dāng)該交路段的動(dòng)車(chē)組滿(mǎn)足約束條件 ⑶ 的里程約束。

（4）每層循環(huán)結(jié)束后，將由 ( n + 1) 條運(yùn)行線(xiàn)構(gòu)成的可行交路段集合 Rn+1保存到 R 集合中，此時(shí)如果 Rn+1中仍然有交路段存在，令 n = n + 1，轉(zhuǎn)到步驟（3），否則退出循環(huán)。

（5）為提高動(dòng)車(chē)組運(yùn)用效率，設(shè)定每個(gè)動(dòng)車(chē)組的日均車(chē)公里數(shù)不少于 1 300 km，刪除交路備選集 Rf中日均車(chē)公里小于 1 300 km 的交路，得出合理的交路備選集。

3.2整數(shù)規(guī)劃模型求解

整數(shù)規(guī)劃求解的流程如下。

（1）根據(jù)給定的交路備選集 Rf，利用模型M-1 求解出最少動(dòng)車(chē)組使用數(shù)量。

（2）根據(jù)當(dāng)前交路方案求出的最少動(dòng)車(chē)組使用數(shù)量，利用模型 M-2 求出當(dāng)前交路方案最少檢修次數(shù)，如果無(wú)解，轉(zhuǎn)到步驟（3）；否則退出循環(huán)，得出最少檢修次數(shù)。

（3）松弛公式 ⑻ 的約束上界 F1，使最少動(dòng)車(chē)組數(shù)量加 1，如果當(dāng)前動(dòng)車(chē)組數(shù)量超過(guò)限定的最大動(dòng)車(chē)組使用數(shù)量 Fmax，則當(dāng)前交路方案無(wú)解，退出循環(huán)；否則轉(zhuǎn)到步驟（2）。

多目標(biāo)整數(shù)規(guī)劃求解流程如圖2所示。

圖2　多目標(biāo)整數(shù)規(guī)劃求解流程

4算例分析

以 2013年7月列車(chē)運(yùn)行圖上全部交路均在京廣(北京西—廣州南)、廣深 (廣州南—深圳北) 高速鐵路上的高速和動(dòng)車(chē)組列車(chē)作為研究對(duì)象，應(yīng)用構(gòu)建的模型和算法編制動(dòng)車(chē)組交路計(jì)劃，對(duì)模型進(jìn)行驗(yàn)證。

4.1數(shù)據(jù)準(zhǔn)備

（1）列車(chē)運(yùn)行圖數(shù)據(jù)。①始發(fā)、終到站包括北京西、石家莊、鄭州東、濟(jì)南西、西安北、信陽(yáng)東、武漢、漢口、岳陽(yáng)東、長(zhǎng)沙南、廣州南、深圳北站共 12 個(gè)。②各折返站的最小折返作業(yè)時(shí)間為tmin= 15 min。③開(kāi)行列車(chē) 38 對(duì)/d，列車(chē)最高運(yùn)行速度 300 km/h。

（2）動(dòng)車(chē)組數(shù)據(jù)。①動(dòng)車(chē)組一級(jí)檢修里程為4 000±400 km。②動(dòng)車(chē)段所檢修能力。京廣、廣深高速鐵路沿線(xiàn)設(shè)置的動(dòng)車(chē)段所不僅承擔(dān) 2 條線(xiàn)路上運(yùn)行動(dòng)車(chē)組的一級(jí)檢修任務(wù)，而且還承擔(dān)其他線(xiàn)路上的動(dòng)車(chē)組檢修任務(wù)。由于動(dòng)車(chē)組交路的特點(diǎn)，每個(gè)動(dòng)車(chē)段所每日實(shí)際檢修的動(dòng)車(chē)組數(shù)量不是定值，并且不同時(shí)段的動(dòng)車(chē)段所檢修能力占用情況也不同，因而應(yīng)分時(shí)段考慮動(dòng)車(chē)段所檢修能力。實(shí)際上，由于動(dòng)車(chē)組一級(jí)檢修工作主要集中在 20 : 00 到次日 8 : 00 之間進(jìn)行，該時(shí)段的檢修能力最為緊張，因而以該時(shí)間段的動(dòng)車(chē)段所一級(jí)檢修能力作為檢算數(shù)據(jù)。京廣、廣深高速鐵路沿線(xiàn)動(dòng)車(chē)段所檢修能力如表1所示。

表1　京廣、廣深高速鐵路沿線(xiàn)動(dòng)車(chē)段所檢修能力及檢修數(shù)量計(jì)算結(jié)果 　　　組

4.2計(jì)算結(jié)果

根據(jù)原運(yùn)行圖數(shù)據(jù)，完成算例中的全部列車(chē)運(yùn)行任務(wù)實(shí)際共需要?jiǎng)榆?chē)組 38 組，檢修 36 次。依據(jù)設(shè)計(jì)的模型和算法重新編制動(dòng)車(chē)組交路計(jì)劃，共構(gòu)造交路備選集 11 375 個(gè)，構(gòu)造時(shí)間為 0.43 s；按照模型 M-1 求出最少動(dòng)車(chē)組使用數(shù)量為 38 組，以此為約束條件按照模型 M-2 求解得出最少檢修次數(shù)為 32 次，比原運(yùn)行圖規(guī)定的檢修次數(shù)少 4 次，說(shuō)明采用該模型能夠進(jìn)一步優(yōu)化動(dòng)車(chē)組交路計(jì)劃。最后求解得到動(dòng)車(chē)組交路共 31個(gè)，其中單日單條交路 24 條，兩日交路 7 條，動(dòng)車(chē)組日均車(chē)公里2 526 km，平均一級(jí)檢修里程為 3 000 km。計(jì)算得到的各動(dòng)車(chē)段所檢修數(shù)量如表1所示，繪制的動(dòng)車(chē)組交路如圖3所示。

圖3　動(dòng)車(chē)組交路方案

5結(jié)束語(yǔ)

在動(dòng)車(chē)組交路計(jì)劃編制過(guò)程中考慮了動(dòng)車(chē)段所的一級(jí)檢修能力，運(yùn)用多目標(biāo)整數(shù)規(guī)劃模型按照最少動(dòng)車(chē)組數(shù)為主要優(yōu)化目標(biāo)，最少檢修次數(shù)為次要目標(biāo)，使用 Cplex 軟件進(jìn)行精確求解，得到滿(mǎn)足約束條件的最少運(yùn)用動(dòng)車(chē)組數(shù)和最少檢修次數(shù)。求解結(jié)果表明，該模型與算法可有效求解動(dòng)車(chē)組交路計(jì)劃編制問(wèn)題，獲得較優(yōu)的可行解。但是，目前的動(dòng)車(chē)組交路計(jì)劃優(yōu)化模型中考慮的約束較少，未考慮空車(chē)回送、動(dòng)車(chē)組車(chē)型等條件；此外，在運(yùn)行圖結(jié)構(gòu)固定的條件下動(dòng)車(chē)組運(yùn)用效率仍然存在提高空間。從優(yōu)化角度出發(fā)，列車(chē)運(yùn)行圖與動(dòng)車(chē)組交路計(jì)劃應(yīng)同步編制，協(xié)同優(yōu)化，才能最終實(shí)現(xiàn)動(dòng)車(chē)組運(yùn)用與列車(chē)運(yùn)行的最優(yōu)結(jié)合。

[1] 王 瑩，劉 軍，苗建瑞. 基于列生成算法的動(dòng)車(chē)組檢修計(jì)劃優(yōu)化[J]. 中國(guó)鐵道科學(xué)，2010，31 (2)：115-120.

WANG Ying，LIU Jun，MIAO Jian-rui. Column Generation Algorithms based Optimization Method for Maintenance Scheduling of Multiple Unit[J]. China Railway Science，2010，31(2)：115-120.

[2] 王 瑩. 動(dòng)車(chē)組運(yùn)用計(jì)劃和乘務(wù)計(jì)劃的優(yōu)化方法研究[D].北京：北京交通大學(xué)，2009.

[3] LU C， ZHOU L S， YUE Y X，et al. A Branch and Bound Algorithm for the Exact Solution of the Problem of EMU Circulation Scheduling in Railway Network[J]. Mathematical Problems in Engineering，2016 (2)：1-14.

[4] 李 華，韓寶明，李得偉，等. 求解動(dòng)車(chē)組交路計(jì)劃的改進(jìn)型蟻群算法[J]. 物流技術(shù)，2013，32(2)：145-147，160.

LI Hua，HAN Bao-ming，LI De-wei，et al. Research on Improved Ant Colony Algorithm in EMU Routing Schemes[J]. Logistics Technology，2013，32(2)：145-147，160.

[5] ZHOU Y，ZHOU L S，WANG Y，et al. Using Improved Ant Colony Algorithm to Investigate EMU Circulation Scheduling Problem[J]. Discrete Dynamics in Nature and Society，2014(2)：1-13.

[6] 王忠凱. 動(dòng)車(chē)組運(yùn)用檢修計(jì)劃優(yōu)化方法的研究[D]. 北京：中國(guó)鐵道科學(xué)研究院，2012.

[7] 李 華，韓寶明，張 琦，等. 動(dòng)車(chē)組交路計(jì)劃優(yōu)化模型與算法研究[J]. 鐵道學(xué)報(bào)，2013，35(3)：1-8.

LI Hua，HAN Bao-ming，ZHANG Qi，et al. Research on Optimization Model and Algorithm of EMU Circulation Plan[J]. Journal of the China Railway Society，2013， 35(3)：1-8.

[8] 李 建，林柏梁，耿令乾，等. 基于交路接續(xù)的動(dòng)車(chē)組運(yùn)用計(jì)劃優(yōu)化模型與算法[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2015，15(5)：172-177，194.

LI Jian，LIN Bo-liang，GENG Ling-qian，et al. Optimization Model and Algorithm for Motor Trainset Utilization Scheduling based on Routes Connection[J]. Journal of Transportation Systems Engineering and Information Technology，2015，15(5)：172-177，194.

[9] 苗建瑞，王 瑩，楊肇夏. 基于最優(yōu)接續(xù)網(wǎng)絡(luò)的動(dòng)車(chē)組交路計(jì)劃優(yōu)化模型與算法研究[J]. 鐵道學(xué)報(bào)，2010，32(2)：1-7.

MIAO Jian-rui，WANG Ying，YANG Zhao-xia. Research on the Optimization of EMU Circulation based on Optimized Connecting Network[J]. Journal of The China Railway Society，2010，32(2)：1-7.

[10] 黃興亮. 動(dòng)車(chē)組交路計(jì)劃編制優(yōu)化理論與方法研究[D]. 成都：西南交通大學(xué)，2012.

[11] 陳 然，周磊山，樂(lè)逸祥，等. 基于專(zhuān)家系統(tǒng)的網(wǎng)絡(luò)化動(dòng)車(chē)組運(yùn)用計(jì)劃的編制[J]. 中國(guó)鐵道科學(xué)，2016，37(1)：108-116.

CHEN Ran，ZHOU Lei-shan，YUE Yi-xiang，et al. Network EMU Scheduling based on Expert System[J]. China Railway Science，2016，37(1)：108-116.

[12] 余曉園，王 瑩，李元?jiǎng)P. 高速鐵路列車(chē)開(kāi)行模式對(duì)動(dòng)車(chē)組運(yùn)用的影響研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2016，38(7)：1-6，46.

YU Xiao-yuan，WANG Ying，LI Yuan-kai. Study on Influence of High-Speed Railway Train Operation Mode on Utilization of EMU[J]. RailwayTransport and Economy，2016，38(7)：1-6，46.

[13] 王 昕. 高速鐵路動(dòng)車(chē)組交路與列車(chē)運(yùn)行方案圖協(xié)調(diào)優(yōu)化方法研究[D]. 北京：北京交通大學(xué)，2015.

責(zé)任編輯：劉 新

Optimization Model and Algorithm for EMU Routing Plan with Constraint of Maintenance Capacity

JIANG Zheng-jie1, NIE Lei1, HE Zhen-huan1，TONG Jia-nan2

(1.School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China；2.The Second Civil Engineering Design & Research Institute，China Railway Eryuan Engineering Group CO.LTD, Chengdu 610036, Sichuan, China)

With less and unbalanced distribution of EMU depots in China, the capacity for Level-1 maintenance is becoming an important constraint of EMU routing plan. A multi-objective integer model for EMU routing plan is constructed with consideration of Level-1 maintenance capacity of EMU depot. Firstly, a potential set is constructed by considering the EMU route connection rule and the constraint of Level-1 maintenance condition, and the EMU routing plan is formulated as set partitioning problem. Secondly, based on the importance of the objectives, stratified sequencing method is used to decompose the multi-objective model into two single integral objective models by taking minimum number of EMU as the main objective and minimum maintenance as the secondary one, both of which can be solved by using the exact algorithm. Thirdly, a case study verifies the effectiveness of the optimization model and algorithm, and provides reference for the scheduling optimization of EMU routing plan.

High-Speed Railway; EMU Routing; Stratified Sequencing Method; Multi-Objective Integer Programming

1003-1421(2016)10-0077-06

U292.6

A

10.16668/j.cnki.issn.1003-1421.2016.10.16

2016-05-05

2016-08-29

國(guó)家自然科學(xué)基金資助項(xiàng)目(U1434207)；中國(guó)鐵路總公司科技研究開(kāi)發(fā)計(jì)劃課題(2013X014-C)