基于增強模擬退火算法的動車所調車作業計劃多目標優化方法

劉 毅，唐秋華，何 明

(1.武漢科技大學 冶金裝備及其控制教育部重點實驗室，湖北 武漢 430081；2.武漢科技大學機械傳動與制造工程湖北省重點實驗室，湖北 武漢 430081)

0 引言

動車運用所調車作業計劃是進行動車組清洗、檢修等基礎維護作業的行動指南。合理編制調車作業計劃可極大提升動車所的作業安全性與使用效率。目前，動車所在實際作業過程中，常由于調車作業計劃不合理，導致作業股道、咽喉區被無效占用，使得待檢修動車組長時間等待或進行過多非必要轉線。因此，亟需合理編制動車組調車作業計劃，提高資源利用率，減少無效等待時間。

針對該問題，殷迪等[1]構建了整數規劃模型，童佳楠等[2]將其轉換為具有特殊過程約束的混合流水作業車間調度問題。史錦堂等[3]重點考慮靈活存車和列位占用問題。戶佐安等[4]建立了考慮股道列位占用的動車所調車作業計劃編制優化模型。張惟皎等[5]重點考慮存車線的列位占用問題，建立存車線運用優化模型。以上研究多聚焦于列位占用、總作業時長等單目標優化問題，忽略了實際作業往往具有多個互相沖突的目標。例如，動車組在轉換作業區時需要進行股道間轉線，轉線所跨越的股道數量越多，調車作業的耗時和費用也將越大，轉線復雜度越高。此外，以上研究在作業模式上，主要考慮需要清洗、檢修2 項任務的作業類型，而未考慮僅需進行檢修作業的動車組在計劃中的作業安排。因此，需要在常規目標基礎上，另行考慮轉線復雜度的影響，同時在計劃編制中，增加僅檢修的作業模式，提升調車計劃的實際性。

在求解方法方面，已有文獻主要采用遺傳算法(GA)、粒子群算法(PSO)等群智能算法。其中，韓寶明等[6]提出一種改進遺傳算法，用以求解動車所一級修靈活作業順序的非線性整數模型。王家喜等[7]以調車總鉤數最少為目標，利用粒子群優化算法求解。與群智能算法相比，局部搜索算法更加關注問題特點、參數較少且魯棒性強，亦可用于求解動車所調車作業計劃多目標優化問題。

據此，提出一種增強模擬退火算法，通過設計基于啟發式規則的解碼策略及基于歸檔集的重啟機制[8]，用以求解以動車所調車作業時間最小化、調車作業轉線復雜度最小化為目標的多目標優化問題。

1 問題描述

動車所按照其功能主要包括存車區、清洗區、檢修區、輔助股道等部分，多采用盡頭式布局方式，各區域之間通過咽喉區相連，構成完整的動車所檢修系統。動車組在完成當日載客任務后，進入存車區，根據清洗區和檢修區的使用情況選擇下一步作業；完成全部作業任務后，返回存車區待命。若下一步作業的所有股道均被占用或下一步作業所在區域與當前作業區之間咽喉區轉線股道被占用，則只能在原位置等待，直至上述2 個條件均已滿足，才能繼續進行作業。盡頭式動車所如圖1所示。

圖1 盡頭式動車所Fig.1 Stub-end EMU depot

咽喉區存在于動車所相鄰作業區之間，內部匯聚道岔等轉線設備，是動車組進行作業區轉換的必經之路。咽喉區股道同其他作業股道均具有獨占性，但不允許等待，動車組需按時通過，進入下一工序。為簡化問題，將每個咽喉區處理為一條特殊的作業股道，其操作時長等于轉線時長。咽喉區股道運用頻率極高，在時間和空間維度都可能存在不相容性，因而是動車所作業編制問題中的重難點。此外，動車組在進行不同作業區之間轉換時，需通過咽喉區股道進行轉線，動車組轉線需要調動人員、設備等多方面資源[9]。轉線所跨越股道的數目增加會使調車作業的難度和資源消耗增大，不合理的轉線方案也會降低動車組在作業區之間轉換的安全性[10]。

由此，動車所調車作業計劃優化問題可總結為：在動車所設備資源、布局等前提確定情況下，編制可行的動車所調車作業計劃，力求獲得更小的總調車作業時間及更低的轉線復雜度。

2 數學模型

該問題需同時優化調車作業計劃總時間、轉線復雜度2 個目標，基于此構建多目標優化模型。符號說明如表1所示。

表1 符號說明Tab.1 Symbol description

2.1 目標函數

動車組進所后，按照調車作業計劃完成任務，進入存車區等候出所?？傋鳂I時間越短，在存車區等候時間越長，則該計劃的魯棒性越強；采用調車作業計劃的轉線所跨越股道總數量化轉線復雜度。降低作業計劃的轉線復雜度，調車作業的難度與費用也會降低。據此，多目標函數由公式⑴—⑵組成。

公式⑴表示最小調車作業計劃總作業時間；公式⑵表示最小調車作業計劃轉線復雜度。

2.2 優化模型

對股道分配進行約束。

公式⑶表示可變作業模式動車組須從A，B兩種作業模式選擇一種作業模式。

公式⑷表示選定作業模式后，每個階段的操作 需在指定作業區內進行。

公式⑸—⑹表示任一股道上的作業需按先后順序分配，且每一位置上最多只能分配一個任務。

對時序邏輯進行約束。

公式⑺表示股道d上第g+ 1項操作的開始時刻不得早于其第g項操作的結束時刻。

公式⑻—⑼表示動車組e第s個作業的結束時刻大于其開始時刻加上該作業區的標準作業時間；完成任務后原地等待轉線。

公式⑽—⑾表示動車組e第s個作業步驟的結束時刻加上標準轉線時間，等于其第s+1 個作業步驟的開始時刻。

公式⑿—⒀表示股道d上進行的第g項操作開始 時刻等于所分配的動車組e第s個作業的開始時刻。

公式⒁—⒂表示股道d上進行的第g項操作結束時刻等于所分配動車組e第s個作業的結束時刻。

3 增強模擬退火算法

動車所調車作業計劃編制問題包含時間和空間多維約束條件，影響因素多[11]；隨著動車組數目的增加，求解難度逐步增大，屬于NP-hard 問題。在實際工作中，傳統人工編制方法并不能滿足檢修計劃對于速度和安全性的實際需求，因而擬采用智能優化算法對該問題進行求解[12]?？紤]到模擬退火算法具有參數較少、魯棒性強、適用于求解復雜非線性優化問題的特點，選用其作為優化算法，并結合問題特征進行改進，以獲得更好的求解效果。

3.1 編碼及初始化

3.1.1 問題編碼

解的編碼策略如圖2 所示，調車作業計劃編碼由2 段長度為動車組列數的字符串組成，第一串對應于決策變量Xe，l，表示各動車組的檢修模式，只能是A，B，C 3種模式中的一種。第二串為各動車組的作業先后順序。

圖2 解的編碼策略Fig.2 Encoding strategy of solutions

3.1.2 基于入所時間的初始化

初始解性能對局部搜索算法求解速度影響較大，而隨機初始化會使得初始解質量較差，需進行適當改善[13]。為此，針對作業順序排序，設定先進入存車區的車輛在各作業區具備更高的作業優先權，便于及早完成檢修任務，回歸存車區待命；同時還能最小化各動車組在動車所的作業流程時間，減少沖突與無效等待時間，使得各動車組能夠提前做好出所準備。

3.2 基于組合啟發式規則的解碼設計

動車所調車作業計劃編制約束復雜，在解碼時易造成股道分配沖突，導致解不可行，求解效率極低[14]。因此，擬設計組合啟發式規則，通過明晰空閑股道選擇方式、同一股道上的沖突消解方式，在給定編碼前提下獲得性能較優的解。

3.2.1 股道分配規則

在動車組進行作業區間轉換時，為明確股道分配方式，并避免無效的股道變換，導致轉線復雜度上升，設計股道分配規則進行約束。

在對任意動車組e的下一項作業進行股道分配時，檢查作業區r所有股道DR當前占用情況，并找出最早空閑股道分配給e；若此時無空閑股道，需使該動車組在當前作業股道等待，直至下一項作業區存在空閑股道；當有多條空閑股道同時存在時，考慮作業區股道布置采用近似對稱的方式，各作業區通過咽喉區股道相連；咽喉區股道視為一條特殊股道，處于動車所布局中軸線上。因此，在為某動車組e分配作業股道時，優先分配靠近中軸線的股道，以減少動車組轉換作業區時跨越的股道數量、降低轉線復雜度，采用以下方式選擇轉線復雜度最小股道作為目標股道。

設定咽喉區股道所處位置為中軸線，則其距離中軸線的偏差值為0。計算其余股道與中軸線的偏差值，并據此進行股道選擇。首先遍歷該作業區z的所有股道，篩選出所有空閑股道，然后依據公式⒃優先選擇股道偏差最小的股道d‘，并將該股道分配給動車組e。若多條股道存在相同股道偏差，則隨機選擇其中一條股道作為待分配股道。

3.2.2 沖突消解規則

動車所調車作業沖突現象主要是由于計劃編制的不合理性，造成2 列或多列動車組在安排至相同作業股道的工作時間存在沖突，致使計劃不可行[15]。由于我國動車所多采用盡頭式布局，在調車作業上存在折返性，以存車區為起始點，檢修區為終止點。動車組行進方向為檢修區定義為正向，行進方向為存車區定義為反向。沖突可能由正向或反向的多列動車組造成。針對該現象，設計相應沖突消解規則進行解決。

若動車組Ne與Ne+1在股道d上存在沖突，判斷兩動車組的行進方向，若均為同一方向，比較兩動車組在該股道進行作業的起始時間Ie，s和Ie+1，s，若Ie，s

3.2.3 基于組合啟發式規則的解碼流程

在前述規則基礎上，解碼步驟如下。

步驟1：獲得一個解，如｛(B，A，B，A，C，B，C，B)，(3，2，5，4，1，7，8，6)｝。

步驟2：運用股道分配規則給動車組分配相應股道。

步驟3：判斷沖突。①判斷該解是否存在沖突情況；②若存在，使用沖突消解規則；若不存在，轉步驟4。

步驟4：生成一個可行的調車作業計劃。

3.3 鄰域搜索

針對解的編碼方式，通過兩種鄰域搜索方式，來保證算法解的可行性和多樣性。

（1）針對作業順序編碼，隨機選擇編碼中相鄰兩點，交換其作業順序與作業模式。

（2）針對檢修模式編碼，隨機選擇編碼中一點，若其作業模式為先清洗后檢修，則變為先檢修后清洗，反之亦然。僅檢修作業模式由于其固定的作業屬性，不參與該鄰域搜索。

3.4 基于Pareto的性能評價

由于算法需要同時考慮調車作業最小總時間和最小轉線復雜度2 個優化目標，因而引用Pareto 優化概念，通過個體間的支配關系判斷解的優劣程度，均衡各目標解之間的關系。對于某一解Scurrent，若其他解均無法支配該解，則稱Scurrent為一個非支配解，所有的非支配解放入歸檔集中，定義為F。關于歸檔集更新，若通過鄰域結構變化產生的新解Snew，可支配歸檔集F中任意一個解Si，則將Snew放入歸檔集，并刪除歸檔集中所有可支配解，構成新的非支配解歸檔集。

3.5 基于歸檔集的重啟機制

模擬退火屬于局部搜索算法，在求解問題時，為避免陷入局部最優解，使歸檔集中解的分布更優，設定重啟觸發參數dn=0，Dn為啟動重啟機制的臨界值?？紤]問題規模對算法獲得更優解的影響，取Dn=Ne∕2，其中Ne為動車組數量。當連續迭代次數超過Dn次而未更新歸檔集時，即dn>Dn時，觸發重啟機制，選取歸檔集中最優個體解作為算法當前解開始迭代。最優個體解通過使用擂臺賽法則對每一代中歸檔集進行計算獲得。

3.6 算法求解流程

改進多目標模擬退火算法流程圖如圖3 所示。首先，輸入當日各動車組運用計劃、各作業區標準作業時間等相關數據。算法開始，產生初始解。隨后通過啟發式規則進行解碼，并通過鄰域搜索更新獲得新解。在更新解的過程中，采用改進收斂準則接受劣解；若出現非支配解，更新歸檔集；當滿足重啟條件時對算法進行重啟。滿足終止條件后，算法結束，輸出歸檔集并獲得最終調車作業計劃方案。

圖3 改進多目標模擬退火算法流程圖Fig.3 Procedure of multi-objective simulated annealing algorithm

4 實例分析

某動車運用所某日動車組運用計劃案例如表2所示，其中D8 列動車組為僅檢修模式，其余動車組需進行清洗、檢修2 項任務。建立多類型股道資源案例如表3 所示。在下述實驗中，各作業區標準作業時間為：清洗區p1= 5 min，咽喉區股道p2=p5= 6 min，清洗區p3= 60 min，輔助股道p4= 4 min，檢修區p6= 150 min，且各工作區作業時間固定不變。

表2 動車組運用計劃案例Tab.2 EMU rescheduling cases

表3 股道資源案例Tab.3 Track resource case

經過多次實驗比較，采用T0=15 000，Maxgen=150，Alpfa=0.9，LK=30作為實驗參數，所提EMOSA算法的求解效果最佳。

4.1 改進算子有效性驗證

相較原始多目標模擬退火算法，所提算法主要改進包括基于啟發式規則的解碼流程、與問題規模相關聯的重啟機制。為驗證改進算子的有效性，將原始多目標模擬退火算法、僅加入解碼設計策略、僅加入重啟機制、同時加入所有改進的4 種算法分別命名為MOSA，MOSA_Re，MOSA_De，EMOSA，采用逆世代距離和超體積比率作為評價指標進行性能比較。

其中， 逆世代距離(Inverted Generational Distance，IGD)通過計算目標算法獲得的解與最優非支配解集之間的距離，以判斷算法的收斂性和多樣性。如公式⒄所示，最優非支配解包含所有測試算法結果中的非支配解。IGD值越接近于0，則表示解的收斂性和多樣性越好。

式中：dtj表示最優非支配解集中的解j到目標算法獲得的解中距離最近解的歐式距離；|TP|表示最優非支配解集中解的數量。

超體積比率(Hyper volume Ratio，HVR)表示所求目標算法Pareto 解集與參考點w的超體積占最優非支配解集邊界與參考點w的超體積的比值，如公式⒅所示。獲得的HVR值越接近1，表示解越接近真正的邊界，算法綜合性能越好。

式中：n為目標算法獲得的解的個數；m為算法獲得最優非支配解集的個數；vi為第i個超立方體。

為保證案例多樣性及滿足不同規模動車組對于最小股道資源的需求，通過改變動車組數目及股道資源狀態，來獲取不同規模案例，將表3 中前8，前9直至前11列動車組分別作為獨立運用計劃案例與表4股道類型Ⅰ-Ⅴ、Ⅱ-Ⅵ、Ⅲ-Ⅷ、Ⅵ-Ⅸ進行逐一組合，總計生成20 個不同規模的實驗案例。對每個案例獨立運行10 次的指標均值進行統計，改進算子有效性實驗中IGD，HVR值的95%置信區間如圖4所示。

表4 動車組在各線區作業起止時間Tab.4 Starting and ending time of EMU operation in each line area

圖4 改進算子有效性實驗中IGD、HVR值的95%置信區間Fig.4 95% confidence intervals of IGD, HVR values from validity tests for the improvement strategies

實驗結果顯示，融合2 種改進算子的EMOSA算法在兩項評價指標中表現均為最優，即意味著該算法改進點能夠有效針對動車所調車作業計劃問題的特性，所得非支配解集收斂性強，擁有更好的魯棒性及多樣性，可以更快速獲得優質計劃方案；兩種具有單一改進算子的算法相較于原始MOSA算法也均獲得了性能提升。重啟機制以動車組數目作為閾值，保證其運用頻率適當，有效避免算法陷入局部最優解?；趩l式規則的解碼設計提升算法性能的原因為：①沖突消解規則可以消解股道沖突，提升解的多樣性，剔除不可行解；②股道分配規則可以引導股道分配方案向積極方向進行優化，減少隨機性，提升尋優效率。

4.2 實際案例分析

某動車運用所某日實際運用計劃如表2 中D1—D10 所示，其中D8 列動車組僅需進行檢修作業，該動車所的檢修設備數量如表3 中類型Ⅲ所示，采用近似對稱布局，因此以存車線4—咽喉區1—清洗線1—咽喉區2—檢修線3 作為動車所中軸線，用以統計調車作業中轉線所跨越股道數量。采用所提EMOSA 算法對該日調車作業進行計劃編制。動車組在各線區作業起止時間如表4 所示，對應的股道占用甘特圖如圖5所示。

圖5 股道占用甘特圖Fig.5 Gantt chart of track occupancy

由結果可知，本算例調車作業計劃的總作業時長為2 751 min，總轉線跨越股道數僅為93 條。動車所各作業區設備資源得到均衡合理利用。各列動車組均在運用計劃規定發車時間前完成各項檢修任務，且預留充足時間在存車區待命，以提高應對各類臨時突發狀況的能力。通過所提算法獲得該作業計劃，求解時間僅為3.5 s，相較于目前動車所采用的人工編制調車作業計劃方式，可大幅縮減計劃編制時間，同時提升計劃方案的可靠性和實用性。由此，證明所提模型及算法能夠有效針對動車運用所調車作業計劃編制的特性與難點，合理避免股道占用沖突，快速穩定地編制出可行調車作業計劃方案，同時有效降低調車作業轉線復雜度，縮短總作業時間，從而提高動車運用所的資源使用效率，降低調度人員的工作量，提升動車運用所的經濟效益。

5 結束語

針對帶有咽喉區股道約束的盡頭式布局動車所調車作業計劃編制問題，將僅檢修作業模式考慮在內，以最小作業時間和最小轉線復雜度為目標，提出了一種增強多目標模擬退火算法，其中包含2 種改進措施：基于啟發式規則的解碼設計，幫助算法獲得性能較優的解；與問題規模相關的帕累托前沿解集重啟機制，幫助算法跳出局部最優解。采用不同規模的多個案例，驗證了改進算子的有效性，并以某動車運用所為例，驗證了模型和算法的可行性和合理性。未來研究可考慮多列位情況下動車所調車作業計劃編制問題。