動車所調(diào)車作業(yè)計劃優(yōu)化模型與算法

殷 迪，唐秋華，張子凱，韓大勇

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

為保證行車安全，動車組必須在夜間返回動車所進(jìn)行維修，維修方式通常為一級修，主要包括檢修和清洗兩項作業(yè)，分別在檢修股道和清洗股道上完成，此外，動車所還配備有一定數(shù)量的存車股道，主要用于動車組待檢時的臨時停放及檢后預(yù)留停放。動車所需根據(jù)動車組的運(yùn)用計劃編制調(diào)車作業(yè)計劃，即在動車組出入動車所時間確定的前提下，合理分配每輛動車組的檢修、清洗和停放股道及占用相應(yīng)股道的時間，在確保動車組按計劃運(yùn)行的同時順利完成一級修任務(wù)，為其下一個行程提供安全保障。傳統(tǒng)的調(diào)車作業(yè)計劃編制主要依賴于調(diào)度人員的經(jīng)驗，存在編制難度大、效率低等不足，加之我國動車組數(shù)量不斷增多、股道資源持續(xù)擴(kuò)增，如何科學(xué)、有效且快速地完成調(diào)車作業(yè)計劃編制，是當(dāng)前亟需解決的問題。

根據(jù)優(yōu)化目標(biāo)的不同，調(diào)車作業(yè)計劃編制問題主要分為兩類：①單目標(biāo)優(yōu)化問題，如最小化動車所內(nèi)總延誤時間[1]，最小化調(diào)車總鉤數(shù)[2]，最小化動車組檢修完成時間[3]，最大化股道利用率[4]等。②多目標(biāo)優(yōu)化問題，如最小化檢修區(qū)無效占用時間和調(diào)車路徑費(fèi)用[5]，最大化存車線利用率和減少調(diào)車作業(yè)走行距離等[6]，最小化總延誤時間、檢修區(qū)無效占用時間、擁堵時間和維修成本[7]。基于構(gòu)建的優(yōu)化模型，求解調(diào)車作業(yè)計劃編制優(yōu)化問題的方法主要有精確算法和啟發(fā)式算法，不過前者雖然可求得問題的最優(yōu)解，但求解效率偏低，而后者則能在較短時間內(nèi)求得問題的近優(yōu)解，實用價值較高，因此，本文將動車所調(diào)車作業(yè)計劃編制問題轉(zhuǎn)化為帶有不定加工時長的Job-Shop調(diào)度問題，以動車組在存車線上的總預(yù)留時間最大化為目標(biāo)函數(shù)，建立動車所調(diào)車作業(yè)計劃編制優(yōu)化模型，設(shè)計了求解該模型的啟發(fā)式算法，并借助實驗算例驗證了模型和算法的有效性。

1 問題描述

圖1所示為典型的動車組一級維修流程示意圖。當(dāng)動車組進(jìn)所后，先后通過存車區(qū)1、作業(yè)區(qū)、存車區(qū)2，最后出所。存車區(qū)1可用于停放剛?cè)胨膭榆嚱M，當(dāng)作業(yè)區(qū)有可用的作業(yè)股道時，也可不在存車區(qū)1停留直接進(jìn)入作業(yè)區(qū)作業(yè)；清洗和檢修作業(yè)在作業(yè)區(qū)內(nèi)完成，每項作業(yè)時長須滿足標(biāo)準(zhǔn)作業(yè)時間，且兩項作業(yè)之間的順序是不固定的；存車區(qū)2停放完成全部維修工作且等待出所的動車組。動車組在動車所內(nèi)的調(diào)車路徑包含動車組從存車區(qū)1到作業(yè)區(qū)的轉(zhuǎn)線、作業(yè)區(qū)內(nèi)部的轉(zhuǎn)線和作業(yè)區(qū)到存車區(qū)2的轉(zhuǎn)線，轉(zhuǎn)線時間均按標(biāo)準(zhǔn)作業(yè)時間進(jìn)行。動車組轉(zhuǎn)線時必須滿足股道時空相容性，如果下一作業(yè)區(qū)域的股道已全被占用，動車組必須停在當(dāng)前股道進(jìn)行等待。因此，可將動車所調(diào)車作業(yè)計劃編制問題描述為加工時長不定、加工順序不定的Job-Shop調(diào)度問題。在實際作業(yè)現(xiàn)場，動車所作業(yè)區(qū)配備的檢修設(shè)備往往能力有限，是動車所檢修能力的瓶頸，對動車組檢修效率影響較大[5]，故而應(yīng)盡量減少動車組對作業(yè)區(qū)股道的不必要占用，以便提高檢修設(shè)備利用率和動車所檢修吞吐量，當(dāng)動車組檢修作業(yè)完成后，應(yīng)盡快將動車組調(diào)入存車區(qū)2等待出所，確保每輛動車組按規(guī)定時刻出所，避免延誤。

圖1 動車組一級維修流程Fig.1 First-level maintenance procedure of EMU

2 MIP優(yōu)化模型構(gòu)建

2.1 符號說明

集合：

E動車組集合，索引為e,e∈{1,2,...,Ne}。

Z作業(yè)區(qū)集合，索引為z,z∈{1,2,3,4}，分別代表存車區(qū)1、清洗區(qū)、檢修區(qū)和存車區(qū)2。

Dz作業(yè)區(qū)作業(yè)線集合,索引為Dz,d,d∈{D1,D2,D3,D4}。

R相鄰作業(yè)線區(qū)轉(zhuǎn)線股道集合，索引為r，r′表示股道d和d′之間的轉(zhuǎn)線股道，若存在連通關(guān)系，則rd,d′=1 ；否則為0。

參數(shù)：

τr標(biāo)準(zhǔn)轉(zhuǎn)線時間,min。

pz各作業(yè)區(qū)標(biāo)準(zhǔn)作業(yè)時間,min。

n每條股道上執(zhí)行的第n個作業(yè)，n={1,...,Nd}。

l每個動車組執(zhí)行的第l個作業(yè)，l={1,2,3,4}。

中間變量：

Sez連續(xù)變量，動車組e占用作業(yè)區(qū)z的開始時刻。

Fez連續(xù)變量，動車組e占用作業(yè)區(qū)z的結(jié)束時刻。

Bdn連續(xù)變量，股道d的第n個作業(yè)的開始時刻。

Tdn連續(xù)變量，股道d的第n個作業(yè)的結(jié)束時刻。

決策變量：

Xezl0-1變量，動車組e的第l個操作在作業(yè)區(qū)z執(zhí)行。

Yezdn0-1變量，動車組e在作業(yè)區(qū)z的股道d上執(zhí)行的第n個操作。

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

當(dāng)動車組檢修作業(yè)完成后，應(yīng)盡快將其調(diào)入存車區(qū)2準(zhǔn)備出所，動車組在存車區(qū)2上總預(yù)留時間越長，準(zhǔn)備就越充分，對作業(yè)區(qū)股道的不必要占用時間就越短，以動車組在存車線上的總預(yù)留時間最大化為目標(biāo)函數(shù)，表達(dá)式為

(1)

2.3 約束條件

分配約束：每輛動車組必須進(jìn)行清洗和檢修作業(yè)，每項作業(yè)僅需執(zhí)行一次，且兩項作業(yè)之間無固定先后順序，孰前孰后均可，則有

(2)

(3)

每輛動車組需要遍歷存車區(qū)1、清洗區(qū)、檢修區(qū)和存車區(qū)2共四個區(qū)域，且在每個區(qū)域內(nèi)，每輛動車組只能占用一條股道，則有

(4)

給定股道d的第n個作業(yè)最多可進(jìn)行一個作業(yè)，則有

(5)

在任意給定的股道d上，前面的作業(yè)先分配后才能分配后面的作業(yè)，則有

?d∈Dz,?n∈Nd

(6)

定時約束：如果動車組e在作業(yè)區(qū)z的作業(yè)確定為股道d上的第n個作業(yè)，則該作業(yè)的起止時刻等于動車組e在作業(yè)區(qū)z上的起止時刻，其中M是一個足夠大的數(shù)，有

Sdn≤Bez+M(1-Yezdn),

?e∈E,?z∈Z,?d∈Dz,?n∈Nd

(7)

Sdn≥Bez-M(1-Yezdn),

?e∈E,?z∈Z,?d∈Dz,?n∈Nd

(8)

Fdn≤Tez+M(1-Yezdn),

?e∈E,?z∈Z,?d∈Dz,?n∈Nd

(9)

Fdn≥Tez-M(1-Yezdn),

?e∈E,?z∈Z,?d∈Dz,?n∈Nd

(10)

如果動車組e′在動車組e后進(jìn)入作業(yè)區(qū)z的股道d，動車組e′在該作業(yè)區(qū)的開始時間不小于動車組e在該作業(yè)區(qū)的結(jié)束時間，則有

Be′z′≥Tez-M(2-Yezdn-Ye′z′d,n+1),

?e,e′∈E,?z,z′∈Z

(11)

動車組e在工作區(qū)z的停留時間不小于該區(qū)域標(biāo)準(zhǔn)作業(yè)時間，則有

(12)

轉(zhuǎn)線約束：轉(zhuǎn)線作業(yè)時長約束，即動車組e在前一區(qū)域z的結(jié)束時刻加上通過轉(zhuǎn)線股道r的作業(yè)時間等于下一區(qū)域z′的開始時刻，則有

(13)

(14)

上述MIP模型是一個具有空間、時間二維特性、約束條件復(fù)雜的組合優(yōu)化問題，隨著動車組數(shù)目、動車所股道數(shù)目的增加，將會產(chǎn)生“組合爆炸”，而在實際的調(diào)車作業(yè)現(xiàn)場，調(diào)度員期望能快速生成近優(yōu)解乃至最優(yōu)解，考慮到現(xiàn)場操作需要的易用性和可解析性，擬設(shè)計規(guī)則組合算法對問題進(jìn)行求解。

3 調(diào)車作業(yè)計劃編制算法

為了科學(xué)、有效、快速地編制動車所調(diào)車作業(yè)計劃，本文設(shè)計的求解算法融合了“先到先加工”“股道均衡分配”“股道無效占用時間最小化”等3種分配規(guī)則，并設(shè)計“沖突消解策略”以保證調(diào)車作業(yè)計劃的可行性。

3.1 先到先加工規(guī)則

動車所確定動車組的運(yùn)用計劃后，動車組入所的時刻隨之確定。根據(jù)先到先加工的原則，獲得動車組入所后作業(yè)分配的先后順序。

3.2 股道均衡分配規(guī)則

3.3 股道無效占用時間最小化規(guī)則

(15)

(16)

3.4 沖突消解策略

3.5 調(diào)車作業(yè)計劃編制步驟

當(dāng)動車所給定動車組運(yùn)用計劃后，基于上述的作業(yè)分配規(guī)則及策略，動車組的調(diào)車作業(yè)計劃編制具體步驟如下：

步驟1：初始化動車所一級檢修的基本參數(shù)Dz、pz等，設(shè)定每條股道的使用時間窗Time_Window(d,n)及其最早可用時間節(jié)點rz,d為0，根據(jù)“先到先加工規(guī)則”確定動車組的分配順序π(e)。

步驟5：令e=e+1，返回步驟 1，直至所有的動車組分配完，調(diào)車作業(yè)計劃編制完成。

4 算例實驗與分析

為了驗證上述模型和算法的有效性，本文設(shè)計了啟發(fā)式算法(HEU)與精確算法求解的對比實驗。實驗計算機(jī)配置：CPU 為Intel core i5 2.3 GHz，內(nèi)存為8.00 GB 2133 MHz，啟發(fā)式算法求解軟件為Matlab，精確算法求解器(MIP-Solver)為GAMS24.0/Cplex。借助實驗首先驗證模型和算法的有效性，再將所提出的啟發(fā)式算法與調(diào)度問題中常見的啟發(fā)式算法進(jìn)行比較，并評估解的質(zhì)量，最后討論目標(biāo)值和運(yùn)算時間隨股道資源狀態(tài)變化的變化趨勢。

4.1 MIP-CPLEX對比實驗

表1所示為動車組運(yùn)用計劃案例。案例一、二中的動車組EMU 1-8進(jìn)出所時刻均為動車所的實際運(yùn)用計劃，其一級檢修參數(shù)在表1中給出，標(biāo)準(zhǔn)轉(zhuǎn)線時間都為τr=5 min。假設(shè)股道資源可變，分別設(shè)置不同區(qū)域的股道條數(shù)，以股道狀態(tài)I為例，4-2-3-6表示存車區(qū)1的存車線條數(shù)為4條，清洗線2條，檢修線3條，存車區(qū)2的存車線條數(shù)為6條。同理，設(shè)置股道資源狀態(tài)II：4-2-3-7，III：4-2-3-8，IV：4-2-4-6，V：4-2-4-7，VI：4-2-4-8, VII: 4-2-5-6，VIII：4-2-5-8。在下述實驗中，分別改變動車組的數(shù)量、股道資源的狀態(tài)來獲得不同的實驗算例。

表1 動車組運(yùn)用計劃案例Table 1 EMU rolling stock cases

為了驗證上述算法的有效性，固定股道狀態(tài)，改變動車組的數(shù)目：取案例一、二的前3、4、5、6輛動車組的進(jìn)出所時刻，分別用MIP-Solver、HEU算法對算例進(jìn)行求解并對比。設(shè)定MIP-Solver求解的最大時間上限為3 h，MIP-Solver(有初始解)是將啟發(fā)式算法求得的解賦值給MIP-Solver后再進(jìn)行求解。當(dāng)股道狀態(tài)固定為I時，算法求解結(jié)果如表2所示。由表2可見，MIP-Solver在規(guī)定的時間內(nèi)均找到了可行解，且案例一、二中的算例3、4、5為最優(yōu)解，算例6在規(guī)定的時間內(nèi)求得的目標(biāo)值的Gap分別為為1.3%、2.0%，隨著動車組數(shù)量的增加，MIP-Solver的求解時間逐漸變大；與之對比，HEU算法求解案例一、二中算例3、4、5的目標(biāo)值與MIP-solver求解的目標(biāo)值相同，而算例6中的目標(biāo)值略低于MIP-Solver所求解的目標(biāo)值，且HEU算法求解時間均在0.5 s以內(nèi)。然后，將HEU算法的解帶入MIP-Solver進(jìn)行檢驗，與預(yù)想一致，將HEU算法所求初值賦予MIP-Solver會極大地減小求解空間，并快速地得到Gap為0且與HEU算法求解相同的目標(biāo)值。

表2 算法求解結(jié)果Table 2 Algorithm solution results

圖2所示為案例二的前6個動車組的調(diào)車作業(yè)計劃求解結(jié)果Gantt圖，橫軸為時間軸，縱軸為股道編號。股道上繪制的長條表示動車組對相應(yīng)股道的占用，長條的長度為股道占用時長。從圖2中可以看出，股道資源均衡利用，且在清洗區(qū)和檢修區(qū)完成作業(yè)時間均為標(biāo)準(zhǔn)作業(yè)時間。上述小規(guī)模對比試驗結(jié)果證明了所提出算法的有效性。

圖2 動車所調(diào)車作業(yè)Gantt圖Fig.2 Shunting schedule Gantt of EMU depot

4.2 啟發(fā)式算法對比實驗

將本文提出的啟發(fā)式算法(HEU)與FCFS、EDD及STT等3種常見的啟發(fā)式算法[8]進(jìn)行對比分析，其中FCFS的基本思想為:先回到動車所的最先進(jìn)行調(diào)度，且分配到最先空閑的車道上；EDD的基本思想為：最先離開動車所的車輛，具有最高優(yōu)先權(quán)，且分配到最先空閑的車道上；STT的基本思想為：最短在庫時間優(yōu)先法則。計算每輛動車在動車所的停留時間(停留時間=出所時刻-入所時刻)，該時間最短的具有最高優(yōu)先權(quán)，分配到最先空閑的車道上。

實驗算例設(shè)置：動車組的數(shù)量分別取案例一和二中的前5、6、7、8輛；股道資源狀態(tài)分別從I取到VIII共八種情形。從而可得，每個案例的算例規(guī)模為32個，兩組案例共64個算例。為了驗證算法的性能，采用偏移比DP[8]比較上述四種啟發(fā)式算法在64個案例中的優(yōu)越性。計算公式為

(17)

式中，Objbest為每個案例下，4種啟發(fā)式算法求出的最好解的目標(biāo)值，Objsol為每個啟發(fā)式算法獲取解的目標(biāo)值。4種啟發(fā)式算法在64個案例下的對比結(jié)果見表3。由表3對比分析可知，在計算時間無顯著差異的情況下，HEU算法相較于另外3種常見的啟發(fā)式算法，其解的質(zhì)量在所有案例中均是最優(yōu)的。

表3 算法結(jié)果對比Table 3 Algorithms solution comparison

5 結(jié)語

為了有效、快速地實現(xiàn)調(diào)車作業(yè)計劃編制與優(yōu)化，構(gòu)建了動車所調(diào)車作業(yè)計劃編制與優(yōu)化的混合整數(shù)規(guī)劃模型，并描述了模型的約束和目標(biāo)。在模型的基礎(chǔ)上，設(shè)計了基于“先進(jìn)先服務(wù)”“股道均衡分配”“股道占用時間最小化”規(guī)則的啟發(fā)式求解算法。在實驗算例中，對本文所提出的啟發(fā)式算法求解結(jié)果與精確的MIP算法求解結(jié)果進(jìn)行比較，驗證該啟發(fā)式算法的可行性和求解效率，此外，又將其與調(diào)度中常見的3類啟發(fā)式算法進(jìn)行了比較，結(jié)果表明，本文所提的啟發(fā)式算法求解結(jié)果具有明顯的優(yōu)越性。在未來的工作中，更多符合實際現(xiàn)場的因素應(yīng)予考慮，例如動車組的長短編之分，股道之間的瓶頸沖突等，在本文所提出的啟發(fā)式算法基礎(chǔ)上可設(shè)計出更優(yōu)化的算法對實際問題進(jìn)行求解。