劉 毅，唐秋華，何 明

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

0 引言

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

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

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

據(jù)此，提出一種增強模擬退火算法，通過設(shè)計基于啟發(fā)式規(guī)則的解碼策略及基于歸檔集的重啟機制[8]，用以求解以動車所調(diào)車作業(yè)時間最小化、調(diào)車作業(yè)轉(zhuǎn)線復(fù)雜度最小化為目標的多目標優(yōu)化問題。

1 問題描述

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

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

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

由此，動車所調(diào)車作業(yè)計劃優(yōu)化問題可總結(jié)為：在動車所設(shè)備資源、布局等前提確定情況下，編制可行的動車所調(diào)車作業(yè)計劃，力求獲得更小的總調(diào)車作業(yè)時間及更低的轉(zhuǎn)線復(fù)雜度。

2 數(shù)學(xué)模型

該問題需同時優(yōu)化調(diào)車作業(yè)計劃總時間、轉(zhuǎn)線復(fù)雜度2 個目標，基于此構(gòu)建多目標優(yōu)化模型。符號說明如表1所示。

表1 符號說明Tab.1 Symbol description

2.1 目標函數(shù)

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

公式⑴表示最小調(diào)車作業(yè)計劃總作業(yè)時間；公式⑵表示最小調(diào)車作業(yè)計劃轉(zhuǎn)線復(fù)雜度。

2.2 優(yōu)化模型

對股道分配進行約束。

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

公式⑷表示選定作業(yè)模式后，每個階段的操作 需在指定作業(yè)區(qū)內(nèi)進行。

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

對時序邏輯進行約束。

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

公式⑻—⑼表示動車組e第s個作業(yè)的結(jié)束時刻大于其開始時刻加上該作業(yè)區(qū)的標準作業(yè)時間；完成任務(wù)后原地等待轉(zhuǎn)線。

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

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

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

3 增強模擬退火算法

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

3.1 編碼及初始化

3.1.1 問題編碼

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

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

3.1.2 基于入所時間的初始化

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

3.2 基于組合啟發(fā)式規(guī)則的解碼設(shè)計

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

3.2.1 股道分配規(guī)則

在動車組進行作業(yè)區(qū)間轉(zhuǎn)換時，為明確股道分配方式，并避免無效的股道變換，導(dǎo)致轉(zhuǎn)線復(fù)雜度上升，設(shè)計股道分配規(guī)則進行約束。

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

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

3.2.2 沖突消解規(guī)則

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

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

3.2.3 基于組合啟發(fā)式規(guī)則的解碼流程

在前述規(guī)則基礎(chǔ)上，解碼步驟如下。

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

步驟2：運用股道分配規(guī)則給動車組分配相應(yīng)股道。

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

步驟4：生成一個可行的調(diào)車作業(yè)計劃。

3.3 鄰域搜索

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

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

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

3.4 基于Pareto的性能評價

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

3.5 基于歸檔集的重啟機制

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

3.6 算法求解流程

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

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

4 實例分析

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

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

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

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

4.1 改進算子有效性驗證

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

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

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

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

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

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

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

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

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

4.2 實際案例分析

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

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

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

5 結(jié)束語

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