范賢，徐小明，錢(qián)程

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

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

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

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

Jacobsen等[7]研究了檢修場(chǎng)內(nèi)的列車(chē)調(diào)車(chē)計(jì)劃問(wèn)題，該問(wèn)題更多地考慮了檢修資源(如檢修設(shè)備、檢修人員等)的約束。Tomii等[8]研究了站臺(tái)的列車(chē)調(diào)車(chē)問(wèn)題，一種簡(jiǎn)化的列車(chē)單元調(diào)車(chē)問(wèn)題。因?yàn)榱熊?chē)不需要解編，且存車(chē)線上只能同時(shí)停放一組列車(chē)。之后，Tomii等[9]在此基礎(chǔ)上進(jìn)行了擴(kuò)展，考慮了列車(chē)的檢修、清洗等任務(wù)的調(diào)度和場(chǎng)站工作人員的排班。

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

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

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

1 問(wèn)題描述

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

圖1 典型的動(dòng)車(chē)運(yùn)用所布局

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

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

2 優(yōu)化模型

本節(jié)中，我們將對(duì)動(dòng)車(chē)運(yùn)用所調(diào)車(chē)作業(yè)計(jì)劃問(wèn)題構(gòu)建模型。為了簡(jiǎn)化問(wèn)題和求解方便，我們做出如下假設(shè)：

(1)已知每一列動(dòng)車(chē)組的入所和出所的時(shí)間；

(2)入所的動(dòng)車(chē)組都需要進(jìn)行一級(jí)檢修，包括洗車(chē)作業(yè)和檢修作業(yè)，兩項(xiàng)作業(yè)的執(zhí)行順序不固定；

(3)動(dòng)車(chē)組洗車(chē)作業(yè)需要的最小作業(yè)時(shí)間相同且固定，與動(dòng)車(chē)組無(wú)關(guān)；

(4)動(dòng)車(chē)組檢修作業(yè)需要的最小作業(yè)時(shí)間相同且固定，與動(dòng)車(chē)組無(wú)關(guān)；

(5)動(dòng)車(chē)組調(diào)車(chē)作業(yè)需要的作業(yè)時(shí)間都是相同且固定的，與調(diào)車(chē)作業(yè)涉及的作業(yè)軌道無(wú)關(guān)。

2.1 模型參數(shù)

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

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

2.2 模型表達(dá)

上文提到，對(duì)檢修和洗車(chē)線區(qū)的利用率反映出調(diào)車(chē)作業(yè)計(jì)劃的質(zhì)量，減少對(duì)洗車(chē)線和檢修線的無(wú)效占用能提高檢修效率，因此，提高調(diào)車(chē)作業(yè)計(jì)劃的質(zhì)量需要最小化動(dòng)車(chē)組對(duì)作業(yè)線的占用時(shí)長(zhǎng)，如式(1)所示：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

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

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

3 求解算法

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

3.1 貪婪算法

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

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

圖2 動(dòng)車(chē)組檢修流程圖

(1)當(dāng)動(dòng)車(chē)組到達(dá)運(yùn)用所時(shí)，依次檢查洗車(chē)線是否空閑，如果有洗車(chē)線空閑，將動(dòng)車(chē)組調(diào)至該洗車(chē)線進(jìn)行洗車(chē)；

(2)如果沒(méi)有洗車(chē)線空閑，依次檢查檢修線是否空閑，如果有檢修線空閑，將動(dòng)車(chē)組調(diào)至該檢修線進(jìn)行檢修；

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

(4)洗車(chē)作業(yè)結(jié)束后檢查是否有檢修線空閑，如果有，調(diào)車(chē)至檢修線進(jìn)行檢修，檢修完畢后調(diào)車(chē)至存車(chē)線等待發(fā)車(chē)出所；

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

需要注意的是調(diào)車(chē)作業(yè)對(duì)作業(yè)線的占用。調(diào)車(chē)過(guò)程中需要占用咽喉區(qū)的進(jìn)出作業(yè)線，所以同一時(shí)刻只能有一項(xiàng)調(diào)車(chē)作業(yè)進(jìn)行，同時(shí)，調(diào)車(chē)的過(guò)程中也會(huì)同時(shí)占用當(dāng)前作業(yè)線和調(diào)車(chē)的目標(biāo)作業(yè)線。另外，本文不考慮動(dòng)車(chē)組出入所的調(diào)車(chē)作業(yè)。

3.2 鄰域搜索

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

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

Step 2 對(duì)s進(jìn)行鄰域操作，即從s的鄰域N(s)內(nèi)取解s′，使得目標(biāo)函數(shù)值f(s′)

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

Step 4 否則，算法結(jié)束。

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

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

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

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

4 算例分析

4.1 算例設(shè)計(jì)

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

表2 動(dòng)車(chē)組運(yùn)用計(jì)劃

4.2 算例結(jié)果及分析

4.2.1 普通算例的結(jié)果及分析

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

表3 動(dòng)車(chē)組在運(yùn)用所的檢修方案

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

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

4.2.2 動(dòng)車(chē)組集中入所算例的結(jié)果及分析

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

表4 特殊設(shè)計(jì)的動(dòng)車(chē)組運(yùn)用計(jì)劃

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

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

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

4.3 算法可靠性測(cè)試

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

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

5 結(jié)論

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

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