基于動態(tài)規(guī)劃的鐵路轉(zhuǎn)運(yùn)站散裝物資對位卸載作業(yè)優(yōu)化算法

謝得卉，陳 曦，劉振元，樊垚堤，唐淑賢

（1.華中科技大學(xué) 人工智能與自動化學(xué)院，湖北 武漢 430074；2.雅礱江流域水電開發(fā)有限公司，四川 成都 610051）

0 引言

我國大型水電工程一般位于地勢階梯交界地帶，建設(shè)的地理環(huán)境特殊，交通極為不便。同時，水電工程建設(shè)需要的物資種類多、數(shù)量大、來源廣，為了保障物資供應(yīng)，通常會在火車站附近且毗鄰施工現(xiàn)場處設(shè)置鐵路轉(zhuǎn)運(yùn)站以負(fù)責(zé)工程物資的存放與轉(zhuǎn)運(yùn)。在鐵路轉(zhuǎn)運(yùn)站中，水泥、粉煤灰等散裝物料是主要的存儲物資，需要存儲到散裝物資儲罐中。鐵路轉(zhuǎn)運(yùn)站與火車站由鐵路專用線連接，鐵路轉(zhuǎn)運(yùn)站內(nèi)有若干條軌道，軌道沿線放置了不同的散裝物資儲罐，其設(shè)施布局如圖1所示。

圖1 鐵路轉(zhuǎn)運(yùn)站設(shè)施布局圖

鐵路轉(zhuǎn)運(yùn)站散裝物資進(jìn)場的具體工作流程是運(yùn)送物資的貨運(yùn)列車到達(dá)火車站進(jìn)行列車編組，編組完成后再通過鐵路專用線將貨車組牽引至鐵路轉(zhuǎn)運(yùn)站，在轉(zhuǎn)運(yùn)站將貨車組與散裝物資儲罐分批對位后進(jìn)行物資逐批卸載存儲，卸載完成后將空貨車運(yùn)回火車站。

由于鐵路線路緊張、運(yùn)輸物資數(shù)量大等，鐵路轉(zhuǎn)運(yùn)站的散裝物資進(jìn)場物流作業(yè)往往會發(fā)生延時，延時過長不僅會影響轉(zhuǎn)運(yùn)站的運(yùn)行效率，也會給轉(zhuǎn)運(yùn)站帶來較高的延時費(fèi)用。貨車組對位卸載是散裝物資進(jìn)場物流中的重要一環(huán)，確定合適的卸載方案減少卸載時長，可以降低延時費(fèi)用，同時提高鐵路轉(zhuǎn)運(yùn)站的運(yùn)行效率，優(yōu)化散裝物資進(jìn)場物流作業(yè)。

鐵路轉(zhuǎn)運(yùn)站是一類貨物轉(zhuǎn)運(yùn)系統(tǒng)，同時具有倉儲系統(tǒng)和轉(zhuǎn)運(yùn)系統(tǒng)的特點(diǎn)，國內(nèi)外學(xué)者對貨物轉(zhuǎn)運(yùn)系統(tǒng)的研究由來已久，貨物裝卸作為轉(zhuǎn)運(yùn)系統(tǒng)堆場作業(yè)調(diào)度中的重要環(huán)節(jié)，目前已取得了一定的研究成果。

Zhou，等[1]建立了混合整數(shù)規(guī)劃模型來優(yōu)化堆場起重機(jī)和運(yùn)輸車輛的裝卸作業(yè)，并提出了兩階段啟發(fā)式算法來解決該問題，提高了堆場的作業(yè)效率。He，等[2]建立了兩階段隨機(jī)規(guī)劃模型以最小化集裝箱在指定堆場區(qū)域沒有可用空擋的風(fēng)險，并且最小化總運(yùn)輸距離，以提高集裝箱碼頭的裝卸效率。Hu，等[3]通過對進(jìn)港集裝箱集群和出港集裝箱集群的預(yù)分配，建立了多目標(biāo)數(shù)學(xué)規(guī)劃模型，以求最小化空載運(yùn)輸距離和多船集裝箱裝卸的最短完成時間。杜建平[4]對港口煤炭運(yùn)輸?shù)闹修D(zhuǎn)作業(yè)流程包括港口煤炭卸車作業(yè)流程進(jìn)行了詳細(xì)分析，給出了港口煤炭中轉(zhuǎn)作業(yè)組織優(yōu)化方法。李孟斌[5]針對如何提高自動化集裝箱碼頭裝卸船作業(yè)效率展開研究，以最小化堆場和船舶翻箱量為優(yōu)化目標(biāo)，建立了自動化集裝箱碼頭裝船排箱問題模型。林燕[6]以完成給定裝卸作業(yè)任務(wù)的最短時間為優(yōu)化目標(biāo)，設(shè)計(jì)了以低架橋分配小車作為調(diào)度中心的啟發(fā)式算法。李坤[7]研究了具有代表性的集裝箱裝載計(jì)劃問題以及卸載集裝箱車輛調(diào)度與堆場空間分配問題，建立了相應(yīng)的數(shù)學(xué)規(guī)劃模型。陶莎，等[8]研究基于關(guān)鍵資源優(yōu)先的單元化“裝卸、搬運(yùn)、裝卸”三級作業(yè)鏈的調(diào)度問題,在關(guān)鍵資源優(yōu)先的條件下,將兩非關(guān)鍵各作業(yè)級的調(diào)度問題分別轉(zhuǎn)化為最小單位流問題，并進(jìn)一步提出三級裝卸搬運(yùn)的分時協(xié)調(diào)策略來求解大規(guī)模問題。

綜上所述，目前大多數(shù)研究集中在集裝箱碼頭的裝卸問題上，對鐵路轉(zhuǎn)運(yùn)堆場作業(yè)中的裝卸問題關(guān)注較少。雖然二者具有一定相似性和互通性，但在作業(yè)流程上還存在差異。本文以鐵路轉(zhuǎn)運(yùn)站散裝物資進(jìn)場物流作業(yè)為背景，研究轉(zhuǎn)運(yùn)站內(nèi)裝載散裝物資貨車組的對位卸載問題，建立了該問題的0-1整數(shù)規(guī)劃模型，證明該問題是個NP 完全問題，并采用基于動態(tài)規(guī)劃的啟發(fā)式算法進(jìn)行求解，進(jìn)行了相應(yīng)的計(jì)算實(shí)驗(yàn)。

1 問題描述與模型建立

1.1 問題描述

裝有多種散裝物資的貨運(yùn)列車分別到達(dá)火車站后對其進(jìn)行重新組合，分組后得到的貨車組由機(jī)車牽引至鐵路轉(zhuǎn)運(yùn)站，在轉(zhuǎn)運(yùn)站內(nèi)以貨車組為單位將散裝物資對位卸載到散裝物資儲罐。其中，貨車是裝載物資的最小實(shí)體單元，貨運(yùn)列車和貨車組均由裝載散裝物資的多輛貨車構(gòu)成。

鐵路轉(zhuǎn)運(yùn)站內(nèi)散裝物資儲罐位置是固定的，因卸載區(qū)域的空間有限以及卸載設(shè)備的數(shù)量限制，且每輛貨車只裝載一種物資，故一個儲罐只能進(jìn)行一輛貨車的對位卸載。若貨車組裝載物資順序與儲罐排布順序不一致會增加卸載時長，為了提高貨車組的對位卸載效率，應(yīng)盡量將可以同時卸載的貨車連續(xù)排列，如圖2所示。

圖2 貨車組排序卸載圖

一次對位只能完成貨車組中部分貨車的卸載，要完成所有貨車的物資卸載則需要進(jìn)行多次對位，故整個貨車組的卸載作業(yè)要分多個卸載批次來完成。一個卸載批次內(nèi)的貨車可以同時卸載，每個卸載批次對應(yīng)一個卸載方案，各卸載批次按順序卸載。一個卸載方案包括各物資的貨車數(shù)量和卸載時長，卸載方案的舉例見表1。

表1 卸載方案舉例

因此，整個貨車組的卸載方案是由各卸載批次的卸載方案組合構(gòu)成，卸載方案來源于由歷史作業(yè)記錄整理好的卸載方案庫。

根據(jù)上述問題描述，給出以下假設(shè)條件：

（1）鐵路轉(zhuǎn)運(yùn)站的卸載線每次只能進(jìn)行一個貨車組的對位卸載，且貨車組的卸載批次依次進(jìn)行，不能同時卸載多個批次。

（2）假設(shè)儲罐的空間足夠大，不存在空間不足使卸載受阻的情況。

（3）假設(shè)每批次卸載時卸載設(shè)備足夠，無設(shè)備數(shù)量約束。

1.2 模型建立

根據(jù)上述問題描述及假設(shè)，以最短卸載時長為目標(biāo)，建立0-1整數(shù)規(guī)劃模型。

假設(shè)現(xiàn)有J 個可選的卸載方案，第j 卸載方案的卸載時長為tj，共有M種物資，方案j中物資m的卸載貨車數(shù)量為ajm，貨車組中各物資的貨車數(shù)已知，分別為bm，將貨車組分為I 個批次卸載(I 是貨車組中各物資單獨(dú)卸載時的最小卸載批次數(shù)之和)，xij為0-1 變量，第i個批次選擇方案j時xij=1,否則為0。建立如下模型：

其中，式（1）表示目標(biāo)函數(shù)為最小化卸載時長，式（2）表示每個批次只能選擇一個卸載方案，式（3）表示整個貨車組選擇的卸載方案組合滿足貨車組內(nèi)各物資的貨車數(shù)要求，即貨車組內(nèi)的所有裝載物資的貨車均完成卸載。

1.3 復(fù)雜度證明

鐵路轉(zhuǎn)運(yùn)站散裝物資的對位卸載問題是離散最優(yōu)化問題，為證明其計(jì)算復(fù)雜度，需將一個已知的NP完全問題在多項(xiàng)式時間內(nèi)歸約到它，這樣便可證明該問題至少和這個已知的NP完全問題一樣難[9]。

接下來將借助資源受限的廣義指派問題來證明鐵路轉(zhuǎn)運(yùn)站散裝物資對位卸載問題的NP完全性，資源受限廣義指派問題目前已被證明是NP 完全問題[10-11]。

資源受限廣義指派問題描述為：假設(shè)有n個任務(wù)需要指派給m個機(jī)器，cij表示任務(wù)i指派給機(jī)器j時所需的成本費(fèi)用，表示任務(wù)i 指派給機(jī)器j 時的資源消耗，表示分配給機(jī)器j 的固定資源，為0-1 變量表示任務(wù)i指派給機(jī)器j完成，否則為0。要求每個任務(wù)只能由一臺機(jī)器完成，每臺機(jī)器的資源消耗量不能超過其固定資源數(shù)量，建立數(shù)學(xué)模型如下：

其中式（4）表示目標(biāo)函數(shù)為最小化成本費(fèi)用，式（5）表示每個任務(wù)只能選擇一臺機(jī)器來完成，式（6）表示每臺機(jī)器的資源消耗量不超過其固定分配量。下面將該問題進(jìn)行轉(zhuǎn)換，設(shè)N={1,2,…,n}表示任務(wù)集合，M={1,2,…,m}表示機(jī)器集合,轉(zhuǎn)換如下：

其中，式（8）中的yj為松弛變量，為零系數(shù)。

顯然，該轉(zhuǎn)換可在多項(xiàng)式時間內(nèi)完成，由此可知資源受限廣義指派問題可歸約到鐵路轉(zhuǎn)運(yùn)站散裝物資的對位卸載問題，則該卸載問題至少和資源受限廣義指派問題一樣難，是個NP完全問題。

2 基于動態(tài)規(guī)劃的啟發(fā)式算法

2.1 動態(tài)規(guī)劃建模

求解鐵路轉(zhuǎn)運(yùn)站散裝物資對位卸載問題的前提是已知一個貨車組的組成，即裝載各種物資的貨車數(shù)已知，該問題求解可分為兩種情況：

（1）貨車組內(nèi)只有一種物資時，可根據(jù)該貨車組內(nèi)該物資的貨車數(shù)和只卸載該物資的卸載方案確定最優(yōu)卸載方案組合。

（2）貨車組內(nèi)有多種物資時，其最優(yōu)卸載方案組合可根據(jù)動態(tài)規(guī)劃逆序解法求解。

以某待卸載的貨車組為例，該貨車組有4輛貨車的A 物資，3 輛貨車的B 物資，其有效卸載方案見表2。

表2 有效卸載方案表

根據(jù)動態(tài)規(guī)劃的基本原理和基本方程，對該卸載問題進(jìn)行動態(tài)規(guī)劃逆序解法建模求解[12-13]，建立模型如下：

（1）階段。將該卸載問題分為P 個階段，每個階段確定一個卸載方案，階段數(shù)P為待卸載貨車組中各物資單獨(dú)卸載時的最小卸載批次數(shù)之和。

在此案例中，根據(jù)已有的有效卸載方案表，物資A單獨(dú)卸載時要分為兩個批次，由卸載方案3和卸載方案4組成，物資B單獨(dú)卸載時選擇卸載方案5，即一個批次便可完成卸載。故該案例貨車組的階段總數(shù)為3。

（2）狀態(tài)變量。Sp=(rqp1,rqp2,…,rqpMˉ)T，狀態(tài)變量Sp是一個多維變量，表示p 階段開始時，貨車組中各物資剩余的貨車數(shù)，rqpm表示第p階段開始時，物資m的剩余貨車數(shù)，其中m ∈M，表示物資種類數(shù)。

上述案例采用逆序解法，故起始狀態(tài)已知，則第4 階段的狀態(tài)變量S4=(0,0)T，第1 階段的狀態(tài)變量S1=(4,3)T。

（3）決策變量。決策變量upk表示第p 階段選擇卸載方案k。

允許決策集合Dp(Sp+1)表示在已知狀態(tài)Sp+1時，第p 階段允許的決策集合，即允許的卸載方案中，各物資貨車數(shù)不能超過貨車組內(nèi)初始的貨車數(shù)與第p+1階段狀態(tài)中剩余對應(yīng)貨車數(shù)的差值。其中，rq(p+1)m表示第p+1 階段物資m 剩余的貨車數(shù),表示待卸載貨車組中物資m的貨車總數(shù)。

在該案例中，若第2階段選擇了方案2，則在第2階段對物資A的允許決策集合為：

（4）狀態(tài)轉(zhuǎn)移方程。Sp+1=Sp-(qp1,qp2,…,qpMˉ)Tup，其中，(qp1,qp2,…,qpMˉ)T是被選中的卸載方案中各物資的貨車數(shù)列向量。

在該案例中，若在第1階段選擇了卸載方案4，則S2=S1-(q1A,q1B)Tu1k=(4,3)T-(1,0)T=(3,3)T。

（5）階段指標(biāo)函數(shù)。階段指標(biāo)函數(shù)vp(Sp，up)表示第p 階段，在狀態(tài)Sp下，采用決策up的卸載方案時消耗的卸載時長。

此案例中，若第3 階段選擇卸載方案1，則v3(S3，u31)=100。

（6）最優(yōu)指標(biāo)函數(shù)。最優(yōu)指標(biāo)函數(shù)fp(Sp)表示從第p（p=P，P-1,...,2,1）階段開始，貨車組各物資的剩余貨車數(shù)狀態(tài)為Sp的情況下，到最后一個階段的最小卸載總時長。f1(S1)為整體最優(yōu)函數(shù)值。

則可得到動態(tài)規(guī)劃的逆序遞推方程：

表3 P=3求解結(jié)果表

表4 P=2求解結(jié)果表

從表3-表5 可知，該案例求出的最短卸載時長為160min，分為兩個批次卸載，最優(yōu)卸載方案組合為方案1和方案6。

表5 P=1求解結(jié)果表

2.2 啟發(fā)式規(guī)則

從2.1 節(jié)的案例可以看出，在計(jì)算進(jìn)行到第1 階段時存在較多無效計(jì)算結(jié)果，在階段數(shù)比較多時，這些無效的計(jì)算大大降低了算法效率，增加了計(jì)算時間。為了減少無效計(jì)算，提高計(jì)算效率，引入以下啟發(fā)式規(guī)則：

（1）對每階段中每個狀態(tài)下允許決策的卸載方案進(jìn)行判斷，若該狀態(tài)下的允許決策方案不存在組合卸載方案，則對該狀態(tài)下的各物資做單獨(dú)卸載處理，下階段該狀態(tài)便不再參與計(jì)算。

（2）對每階段中每個狀態(tài)的允許決策卸載方案按物資種類數(shù)分組，按種類數(shù)從多到少分組計(jì)算，若種類數(shù)最多的組中卸載方案數(shù)小于10，再對下一分組進(jìn)行計(jì)算，否則只計(jì)算物資種類數(shù)最多的一組。

（3）若計(jì)算還未進(jìn)行到第1 階段時，便在某個階段出現(xiàn)整個對位卸載問題可行解，則對該階段中其他狀態(tài)進(jìn)行計(jì)算，若存在某個狀態(tài)下的階段卸載時長比已出現(xiàn)的可行解卸載時長小60min及以上，則再進(jìn)行最多一個階段的計(jì)算，否則終止計(jì)算。

現(xiàn)假設(shè)卸載方案庫中有最多三種物資可一起卸載的方案，則該啟發(fā)式算法流程如圖3所示。

圖3 基于動態(tài)規(guī)劃的啟發(fā)式算法流程圖

3 應(yīng)用案例

3.1 案例背景

計(jì)算案例中的有效卸載方案來源于孔妍[14]和唐淑賢[15]的整理，共計(jì)160 個。160 個有效方案是兩篇文獻(xiàn)以某流域水電開發(fā)工程中鐵路轉(zhuǎn)運(yùn)站某年1 月至6月工作月報為依據(jù)，再以轉(zhuǎn)運(yùn)站半年內(nèi)每種組合方案的實(shí)際卸載、對位時長的平均值為基準(zhǔn)，最終經(jīng)轉(zhuǎn)運(yùn)站相關(guān)工作人員根據(jù)經(jīng)驗(yàn)適當(dāng)調(diào)整后得到。

根據(jù)需要卸載的貨車數(shù)量將貨車組分為四個規(guī)模，規(guī)模1 至規(guī)模4 依次為：(0,10],(10,20],(20,30],(30,40]，每個規(guī)模下各設(shè)計(jì)54 個案例，共計(jì)216 個案例，對其采用本文提出的基于動態(tài)規(guī)劃的啟發(fā)式算法進(jìn)行求解。

計(jì)算案例的數(shù)據(jù)說明如下：

（1）鐵路轉(zhuǎn)運(yùn)站用貨車運(yùn)輸?shù)纳⒀b物資有6 種，分別以U,V,W,X,Y,Z編號。

（2）鐵路轉(zhuǎn)運(yùn)站內(nèi)的機(jī)車最大可牽引35 輛滿載的貨車，故計(jì)算案例中貨車組最大貨車數(shù)量為40。

3.2 案例求解及分析

根據(jù)本文第1 節(jié)建立的數(shù)學(xué)模型以及第2 節(jié)提出的動態(tài)規(guī)劃方法，分別采用動態(tài)規(guī)劃、基于動態(tài)規(guī)劃的啟發(fā)式算法求解該問題的216 個案例并作對比分析。

每個案例均給出貨車組中6種物資的貨車數(shù)量，各算法根據(jù)給出的各物資數(shù)量，求解出卸載方案組合，取運(yùn)行時間進(jìn)行計(jì)算效率對比，各算法的計(jì)算效率見表6。

通過表6可以看出，加入啟發(fā)式規(guī)則的動態(tài)規(guī)劃計(jì)算效率大大提高，但是啟發(fā)式動態(tài)規(guī)劃算法得到的是滿意解，不一定為最優(yōu)解。為了確定基于動態(tài)規(guī)劃的啟發(fā)式算法的質(zhì)量，采用DR（Difference Ra-tio，偏差率）指標(biāo)來表征其解的質(zhì)量，它代表當(dāng)前解與最優(yōu)解之間的距離，計(jì)算方式見式（10）。

表6 各算法計(jì)算效率表

對于每一個案例來說，Cbest是最優(yōu)目標(biāo)值，即最短卸載時長,用動態(tài)規(guī)劃方法求得；C 是基于動態(tài)規(guī)劃的啟發(fā)式算法求解出的卸載時長。DR越小，說明基于動態(tài)規(guī)劃的啟發(fā)式算法的解越接近，即求解的結(jié)果越好?；趧討B(tài)規(guī)劃的啟發(fā)式算法在各規(guī)模下的算法質(zhì)量見表7。

表7 基于動態(tài)規(guī)劃的啟發(fā)式算法質(zhì)量表

從表7可以看出，在規(guī)模1和規(guī)模2中，該啟發(fā)式算法的DR為零，規(guī)模3和規(guī)模4下DR的平均值也很小，說明該啟發(fā)式算法在大多數(shù)情況下的求解結(jié)果就是最優(yōu)值，即使出現(xiàn)偏差，與最優(yōu)值也很接近，且DR標(biāo)準(zhǔn)差很小，即該算法比較穩(wěn)定。

4 結(jié)語

本文以大型水電工程鐵路轉(zhuǎn)運(yùn)站中的散裝物資進(jìn)場物流作業(yè)為背景，對該物流作業(yè)中的對位卸載問題進(jìn)行分析，建立了相應(yīng)的整數(shù)線性規(guī)劃模型，并證明了該問題是個NP完全問題，再對該問題進(jìn)行動態(tài)規(guī)劃建模，采用基于動態(tài)規(guī)劃的啟發(fā)式算法進(jìn)行求解。

通過對案例進(jìn)行計(jì)算實(shí)驗(yàn)可知，基于動態(tài)規(guī)劃的啟發(fā)式算法計(jì)算效率大大提高，即使在卸載規(guī)模較大的情況下，平均計(jì)算時間也不超過1s，同時算法質(zhì)量也得到了很好的保證。