郭佳鵬 趙 寧 吳秀麗

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

0 引言

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

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

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

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

1 問題描述

我國的動車生產(chǎn)中，由于工藝等條件的限制，生產(chǎn)順序并非是列車的出廠順序，所以車廂順序需要在調(diào)車線進(jìn)行調(diào)整。該調(diào)整過程可描述如下：假設(shè)軌道中的車廂服從先入先出原則，第t個存車軌道為Qt，第i輛列車的第j節(jié)車廂表示為Ci,j，則圖1所示的存車軌道Q1、Q2的車廂儲存狀態(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)入存車軌道時，選擇有存儲空間的軌道，并將其存儲在第一個位置。在上述存儲狀態(tài)的基礎(chǔ)上，通過中間軌道調(diào)換存車軌道和存儲位置，但每條軌道需滿足先入先出的原則。例如圖1中的C1,3離開Q1之后，C1,6才能離開。離開的車廂再進(jìn)入隊列時和新車廂進(jìn)入存車軌道方式相同，只能排在C1,7或C1,1之前。最終通過上述方式在某一存車軌道按順序組合目標(biāo)列車的全部車廂，即實現(xiàn)組車。假定QD為出口軌道，對應(yīng)的列車i有n節(jié)車廂，其最終組車狀態(tài)的車廂順序為(Ci,1,Ci,2, …,Ci,n)。

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

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

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

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

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

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

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

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

2.1 模型邏輯

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

圖2 軌道布置Fig.2 Track layout

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

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

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

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

2.2 實驗設(shè)計

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

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

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

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

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

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

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

HMR按順序分為5個步驟，每個步驟對應(yīng)一條選擇規(guī)則。當(dāng)車廂Ci,j到達(dá)交車線時，對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á)時，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。針對滿足規(guī)則4優(yōu)劣值條件的多條軌道，因為靠近暫存軌道Qbuffer的軌道調(diào)度所需的距離較短，所以靠近暫存軌道Qbuffer的軌道優(yōu)先。

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

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

4 實驗分析

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

4.1 小批量訂單分析

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

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

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

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

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

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

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

4.2 中批量訂單分析

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

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

圖9 4種規(guī)則的對比(中批量)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ī)則的比較(中批量)

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

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

圖10 補(bǔ)充實驗結(jié)果Fig.10 Supplementary experiment results

4.3 大批量訂單分析

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

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

圖11 大批量實驗結(jié)果對比Fig.11 Comparison of large batch experimental results

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

5 結(jié)論

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