動(dòng)車生產(chǎn)中的組車優(yōu)化調(diào)度方法

郭佳鵬 趙 寧 吳秀麗

北京科技大學(xué)機(jī)械工程學(xué)院，北京，100083

0 引言

近年來(lái)，動(dòng)車的快速發(fā)展帶來(lái)了動(dòng)車生產(chǎn)交付的新問題。動(dòng)車生產(chǎn)中，列車車廂生產(chǎn)受制造工藝影響，產(chǎn)出順序與交車順序并不相同。此時(shí)需要把列車車廂暫存到交車線，當(dāng)一列車的車廂全部完成時(shí)，調(diào)出全部車廂組成列車交付。由于交車線數(shù)量有限，而積壓的訂單和列車車廂越來(lái)越多，調(diào)出目標(biāo)車廂時(shí)需對(duì)大量車廂進(jìn)行連鎖調(diào)整，造成了額外成本并嚴(yán)重影響組車和聯(lián)調(diào)效率。如何優(yōu)化調(diào)度，縮短調(diào)車過(guò)程中的車廂調(diào)運(yùn)距離和交車時(shí)間，是本問題的研究目標(biāo)。

組車優(yōu)化調(diào)度問題與火車車廂運(yùn)行編組調(diào)度、車輛調(diào)度等問題相似。王典等[1]以車輛在編組站的總停留時(shí)間和總額外中轉(zhuǎn)時(shí)間最小為目標(biāo)，構(gòu)建了多目標(biāo)混合整數(shù)線性規(guī)劃模型；肖杰等[2]采用遺傳算法建立了單組列車編組優(yōu)化模型；郭瑞等[3]設(shè)計(jì)了優(yōu)先規(guī)則和推理算法；畢明凱等[4]以運(yùn)輸費(fèi)用最小為目標(biāo)函數(shù)，構(gòu)建了編組去向和調(diào)車線數(shù)量協(xié)調(diào)優(yōu)化模型；趙軍等[5]針對(duì)雙向編組站配流問題，構(gòu)建了大規(guī)模混合整數(shù)線性規(guī)劃模型；張其亮等[6]針對(duì)復(fù)線列車調(diào)度問題，提出了一種混合粒子群優(yōu)化算法進(jìn)行求解。上述研究都取得了很好效果，但研究問題與目標(biāo)函數(shù)都與本文不同。

車輛調(diào)度問題包括車輛使用成本最小的調(diào)度問題[7]、堆場(chǎng)中的車輛調(diào)度問題[8]和AGV的調(diào)度問題[9]，這些車輛調(diào)度屬于小規(guī)模的車輛調(diào)度，可以通過(guò)智能算法找到一個(gè)比較優(yōu)秀的結(jié)果。對(duì)于大規(guī)模車輛調(diào)度問題，徐奇等[10]在港口的拖輪調(diào)度問題中，利用啟發(fā)式規(guī)則和模擬退火算法相結(jié)合的算法進(jìn)行優(yōu)化。對(duì)于集裝箱碼頭調(diào)度問題，梁亮等[11]建立了整數(shù)規(guī)劃模型，并利用二階段啟發(fā)式算法進(jìn)行調(diào)度優(yōu)化；曾慶成等[12]提出了神經(jīng)網(wǎng)絡(luò)和模擬退火算法的混合優(yōu)化算法；李斌等[13]集成服務(wù)系統(tǒng)的理念，建立了一個(gè)新的調(diào)度體系。針對(duì)散貨碼頭中的車輛調(diào)度問題，VAN VIANEN 等[14]用調(diào)度規(guī)則代替調(diào)度算法，縮短了調(diào)度所需的時(shí)間；鹿特丹港的調(diào)度仿真模型[15]中，使用啟發(fā)式的算法結(jié)果與最優(yōu)解偏差為10%，但運(yùn)算時(shí)間僅為求得最優(yōu)解的0.01%。然而，上述車輛調(diào)度的研究都沒有考慮車輛的編組和編組導(dǎo)致的聯(lián)動(dòng)調(diào)車問題，因此也不同于本文研究問題。

上述研究成果無(wú)法直接用到動(dòng)車組車調(diào)度中。對(duì)于不追求最優(yōu)解的工程問題，啟發(fā)式方法往往可以獲得很好的實(shí)用效果。為了探索適合該問題的啟發(fā)式調(diào)度方法，本文基于離散事件仿真技術(shù)建立組車調(diào)度仿真模型，并采用仿真調(diào)度的方法進(jìn)行研究。

1 問題描述

我國(guó)的動(dòng)車生產(chǎn)中，由于工藝等條件的限制，生產(chǎn)順序并非是列車的出廠順序，所以車廂順序需要在調(diào)車線進(jìn)行調(diào)整。該調(diào)整過(guò)程可描述如下：假設(shè)軌道中的車廂服從先入先出原則，第t個(gè)存車軌道為Qt，第i輛列車的第j節(jié)車廂表示為Ci,j，則圖1所示的存車軌道Q1、Q2的車廂儲(chǔ)存狀態(tài)可表示為(C1,7,C2,2,C1,6,C1,3)和(C1,1,C2,5,C2,8,C2,4)。

圖1 交車線示意圖Fig.1 Delivery line diagram

當(dāng)有新車廂進(jìn)入存車軌道時(shí)，選擇有存儲(chǔ)空間的軌道，并將其存儲(chǔ)在第一個(gè)位置。在上述存儲(chǔ)狀態(tài)的基礎(chǔ)上，通過(guò)中間軌道調(diào)換存車軌道和存儲(chǔ)位置，但每條軌道需滿足先入先出的原則。例如圖1中的C1,3離開Q1之后，C1,6才能離開。離開的車廂再進(jìn)入隊(duì)列時(shí)和新車廂進(jìn)入存車軌道方式相同，只能排在C1,7或C1,1之前。最終通過(guò)上述方式在某一存車軌道按順序組合目標(biāo)列車的全部車廂，即實(shí)現(xiàn)組車。假定QD為出口軌道，對(duì)應(yīng)的列車i有n節(jié)車廂，其最終組車狀態(tài)的車廂順序?yàn)?Ci,1,Ci,2, …,Ci,n)。

以調(diào)出車廂Ci,j為例來(lái)說(shuō)明，組車過(guò)程需要確定QD中按順序缺失的車廂Ci,j，并將車廂Ci,j從對(duì)應(yīng)的Qt調(diào)入QD。調(diào)出車廂Ci,j需要進(jìn)行以下操作：

(1)將存車軌道Qt中阻擋車廂Ci,j到達(dá)QD的多個(gè)車廂順序移出軌道Qt。

(2)移出的車廂可進(jìn)入用于調(diào)車的預(yù)留軌道Qbuffer。

(3)移出目標(biāo)車廂Ci,j，j←j+1。

(4)從預(yù)留軌道Qbuffer中移出暫存車廂，重新選擇進(jìn)入新的存車軌道。

重復(fù)上述過(guò)程，直到Ci,n均按照順序移入QD。上述過(guò)程中，只有步驟(4)把暫存車廂重新移入存車軌道時(shí)存在優(yōu)化空間。重新進(jìn)入軌道會(huì)造成新的存車順序，對(duì)后續(xù)的調(diào)車帶來(lái)不同程度的影響。在調(diào)車過(guò)程中，每次移動(dòng)車廂都會(huì)耗費(fèi)一定能源，耗費(fèi)能源與車廂行程成正比，記為wi,j，則該問題的目標(biāo)函數(shù)為min∑wi,j。

此外，由于生產(chǎn)存在一定的不確定性，因此可認(rèn)為新車廂到達(dá)順序隨機(jī)，新車廂到達(dá)時(shí)通過(guò)分配車廂存儲(chǔ)軌道，實(shí)現(xiàn)未來(lái)調(diào)車過(guò)程的優(yōu)化。調(diào)車時(shí)可通過(guò)步驟(4)重新分配車廂存儲(chǔ)軌道，來(lái)優(yōu)化后續(xù)調(diào)車的行駛距離。為了節(jié)約存儲(chǔ)空間，調(diào)車線中只要任意列車的全部車廂到齊，即可實(shí)施上述組車過(guò)程。上述問題具有高動(dòng)態(tài)性和隨機(jī)性，難以通過(guò)建立數(shù)學(xué)模型的方法求解，所以本文利用啟發(fā)式的方法尋求存儲(chǔ)軌道分配規(guī)則，并針對(duì)企業(yè)實(shí)例建立仿真模型。

2 仿真模型構(gòu)建

2.1 模型邏輯

某動(dòng)車企業(yè)列調(diào)車間共6條軌道，如圖2所示。車廂由入口軌道進(jìn)入交車線，組車成功后整列列車由出口軌道駛出存車線。仿真模型中軌道的長(zhǎng)度按企業(yè)具體情形建立，結(jié)合車廂長(zhǎng)度每條軌道的最大容量為8節(jié)車廂。

圖2 軌道布置Fig.2 Track layout

車廂進(jìn)入存車軌道時(shí)，根據(jù)相應(yīng)的規(guī)則，通過(guò)中間軌道進(jìn)入相應(yīng)的存車軌道，考慮到車廂調(diào)車的問題，預(yù)留1個(gè)軌道進(jìn)行調(diào)車，這里將軌道6作為暫存軌道Qbuffer。

仿真過(guò)程首先隨機(jī)產(chǎn)生車廂，車廂根據(jù)相應(yīng)的規(guī)則進(jìn)入存車軌道，當(dāng)某列列車對(duì)應(yīng)的全部車廂都進(jìn)入存車軌道時(shí)，觸發(fā)組車事件。組車時(shí)，根據(jù)列車車廂原始順序?qū)噹M(jìn)行調(diào)整并按次序組車；調(diào)車時(shí)，將目標(biāo)車廂前方的車廂依次移入軌道6，再將目標(biāo)車廂移出。圖3、圖4分別為仿真邏輯流程圖和組車流程圖。

圖3 仿真邏輯流程圖Fig.3 Simulation flow chart

圖4 調(diào)車流程Fig.4 Marshalling flow chart

2.2 實(shí)驗(yàn)設(shè)計(jì)

根據(jù)訂單的批量設(shè)計(jì)3組(小批量訂單、中批量訂單、大批量訂單)實(shí)驗(yàn)。模型利用3種運(yùn)算的方案：窮舉算法、遺傳算法(genetic algorithm, GA)和啟發(fā)式規(guī)則進(jìn)行仿真對(duì)比。

窮舉算法適用于小批量訂單情形。新車廂進(jìn)入存車線時(shí)依次枚舉所有軌道，并仿真后續(xù)的組車。

遺傳算法適合中批量訂單情形。隨著訂單的增多，窮舉算法的計(jì)算量難以承受，采用遺傳算法選擇車廂與存車線的對(duì)應(yīng)關(guān)系。

啟發(fā)式規(guī)則適合大批量訂單情形。隨著訂單進(jìn)一步增多，遺傳算法收斂速度得不到保證，此時(shí)完全采用啟發(fā)式規(guī)則選擇存車線。

企業(yè)實(shí)際生產(chǎn)中往往是隨機(jī)選擇存車線，因此另外定義一種隨機(jī)選擇存車線的規(guī)則，用于實(shí)驗(yàn)的數(shù)據(jù)對(duì)比。隨機(jī)規(guī)則在車廂進(jìn)行入庫(kù)操作時(shí)產(chǎn)生一個(gè)隨機(jī)數(shù)，根據(jù)隨機(jī)數(shù)選擇軌道，如果該軌道的容量已滿，則重新確定隨機(jī)軌道。

3 啟發(fā)式規(guī)則設(shè)計(jì)

窮舉算法和遺傳算法在此不再贅述，僅說(shuō)明采用的啟發(fā)式的調(diào)車規(guī)則(heuristic marshalling rule, HMR)。

HMR按順序分為5個(gè)步驟，每個(gè)步驟對(duì)應(yīng)一條選擇規(guī)則。當(dāng)車廂Ci,j到達(dá)交車線時(shí)，對(duì)5條規(guī)則依次進(jìn)行判定，如當(dāng)前規(guī)則可找到Ci,j的存放軌道，則HMR結(jié)束；否則進(jìn)入下一條規(guī)則，直到找到Ci,j的存放軌道結(jié)束。

HMR具體規(guī)則如下：

(1)規(guī)則1。遍歷當(dāng)前所有具有空閑位置的軌道，在其排在最后的車廂中尋找k

圖5 規(guī)則1示例Fig.5 Example of rule 1

(2)規(guī)則2。尋找沒有任何車廂的空軌道，如果有多條空軌道，則優(yōu)先進(jìn)入靠近暫存軌道Qbuffer的軌道。如沒有空軌道，則進(jìn)入規(guī)則3。

(3)規(guī)則3。遍歷當(dāng)前所有具有空閑位置的軌道，在有空閑位置的軌道最后的車廂中尋找同列車車廂Ci,j+1，如有存在Ci,j+1，則選擇其所在軌道；如不存在，則進(jìn)入規(guī)則4。假定車廂C1,3到達(dá)時(shí)，Q1上的最后車廂為C1,4，剛好是C1,3的后一節(jié)車廂，那么應(yīng)該進(jìn)入Q1，如圖6所示。

圖6 規(guī)則3示例Fig.6 Example of rule 3

(4)規(guī)則4。遍歷當(dāng)前所有具有空閑位置的軌道，尋找可與Ci,j組車且滿足k

圖7 規(guī)則4示例Fig.7 Example of rule 4

(5)規(guī)則5。針對(duì)滿足規(guī)則4優(yōu)劣值條件的多條軌道，因?yàn)榭拷鼤捍孳壍繯buffer的軌道調(diào)度所需的距離較短，所以靠近暫存軌道Qbuffer的軌道優(yōu)先。

上述HMR的5條規(guī)則的設(shè)計(jì)思路是：規(guī)則1盡量按照編組順序存車，以最小化組車時(shí)所需的調(diào)車數(shù)為目標(biāo)，形成軌道的車廂順序。規(guī)則2的思路是，當(dāng)無(wú)法按照編組順序存車時(shí)，將車廂存入空軌道，目的同樣是盡量減少調(diào)車。如果已經(jīng)沒有空軌道，那么為了保證最少的調(diào)車，設(shè)計(jì)了基于貪婪算法的規(guī)則4和規(guī)則5，保證每一步都是當(dāng)前情況下的局部最優(yōu)。由于貪婪算法專注于局部最優(yōu)，可能會(huì)導(dǎo)致整體優(yōu)化效果較差，因此設(shè)計(jì)了規(guī)則3對(duì)貪婪算法進(jìn)行修正，優(yōu)先保證相鄰車廂的相鄰存放。

定義沒有規(guī)則3即只有規(guī)則1、規(guī)則2、規(guī)則4、規(guī)則5的調(diào)車方案為貪婪規(guī)則(greedy marshalling rule, GMR)。通過(guò)實(shí)驗(yàn)對(duì)比HMR和GMR的優(yōu)劣性，利用幾組實(shí)驗(yàn)和隨機(jī)算法、遺傳算法、窮舉算法進(jìn)行對(duì)比，證明HMR能夠在短時(shí)間求得較為優(yōu)秀的解。

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

根據(jù)某動(dòng)車生產(chǎn)企業(yè)的實(shí)際情形，軌道長(zhǎng)度為130 m，車廂長(zhǎng)度為16 m，每條軌道最多容納8節(jié)車廂。每種列車也由8節(jié)車廂組成，可在一條軌道內(nèi)完成組車。針對(duì)不同的訂單批量設(shè)計(jì)3組實(shí)驗(yàn)。實(shí)驗(yàn)考慮了列車種類，同一種類列車的相同編號(hào)車廂可以替代使用。其中，小批量訂單只針對(duì)1種列車，中批量針對(duì)2種列車，大批量針對(duì)3種列車。

4.1 小批量訂單分析

小批量實(shí)驗(yàn)假定車間內(nèi)有2條可用軌道，即Qt∈{Q1，Q2}。小批量實(shí)驗(yàn)的假定生產(chǎn)任務(wù)為1種列車，生成該種列車的10輛列車訂單。每輛列車由8節(jié)車廂組成，同編號(hào)車廂可以互換。假定車廂到達(dá)交車線順序隨機(jī)，對(duì)比驗(yàn)證HMR和GMR的優(yōu)劣。

式中，Si為車廂i運(yùn)行的距離；n為車廂數(shù)。

實(shí)驗(yàn)結(jié)果如圖8所示，HMR和GMR明顯優(yōu)于隨機(jī)規(guī)則的實(shí)驗(yàn)結(jié)果；相比于窮舉算法，HMR和GMR均能夠求出較優(yōu)的結(jié)果；GMR的結(jié)果有時(shí)會(huì)有較大的偏差，而HMR的結(jié)果相對(duì)于GMR更穩(wěn)定。GMR、HMR、隨機(jī)規(guī)則與窮舉算法得出的最優(yōu)解如表1、表2所示。

圖8 4種規(guī)則的對(duì)比(小批量)Fig.8 Comparison of 4 rules(small batch)

窮舉算法GMRHMR隨機(jī)規(guī)則平均距離433535516840距離標(biāo)準(zhǔn)差461079887

表2 3種規(guī)則的比較(小批量)

根據(jù)小批量生產(chǎn)計(jì)劃的實(shí)驗(yàn)分析結(jié)果可知，在小批量生產(chǎn)計(jì)劃的條件下，HMR和GMR一般能得出相對(duì)較優(yōu)的解，實(shí)驗(yàn)結(jié)果比較穩(wěn)定，但在個(gè)別情況下會(huì)出現(xiàn)一些較大誤差，且HMR的處理結(jié)果優(yōu)于GMR的處理結(jié)果。

4.2 中批量訂單分析

中批量實(shí)驗(yàn)定義車間內(nèi)有3條可用軌道，即Qt∈{Q1，Q2，Q3}。本組實(shí)驗(yàn)需生產(chǎn)2種列車，每種列車均有10輛列車，每輛列車有8個(gè)車廂。因此中批量訂單實(shí)驗(yàn)共存在(2×8×10)！=160！種情形，顯然無(wú)法采用窮舉算法求解，所以采用遺傳算法作為參照。

如圖9可知，HMR和GMR在大部分的情況下是優(yōu)于其他規(guī)則的。相對(duì)于隨機(jī)規(guī)則，HMR和GMR在大部分情況下能夠極大縮短調(diào)度距離；HMR和GMR在大部分分情況下優(yōu)于遺傳算法(GA)，充分表明了啟發(fā)式規(guī)則的可行性。

圖9 4種規(guī)則的對(duì)比(中批量)Fig.9 Comparison of 4 rules (middle batch)

表3證明了HMR和GMR的可行性。HMR和GMR的調(diào)度距離均值均小于隨機(jī)規(guī)則的調(diào)度距離均值，但GMR的方差遠(yuǎn)大于其他2種規(guī)則的方差，表明GMR的結(jié)果穩(wěn)定性較差，容易得出較大偏差的結(jié)果，HMR的結(jié)果略優(yōu)于GMR的結(jié)果。

表3 4種規(guī)則的比較(中批量)

本文遺傳算法的解碼過(guò)程采用離散事件仿真的方式對(duì)編碼進(jìn)行評(píng)價(jià)，為節(jié)約計(jì)算時(shí)間，設(shè)定最大代數(shù)為10，種群規(guī)模為20。為了彌補(bǔ)搜索范圍過(guò)小的劣勢(shì)，設(shè)計(jì)了補(bǔ)充實(shí)驗(yàn)。

補(bǔ)充實(shí)驗(yàn)采用“HMR+GA”的方式，先將HMR計(jì)算出的結(jié)果作為遺傳算法的初始解，然后利用遺傳算法進(jìn)行運(yùn)算，統(tǒng)計(jì)每節(jié)車廂的平均運(yùn)行距離。對(duì)比兩種結(jié)果的差距，差距較小則說(shuō)明HMR結(jié)果與最優(yōu)解差距較小，反之則說(shuō)明差距較大。計(jì)算結(jié)果如圖10所示。由圖10可知，雖然“HMR+GA”能進(jìn)一步獲得比HMR結(jié)果更好的解，但僅有第4、第5次實(shí)驗(yàn)的優(yōu)化效果能夠達(dá)到10%，其他實(shí)驗(yàn)的結(jié)果優(yōu)化效果均在5%以下，平均優(yōu)化效果為2.76%，這說(shuō)明HMR可以快速找到近優(yōu)解。

圖10 補(bǔ)充實(shí)驗(yàn)結(jié)果Fig.10 Supplementary experiment results

4.3 大批量訂單分析

對(duì)于大批量訂單，窮舉算法和遺傳算法都很難在短時(shí)間獲得較優(yōu)解，因此采用 “HMR+GA”進(jìn)行對(duì)比。

大批量生產(chǎn)計(jì)劃實(shí)驗(yàn)包含3種列車，每種列車均有10輛列車，每輛列車有8個(gè)車廂。大批量實(shí)驗(yàn)定義車間內(nèi)有5條可用軌道，即Qt∈{Q1，Q2，Q3，Q4，Q5}。實(shí)驗(yàn)結(jié)果如圖11所示。由圖11可以看出，HMR、GMR和HMR+GA對(duì)于隨機(jī)規(guī)則在優(yōu)化距離上都存在顯著優(yōu)勢(shì)。10次實(shí)驗(yàn)中，HMR+GA的結(jié)果與HMR的結(jié)果完全相同，二者結(jié)果略優(yōu)于GMR，但HMR+GA的計(jì)算時(shí)間平均為19 min55 s ，HMR的計(jì)算時(shí)間僅為13.7 s。這幾種方案的均值方差如表4所示，HMR和GMR的實(shí)驗(yàn)結(jié)果明顯優(yōu)于隨機(jī)規(guī)則的實(shí)驗(yàn)結(jié)果，HMR結(jié)果的穩(wěn)定性相對(duì)于其他方法有明顯的優(yōu)勢(shì)。

圖11 大批量實(shí)驗(yàn)結(jié)果對(duì)比Fig.11 Comparison of large batch experimental results

平均距離距離標(biāo)準(zhǔn)差GMR58756HMR56541隨機(jī)規(guī)則89647

5 結(jié)論

動(dòng)車車廂組車過(guò)程是一個(gè)高動(dòng)態(tài)和隨機(jī)的過(guò)程，難以建立數(shù)學(xué)模型并求解，為此建立了離散事件仿真模型，并針對(duì)該問題設(shè)計(jì)了啟發(fā)式規(guī)則。仿真實(shí)驗(yàn)表明，本文提出的HMR規(guī)則針對(duì)大、中、小三種批量，都能夠快速找到近優(yōu)解。HMR規(guī)則原理非常簡(jiǎn)單，易于實(shí)施，節(jié)約組車成本。