范賢，徐小明，錢程

(合肥工業(yè)大學 汽車與交通工程學院，安徽 合肥 230009)

為保證動車組列車的安全穩(wěn)定運行，動車組列車采用預防修的方式進行檢修。為了安全高效地完成動車組的檢修任務，動車運用所需要根據(jù)動車組的運用計劃，提前制定調車作業(yè)計劃。隨著高速鐵路的快速發(fā)展，動車組的檢修任務快速增加，動車運用所的檢修能力成為制約高鐵運營的重要因素，提高運用所的檢修能力對于高鐵運營具有重要意義。動車組檢修工作是保障動車組列車安全運行的關鍵，當前動車所面臨的檢修壓力不斷增大，以全路規(guī)模最大的動車所——上海虹橋動車所為例，日均檢修量達到64～75組[1]。除了擴建動車運用所，制定高效合理的調車作業(yè)計劃成為提高運用所檢修能力最直接、快速和廉價的方案。此外，目前很多動車運用所還是采用手工的方式編制調車計劃，不但效率低、質量難以保證，而且隨著檢修任務的增加，手工編制調車計劃將變得越來越困難。

動車運用所調車作業(yè)計劃問題是隨著高速鐵路發(fā)展而出現(xiàn)的鐵路優(yōu)化方面的新問題。Caprara等[2]對客運鐵路的相關問題進行了總結和回顧，其中列車單元調車問題(train unit shunting problem, TUSP)與動車運用所調車作業(yè)計劃問題有很多關聯(lián)性。

列車單元調車問題是在給定列車時刻表的條件下，確定到發(fā)列車的解編、編組和在存車線的存放方案，使得列車單元運用無沖突，且成本最小。Freling等[3]將列車單元調車問題分解成列車單元匹配問題和列車單元停放問題兩個子問題分開求解。Kroon等[4]提出了一個新的模型，綜合考慮了列車單元的匹配和停放問題。Haahr等[5]運用三種不同的算法求解列車單元調車問題，并測試了不同算法的性能。Lentink等[6]提出了一個更加完整的列車單元調車問題，還包含列車單元的路由和路由成本計算這兩個子問題。

Jacobsen等[7]研究了檢修場內的列車調車計劃問題，該問題更多地考慮了檢修資源(如檢修設備、檢修人員等)的約束。Tomii等[8]研究了站臺的列車調車問題，一種簡化的列車單元調車問題。因為列車不需要解編，且存車線上只能同時停放一組列車。之后，Tomii等[9]在此基礎上進行了擴展，考慮了列車的檢修、清洗等任務的調度和場站工作人員的排班。

由于鐵路系統(tǒng)的差異，當前對運用所調車作業(yè)計劃問題的研究主要集中在國內，大多采用啟發(fā)式方法求解。王忠凱等[10]較早地對該問題進行了研究，以檢修流程要求和股道布局等為約束條件，以減少對洗車線等稀缺資源的占用和調車費用最低為目標建立模型。郭小樂等[11]以動車組在動車運用所內的總延誤時間最小為目標。童佳楠等[12]考慮了檢修線為雙列位的情況。王家喜等[13]以最小化調車總鉤數(shù)為目標，重點考慮了進路沖突約束。殷迪等[14]將調車作業(yè)計劃編制問題轉化為帶有不定加工時長的車間調度問題。韓寶明等[15]研究了加入人工洗車的調車作業(yè)計劃問題，使更加接近動車運用所的實際。

綜上所述，動車運用所調車作業(yè)計劃問題相比于列車單元調車問題更加關注列車在各個線區(qū)的作業(yè)和流轉，需要對場站設施進行更加微觀地建模。一些既有文獻對動車運用所的進路沖突考慮不足，導致編制的調車計劃無法應用于實踐。另外，隨著檢修規(guī)模擴大，許多方法由于計算時間過長等原因，不適用于實踐應用，因此開發(fā)一種快速的求解算法顯得格外重要。

本文針對動車運用所一級檢修的調車作業(yè)計劃編制問題，考慮檢修流程、股道占用、進路沖突等約束，以所有動車組完成檢修任務的時刻之和最小為目標，建立優(yōu)化模型，設計基于貪婪和鄰域搜索的啟發(fā)式算法進行求解，并開展算例分析，驗證算法的有效性。

1 問題描述

圖1所示是一種典型的盡端式動車運用所的布局，包括檢修線區(qū)、洗車線區(qū)、存車線區(qū)和咽喉區(qū)的運用所出入線。每個線區(qū)有若干條作業(yè)股道，不同作業(yè)線區(qū)通過調車股道連接，動車組通過調車股道在不同的線區(qū)流轉。

圖1 典型的動車運用所布局

一級檢修主要包含檢修作業(yè)和洗車作業(yè)兩項作業(yè)工序，完成這兩項作業(yè)后，動車組的檢修任務結束。動車組檢修作業(yè)工序一般不固定，但因為未洗車而直接進行檢修作業(yè)對檢修車間的環(huán)境有較大影響，所以動車運用所一般傾向于采用先洗車后檢修的作業(yè)順序。同時，存車作業(yè)并不是必須的，是否需要存車作業(yè)取決于洗車線和檢修線的占用情況，以及動車組完成所有的檢修作業(yè)時距離出所的時間之差。例如，當檢修線區(qū)和洗車線區(qū)的作業(yè)軌道都被占用時，新到運用所的動車組只能進行存車，等待檢修；當動車組完成所有檢修任務后，如果距離運用計劃中的下一個營運任務的時間較早，也需要進行存車，等待出所執(zhí)行營運任務。在極端情況下，動車組可以在無存車作業(yè)的情況下完成所有檢修任務后離開動車運用所。調車作業(yè)計劃問題是在已知待檢修動車組的入所和出所的時間的條件下，根據(jù)運用所檢修設施的具體布局，結合檢修流程等檢修規(guī)范，進路沖突、股道占用等實際約束，確定需要檢修的動車組在存車線、檢修線、洗車線等功能線區(qū)上的路由和停留方案，即確定檢修動車組各項檢修作業(yè)的順序、檢修作業(yè)的起始和終止時刻以及占用的作業(yè)線，使得動車組能夠在規(guī)定時間內完成檢修計劃中規(guī)定的檢修內容。

在動車運用所調車作業(yè)計劃問題中，對檢修和洗車線區(qū)的利用率能夠反映出調車作業(yè)計劃的質量，對作業(yè)線區(qū)的無效占用越少，調車作業(yè)計劃的質量越高。王家喜等[14]以最小化調車鉤數(shù)為目標進行求解，但是調車鉤數(shù)只能從側面反映出檢修流程的優(yōu)劣，不能直接反映調車計劃對檢修線和洗車線等關鍵線區(qū)的占用情況。本文中，我們以所有動車組完成最后的檢修任務，開始調車離開作業(yè)線的時刻之和最小化為目標進行求解。

2 優(yōu)化模型

本節(jié)中，我們將對動車運用所調車作業(yè)計劃問題構建模型。為了簡化問題和求解方便，我們做出如下假設：

(1)已知每一列動車組的入所和出所的時間；

(2)入所的動車組都需要進行一級檢修，包括洗車作業(yè)和檢修作業(yè)，兩項作業(yè)的執(zhí)行順序不固定；

(3)動車組洗車作業(yè)需要的最小作業(yè)時間相同且固定，與動車組無關；

(4)動車組檢修作業(yè)需要的最小作業(yè)時間相同且固定，與動車組無關；

(5)動車組調車作業(yè)需要的作業(yè)時間都是相同且固定的，與調車作業(yè)涉及的作業(yè)軌道無關。

2.1 模型參數(shù)

表1列出了本文模型中所用的參數(shù)符號。

表1 參數(shù)符號及其定義

2.2 模型表達

上文提到，對檢修和洗車線區(qū)的利用率反映出調車作業(yè)計劃的質量，減少對洗車線和檢修線的無效占用能提高檢修效率，因此，提高調車作業(yè)計劃的質量需要最小化動車組對作業(yè)線的占用時長，如式(1)所示：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

模型中，式(3)表示動車組在作業(yè)線f上的檢修順序約束；式(4)表示動車組k執(zhí)行各項檢修作業(yè)的順序約束；式(5)為作業(yè)r在作業(yè)線上的最小停留時長約束；式(6)為動車組k完成所有檢修作業(yè)時刻的約束；式(7)為作業(yè)線f占用的時空相容性約束，即當作業(yè)線f上的作業(yè)j緊接著作業(yè)i執(zhí)行，那么作業(yè)j的開始時間大于作業(yè)i的結束時間；式(8)為動車組k檢修作業(yè)順序的時間約束，即當動車組k的作業(yè)j緊接著作業(yè)i執(zhí)行，那么作業(yè)j的開始時間大于作業(yè)i的結束時間；式(9)為作業(yè)線數(shù)量約束，作業(yè)線上第一個作業(yè)(或最后一個作業(yè))之和等于作業(yè)線的數(shù)量；式(10)為檢修動車組數(shù)量約束，動車組執(zhí)行的第一個作業(yè)(或最后一個作業(yè))之和等于動車組的數(shù)量；式(11)為動車組開始檢修的時間晚于動車組入所時間的約束；式(12)為動車組檢修結束的時間早于動車組出所的時間的約束；式(13)為決策變量的取值范圍約束。

由于存車作業(yè)在數(shù)量上和時間上具有的靈活性，考慮存車作業(yè)將使得模型構建變得困難，同時存車線區(qū)并不是動車運用所的瓶頸資源，因此在該模型中不考慮存車作業(yè)，對問題進行了簡化處理。本文需要解決的是完整的調車作業(yè)計劃，即包含所有檢修、洗車、存車和調車作業(yè)占用的作業(yè)軌道和時間。該模型只考慮了檢修作業(yè)和洗車作業(yè)對作業(yè)線的占用，因此模型的解不是完整的可行解，僅包含檢修、存車和相關的調車作業(yè)。具體來說，對于每一組動車組，在該動車組的檢修流程中，在檢修作業(yè)之間和在所有的檢修作業(yè)完成之后插入存車作業(yè)，并安排具體的存車作業(yè)線，保證存車作業(yè)線的時空占用相容，以此得出一個完整可行的調車作業(yè)計劃。

3 求解算法

動車運用所調車作業(yè)計劃問題是確定動車組的檢修作業(yè)順序和檢修作業(yè)的開始結束時間，同時將檢修作業(yè)分配到相應的作業(yè)線上，滿足作業(yè)線的時空占用相容性等約束。由于本文提出的模型為簡化問題后的模型，得出的解并不是完整的調車作業(yè)計劃，因此我們提出了一種兩階段的啟發(fā)式算法對該問題進行求解。第一階段通過貪婪啟發(fā)式算法求出初始解，第二階段通過對初始解進行鄰域搜索來優(yōu)化初始解。

3.1 貪婪算法

采用貪婪算法，通過模擬動車組在動車運用所的檢修流程來獲得初始解。考慮到實際調車計劃的編制一般以分鐘為單位，同時為了減小求解的復雜度，本文以分鐘為單位，將檢修規(guī)劃周期離散化。例如，規(guī)劃周期為16 h，則可以劃分為960 min。任意一條作業(yè)線在任意一個時刻都對應一個狀態(tài)，表示該作業(yè)線處于空閑狀態(tài)或者被動車組占用。

存車作業(yè)并不是動車組檢修的必要作業(yè)，只有當檢修線和洗車線都被占用，或者動車組完成所有檢修作業(yè)的時刻早于離開動車運用所的時刻時才需要進行存車。所以為了減少檢修流程的時間，應盡量減少不必要的存車操作，同時考慮到未洗車動車組對檢修作業(yè)和檢修車間環(huán)境的影響，動車運用所一般傾向于先洗車后檢修的作業(yè)順序，但為了加快檢修的速度，此順序并不是固定的。在求解開始時，首先按照入所時間的先后順序對動車組進行排序。動車組的檢修流程如圖2所示。

圖2 動車組檢修流程圖

(1)當動車組到達運用所時，依次檢查洗車線是否空閑，如果有洗車線空閑，將動車組調至該洗車線進行洗車；

(2)如果沒有洗車線空閑，依次檢查檢修線是否空閑，如果有檢修線空閑，將動車組調至該檢修線進行檢修；

(3)如果洗車線和檢修線都被占用，那么調至存車線進行存車，同時時刻監(jiān)視洗車線的占用情況，一旦有洗車線空閑，立即調車至洗車線進行洗車；

(4)洗車作業(yè)結束后檢查是否有檢修線空閑，如果有，調車至檢修線進行檢修，檢修完畢后調車至存車線等待發(fā)車出所；

(5)如果沒有檢修線空閑，那么進行存車作業(yè)，同時時刻監(jiān)視檢修線的占用情況，一旦有檢修線空閑，立即調車至檢修線進行檢修。檢修完畢后調車至存車線等待發(fā)車出所。

需要注意的是調車作業(yè)對作業(yè)線的占用。調車過程中需要占用咽喉區(qū)的進出作業(yè)線，所以同一時刻只能有一項調車作業(yè)進行，同時，調車的過程中也會同時占用當前作業(yè)線和調車的目標作業(yè)線。另外，本文不考慮動車組出入所的調車作業(yè)。

3.2 鄰域搜索

鄰域搜索是一種求解最優(yōu)化問題的啟發(fā)式算法，從初始解開始，通過在當前解的鄰域中尋找更優(yōu)解并更新當前解，不斷迭代地尋找更優(yōu)解，直到滿足算法終止準則。本文采用的鄰域搜索算法如下：

Step 1 通過貪婪算法得到初始解s,并令sbest=s;

Step 2 對s進行鄰域操作，即從s的鄰域N(s)內取解s′，使得目標函數(shù)值f(s′)

Step 3 如果存在這樣的解s′，那么令s=s′,sbest=s′,轉到Step 2；

Step 4 否則，算法結束。

本文定義以下兩種鄰域操作：

(1)插入作業(yè)操作。給定兩條相同類型的作業(yè)線，將其中一條作業(yè)線上的一個作業(yè)插入到另一條作業(yè)線上的任意位置。

(2)交換作業(yè)順序。給定一條作業(yè)線，選擇作業(yè)線上的兩個作業(yè)，交換這兩個作業(yè)的執(zhí)行順序。

在進行鄰域操作后，我們得到了一個新的解，新解對應的檢修方案和目標函數(shù)值參考求初始解的貪婪算法求得，具體如下：首先，根據(jù)動車組的入所時間和動車組在洗車線上的作業(yè)執(zhí)行順序確定動車組在洗車線上的作業(yè)的開始和結束時間。隨后，同時考慮入所時間，洗車作業(yè)的開始、結束時間和動車組在檢修線上的作業(yè)執(zhí)行順序確定檢修作業(yè)的開始結束時間，即當動車組的入所時間和洗車開始時間之間的時間滿足檢修用時，且不與其他動車組的檢修時間沖突時，先安排動車組進行檢修；否則，在洗車后進行檢修，并根據(jù)洗車結束時間和檢修線上一個作業(yè)的結束時間確定該動車組檢修的開始和結束時間。注意，如果鄰域操作得到的解是不可行解，則放棄該解。

4 算例分析

4.1 算例設計

本節(jié)以圖1 中的橫向盡頭式的動車運用所為基礎開展算例研究。該動車運用所有檢修線4條，洗車線2條和存車線9條。調車計劃規(guī)劃周期從下午4時開始，到第二天上午8時結束，共計16 h，將時間離散為以分鐘為單位，共960 min。表 2 為動車組運用計劃，其中，出入所的時間以分鐘為單位，并以下午4時為0時刻計算。

表2 動車組運用計劃

4.2 算例結果及分析

4.2.1 普通算例的結果及分析

本文假設同一種類型的作業(yè)的最小用時都是相同的，與作業(yè)的股道和執(zhí)行作業(yè)的人員無關。假設檢修作業(yè)最小用時90 min，洗車作業(yè)最小用時30 min，調車作業(yè)用時5 min。本文算法通過C#編程實現(xiàn)，在內存為16 GB，CPU為i7-4710HQ的計算機上運行，運行時間小于1 s。表 2 中的普通算例的結果如表 3所示。表中W1(0～30)中，W1表示對應的作業(yè)線，括號內數(shù)字為動車組在作業(yè)線上的開始和結束時刻，作業(yè)之間的時間間隔表示調車作業(yè)用時，其他符號含義類似。

表3 動車組在運用所的檢修方案

求解過程中發(fā)現(xiàn)，對于上述算例，鄰域搜索并不能改進初始解。分析動車組在運用所的檢修流程后發(fā)現(xiàn)，動車組入所后即開始檢修任務，且檢修過程中沒有額外的存車作業(yè)。

對算例進行進一步分析，最優(yōu)的檢修流程為：洗車—調車—檢修—調車—存車，目標函數(shù)不包含最后的調車和存車用時，那么一組動車組最小占用作業(yè)線的時長為洗車、調車和檢修的最小用時之和，因此，解的下界可以通過動車組的入所時刻加檢修流程最小用時求得。對于上述算例，所有動車組的入所時刻之和為3 610，一組動車組檢修流程最小用時為一次調車作業(yè)、一次洗車作業(yè)和一次檢修作業(yè)的最小所需用時之和，即125，那么目標函數(shù)解的下限為3 610+125×15=5 485。因此，初始解即為最優(yōu)解。

4.2.2 動車組集中入所算例的結果及分析

如果出現(xiàn)動車組集中入所的情況時，動車組在入所時和檢修過程中由于檢修作業(yè)線都被占用，將不可避免地出現(xiàn)存車作業(yè)。因此我們在表2算例的基礎上設計一個特殊的算例，如表4所示。該算例中，動車組將會在300～500之間(即當日21:00到次日0:20)集中入所，此時會出現(xiàn)作業(yè)線被全部占用的情況。

表4 特殊設計的動車組運用計劃

在該算例下，最優(yōu)解的下界為6 850，貪婪算法得到的初始解為6 985，對初始解進行鄰域搜索后的解為6 975，鄰域搜索后的解相比初始解可以減少總計10 min的檢修用時，詳細的調車計劃如表5所示。

表5 初始解和鄰域搜索優(yōu)化后的動車組檢修方案

詳細分析兩個解的調車計劃可以發(fā)現(xiàn)，鄰域搜索后的解相比初始解減少了兩次存車作業(yè)，即動車組EMU14和動車組EMU15各減少了一次存車作業(yè)。但是由于檢修過程中的存車作業(yè)具有靈活性，因此減少存車作業(yè)次數(shù)并不一定減少對作業(yè)線的占用時長。例如，EMU15雖然減少了一次存車作業(yè)，但是總的存車時長沒有減少，因此完成所有檢修任務的時間并沒有減少。鄰域搜索算法雖然對解的優(yōu)化有限，甚至沒有優(yōu)化，但在求解過程中可以得到多組不同的解，在實際應用中，可用于改善動車組檢修作業(yè)的流程，或為調車作業(yè)計劃編制人員提供決策支持。

4.3 算法可靠性測試

表6 不同規(guī)模算例的測試結果

對于15組動車組的算例，隨機生成的5個算例中，有3個算例直接通過貪婪算法就能求出最優(yōu)解，另兩個算例的解的Gap值也較小。鄰域搜索對該規(guī)模下的算例作用有限，只有一個算例有0.82%的改進，表明了本文提出的貪婪算法求得的初始解即為較好的解。對于20組動車組規(guī)模的算例，動車運用所的檢修資源變得更加緊張，檢修流程中存在多余的存車作業(yè)，Gap值明顯增大。在該規(guī)模下的算例，鄰域搜索取得了較好的效果，5個算例中，有4個算例對初始解有不同程度的優(yōu)化，平均優(yōu)化1.35%。算例測試表明所提出的算法能有效求解本文問題。

5 結論

本文以動車運用所的股道布局、股道時空占用相容性和檢修作業(yè)要求等為約束，以最小化完成動車組所有檢修任務的時刻之和為目標，將動車運用所調車作業(yè)計劃問題構建為0-1整數(shù)規(guī)劃模型。由于模型的解并不是問題的完整可行解，因此設計了結合貪婪策略和鄰域搜索的啟發(fā)式算法。算例分析表明，基于貪婪策略的初始解算法能快速地得出較好的初始解，甚至能直接求出最優(yōu)解。

本文研究的動車運用所同一時刻只允許一組動車組調車，所以調車作業(yè)進路沖突問題容易解決，但當動車運用所規(guī)模較大，進路復雜時，調車進路沖突問題將是一個值得研究的問題。同時，如果檢修動車組數(shù)量繼續(xù)增加，當前的算法可能不能保證得出可行解，對于大規(guī)模算例的算法改進也是值得研究的一個方向。