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

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

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

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

1 問(wèn)題描述

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

圖1 動(dòng)車(chē)組一級(jí)維修流程Fig.1 First-level maintenance procedure of EMU

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

2.1 符號(hào)說(shuō)明

集合：

E動(dòng)車(chē)組集合，索引為e,e∈{1,2,...,Ne}。

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

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

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

參數(shù)：

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

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

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

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

中間變量：

Sez連續(xù)變量，動(dòng)車(chē)組e占用作業(yè)區(qū)z的開(kāi)始時(shí)刻。

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

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

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

決策變量：

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

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

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

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

(1)

2.3 約束條件

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

(2)

(3)

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

(4)

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

(5)

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

?d∈Dz,?n∈Nd

(6)

定時(shí)約束：如果動(dòng)車(chē)組e在作業(yè)區(qū)z的作業(yè)確定為股道d上的第n個(gè)作業(yè)，則該作業(yè)的起止時(shí)刻等于動(dòng)車(chē)組e在作業(yè)區(qū)z上的起止時(shí)刻，其中M是一個(gè)足夠大的數(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)

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

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

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

(11)

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

(12)

轉(zhuǎn)線(xiàn)約束：轉(zhuǎn)線(xiàn)作業(yè)時(shí)長(zhǎng)約束，即動(dòng)車(chē)組e在前一區(qū)域z的結(jié)束時(shí)刻加上通過(guò)轉(zhuǎn)線(xiàn)股道r的作業(yè)時(shí)間等于下一區(qū)域z′的開(kāi)始時(shí)刻，則有

(13)

(14)

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

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

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

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

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

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

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

(15)

(16)

3.4 沖突消解策略

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

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

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

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

4 算例實(shí)驗(yàn)與分析

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

4.1 MIP-CPLEX對(duì)比實(shí)驗(yàn)

表1所示為動(dòng)車(chē)組運(yùn)用計(jì)劃案例。案例一、二中的動(dòng)車(chē)組EMU 1-8進(jìn)出所時(shí)刻均為動(dòng)車(chē)所的實(shí)際運(yùn)用計(jì)劃，其一級(jí)檢修參數(shù)在表1中給出，標(biāo)準(zhǔn)轉(zhuǎn)線(xiàn)時(shí)間都為τr=5 min。假設(shè)股道資源可變，分別設(shè)置不同區(qū)域的股道條數(shù)，以股道狀態(tài)I為例，4-2-3-6表示存車(chē)區(qū)1的存車(chē)線(xiàn)條數(shù)為4條，清洗線(xiàn)2條，檢修線(xiàn)3條，存車(chē)區(qū)2的存車(chē)線(xiàn)條數(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í)驗(yàn)中，分別改變動(dòng)車(chē)組的數(shù)量、股道資源的狀態(tài)來(lái)獲得不同的實(shí)驗(yàn)算例。

表1 動(dòng)車(chē)組運(yùn)用計(jì)劃案例Table 1 EMU rolling stock cases

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

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

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

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

4.2 啟發(fā)式算法對(duì)比實(shí)驗(yàn)

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

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

(17)

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

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

5 結(jié)語(yǔ)

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