劉禹顯，牛 豐

（1.鐵道黨校 研修培訓(xùn)中心，北京 100088；2.中國(guó)鐵路總公司 辦公廳，北京 100844)

0 引言

動(dòng)車組在我國(guó)鐵路旅客運(yùn)輸中得到廣泛應(yīng)用，我國(guó)高速動(dòng)車組列車在旅客列車中的比重已超過(guò)50%。推進(jìn)包括動(dòng)車組運(yùn)用在內(nèi)的鐵路運(yùn)輸組織和調(diào)度指揮智能化，是“十三五”期間我國(guó)鐵路面臨信息化的重要任務(wù)。目前我國(guó)鐵路運(yùn)輸?shù)膶?shí)際生產(chǎn)操作中，動(dòng)車組列車作業(yè)調(diào)度計(jì)劃主要依靠人工經(jīng)驗(yàn)制訂，存在著環(huán)境適應(yīng)性差、計(jì)劃效率低等問(wèn)題。因此，建立能夠?yàn)橄嚓P(guān)信息系統(tǒng)開發(fā)奠定基礎(chǔ)的優(yōu)化方法具有重要意義。

目前在動(dòng)車組運(yùn)用方面的研究主要集中于動(dòng)車組運(yùn)用計(jì)劃安排和動(dòng)車組運(yùn)用作業(yè)調(diào)度2個(gè)方面。前者主要關(guān)注動(dòng)車組運(yùn)用數(shù)量和循環(huán)運(yùn)用；后者主要研究在日常運(yùn)輸組織過(guò)程中一定動(dòng)車組資源的合理運(yùn)用問(wèn)題。一些學(xué)者將動(dòng)車組運(yùn)用計(jì)劃編制轉(zhuǎn)化成不考慮檢修約束的指派問(wèn)題和考慮動(dòng)車組檢修約束的(多)旅行商2類問(wèn)題。由于我國(guó)路網(wǎng)和列車開行數(shù)量規(guī)模較大，因而在求解時(shí)常采用啟發(fā)式算法，包括基于概率的局域搜索算法、蟻群算法、模擬退火算法、遺傳算法、大規(guī)模鄰域搜索算法[2-4]，以及采用列生成法等精確算法求解[5]。在國(guó)外，Lin等[6]、Cacchiani等[7]分別采用分枝定界和拉格朗日松弛方法求解動(dòng)車組運(yùn)用作業(yè)調(diào)度問(wèn)題。

動(dòng)車組運(yùn)用作業(yè)調(diào)度(Train Unite Scheduling Problem，TUSP)是以列車運(yùn)行圖中各列車始發(fā)終到時(shí)間關(guān)系和可使用的動(dòng)車組資源為基礎(chǔ)，結(jié)合運(yùn)輸組織實(shí)際情況[8]，特別是動(dòng)車組狀態(tài)約束、動(dòng)車組類型約束、動(dòng)車組運(yùn)用接續(xù)條件約束，有效降低動(dòng)車組接續(xù)成本，對(duì)動(dòng)車組日常運(yùn)用方案進(jìn)行合理安排的問(wèn)題。研究基于TUSP問(wèn)題和列車運(yùn)行圖之間的關(guān)系，構(gòu)建混合整數(shù)規(guī)劃模型，并采用模擬退火求解算法，通過(guò)高速鐵路網(wǎng)絡(luò)實(shí)際算例進(jìn)行分析。

1 TUSP問(wèn)題描述與模型構(gòu)建

TUSP問(wèn)題通常以在給定列車運(yùn)行圖和動(dòng)車組資源條件下，確定出每一動(dòng)車組所需擔(dān)當(dāng)車次及其順序的合理方案，以實(shí)現(xiàn)最低動(dòng)車組接續(xù)成本最小化的目標(biāo)。同時(shí)，TUSP問(wèn)題還需滿足下列要求。①可使用動(dòng)車組資源的運(yùn)用時(shí)間范圍：每個(gè)動(dòng)車組可被運(yùn)用的時(shí)間范圍是全日列車運(yùn)行圖的運(yùn)營(yíng)時(shí)段。②動(dòng)車組狀態(tài)約束： 每個(gè)動(dòng)車組投入運(yùn)用的起始空間位置已知，動(dòng)車組狀態(tài)由運(yùn)用作業(yè)調(diào)度方案決定。③動(dòng)車組類型約束：每個(gè)車次的擔(dān)當(dāng)動(dòng)車組類型符合要求。④動(dòng)車組運(yùn)用接續(xù)條件約束：每個(gè)動(dòng)車組擔(dān)當(dāng)?shù)南噜徿嚧伍g滿足接續(xù)時(shí)間要求。根據(jù)上述描述，TUSP問(wèn)題的集合、參數(shù)和變量定義如下。

1.1 符號(hào)定義

車站集合S = {1，2，…，l}；列車運(yùn)行圖車次集合為T = {1，2，…，n}；動(dòng)車組運(yùn)用的車次集合T' = {0，…，n + 1}，其中0和n + 1是虛擬車次，0為所有動(dòng)車組的起始虛擬車次，n + 1為動(dòng)車組的終止車次，即每個(gè)動(dòng)車組的運(yùn)用工作必須從0開始，以n + 1結(jié)束；可用動(dòng)車組集合D = {1，2，…，m}；車次i的類型要求為TRi，i ∈?R；車次i的始發(fā)終到時(shí)刻分別為REi和RLi，i ∈?R；動(dòng)車組k的類型為DCk，k ∈?D；動(dòng)車組k從車次i接續(xù)車次j的成本為 Cijk，i，j ∈?T'，k ∈?D，Cijk包括列車始發(fā)終到站和始發(fā)終到車站位置相關(guān)的接續(xù)成本，包含接續(xù)時(shí)間成本Tijk、異地接續(xù)空駛成本dijk兩部分，計(jì)算公式為Cijk= Tijk+ Mdijk，其中M為動(dòng)車組回送的權(quán)重系數(shù)，可取為一個(gè)很大的常數(shù)；車次i與車次 j間的接續(xù)時(shí)間為 Tij，i，j ∈?T'，k ∈?D，其與車次i的終到時(shí)刻和車次j的始發(fā)時(shí)刻有關(guān)；動(dòng)車組整備時(shí)間為P。

1.2 決策變量和模型建立

引入動(dòng)車組的車次擔(dān)當(dāng)次序變量xijk和動(dòng)車組的車次接續(xù)關(guān)系變量。其中，若動(dòng)車組k (k ∈?V)先擔(dān)當(dāng)車次i再接續(xù)擔(dān)當(dāng)車次j，則xijk= 1，否則xijk= 0；若車次i與車次j由某一動(dòng)車組擔(dān)當(dāng)，并存在接續(xù)關(guān)系，則yij= 1，否則yij= 0。將xijk和yij作為求解動(dòng)車組運(yùn)用作業(yè)調(diào)度方案的決策變量，以最小化接續(xù)成本為目標(biāo)，建立TUSP問(wèn)題的優(yōu)化模型如下。

其中，公式 ⑴ 為最小化接續(xù)成本的目標(biāo)函數(shù)。公式 ⑵—⑸ 為動(dòng)車組狀態(tài)約束：公式 ⑵—⑶ 表示每一動(dòng)車組從擔(dān)當(dāng)車次0開始到車次n + 1結(jié)束；公式⑷ 表示每一動(dòng)車組擔(dān)當(dāng)車次存在緊前緊后的守恒關(guān)系；公式 ⑸ 為 yij與 xijk間的關(guān)系。公式 ⑹ 為動(dòng)車組類型約束，也即執(zhí)行車次j的動(dòng)車組類型與該車次所需車型需求相匹配；公式 ⑺ 為動(dòng)車組運(yùn)用接續(xù)條件約束，即當(dāng)車次i、車次j間存在緊前緊后接續(xù)關(guān)系時(shí)，擔(dān)當(dāng)車次j的開始時(shí)刻不能早于車次i的完成擔(dān)當(dāng)時(shí)刻加上整備時(shí)間和接續(xù)時(shí)間。公式 ⑻—⑾為變量的取值約束，其中公式 ⑻ 表示若i = j，則xiik和yii為0，即動(dòng)車組運(yùn)用不存在重復(fù)車次；公式 ⑼ 表示0車次不存在緊前車次；公式 ⑽ 表示n + 1車次不存在緊后車次；公式 ⑾ 表示任何xijk和yij的0-1變量取值約束。

上述TUSP模型是一個(gè)混合整數(shù)規(guī)劃，以動(dòng)車組接續(xù)成本最小化作為優(yōu)化目標(biāo)，約束條件全面考慮了動(dòng)車組運(yùn)用作業(yè)調(diào)度的各項(xiàng)要求，使得模型的解能夠滿足動(dòng)車組運(yùn)用作業(yè)調(diào)度的實(shí)際需求。

2 基于車次順序的模擬退火算法

由于TUSP較為復(fù)雜，屬于NP-hard問(wèn)題，現(xiàn)有商用軟件很難在可控時(shí)間內(nèi)完成實(shí)際規(guī)模問(wèn)題的求解，因而采用模擬退火算法求解。模擬退火(Simulated Annealing，SA)算法最早由Ward等[9]引入組合優(yōu)化領(lǐng)域。這一算法是一種局部搜索算法，但能以一定概率接受一個(gè)劣解，從而有效避免陷入局部最優(yōu)。

2.1 基于車次順序列表的構(gòu)解方法

將動(dòng)車組運(yùn)用作業(yè)調(diào)度方案表示為一個(gè)車次順序列表。根據(jù)列車運(yùn)行圖車次集合T，隨機(jī)生成一組包含1-n的車次順序列表T_list。例如，當(dāng)列車集合有10個(gè)車次時(shí)，車次列表T_list為一包含1—10的列向量 (5，7，8，9，2，10，3，6，1，4)。

在車次順序列表中，一個(gè)動(dòng)車組擔(dān)當(dāng)車次的范圍從上一動(dòng)車組擔(dān)當(dāng)車次之后一車次起，至在運(yùn)營(yíng)時(shí)間內(nèi)，滿足各項(xiàng)約束條件，可擔(dān)當(dāng)車次止的一個(gè)連續(xù)的車次順序列表片段。

2.2 動(dòng)車組運(yùn)用作業(yè)調(diào)度方案目標(biāo)計(jì)算

根據(jù)動(dòng)車組運(yùn)用作業(yè)調(diào)度方案和車次順序列表對(duì)應(yīng)關(guān)系，其目標(biāo)函數(shù)值計(jì)算流程如下。

（1）按照車次順序列表T_list順序選取分配的車次i。

（2）可用動(dòng)車組列表D_list生成。校驗(yàn)動(dòng)車組集合D中車輛k空閑時(shí)間段與車次i所需起止時(shí)間段是否匹配。如果有滿足上述條件的匹配，則將該車次存入可用動(dòng)車組列表D_list。

（3）動(dòng)車組任務(wù)指派。選取D_list中滿足車次i的動(dòng)車組類型需求的調(diào)運(yùn)成本最低動(dòng)車組組合，將對(duì)應(yīng)動(dòng)車組時(shí)間段安排車次i。

（4）更新動(dòng)車組任務(wù)安排狀態(tài)。將D_list中被分配動(dòng)車組在車次i起止時(shí)間狀態(tài)更改為被占用。

（5）調(diào)運(yùn)成本計(jì)算。待任務(wù)列表中所有車次都分配完畢，計(jì)算所使用的動(dòng)車組的接續(xù)成本，得到目標(biāo)函數(shù)值。

2.3 解的擾動(dòng)策略和接受機(jī)制

采用隨機(jī)置換方法對(duì)當(dāng)前車次順序列表進(jìn)行擾動(dòng)，即在當(dāng)前任務(wù)列表中隨機(jī)選2個(gè)車次位置id_1與id_2，交換2個(gè)車次位置D_list (id_1)與D_list (id_2)。例如，隨機(jī)選擇到2.2節(jié)中車次順序列表的第3位與第6位，置換對(duì)應(yīng)位置的車次后，新的車次順序列表變?yōu)?5，7，10，9，2，8，3，6，1，4)。

由于優(yōu)化模型屬于最小化問(wèn)題，若Δf＜0，則接受新車次順序列表以及所求得的新解；若Δf≥0，則采用Metropolis接受準(zhǔn)則，即計(jì)算接受概率exp (-df / T )，若大于(0，1)之間的隨機(jī)數(shù)rand，則同樣接受新車次順序列表及新解；否則保留當(dāng)前車次順序列表及當(dāng)前解。

2.4 模擬退火冷卻進(jìn)度表和終止規(guī)則

冷卻進(jìn)度表影響模擬退火算法的性能，其包括初始溫度T0，結(jié)束溫度Tend，冷卻速率r，Markov鏈長(zhǎng)L。

2.5 算法框架和求解步驟

根據(jù)以上算法設(shè)計(jì)思想，基于車次分配列表的模擬退火算法框架如圖1所示。

圖1 模擬退火算法框架圖Fig.1 Algorithm framework of SA

模擬退火算法的步驟如下。

步驟1：初始化參數(shù)，設(shè)定初始溫度T = T0。

步驟2：隨機(jī)生成各動(dòng)車組擔(dān)當(dāng)車次順序的初始列表T_list，并計(jì)算目標(biāo)函數(shù)f (T_list)。

步驟3：擾動(dòng)產(chǎn)生各動(dòng)車組擔(dān)當(dāng)車次順序的列表T'_list，重新計(jì)算目標(biāo)函數(shù)f (T'_list)。

步驟4：判斷目標(biāo)函數(shù)是否更優(yōu)，若是，則接受新車次列表與新解；否則按Metropolis準(zhǔn)則以一定概率接受新車次列表與新解。

步驟5：判斷是否達(dá)到迭代次數(shù)，若是，則執(zhí)行步驟6；否則執(zhí)行步驟3。

步驟6：降溫過(guò)程，以一定速率進(jìn)行冷卻退火。

步驟7：判斷是否達(dá)到終止條件，若是則輸出解；否則執(zhí)行步驟3。

3 算例分析

3.1 算例數(shù)據(jù)

為了驗(yàn)證所設(shè)計(jì)的基于任務(wù)列表的模擬退火算法對(duì)TUS問(wèn)題的求解效果，選擇我國(guó)中東部高速鐵路網(wǎng)絡(luò)和列車運(yùn)行圖數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，我國(guó)中東部高速鐵路網(wǎng)絡(luò)如圖2所示。可用動(dòng)車組集合的信息如表1所示，需要承擔(dān)列車運(yùn)行圖上26個(gè)車次的擔(dān)當(dāng)任務(wù)，各車次所需動(dòng)車組類型、始發(fā)站、終點(diǎn)站及始發(fā)終到時(shí)刻等列車運(yùn)行圖信息如表2所示。

考慮到算例規(guī)模，所采用的模擬退火算法參數(shù)為：T0= 1 000，Tend= 0.001，r = 0.95，L = 100。這些參數(shù)可使Metropolis接受概率在高溫狀態(tài)接近

圖2 我國(guó)中東部高速鐵路網(wǎng)絡(luò)Fig.2 High-speed railway network in Central and East China

表1 可用動(dòng)車組集合的信息Tab.1 Available EMU groups information

1，在低溫時(shí)概率接近0，符合模擬退火算法的收斂要求。

表2 列車運(yùn)行圖信息Tab.2 Train working diagram information

圖3 動(dòng)車組運(yùn)用作業(yè)調(diào)度優(yōu)化方案的甘特圖Fig.3 Gantt chart of EMU operation scheduling optimization

3.2 算例結(jié)果

根據(jù)算例數(shù)據(jù)和算法參數(shù)，利用基于車次順序列表的模擬退火算法求解。優(yōu)化方案需使用動(dòng)車組6列，即D1，D3，D5，D7，D10，D11， 動(dòng)車組運(yùn)用作業(yè)調(diào)度優(yōu)化方案的甘特圖如圖3所示。在優(yōu)化方案中，D5為濟(jì)南—青島間異地接續(xù)，其他均為本地接續(xù)。各動(dòng)車組完成當(dāng)日運(yùn)用任務(wù)后，可依據(jù)所處位置進(jìn)行下一日運(yùn)用作業(yè)調(diào)度安排。

4 結(jié)束語(yǔ)

動(dòng)車組運(yùn)用作業(yè)調(diào)度問(wèn)題是高速鐵路運(yùn)輸組織研究的重要問(wèn)題。由于動(dòng)車組運(yùn)用作業(yè)調(diào)度問(wèn)題是一個(gè)復(fù)雜的組合優(yōu)化問(wèn)題，無(wú)論在理論上還是實(shí)踐中都難以得到精確最優(yōu)解。通過(guò)對(duì)列車運(yùn)行圖和動(dòng)車組作業(yè)調(diào)度計(jì)劃之間關(guān)系的分析，將其歸結(jié)為以最小化接續(xù)成本為目標(biāo)的混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了一種基于車次順序列表的模擬退火算法對(duì)該問(wèn)題進(jìn)行求解。利用我國(guó)中東部區(qū)域部分高速鐵路列車實(shí)際數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，優(yōu)化結(jié)果表明算法可以有效解決動(dòng)車組運(yùn)用作業(yè)調(diào)度方案制訂問(wèn)題。研究所建立的優(yōu)化模型和優(yōu)化算法具有較好的可拓展性，對(duì)更大規(guī)模的路網(wǎng)和更多高速鐵路車次的實(shí)際問(wèn)題同樣適用，能夠?yàn)閯?dòng)車組運(yùn)用調(diào)度工作提供高效的決策支持。但是，由于我國(guó)高速鐵路網(wǎng)絡(luò)存在多種類型動(dòng)車組運(yùn)用的實(shí)際情況，下一步研究工作可以通過(guò)模型和算法的擴(kuò)展，使之能夠適用于多種類型動(dòng)車組列車等更復(fù)雜情形。