陳 韜， 呂紅霞， 潘金山， 趙敬勇

(1. 西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院， 四川 成都 610031；2. 西南交通大學(xué) 全國(guó)鐵路列車(chē)運(yùn)行圖編制研發(fā)培訓(xùn)中心， 四川 成都 610031；3. 西南交通大學(xué) 綜合交通運(yùn)輸智能化國(guó)家地方工程聯(lián)合實(shí)驗(yàn)室， 四川 成都 610031；4. 濟(jì)南鐵路局 濟(jì)西站，山東 濟(jì)南 250117)

動(dòng)車(chē)所承擔(dān)動(dòng)車(chē)組除高級(jí)檢修以外的全部維修工作以及動(dòng)車(chē)組存車(chē)作業(yè)，一般設(shè)置在高鐵線路始發(fā)站、終到站、樞紐站附近，是保證動(dòng)車(chē)組具有安全正常運(yùn)用狀態(tài)的維修整備場(chǎng)所。相對(duì)于不斷出入的動(dòng)車(chē)組，動(dòng)車(chē)運(yùn)用所的檢修設(shè)備能力相對(duì)稀缺。因此，限制了給定時(shí)段內(nèi)動(dòng)車(chē)所通過(guò)或接發(fā)的動(dòng)車(chē)組數(shù)量。動(dòng)車(chē)所在給定時(shí)段內(nèi)，一定設(shè)備條件和作業(yè)方式下，能整備的最大動(dòng)車(chē)數(shù)量即為動(dòng)車(chē)所通過(guò)能力。正確計(jì)算動(dòng)車(chē)所通過(guò)能力對(duì)挖掘動(dòng)車(chē)所作業(yè)能力、協(xié)調(diào)高鐵路網(wǎng)點(diǎn)線能力有重要意義。

目前，動(dòng)車(chē)所通過(guò)能力計(jì)算的相關(guān)研究較少，大部分研究主要集中在普速車(chē)站客車(chē)整備所通過(guò)能力計(jì)算、高鐵客運(yùn)站通過(guò)能力計(jì)算、動(dòng)車(chē)所調(diào)車(chē)作業(yè)計(jì)劃編制問(wèn)題上。普速車(chē)站客車(chē)整備所通過(guò)能力目前仍然采用傳統(tǒng)的利用率法進(jìn)行計(jì)算，限于各種參數(shù)取值的影響，計(jì)算結(jié)果準(zhǔn)確度不高[1]；高鐵客運(yùn)站需要準(zhǔn)確計(jì)算不同時(shí)段的通過(guò)能力，國(guó)內(nèi)外學(xué)者都致力于運(yùn)用基于各種智能算法的模擬仿真法進(jìn)行計(jì)算，得到較好的效果，但動(dòng)車(chē)所作業(yè)組織復(fù)雜性、靈活性比高鐵客運(yùn)站高，這些理論方法可以借鑒但還不能直接運(yùn)用[2-3]；李波[4]給出單個(gè)環(huán)節(jié)的動(dòng)車(chē)所檢修設(shè)備能力測(cè)試公式，并給定反應(yīng)檢修效果的系數(shù)范圍，但是沒(méi)有考慮檢修作業(yè)間相互影響下的檢修能力；耿敬春等[5]以北京動(dòng)車(chē)段為例，通過(guò)比較分析列車(chē)運(yùn)行圖不同時(shí)段下出入段動(dòng)車(chē)組數(shù)與最小追蹤間隔下出入段動(dòng)車(chē)組數(shù)的關(guān)系，提出出入段能力的適應(yīng)性和加強(qiáng)措施，但沒(méi)有探討動(dòng)車(chē)所能力的計(jì)算方法；林伯梁[6]、李建等[7]研究動(dòng)車(chē)組一級(jí)檢修調(diào)車(chē)作業(yè)計(jì)劃自動(dòng)編制問(wèn)題，根據(jù)人工編圖經(jīng)驗(yàn)設(shè)計(jì)啟發(fā)式規(guī)則，開(kāi)發(fā)相關(guān)信息系統(tǒng)；王忠凱等[8]對(duì)動(dòng)車(chē)組調(diào)車(chē)作業(yè)計(jì)劃編制問(wèn)題建立以核心作業(yè)時(shí)間延誤最小為目標(biāo)的數(shù)學(xué)模型，并運(yùn)用最大最小蟻群算法進(jìn)行模型求解，沒(méi)有涉及動(dòng)車(chē)所通過(guò)能力計(jì)算。

模擬仿真法已被證明是計(jì)算通過(guò)能力的有效方法，通過(guò)多次模擬動(dòng)車(chē)所作業(yè)過(guò)程可以較為精確的確定動(dòng)車(chē)組整備的最大數(shù)量[2-3]。而模擬仿真的關(guān)鍵是要確定有效的智能搜索算法，確保在可接受資源消耗內(nèi)找到理想解。本文在前人研究基礎(chǔ)上，分析動(dòng)車(chē)所通過(guò)能力的影響因素，建立動(dòng)車(chē)所通過(guò)能力計(jì)算的0-1規(guī)劃模型，并運(yùn)用啟發(fā)式排序規(guī)則與基于最長(zhǎng)活動(dòng)鏈的混合鄰域禁忌搜索算法進(jìn)行求解，為模擬仿真計(jì)算動(dòng)車(chē)所通過(guò)能力提供可行的思路。

1 問(wèn)題分析

動(dòng)車(chē)所通過(guò)能力影響因素主要可分為3類(lèi):

(1) 動(dòng)車(chē)所各類(lèi)檢修設(shè)備、各場(chǎng)庫(kù)股道設(shè)備以及連接各場(chǎng)庫(kù)的咽喉道岔設(shè)備，包括站型、股道、咽喉、信號(hào)、檢修庫(kù)、洗車(chē)庫(kù)、吸污設(shè)備等。因此，動(dòng)車(chē)所通過(guò)能力從設(shè)備上又可分為檢修設(shè)備能力、場(chǎng)庫(kù)股道通過(guò)能力及咽喉道岔通過(guò)能力3種，動(dòng)車(chē)所通過(guò)能力不能簡(jiǎn)單的等同于某一類(lèi)設(shè)備的通過(guò)能力，而應(yīng)該是這幾類(lèi)設(shè)備協(xié)調(diào)配合所體現(xiàn)出的整體通過(guò)能力。

(2) 保證行車(chē)安全和作業(yè)質(zhì)量的各種作業(yè)規(guī)則和標(biāo)準(zhǔn)，包括行車(chē)間隔標(biāo)準(zhǔn)(列車(chē)到達(dá)追蹤間隔、出發(fā)追蹤間隔、不同時(shí)到發(fā)間隔等)、動(dòng)車(chē)組檢修作業(yè)時(shí)間標(biāo)準(zhǔn)(洗車(chē)作業(yè)時(shí)間、卸污作業(yè)時(shí)間、檢修庫(kù)檢修作業(yè)時(shí)間等)、動(dòng)車(chē)組走行作業(yè)時(shí)間標(biāo)準(zhǔn)(動(dòng)車(chē)組在各場(chǎng)庫(kù)間的轉(zhuǎn)線作業(yè)時(shí)間)，動(dòng)車(chē)組檢修作業(yè)流程(存車(chē)作業(yè)流程、一級(jí)檢修作業(yè)流程、二級(jí)檢修作業(yè)流程等)、動(dòng)車(chē)組調(diào)車(chē)作業(yè)流程等。這些作業(yè)規(guī)則和標(biāo)準(zhǔn)規(guī)定動(dòng)車(chē)所設(shè)備使用的時(shí)間和頻率，從效率上影響動(dòng)車(chē)所通過(guò)能力。

(3) 動(dòng)車(chē)所技術(shù)作業(yè)方案。動(dòng)車(chē)所技術(shù)作業(yè)是對(duì)動(dòng)車(chē)所能力的直接利用，包括動(dòng)車(chē)組檢修計(jì)劃、動(dòng)車(chē)組運(yùn)用計(jì)劃和動(dòng)車(chē)組調(diào)車(chē)作業(yè)計(jì)劃。其中，動(dòng)車(chē)組檢修和運(yùn)用計(jì)劃是根據(jù)動(dòng)車(chē)交路計(jì)劃及動(dòng)車(chē)組使用狀態(tài)確定的本動(dòng)車(chē)所配屬動(dòng)車(chē)組的日常檢修及分配計(jì)劃，也就是動(dòng)車(chē)所的整備作業(yè)任務(wù)，包括不同檢修動(dòng)車(chē)組的數(shù)量、比例、出入動(dòng)車(chē)所先后順序及時(shí)間等。動(dòng)車(chē)組調(diào)車(chē)作業(yè)計(jì)劃是根據(jù)動(dòng)車(chē)組檢修和運(yùn)用計(jì)劃編制的動(dòng)車(chē)組在動(dòng)車(chē)所內(nèi)各場(chǎng)庫(kù)的股道停留和轉(zhuǎn)線計(jì)劃，涵蓋動(dòng)車(chē)組的進(jìn)所、檢修、存車(chē)和出所的全過(guò)程，是保證動(dòng)車(chē)所整備作業(yè)任務(wù)能夠完成的設(shè)備運(yùn)用計(jì)劃，包括動(dòng)車(chē)組在動(dòng)車(chē)所的出入所進(jìn)路、各場(chǎng)庫(kù)股道運(yùn)用順序、占用起止時(shí)間，轉(zhuǎn)線進(jìn)路及時(shí)間等方案[8]。

動(dòng)車(chē)組調(diào)車(chē)作業(yè)計(jì)劃是動(dòng)車(chē)組檢修作業(yè)任務(wù)與車(chē)站設(shè)備能力相適應(yīng)的關(guān)鍵環(huán)節(jié)，方案的優(yōu)劣對(duì)動(dòng)車(chē)所能力的利用程度有直接影響。相同的檢修和運(yùn)用計(jì)劃，動(dòng)車(chē)組調(diào)車(chē)作業(yè)計(jì)劃方案較優(yōu)時(shí)，給定時(shí)段內(nèi)對(duì)動(dòng)車(chē)所設(shè)備能力占用少，可安排更多的檢修任務(wù)。圖1、圖2為某動(dòng)車(chē)所8:00～13:00間的2個(gè)不同調(diào)車(chē)作業(yè)方案，圖1只能安排整備4列動(dòng)車(chē)組，圖2將圖1中U3的最后1項(xiàng)存車(chē)線上的整備作業(yè)更換1條股道(如圖2上虛橫線所示)則可以安排整備5列動(dòng)車(chē)組。由此可知，假設(shè)給定時(shí)段內(nèi)檢修和運(yùn)用計(jì)劃的動(dòng)車(chē)組數(shù)為Z，如果按最優(yōu)方案安排其調(diào)車(chē)作業(yè)后，無(wú)法再增加動(dòng)車(chē)組，則Z為該時(shí)段內(nèi)動(dòng)車(chē)組最大整備數(shù)，也就是該時(shí)段動(dòng)車(chē)所的通過(guò)能力。

因此，通過(guò)確定給定時(shí)段內(nèi)滿(mǎn)足動(dòng)車(chē)所設(shè)備、作業(yè)規(guī)則和標(biāo)準(zhǔn)等時(shí)空資源的整備動(dòng)車(chē)組數(shù)最多的動(dòng)車(chē)所技術(shù)作業(yè)方案，即確定出給定時(shí)段內(nèi)動(dòng)車(chē)所時(shí)空資源利用率最大的動(dòng)車(chē)所技術(shù)作業(yè)方案，即可得到動(dòng)車(chē)所通過(guò)能力。

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

整備動(dòng)車(chē)組最多的動(dòng)車(chē)所技術(shù)作業(yè)方案的確定需對(duì)動(dòng)車(chē)組的接發(fā)順序、接發(fā)進(jìn)路、作業(yè)占用的股道、占用股道的起止時(shí)刻及作業(yè)間的轉(zhuǎn)線進(jìn)路等變量進(jìn)行決策。下面基于這些決策變量，以整備動(dòng)車(chē)組數(shù)最多為目標(biāo)，給出滿(mǎn)足各種約束的動(dòng)車(chē)所通過(guò)能力計(jì)算模型。

2.1 優(yōu)化目標(biāo)

設(shè)動(dòng)車(chē)所通過(guò)能力計(jì)算時(shí)段的開(kāi)始時(shí)刻為T(mén)Ps和結(jié)束時(shí)刻為T(mén)Pe，本文模型的優(yōu)化目標(biāo)為在計(jì)算時(shí)段[TPs,TPe]內(nèi)盡可能多的整備各種作業(yè)流程的動(dòng)車(chē)組，實(shí)現(xiàn)動(dòng)車(chē)組通過(guò)能力的最大化，即

( 1 )

式中:Z為處在各不同檢修流程的動(dòng)車(chē)組數(shù)量之和，列；ni為動(dòng)車(chē)所辦理的檢修流程i的動(dòng)車(chē)組數(shù)，列；M為動(dòng)車(chē)組檢修流程種類(lèi)數(shù)(日常存車(chē)、一級(jí)檢修、二級(jí)檢修等)。

2.2 約束條件

(1) 動(dòng)車(chē)所檢修的動(dòng)車(chē)組需要滿(mǎn)足動(dòng)車(chē)組檢修流程類(lèi)型比例約束

( 2 )

(2) 股道作業(yè)安排約束條件

每列動(dòng)車(chē)組須滿(mǎn)足場(chǎng)庫(kù)股道時(shí)空占用的唯一性約束，即任意1條股道在任意時(shí)間內(nèi)只允許1列動(dòng)車(chē)組占用，表示為

( 3 )

( 4 )

( 5 )

( 6 )

( 7 )

式( 3 )表示只能給每列動(dòng)車(chē)組的每項(xiàng)作業(yè)安排1條股道；式( 4 )表示每列動(dòng)車(chē)組被安排的股道數(shù)應(yīng)不小于其檢修流程所規(guī)定的作業(yè)數(shù)；式( 5 )表示每列動(dòng)車(chē)組的每項(xiàng)作業(yè)在動(dòng)車(chē)所股道上實(shí)際停留的時(shí)間應(yīng)能夠滿(mǎn)足規(guī)定的最小作業(yè)檢修時(shí)間；式( 6 )表示相繼在同一條股道上到發(fā)的任意兩列動(dòng)車(chē)組，占用該股道的時(shí)間不允許沖突，即當(dāng)某條股道已被某動(dòng)車(chē)組占用時(shí)，不允許該股道再到發(fā)其他動(dòng)車(chē)組；式( 7 )表示僅考慮作業(yè)時(shí)間在計(jì)算時(shí)段的動(dòng)車(chē)組。

(3) 動(dòng)車(chē)組檢修作業(yè)順序約束條件

每列動(dòng)車(chē)組每項(xiàng)檢修作業(yè)的開(kāi)始、結(jié)束時(shí)刻必須滿(mǎn)足其前項(xiàng)、后項(xiàng)作業(yè)時(shí)間的約束

( 8 )

( 9 )

式( 8 )中，當(dāng)k=1時(shí)，表示第1項(xiàng)作業(yè)的開(kāi)始時(shí)刻等于動(dòng)車(chē)組入所時(shí)刻；當(dāng)k≠1時(shí)，表示除第1項(xiàng)作業(yè)外，每項(xiàng)作業(yè)時(shí)間開(kāi)始時(shí)刻都大于前一項(xiàng)作業(yè)結(jié)束時(shí)刻；當(dāng)k=Di時(shí)，表示最后一項(xiàng)作業(yè)結(jié)束時(shí)刻必須等于動(dòng)車(chē)組出所時(shí)刻；式( 9 )僅考慮出入所時(shí)刻在計(jì)算時(shí)段的動(dòng)車(chē)組。

(4) 每列動(dòng)車(chē)組每項(xiàng)檢修作業(yè)的股道安排必須檢修作業(yè)場(chǎng)庫(kù)約束，即每項(xiàng)檢修作業(yè)必須在特定的場(chǎng)庫(kù)股道上完成，即

(10)

式中:Cijkr為檢修流程為i的第j列動(dòng)車(chē)組的第k個(gè)任務(wù)被安排在場(chǎng)庫(kù)的股道r上進(jìn)行作業(yè)的效益。當(dāng)動(dòng)車(chē)組按照動(dòng)車(chē)所工作組織規(guī)定的安排在不能或不允許使用的股道r上時(shí)，Cijkr=0，否則Cijkr=1。

(5) 動(dòng)車(chē)組進(jìn)路安排約束條件

動(dòng)車(chē)組須滿(mǎn)足進(jìn)路時(shí)空占用的唯一性約束，即任何1條進(jìn)路在任意時(shí)間內(nèi)只允許被1列動(dòng)車(chē)組占用，為

(11)

(12)

式中:Iaa為檢修流程為i的第j列動(dòng)車(chē)組與前面檢修流程為i′的第j′列動(dòng)車(chē)組之間的最小到達(dá)間隔時(shí)間；Iad為檢修流程為i的第j列動(dòng)車(chē)組與前面檢修流程為i′的第j′列動(dòng)車(chē)組之間的最小到發(fā)間隔時(shí)間；Idd為檢修流程為i的第j列動(dòng)車(chē)組與前面檢修流程為i′的第j′列動(dòng)車(chē)組之間的最小出發(fā)間隔時(shí)間；Ida為檢修流程為i的第j列動(dòng)車(chē)組與前面檢修流程為i′的第j′列動(dòng)車(chē)組之間的最小發(fā)到間隔時(shí)間；pll′為0-1變量，如果進(jìn)路l與l′存在沖突，則pll′=1，否則pll′=0。

(13)

k≠1∪Dik′≠1∪Dipll′=1

(14)

式(11)表示只允許給每一動(dòng)車(chē)組每項(xiàng)任務(wù)所在股道的轉(zhuǎn)入、轉(zhuǎn)出安排1條進(jìn)路；式(12)表示不同動(dòng)車(chē)組接發(fā)車(chē)進(jìn)路占用沖突時(shí)必須要滿(mǎn)足規(guī)定的最小間隔時(shí)間標(biāo)準(zhǔn)；式(13)表示動(dòng)車(chē)組轉(zhuǎn)線進(jìn)路占用時(shí)間等于前后任務(wù)股道占用起止時(shí)間之差；式(14)表示不同動(dòng)車(chē)組轉(zhuǎn)線進(jìn)路沖突時(shí)，要滿(mǎn)足調(diào)車(chē)最小間隔時(shí)間標(biāo)準(zhǔn)。

3 算法設(shè)計(jì)

動(dòng)車(chē)所通過(guò)能力計(jì)算中的決策變量和約束條件很多，技術(shù)作業(yè)方案數(shù)隨著動(dòng)車(chē)所設(shè)備規(guī)模、動(dòng)車(chē)組數(shù)量的增加而呈現(xiàn)爆炸性增長(zhǎng)，是NP難組合問(wèn)題。若把動(dòng)車(chē)組看作加工工件，動(dòng)車(chē)組在動(dòng)車(chē)所的每項(xiàng)檢修或轉(zhuǎn)線作業(yè)看作加工工序，每項(xiàng)檢修或轉(zhuǎn)線作業(yè)可選的股道或進(jìn)路看作每道加工工序可以選擇的多個(gè)平行機(jī)器，則動(dòng)車(chē)所技術(shù)作業(yè)安排就是1個(gè)每個(gè)工件加工路徑確定的多階段混合流水車(chē)間調(diào)度問(wèn)題[9-10]，而禁忌搜索算法是解決多階段混合流水車(chē)間調(diào)度問(wèn)題的有效算法之一。因此，針對(duì)動(dòng)車(chē)所通過(guò)能力問(wèn)題的特點(diǎn)，本文設(shè)計(jì)啟發(fā)式排序規(guī)則[9]與基于最長(zhǎng)活動(dòng)鏈的混合鄰域禁忌搜索算法[10]HNS-TS:Hybrid(Neighborhood Structure and Tabu Search)相結(jié)合的優(yōu)化算法，進(jìn)行模型的求解。由于直接求解動(dòng)車(chē)所最大整備動(dòng)車(chē)組數(shù)較為困難，算法中引入最晚動(dòng)車(chē)組出所時(shí)刻這一優(yōu)化指標(biāo)。

3.1 優(yōu)化指標(biāo)設(shè)計(jì)

最晚動(dòng)車(chē)組出所時(shí)刻是指某給定技術(shù)作業(yè)方案中最后1列出所動(dòng)車(chē)的出發(fā)時(shí)刻。運(yùn)用該指標(biāo)可以方便的比較給定時(shí)間段內(nèi)、檢修運(yùn)用任務(wù)相同的多個(gè)調(diào)車(chē)作業(yè)方案的優(yōu)劣，該指標(biāo)越小，表明對(duì)應(yīng)的調(diào)車(chē)作業(yè)方案越好。因可以節(jié)省出更多的時(shí)空資源安排動(dòng)車(chē)組作業(yè)，從而提高通過(guò)能力。

本文算法的思路為按檢修類(lèi)型比例生成1組動(dòng)車(chē)組檢修運(yùn)用計(jì)劃，然后在給定時(shí)段內(nèi)為該計(jì)劃生成最晚動(dòng)車(chē)組出所時(shí)刻最小的調(diào)車(chē)作業(yè)方案，如果動(dòng)車(chē)所通過(guò)能力有富裕，繼續(xù)增加檢修動(dòng)車(chē)組并繼續(xù)優(yōu)化調(diào)車(chē)作業(yè)方案，直到通過(guò)能力用盡為止。

3.2 設(shè)計(jì)啟發(fā)式排序規(guī)則生成初始方案

禁忌搜索算法對(duì)初始解依賴(lài)性較大，本文中通過(guò)設(shè)計(jì)啟發(fā)式排序規(guī)則生成初始方案。啟發(fā)式排序規(guī)則是根據(jù)動(dòng)車(chē)所調(diào)車(chē)作業(yè)的長(zhǎng)期實(shí)踐經(jīng)驗(yàn)、偏好性目標(biāo)構(gòu)建的一組動(dòng)車(chē)組調(diào)車(chē)作業(yè)安排優(yōu)先級(jí)的決策規(guī)則。遵循這些規(guī)則，逐個(gè)安排每列動(dòng)車(chē)組的調(diào)車(chē)作業(yè)，可以構(gòu)造出1個(gè)確定性的可行解。

(1) 動(dòng)車(chē)組出入所時(shí)刻確定規(guī)則

(2) 動(dòng)車(chē)組出入所進(jìn)路安排規(guī)則

遵循最大平行進(jìn)路的規(guī)則為動(dòng)車(chē)組安排到發(fā)進(jìn)路。

(3) 動(dòng)車(chē)組股道安排規(guī)則

由于動(dòng)車(chē)組的某些設(shè)備資源具有稀缺性，如檢修庫(kù)、洗車(chē)庫(kù)、不落輪鏇輪臨修等，應(yīng)當(dāng)減少動(dòng)車(chē)組占用這些關(guān)鍵設(shè)備的無(wú)效時(shí)間。因此，遵循先到先排、關(guān)鍵設(shè)備所在股道緊湊使用、股道均衡使用規(guī)則安排動(dòng)車(chē)組每項(xiàng)檢修作業(yè)所在的股道。

(4) 動(dòng)車(chē)組轉(zhuǎn)線調(diào)車(chē)進(jìn)路安排規(guī)則

遵循出場(chǎng)庫(kù)調(diào)車(chē)進(jìn)路優(yōu)先入場(chǎng)庫(kù)調(diào)車(chē)進(jìn)路、最大平行進(jìn)路優(yōu)先的規(guī)則安排進(jìn)路。

(5) 動(dòng)車(chē)組股道占用時(shí)間規(guī)則

遵循最小作業(yè)時(shí)間標(biāo)準(zhǔn)規(guī)則。

(6) 動(dòng)車(chē)組作業(yè)沖突解決規(guī)則

當(dāng)動(dòng)車(chē)組根據(jù)作業(yè)流程進(jìn)行股道安排發(fā)生作業(yè)沖突時(shí)，需要調(diào)整作業(yè)起止時(shí)刻化解沖突。分為兩種情況進(jìn)行不同的操作:

① 動(dòng)車(chē)組出入所發(fā)生接發(fā)進(jìn)路沖突或存車(chē)線沖突時(shí)，需要比較所有與安排動(dòng)車(chē)組進(jìn)路沖突的列車(chē)，分別計(jì)算它們沖突化解需要滿(mǎn)足的最小時(shí)間調(diào)整量，以其中最小值調(diào)整動(dòng)車(chē)組的出入所時(shí)刻；

② 除出入所以外的其他作業(yè)發(fā)生轉(zhuǎn)線進(jìn)路或股道沖突時(shí)，需要延后該項(xiàng)作業(yè)的開(kāi)始時(shí)刻，同時(shí)延長(zhǎng)前一項(xiàng)作業(yè)的終止時(shí)刻，即在前一項(xiàng)作業(yè)中發(fā)生等待時(shí)間，該時(shí)間等于所有可用股道中騰空后能被利用的最小時(shí)間調(diào)整量。

圖3的U3調(diào)車(chē)作業(yè)方案，從臨修線轉(zhuǎn)入檢修線時(shí)通過(guò)設(shè)置等待時(shí)間，化解作業(yè)沖突。

生成動(dòng)車(chē)所調(diào)車(chē)作業(yè)初始方案步驟:

Step1初始化動(dòng)車(chē)所設(shè)備參數(shù)

各場(chǎng)庫(kù)的股道、道岔及其聯(lián)通關(guān)系，生成動(dòng)車(chē)組進(jìn)路聯(lián)通表；初始化不同檢修流程類(lèi)型的動(dòng)車(chē)組比例；初始化動(dòng)車(chē)所不同檢修流程所需的股道占用時(shí)間標(biāo)準(zhǔn)、到發(fā)間隔時(shí)間標(biāo)準(zhǔn)、轉(zhuǎn)線進(jìn)路時(shí)間標(biāo)準(zhǔn)；確定動(dòng)車(chē)所通過(guò)能力計(jì)算的起止時(shí)間段等等；

Step2賦初值動(dòng)車(chē)組總數(shù)n=0；

Step3生成1組符合不同作業(yè)流程類(lèi)型的動(dòng)車(chē)組比例的最小集合；

Step4是否集合中所有動(dòng)車(chē)組均已安排計(jì)劃，是則轉(zhuǎn)Step3；否則，從現(xiàn)在的集合中隨機(jī)選取一沒(méi)有安排計(jì)劃的動(dòng)車(chē)組；

Step5根據(jù)“動(dòng)車(chē)組出入所時(shí)刻確定規(guī)則”確定該動(dòng)車(chē)組的出入所時(shí)刻；

Step6根據(jù)“動(dòng)車(chē)組到發(fā)進(jìn)路安排規(guī)則”、“動(dòng)車(chē)組股道安排規(guī)則”，“動(dòng)車(chē)組股道占用時(shí)間規(guī)則”、“動(dòng)車(chē)組轉(zhuǎn)線調(diào)車(chē)進(jìn)路安排規(guī)則”，為該動(dòng)車(chē)組安排作業(yè)所需的場(chǎng)庫(kù)作業(yè)股道、到發(fā)進(jìn)路、轉(zhuǎn)線進(jìn)路；如果該項(xiàng)作業(yè)找不到空閑的股道或進(jìn)路，說(shuō)明該動(dòng)車(chē)組的作業(yè)安排與其他動(dòng)車(chē)組發(fā)生沖突，轉(zhuǎn)Step7，否則轉(zhuǎn)Step8；

Step7根據(jù)“動(dòng)車(chē)組作業(yè)沖突解決規(guī)則”調(diào)整該動(dòng)車(chē)組作業(yè)起止時(shí)刻以及進(jìn)路占用起止時(shí)刻，轉(zhuǎn)Step6；

Step8若該動(dòng)車(chē)組該項(xiàng)作業(yè)的終止時(shí)刻大于TPe，則將該項(xiàng)作業(yè)的終止時(shí)刻設(shè)為T(mén)Pe，并轉(zhuǎn)Step9；否則判斷該動(dòng)車(chē)組的所有作業(yè)項(xiàng)目是否都被安排了計(jì)劃，是則記錄該動(dòng)車(chē)組，轉(zhuǎn)Step4，否則轉(zhuǎn)Step6；

Step9輸出動(dòng)車(chē)組總數(shù)，該值即為最大通過(guò)能力初始值，算法終止。

3.3 基于最長(zhǎng)活動(dòng)鏈的混合鄰域禁忌搜索算法

運(yùn)用啟發(fā)式排序規(guī)則可以高效生成大規(guī)模調(diào)度問(wèn)題的初始可行解，但不一定是最優(yōu)解。由于每列動(dòng)車(chē)組有多道作業(yè)工序，而加工工序的機(jī)器有限，因此將出現(xiàn)機(jī)器上工序排隊(duì)現(xiàn)象，即每列動(dòng)車(chē)組的工序間出現(xiàn)非生產(chǎn)等待時(shí)間，見(jiàn)圖3，文獻(xiàn)[10]已經(jīng)證明工序加工整體作業(yè)時(shí)間是由最長(zhǎng)關(guān)鍵加工路徑時(shí)間決定的，如果要優(yōu)化某調(diào)車(chē)作業(yè)方案的最晚動(dòng)車(chē)組出所時(shí)刻，必須減少最長(zhǎng)關(guān)鍵加工路徑上的非生產(chǎn)等待時(shí)間，最長(zhǎng)關(guān)鍵加工路徑又稱(chēng)為最長(zhǎng)活動(dòng)鏈。

(1) 最長(zhǎng)活動(dòng)鏈的構(gòu)造

為確定最長(zhǎng)活動(dòng)鏈，參考文獻(xiàn)[10]給出相關(guān)概念：

① 工件的前沿工序:假設(shè)工序u和v是工件J的兩個(gè)工序，在作業(yè)流程中，u需要在v前加工，則u就是v同一個(gè)工件的前沿工序，如果該兩個(gè)工序恰好相鄰，則u是v同一個(gè)工件的直接前沿工序；

② 機(jī)器上的前沿工序:設(shè)工序u和v是機(jī)器F上加工的兩個(gè)工序，如果u的開(kāi)始加工時(shí)間比v早，則稱(chēng)u是v的同一臺(tái)機(jī)器的前沿工序，如果這兩個(gè)工序恰好相鄰，則u是v同1臺(tái)機(jī)器的直接前沿工序；

③ 活動(dòng)鏈:工序u1條活動(dòng)鏈?zhǔn)?組工序的集合，開(kāi)始于1個(gè)沒(méi)有前沿工序的工序(即開(kāi)始于第1道工序)，結(jié)束于工序u，活動(dòng)鏈上的每個(gè)工序都是剩余工序中某塊的工件直接前沿工序或機(jī)器直接前沿工序；

④ 活動(dòng)鏈長(zhǎng)度:活動(dòng)鏈中第1個(gè)加工工序開(kāi)始時(shí)刻至最后1個(gè)加工工序結(jié)束時(shí)刻的長(zhǎng)度；

⑤ 最長(zhǎng)活動(dòng)鏈:所有活動(dòng)鏈中，最晚加工完成的1個(gè)工序的活動(dòng)鏈；

⑥ 活動(dòng)塊:最長(zhǎng)活動(dòng)鏈中，同1個(gè)機(jī)器加工的1組直接相鄰工序的集合。

圖3中，作業(yè)2是作業(yè)3的工件直接前沿工序、是作業(yè)5的工件前沿工序；作業(yè)3是作業(yè)4在洗車(chē)線上的直接前沿工序；作業(yè)1～3、作業(yè)5～9構(gòu)成最長(zhǎng)活動(dòng)鏈，其時(shí)間是這7項(xiàng)作業(yè)時(shí)間之和；作業(yè)3、4和作業(yè)6、7都是最長(zhǎng)活動(dòng)鏈中的活動(dòng)塊。

最長(zhǎng)活動(dòng)鏈構(gòu)造方法:

① 找到所有動(dòng)車(chē)組中最后的作業(yè)工序RiF；

② 確定RiF的機(jī)器直接前沿工序和工件直接前沿工序，比較兩個(gè)工序，選擇結(jié)束時(shí)刻等于RiF的開(kāi)始時(shí)刻的工序作為RiF的活動(dòng)鏈直接前沿工序Ri(M-1)，繼續(xù)查找Ri(M-1)的直接前沿工序，直到第1道作業(yè)Ri1為止，可得最長(zhǎng)活動(dòng)鏈；

③ 如果RiF的機(jī)器直接前沿工序和工件直接前沿工序的結(jié)束時(shí)刻相同，則可以任意選擇或者指定選擇其中之一為直接前沿工序。

(2) 基于最長(zhǎng)活動(dòng)鏈的混合鄰域禁忌搜索算法

禁忌搜索算法的關(guān)鍵之一是在當(dāng)前解的基礎(chǔ)上構(gòu)造出鄰域解，然后通過(guò)優(yōu)化指標(biāo)、禁忌表、評(píng)價(jià)函數(shù)、終止條件等逐步搜索到最優(yōu)解。

在本階段算法中，通過(guò)確定當(dāng)前調(diào)車(chē)作業(yè)方案中的最長(zhǎng)活動(dòng)鏈，然后移動(dòng)或交換最長(zhǎng)活動(dòng)鏈上活動(dòng)塊內(nèi)直接前沿工具有緩沖時(shí)間的作業(yè)，可形成1個(gè)新的可行調(diào)車(chē)作業(yè)方案，從而構(gòu)造出鄰域解。該方法能最大概率的減小最晚動(dòng)車(chē)組出所時(shí)刻，有利于盡快搜索到最優(yōu)解或滿(mǎn)意解，見(jiàn)圖3。作業(yè)7的直接前沿工序具有緩沖時(shí)間，因此可以交換作業(yè)6和作業(yè)7的檢修順序，得到1個(gè)新的安排計(jì)劃，而交換作業(yè)3和作業(yè)4則不成立。

對(duì)禁忌搜索算法的主要參數(shù)進(jìn)行設(shè)計(jì):

① 初始解。運(yùn)用啟發(fā)式排序規(guī)則生成調(diào)車(chē)作業(yè)初始方案；

② 鄰域結(jié)構(gòu)。通過(guò)移動(dòng)或交換當(dāng)前最長(zhǎng)活動(dòng)鏈上的活動(dòng)塊上的動(dòng)車(chē)作業(yè)產(chǎn)生鄰域解；

③ 評(píng)價(jià)函數(shù)。最晚動(dòng)車(chē)組出所時(shí)刻為鄰域解的評(píng)價(jià)函數(shù)；

④ 禁忌表。針對(duì)發(fā)生的作業(yè)移動(dòng)或交換進(jìn)行禁忌，保證后面的迭代搜索不出現(xiàn)相同的移動(dòng)情況。根據(jù)文獻(xiàn)[10]的結(jié)論，HNS-TS算法采用所有工序數(shù)量的1/7為禁忌表長(zhǎng)度是比較理想的，本文采用初始方案中的動(dòng)車(chē)組總工序數(shù)量的1/7為禁忌長(zhǎng)度；

⑤ 特赦條件。為避免丟失最優(yōu)解，規(guī)定在找不到領(lǐng)域解及迭代一定次數(shù)后，特赦禁忌表中最優(yōu)值為當(dāng)前解繼續(xù)進(jìn)行迭代搜索；

⑥ 終止條件。設(shè)置最大迭代次數(shù)作為終止條件，或者最長(zhǎng)活動(dòng)鏈的活動(dòng)塊上以不能發(fā)生交換、移動(dòng)等作業(yè)，則算法停止。

禁忌搜索算法優(yōu)化方案具體步驟為:

Step1設(shè)迭代次數(shù)為1，將啟發(fā)式排序算法初始方案置為當(dāng)前方案；

Step3判斷候選集解中對(duì)象是否滿(mǎn)足藐視準(zhǔn)則，選擇鄰域解中未被禁忌的對(duì)象或者滿(mǎn)足藐視準(zhǔn)則的禁忌對(duì)象為當(dāng)前解，更新禁忌表；

Step4迭代次數(shù)增加1，若迭代次數(shù)為最大迭代次數(shù)或者解無(wú)法改進(jìn)時(shí)，算法終止，輸出最優(yōu)方案，否則轉(zhuǎn)Step2。

如果得到的優(yōu)化方案中最晚動(dòng)車(chē)組出發(fā)時(shí)刻小于終止時(shí)刻TPe，則繼續(xù)按照3.2節(jié)算法增加動(dòng)車(chē)組，直到最晚動(dòng)車(chē)組出發(fā)時(shí)刻大于或等于終止時(shí)刻TPe時(shí)止，由此得到動(dòng)車(chē)所通過(guò)能力。

4 算例驗(yàn)證

某動(dòng)車(chē)所站場(chǎng)情況見(jiàn)圖4。其中21G1～25G1、21G2～25G2暫時(shí)不開(kāi)通使用。規(guī)定的最小車(chē)站間隔時(shí)間分別為列車(chē)到達(dá)追蹤間隔4 min、列車(chē)出發(fā)追蹤間隔3 min、列車(chē)不同時(shí)發(fā)到間隔時(shí)間8 min、列車(chē)不同時(shí)到發(fā)間隔時(shí)間3 min。動(dòng)車(chē)組在動(dòng)車(chē)所內(nèi)各作業(yè)項(xiàng)目的最小時(shí)間標(biāo)準(zhǔn)見(jiàn)表1。日常主要有存車(chē)作業(yè)流程和一級(jí)檢修流程2種，分別為到達(dá)動(dòng)車(chē)所到發(fā)場(chǎng)—到發(fā)場(chǎng)存放動(dòng)車(chē)組—發(fā)車(chē)；到達(dá)動(dòng)車(chē)所到發(fā)場(chǎng)—洗車(chē)庫(kù)洗車(chē)—庫(kù)前場(chǎng)吸污、待檢—檢修庫(kù)技檢作業(yè)—到發(fā)場(chǎng)出庫(kù)待發(fā)(存放)—發(fā)車(chē)。

假設(shè)動(dòng)車(chē)所需要一級(jí)檢修的動(dòng)車(chē)組與存車(chē)作業(yè)的動(dòng)車(chē)組的比例分別為40%、60%，動(dòng)車(chē)組均為16輛編組，根據(jù)動(dòng)車(chē)所歷年數(shù)據(jù)統(tǒng)計(jì)，一級(jí)檢修動(dòng)車(chē)組到達(dá)或發(fā)車(chē)作業(yè)時(shí)間平均為30 min，存車(chē)整備作業(yè)動(dòng)車(chē)組在動(dòng)車(chē)所的整備作業(yè)時(shí)間平均為5 h。計(jì)算23:00～7:00之間的動(dòng)車(chē)所通過(guò)能力。

表1 動(dòng)車(chē)所各項(xiàng)作業(yè)時(shí)間標(biāo)準(zhǔn)

首先根據(jù)40%、60%的作業(yè)流程類(lèi)型比例要求生成1組動(dòng)車(chē)組集合。根據(jù)啟發(fā)式排序規(guī)則安排每組動(dòng)車(chē)組的作業(yè)計(jì)劃，得到1個(gè)滿(mǎn)足所有約束條件的動(dòng)車(chē)調(diào)車(chē)作業(yè)初始方案，該初始方案的動(dòng)車(chē)組數(shù)為14列，其中一級(jí)檢修作業(yè)流程的動(dòng)車(chē)組為6列，存車(chē)作業(yè)流程的動(dòng)車(chē)組為8列，最晚動(dòng)車(chē)組的出所時(shí)刻為6:25。然后構(gòu)造第2階段基于最長(zhǎng)活動(dòng)鏈的禁忌搜索算法對(duì)14列的初始方案進(jìn)行優(yōu)化，經(jīng)過(guò)迭代50次后，得到優(yōu)化方案，其中最晚動(dòng)車(chē)組的出所時(shí)刻提早到6:00，見(jiàn)圖5，表明初始方案給出的通過(guò)能力值偏小，可以利用優(yōu)化方案中節(jié)省出來(lái)的時(shí)間繼續(xù)增加動(dòng)車(chē)組，最終得到動(dòng)車(chē)組為20列，其中一級(jí)檢修作業(yè)流程的動(dòng)車(chē)組為8列，辦理整備作業(yè)流程的動(dòng)車(chē)組為12列，最晚動(dòng)車(chē)組的出發(fā)時(shí)刻為6:30，最終結(jié)果見(jiàn)表2。作業(yè)安排結(jié)果顯示，動(dòng)車(chē)所洗車(chē)庫(kù)和檢修庫(kù)是能力瓶頸所在，限制一級(jí)檢修作業(yè)動(dòng)車(chē)組的數(shù)量，而動(dòng)車(chē)所到發(fā)場(chǎng)能力較為充足，如果不受到40%、60%的作業(yè)流程類(lèi)型比例要求，還可以繼續(xù)接發(fā)2列存車(chē)整備作業(yè)流程動(dòng)車(chē)組，即通過(guò)能力增加到22列。

運(yùn)用傳統(tǒng)的利用率法僅能對(duì)一晝夜整備動(dòng)車(chē)組數(shù)進(jìn)行計(jì)算得到69列，取平均值則23:00～7:00按8 h計(jì)算約為23列，計(jì)算結(jié)果與上述優(yōu)化算法相當(dāng)，利用率法僅給出1個(gè)能力結(jié)果值，無(wú)法精確給出每組動(dòng)車(chē)組設(shè)備利用和安排情況，而本優(yōu)化算法生成最大通過(guò)能力下的調(diào)車(chē)作業(yè)計(jì)劃，因此精確性及實(shí)用性更好。此外，有豐富經(jīng)驗(yàn)的工作人員運(yùn)用圖解法安排并估計(jì)8 h內(nèi)動(dòng)車(chē)所最大通過(guò)能力值也為22列，也驗(yàn)證優(yōu)化算法結(jié)果的正確性，但速度不及本優(yōu)化算法。

5 結(jié)論

本文在建立滿(mǎn)足各種約束條件的動(dòng)車(chē)所通過(guò)能力整數(shù)規(guī)劃模型后，提出啟發(fā)式排序規(guī)則與基于最長(zhǎng)活動(dòng)鏈的混合鄰域禁忌搜索算法相結(jié)合的優(yōu)化算法，為模擬仿真法計(jì)算動(dòng)車(chē)所通過(guò)能力提供思路，并以某實(shí)際動(dòng)車(chē)所23:00～7:00時(shí)段通過(guò)能力計(jì)算為例，驗(yàn)證模型及算法的有效性，結(jié)果優(yōu)于利用率法及圖解法。但尚未考慮更多的實(shí)際情況，例如：實(shí)際作業(yè)時(shí)間呈現(xiàn)隨機(jī)性變化，檢修設(shè)備可以被多列動(dòng)車(chē)組同時(shí)使用，動(dòng)車(chē)組隔日開(kāi)行等，將影響通過(guò)能力計(jì)算結(jié)果的實(shí)用性。下一步將對(duì)這些情況進(jìn)行探討，進(jìn)一步提高計(jì)算方法的適用性。

參考文獻(xiàn)：

[1] 杜文.旅客運(yùn)輸組織[M].北京：中國(guó)鐵道出版社，2012：56-58.

[2] ALEX LANDEX. Capacity Statement for Railways[C]//Annual Transport Conference at Aalborg University. Denmark: Aalborg University ,2007:1-19.

[3] HAMED POURYOUSEF, PASI LAUTALA, THOMAS WHITE. Review of Capacity Measurement Methodologies:Similaritys and Differences in the U.S. and European Railroads[C]// Annual Meeting of the Transportation Research Board.USA: Transportation Research Board, 2013:1-14.

[4] 李波.動(dòng)車(chē)所一、二級(jí)檢修作業(yè)能力優(yōu)化[J].中國(guó)鐵路,2008(12):28-30.

LI Bo.Optimization of First-class and Second-class Maintenance Capability at EMU Depot[J].Chinese Railways,2008(12):28-30.

[5] 耿敬春,牛會(huì)想,肖春光,等.北京動(dòng)車(chē)段出入段線建設(shè)規(guī)模及能力適應(yīng)性分析[J].鐵道工程學(xué)報(bào),2008(10):74-77.

GENG Jingchun, NIU Huixiang, XIAO Chunguang, et al. Adaptablility Analysis of Scale and Capacity of the Entrance & Exit Depot Line of Beijing Multiple Unit Depot[J].Journal of Railway Engineering Society,2008(10):74-77.

[6] 林伯梁,張偉,王家喜.編制動(dòng)車(chē)組一級(jí)修調(diào)車(chē)作業(yè)計(jì)劃的啟發(fā)式算法[EB/OL]. 北京:中國(guó)科技論文在線 [2013-12-16 ].http://www.paper.edu.cn/releasepaper/content/201312-375.

[7] 李建,林伯梁,王家喜.動(dòng)車(chē)組日常檢修計(jì)劃優(yōu)化調(diào)整決策支持系統(tǒng)[EB/OL]. 北京:中國(guó)科技論文在線 [2013-09-12].http://www.paper.edu.cn/releasepaper/content/201309-166.

[8] 王忠凱,史天運(yùn),張惟皎,等.動(dòng)車(chē)運(yùn)用所調(diào)車(chē)作業(yè)計(jì)劃優(yōu)化編制模型與算法[J].鐵道學(xué)報(bào),2013,35(8):1-9.

WANG Zhongkai, SHI Tianyun, ZHANG Weijiao,et al. Model and Algorithm for Optimized Formulation of Scheduled Shunting Operation Plans of Electric Multiple Units Depots[J].Journal of the China Railway Society,2013,35(8):1-9.

[9] 韋秋金.多階段流水車(chē)間調(diào)度問(wèn)題的啟發(fā)式算法研究[D].沈陽(yáng)：東北大學(xué)，2004:8-12.

[10] 邢德偉.加工車(chē)間調(diào)度問(wèn)題中禁忌搜索算法的研究與改進(jìn)[D].西安：西安電子科技大學(xué)，2010:19-32.