基于增強(qiáng)模擬退火算法的動(dòng)車所調(diào)車作業(yè)計(jì)劃多目標(biāo)優(yōu)化方法

劉 毅，唐秋華，何 明

(1.武漢科技大學(xué) 冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430081；2.武漢科技大學(xué)機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430081)

0 引言

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

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

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

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

1 問題描述

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

圖1 盡頭式動(dòng)車所Fig.1 Stub-end EMU depot

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

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

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

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

表1 符號說明Tab.1 Symbol description

2.1 目標(biāo)函數(shù)

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

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

2.2 優(yōu)化模型

對股道分配進(jìn)行約束。

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

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

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

對時(shí)序邏輯進(jìn)行約束。

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

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

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

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

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

3 增強(qiáng)模擬退火算法

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

3.1 編碼及初始化

3.1.1 問題編碼

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

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

3.1.2 基于入所時(shí)間的初始化

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

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

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

3.2.1 股道分配規(guī)則

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

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

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

3.2.2 沖突消解規(guī)則

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

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

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

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

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

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

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

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

3.3 鄰域搜索

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

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

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

3.4 基于Pareto的性能評價(jià)

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

3.5 基于歸檔集的重啟機(jī)制

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

3.6 算法求解流程

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

圖3 改進(jìn)多目標(biāo)模擬退火算法流程圖Fig.3 Procedure of multi-objective simulated annealing algorithm

4 實(shí)例分析

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

表2 動(dòng)車組運(yùn)用計(jì)劃案例Tab.2 EMU rescheduling cases

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

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

4.1 改進(jìn)算子有效性驗(yàn)證

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

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

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

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

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

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

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

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

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

4.2 實(shí)際案例分析

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

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

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

5 結(jié)束語

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