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

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

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

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

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

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

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

0引言

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

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

既有研究中大都以動(dòng)車組數(shù)量和檢修次數(shù)的線性加權(quán)最小為目標(biāo)函數(shù)，但目標(biāo)權(quán)重系數(shù)依賴于決策者的主觀判斷，在實(shí)際應(yīng)用中難以客觀地確定；并且對(duì)于2個(gè)定位不同的目標(biāo)，加權(quán)目標(biāo)實(shí)際意義不明確。因此，首先基于王昕[13]提出的思路，通過(guò)分析交路生成的可行性和合理性約束，建立動(dòng)車組交路備選集，從而將問(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)車組交路計(jì)劃示例

1問(wèn)題描述

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

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

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

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

（1）接續(xù)條件。由同一動(dòng)車組擔(dān)當(dāng)?shù)南噜?2 個(gè)交路段的間隔時(shí)間必須大于動(dòng)車組在車站進(jìn)行接續(xù)作業(yè)需要的最小時(shí)間；由同一動(dòng)車組擔(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)車組檢修規(guī)程，由同一動(dòng)車組擔(dān)當(dāng)?shù)慕宦范沃?，列車的累?jì)走行里程不能超過(guò)規(guī)定的一級(jí)檢修累計(jì)里程 (一般為4 000 km，允許上下浮動(dòng)各 10%)；同時(shí)，列車的累計(jì)運(yùn)行時(shí)間不能超過(guò)規(guī)定的一級(jí)檢修累計(jì)運(yùn)行時(shí)間 48 h。以給定的 2 d 列車運(yùn)行圖為基礎(chǔ)構(gòu)造的動(dòng)車組交路段必然滿足規(guī)定的一級(jí)檢修累計(jì)運(yùn)行時(shí)間約束，因而只需滿足一級(jí)檢修累計(jì)里程約束。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4算例分析

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

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

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

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

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

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

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

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

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

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

[1] 王 瑩，劉 軍，苗建瑞. 基于列生成算法的動(dòng)車組檢修計(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)車組運(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)車組交路計(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)車組運(yùn)用檢修計(jì)劃優(yōu)化方法的研究[D]. 北京：中國(guó)鐵道科學(xué)研究院，2012.

[7] 李 華，韓寶明，張 琦，等. 動(dòng)車組交路計(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)車組運(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)車組交路計(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)車組交路計(jì)劃編制優(yōu)化理論與方法研究[D]. 成都：西南交通大學(xué)，2012.

[11] 陳 然，周磊山，樂(lè)逸祥，等. 基于專家系統(tǒng)的網(wǎng)絡(luò)化動(dòng)車組運(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. 高速鐵路列車開(kāi)行模式對(duì)動(dòng)車組運(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)車組交路與列車運(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)