基于貪婪禁忌搜索算法的垂岸式堆場出口箱裝船翻箱研究

張艷偉, 姜旎旎, 計三有

(1.武漢理工大學 交通與物流工程學院,湖北 武漢 430063; 2.港口物流技術與裝備教育部工程研究中心,湖北 武漢 430063)

0 引言

堆場作業效率是碼頭作業效率的重要保障，堆場翻箱是當前相關研究的重要熱點。通常出口集裝箱在船舶到港前一個時段內提前集港，由于出口箱堆存計劃受船舶配載信息不確定性影響、出口箱陸續到達堆場的時間點和先后順序具有不確定性等，很難保證出口箱集港堆存狀態完全滿足后續裝船順序要求，裝船時出口箱堆場翻箱無法避免，是制約堆場作業效率的重要瓶頸。

早期研究學者主要考慮順岸式碼頭堆場單貝位限制翻箱問題，不涉及場橋大車移動，以翻箱次數衡量裝船時場橋作業效率，利用分支界定、波束搜索、動態規劃等算法進行求解。隨著單貝位翻箱問題研究日漸成熟，目前非限制翻箱問題成為研究重心。Caserta[1]等證明了集裝箱翻箱問題屬于NP難問題，提出了非限制和限制翻箱兩種數學模型。Expósito等[2]針對限制和非限制集裝箱翻箱問題提出了best-first A*算法求解小算例，設計了一種基于領域特定知識的啟發式算法近似求解提高計算效率。Zehendner等[3]改進了前人提出的集裝箱翻箱模型[1]，提出每個周期中翻箱數量新上界和預處理步驟，將模型中變量數減少65%以上。Expósito等[4]設計了一種基于智能策略的分支定界算法，通過探索底層樹中最有希望的節點對Caserta等[1]提出的模型進行求解。Tanaka等[5]提出一個新的翻箱次數下界，構建了效率更高的分支界定算法。Tanaka等[6]提出一種精確算法解決非限制翻箱問題，設計三種優勢屬性消除搜索樹中不必要節點，改進了分支界定下界。Tricoire等[7]引入新的分支界定下界設計元啟發式框架提高算法運行效率。Q. Zeng等[8]以最小化總翻箱數為目標，建立集裝箱組內集裝箱翻箱模型調整提箱順序，提出五種啟發式算法求解模型。B. G. Zweers等[9]針對預編組和翻箱問題設計一個最優分支界定算法，提出了一種基于規則的貝內集裝箱移動次數估計方法。

綜上所述，關于裝船時翻箱問題研究，主要有數學模型構建、基于分支界定限定翻箱次數的上下界、挖掘啟發式規則等。多數文獻研究對象為順岸式堆場單貝位裝船翻箱問題，且對于場橋作業時間通常按操作次數衡量為定值，較少區分場橋大車行走、吊具平移和起升[10]。非限制翻箱啟發式規則一般針對存在壓箱現象的棧頂集裝箱的多次翻箱。

不同于順岸式碼頭水平搬運車輛進入堆場、場橋線邊裝卸，垂岸式碼頭堆場箱區和場橋大車軌道垂直于岸線布局，不同裝船周期出口箱在海側箱區多貝位混堆，場橋多貝位移動取箱，大車帶箱行走至箱區端部對水平搬運車輛進行裝卸，裝船翻箱具有多貝位翻箱決策特征，問題規模大且需考慮大車移動路徑對作業效率影響等。本文以垂岸式自動化碼頭堆場為研究對象，研究裝船時堆場箱區多貝位翻箱問題，考慮場橋大車多貝位翻箱取箱行走、吊具貝內平移和起升時間，提出棧頂集裝箱非必要翻箱規則，以場橋單箱平均操作時間最小為目標進行優化決策。與現有研究相比，具有以下顯著特點：(1)考慮非必要翻箱對場橋作業時間和次數的影響；(2)設計的非必要翻箱啟發式規則約束少。同時，對多貝位落箱位選擇進行優化減少二次翻箱操作；(3)構建貪婪和禁忌兩階段算法進行求解，算例規模符合自動化碼頭生產實際。

1 垂岸式堆場出口箱裝船翻箱模型

垂岸式堆場出口箱裝船翻箱可以描述為堆場多貝位初始堆存狀態和裝船發箱順序已知的情況下，優化場橋取箱、翻箱操作序列、同時在多個貝位內優化決策翻出集裝箱的落箱位，在當前裝船周期內以盡可能少的操作時間完成海側箱區出口箱裝船，同時控制單次取箱的最大翻箱次數和作業時間，保證裝船作業的流暢性。圖1為多貝位集裝箱堆存狀態示意圖，包括當前擬裝船箱和非當前擬裝船箱，數字表示發箱順序，灰度越深發箱順序越靠前，經處理后每個發箱順序對應一個集裝箱。

圖1 堆場貝位堆存狀態及發箱順序標識

1.1 模型假設條件

(1)集裝箱均為20英尺箱，水平搬運設備數量充足，不考慮場橋等待時間；

(2)一次只考慮一個裝船作業周期擬裝船箱，且裝船過程中無集港箱進入堆場；

(3)一個箱區配置一臺場橋，不考慮滿載和空載區別，場橋路徑為曼哈頓距離。

1.2 符號說明

(1)集合

N為所有集裝箱發箱順序集合N=Npre∪Nnext，其中：Npre為當前擬裝船箱發箱順序集合，Nnext為非當前擬裝船箱發箱順序集合；B為貝位號集合；S為棧號集合；H為層號集合。

(2)參數

(3)變量

Anbshm是0-1變量，第m次操作發箱順序為n的集裝箱位于b貝s列h層時為1，否則為0；xnbshm是0-1變量，場橋第m次操作發箱順序為n的集裝箱落箱位是b貝s列h層時為1，否則為0，若為取箱操作，落箱到AGV上，令xn0s1m=1。

1.3 模型約束及目標函數

目標函數:

(λbb+λss)(|xnbshm+1-Anbshm+1|+|Anbshm+1-xnbshm|))

(1)

約束：

(2)

(3)

(4)

(5)

Anbshm+xnbshm<2,?b∈B,s∈S,h∈H,n∈N

(6)

Anbshm+1=Anbshm(1-xnbmsmhmm),?b∈B,s∈S,h∈H,n∈N

(7)

1≤Mt+1-Mt+1≤UBt+1,?t∈Npre

(8)

(9)

目標函數式(1)表示當前裝船周期場橋單箱平均操作時間最小。式(2)約束單個集裝箱堆放箱位唯一，當前擬裝船箱在M次操作內只會被取走一次。式(3)約束集裝箱不可懸空。式(4)約束在當前裝船周期，擬裝船箱均會裝船。式(5)約束當目標箱位于貝位最上層，直接取箱裝船。式(6)約束擬落箱的箱位為空。式(7)表示集裝箱箱位狀態變化關系。式(8)限制提取目標箱時場橋最大操作次數。式(9)為堆場初始狀態的堵塞率計算公式。

2 基于貪婪禁忌搜索算法模型求解

考慮對當前和非當前所有擬裝船箱進行翻箱及取箱操作，設計貪婪算法完成必要翻箱決策求解，嵌套禁忌搜索算法執行局部非必要翻箱操作，以滿足必要翻箱即時決策，減少當前水平搬運設備等待時間。當最小發箱順序集裝箱位于貝內堆棧頂部時直接提取，否則判斷非必要翻箱次數是否達到上界，若超過上界，對目標箱上的堵塞箱建立移動箱位候選解集，選擇評價函數最小的空箱位依次對堵塞箱進行翻箱操作；若未超過上界，根據非必要翻箱規則構建候選解集，從候選解集選擇不在禁忌表內且優于歷史最優解的解，并更新最優解和禁忌表，達到迭代次數時，更新非必要翻箱次數和評價函數，依次搜索所有當前擬裝船箱，直到所有任務完成，輸出操作序列和操作時間。

2.1 編碼方式

集裝箱裝船發箱及翻箱決策旨在形成優化的裝船時場橋翻箱和取箱操作序列。編碼包括堆場箱位位置及箱位內集裝箱的發箱順序，如表1。其中：箱位位置用坐標(b,s,h)表示，b,s,h分別為箱位所在堆場貝位、貝位內棧和層，貝位為0時，表示集裝箱落箱堆放到AGV上被裝船；n表示箱位內集裝箱的發箱順序，空箱位對應的n為0。

2.2 評估函數與翻箱規則構建

禁忌搜索求解非必要翻箱操作采用式(10)對堆場布局的優劣進行評估，以擴大必要翻箱的解搜索空間。貪婪算法需要場橋在滿足操作時間最短的情況下將目標箱的堵塞箱盡可能翻到不堵塞其余箱的列上，采用式(11)進行評估。

f=βgoodmgood+βemptymempty

(10)

其中，mgood，mempty分別表示能使所翻箱不堵塞其余箱的列數和箱區內空列數。βgood，βempty是各子目標的權重系數，取值范圍為[0,1]，兩者之和為1。

基于STM32的嵌入式遠程視頻監控系統設計………………………………馬躍輝, 冀保峰, 程一淼,等(52)

(11)

f(c)=dif(n,b,s)×OP_Time

(12)

其中，式(11)評價落箱位對后續操作產生的影響，nminbs>n，發箱順序為n的集裝箱不會阻塞b貝s列的集裝箱；nminbs

針對必要翻箱操作設計規則1，針對非必要翻箱操作設計規則2，落箱箱位的選擇遵循貝內優先的原則，以便減少集裝箱取箱時場橋的移動。

規則1目標箱位于最上層時直接取箱裝船；當目標箱不在最上層且非必要翻箱次數達到上界時，將堵塞箱移動到離目標箱和堆場海側最近的可用列上。

規則2目標箱不在最上層、非必要翻箱次數未達到上界，且箱區內存在堵塞箱時，選擇目標箱最近且堵塞率最高的列頂部箱進行翻箱，落箱位選擇離目標箱和堆場海側最近的不堵塞其余箱的列；目標箱不在最上層、非必要翻箱次數未達到上界，且箱區不存在堵塞箱時，選擇目標箱最近且集裝箱最少的列頂部箱進行翻箱，落箱位選擇離目標箱和堆場海側最近的不堵塞其余箱的列。

表1 編碼方式

2.3 禁忌表與終止條件設置

將待操作箱原箱位和擬移入箱位進行交換實現領域移動，是否執行交換決策受模型約束限制。領域集合由原箱位和空箱位組成，無阻塞箱或迭代次數達到最大時停止交換。禁忌對象(nm,b,s,h,bm,sm,hm)表示集裝箱nm在預設迭代次數內不能被分配到箱位(b,s,h)和箱位(bm,nm,hm)。禁忌表為禁忌對象組成的隊列，禁忌長度為問題規模的十分之一。

表2 TG算法與LL-Heuristric(LLH)算法求解結果對比

3 算例實驗

3.1 算法有效性

為驗證算法有效性，選用LL-Heuristric(LLH)算法[10]及算例與本文的TG算法進行對比。Lin[10]提出的啟發式規則考慮了場橋大車行走、吊具起升和吊具平移的速度差異，未考慮非必要翻箱過程，落箱位選擇基于最小化翻箱次數進行評估，目標函數為時間和操作次數的加權和。驗證結果如表2所示，本文算法單箱平均耗時提升17.19%以上，單箱平均操作次數(含翻箱和取箱)較LLH算法多，但增值控制在8%以內。使用Python軟件進行編程求解，普通筆記本電腦運算時間在15s以內，符合碼頭操作需求。

3.2 算法規則對比和適用性分析

垂岸式堆場多貝位非必要翻箱過程與堵塞率和非當前周期集裝箱占比相關。結合垂岸式碼頭箱區實際大小，設定既定箱區為5貝6列2層、8貝10列5層兩種規模，結合碼頭生產實際，堵塞率分別為5%、8%、11%、17%、20%，非當前周期集裝箱占比為5%和10%。每種組合設計100個算例，共計2400個算例。組合規則為規則1、2的組合，包含非必要翻箱過程，規則1不包含非必要翻箱過程，通過與隨機落箱規則對比驗證非必要翻箱過程的合理性和適用性。場橋大車行走、吊具平移、吊具起升速度分別為1.2米/秒、1.7米/秒、0.7米/秒。非必要翻箱操作次數上界設為2次。計算結果如表3。

(1)非必要翻箱過程對必要翻箱過程的作用受箱區規模影響較小。在兩種箱區規模情況下，組合規則和規則1單箱操作時間與單箱操作次數偏差在3%以內，說明非必要翻箱次數上界為2時，規則2對規則1影響不大，規則2具有合理性。

(2)利用本文的翻箱規則進行合理預整理能減少堆場裝船翻箱操作時間和操作次數，并且隨著堵塞率和堆場規模的上升，改進效果越明顯。堆場布局為6列5貝2層時，翻箱操作時間改進比例范圍為1%～9%，翻箱次數改進比例范圍為0%～7%；堆場布局為8列10貝5層時，翻箱操作時間改進比例范圍為17～23%，翻箱次數改進比例范圍為21～26%。堵塞率相同情況下，隨著下一周期集裝箱占比減少，當前周期場橋裝船操作時間和操作次數增加，算法適合于當前周期集裝箱占比不同的堆場翻箱問題。

表3 兩種規模情況下各種規則結果對比

4 結論

針對垂岸式集裝箱碼頭出口箱裝船堆場翻箱，考慮非必要翻箱對場橋作業時間和次數的影響，建立數學模型，提出翻箱規則，設計貪婪禁忌搜索算法，通過與LLH算法對比，驗證模型和翻箱規則的有效性，結合堆場實際規模設計兩種箱區規模算例，驗證翻箱規則的適用性。結果表明適當的非必要翻箱能有效改善裝船翻箱的箱區布局，減少場橋操作總時間，提高作業效率。由于場橋作業受水平搬運作業效率影響，下一步研究需要考慮場橋翻箱與水平搬運設備的協同，提出的翻箱規則需要在動態環境中進行測試。