基于動態規劃的鐵路轉運站散裝物資對位卸載作業優化算法

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

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

0 引言

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

圖1 鐵路轉運站設施布局圖

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

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

鐵路轉運站是一類貨物轉運系統，同時具有倉儲系統和轉運系統的特點，國內外學者對貨物轉運系統的研究由來已久，貨物裝卸作為轉運系統堆場作業調度中的重要環節，目前已取得了一定的研究成果。

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

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

1 問題描述與模型建立

1.1 問題描述

裝有多種散裝物資的貨運列車分別到達火車站后對其進行重新組合，分組后得到的貨車組由機車牽引至鐵路轉運站，在轉運站內以貨車組為單位將散裝物資對位卸載到散裝物資儲罐。其中，貨車是裝載物資的最小實體單元，貨運列車和貨車組均由裝載散裝物資的多輛貨車構成。

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

圖2 貨車組排序卸載圖

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

表1 卸載方案舉例

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

根據上述問題描述，給出以下假設條件：

（1）鐵路轉運站的卸載線每次只能進行一個貨車組的對位卸載，且貨車組的卸載批次依次進行，不能同時卸載多個批次。

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

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

1.2 模型建立

根據上述問題描述及假設，以最短卸載時長為目標，建立0-1整數規劃模型。

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

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

1.3 復雜度證明

鐵路轉運站散裝物資的對位卸載問題是離散最優化問題，為證明其計算復雜度，需將一個已知的NP完全問題在多項式時間內歸約到它，這樣便可證明該問題至少和這個已知的NP完全問題一樣難[9]。

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

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

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

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

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

2 基于動態規劃的啟發式算法

2.1 動態規劃建模

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

（1）貨車組內只有一種物資時，可根據該貨車組內該物資的貨車數和只卸載該物資的卸載方案確定最優卸載方案組合。

（2）貨車組內有多種物資時，其最優卸載方案組合可根據動態規劃逆序解法求解。

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

表2 有效卸載方案表

根據動態規劃的基本原理和基本方程，對該卸載問題進行動態規劃逆序解法建模求解[12-13]，建立模型如下：

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

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

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

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

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

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

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

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

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

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

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

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

則可得到動態規劃的逆序遞推方程：

表3 P=3求解結果表

表4 P=2求解結果表

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

表5 P=1求解結果表

2.2 啟發式規則

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

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

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

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

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

圖3 基于動態規劃的啟發式算法流程圖

3 應用案例

3.1 案例背景

計算案例中的有效卸載方案來源于孔妍[14]和唐淑賢[15]的整理，共計160 個。160 個有效方案是兩篇文獻以某流域水電開發工程中鐵路轉運站某年1 月至6月工作月報為依據，再以轉運站半年內每種組合方案的實際卸載、對位時長的平均值為基準，最終經轉運站相關工作人員根據經驗適當調整后得到。

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

計算案例的數據說明如下：

（1）鐵路轉運站用貨車運輸的散裝物資有6 種，分別以U,V,W,X,Y,Z編號。

（2）鐵路轉運站內的機車最大可牽引35 輛滿載的貨車，故計算案例中貨車組最大貨車數量為40。

3.2 案例求解及分析

根據本文第1 節建立的數學模型以及第2 節提出的動態規劃方法，分別采用動態規劃、基于動態規劃的啟發式算法求解該問題的216 個案例并作對比分析。

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

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

表6 各算法計算效率表

對于每一個案例來說，Cbest是最優目標值，即最短卸載時長,用動態規劃方法求得；C 是基于動態規劃的啟發式算法求解出的卸載時長。DR越小，說明基于動態規劃的啟發式算法的解越接近，即求解的結果越好。基于動態規劃的啟發式算法在各規模下的算法質量見表7。

表7 基于動態規劃的啟發式算法質量表

從表7可以看出，在規模1和規模2中，該啟發式算法的DR為零，規模3和規模4下DR的平均值也很小，說明該啟發式算法在大多數情況下的求解結果就是最優值，即使出現偏差，與最優值也很接近，且DR標準差很小，即該算法比較穩定。

4 結語

本文以大型水電工程鐵路轉運站中的散裝物資進場物流作業為背景，對該物流作業中的對位卸載問題進行分析，建立了相應的整數線性規劃模型，并證明了該問題是個NP完全問題，再對該問題進行動態規劃建模，采用基于動態規劃的啟發式算法進行求解。

通過對案例進行計算實驗可知，基于動態規劃的啟發式算法計算效率大大提高，即使在卸載規模較大的情況下，平均計算時間也不超過1s，同時算法質量也得到了很好的保證。