動車組運用作業(yè)調(diào)度問題研究

劉禹顯，牛 豐

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

0 引言

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

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

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

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

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

1.1 符號定義

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

1.2 決策變量和模型建立

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

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

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

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

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

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

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

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

2.2 動車組運用作業(yè)調(diào)度方案目標計算

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

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

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

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

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

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

2.3 解的擾動策略和接受機制

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

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

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

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

2.5 算法框架和求解步驟

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

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

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

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

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

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

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

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

步驟6：降溫過程，以一定速率進行冷卻退火。

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

3 算例分析

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

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

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

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

表1 可用動車組集合的信息Tab.1 Available EMU groups information

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

表2 列車運行圖信息Tab.2 Train working diagram information

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

3.2 算例結(jié)果

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

4 結(jié)束語

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