張艷偉, 姜旎旎, 計(jì)三有

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

0 引言

堆場(chǎng)作業(yè)效率是碼頭作業(yè)效率的重要保障，堆場(chǎng)翻箱是當(dāng)前相關(guān)研究的重要熱點(diǎn)。通常出口集裝箱在船舶到港前一個(gè)時(shí)段內(nèi)提前集港，由于出口箱堆存計(jì)劃受船舶配載信息不確定性影響、出口箱陸續(xù)到達(dá)堆場(chǎng)的時(shí)間點(diǎn)和先后順序具有不確定性等，很難保證出口箱集港堆存狀態(tài)完全滿足后續(xù)裝船順序要求，裝船時(shí)出口箱堆場(chǎng)翻箱無法避免，是制約堆場(chǎng)作業(yè)效率的重要瓶頸。

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

綜上所述，關(guān)于裝船時(shí)翻箱問題研究，主要有數(shù)學(xué)模型構(gòu)建、基于分支界定限定翻箱次數(shù)的上下界、挖掘啟發(fā)式規(guī)則等。多數(shù)文獻(xiàn)研究對(duì)象為順岸式堆場(chǎng)單貝位裝船翻箱問題，且對(duì)于場(chǎng)橋作業(yè)時(shí)間通常按操作次數(shù)衡量為定值，較少區(qū)分場(chǎng)橋大車行走、吊具平移和起升[10]。非限制翻箱啟發(fā)式規(guī)則一般針對(duì)存在壓箱現(xiàn)象的棧頂集裝箱的多次翻箱。

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

1 垂岸式堆場(chǎng)出口箱裝船翻箱模型

垂岸式堆場(chǎng)出口箱裝船翻箱可以描述為堆場(chǎng)多貝位初始堆存狀態(tài)和裝船發(fā)箱順序已知的情況下，優(yōu)化場(chǎng)橋取箱、翻箱操作序列、同時(shí)在多個(gè)貝位內(nèi)優(yōu)化決策翻出集裝箱的落箱位，在當(dāng)前裝船周期內(nèi)以盡可能少的操作時(shí)間完成海側(cè)箱區(qū)出口箱裝船，同時(shí)控制單次取箱的最大翻箱次數(shù)和作業(yè)時(shí)間，保證裝船作業(yè)的流暢性。圖1為多貝位集裝箱堆存狀態(tài)示意圖，包括當(dāng)前擬裝船箱和非當(dāng)前擬裝船箱，數(shù)字表示發(fā)箱順序，灰度越深發(fā)箱順序越靠前，經(jīng)處理后每個(gè)發(fā)箱順序?qū)?yīng)一個(gè)集裝箱。

圖1 堆場(chǎng)貝位堆存狀態(tài)及發(fā)箱順序標(biāo)識(shí)

1.1 模型假設(shè)條件

(1)集裝箱均為20英尺箱，水平搬運(yùn)設(shè)備數(shù)量充足，不考慮場(chǎng)橋等待時(shí)間；

(2)一次只考慮一個(gè)裝船作業(yè)周期擬裝船箱，且裝船過程中無集港箱進(jìn)入堆場(chǎng)；

(3)一個(gè)箱區(qū)配置一臺(tái)場(chǎng)橋，不考慮滿載和空載區(qū)別，場(chǎng)橋路徑為曼哈頓距離。

1.2 符號(hào)說明

(1)集合

N為所有集裝箱發(fā)箱順序集合N=Npre∪Nnext，其中：Npre為當(dāng)前擬裝船箱發(fā)箱順序集合，Nnext為非當(dāng)前擬裝船箱發(fā)箱順序集合；B為貝位號(hào)集合；S為棧號(hào)集合；H為層號(hào)集合。

(2)參數(shù)

(3)變量

Anbshm是0-1變量，第m次操作發(fā)箱順序?yàn)閚的集裝箱位于b貝s列h層時(shí)為1，否則為0；xnbshm是0-1變量，場(chǎng)橋第m次操作發(fā)箱順序?yàn)閚的集裝箱落箱位是b貝s列h層時(shí)為1，否則為0，若為取箱操作，落箱到AGV上，令xn0s1m=1。

1.3 模型約束及目標(biāo)函數(shù)

目標(biāo)函數(shù):

(λ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)

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

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

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

2.1 編碼方式

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

2.2 評(píng)估函數(shù)與翻箱規(guī)則構(gòu)建

禁忌搜索求解非必要翻箱操作采用式(10)對(duì)堆場(chǎng)布局的優(yōu)劣進(jìn)行評(píng)估，以擴(kuò)大必要翻箱的解搜索空間。貪婪算法需要場(chǎng)橋在滿足操作時(shí)間最短的情況下將目標(biāo)箱的堵塞箱盡可能翻到不堵塞其余箱的列上，采用式(11)進(jìn)行評(píng)估。

f=βgoodmgood+βemptymempty

(10)

其中，mgood，mempty分別表示能使所翻箱不堵塞其余箱的列數(shù)和箱區(qū)內(nèi)空列數(shù)。βgood，βempty是各子目標(biāo)的權(quán)重系數(shù)，取值范圍為[0,1]，兩者之和為1。

基于STM32的嵌入式遠(yuǎn)程視頻監(jiān)控系統(tǒng)設(shè)計(jì)………………………………馬躍輝, 冀保峰, 程一淼,等(52)

(11)

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

(12)

其中，式(11)評(píng)價(jià)落箱位對(duì)后續(xù)操作產(chǎn)生的影響，nminbs>n，發(fā)箱順序?yàn)閚的集裝箱不會(huì)阻塞b貝s列的集裝箱；nminbs

針對(duì)必要翻箱操作設(shè)計(jì)規(guī)則1，針對(duì)非必要翻箱操作設(shè)計(jì)規(guī)則2，落箱箱位的選擇遵循貝內(nèi)優(yōu)先的原則，以便減少集裝箱取箱時(shí)場(chǎng)橋的移動(dòng)。

規(guī)則1目標(biāo)箱位于最上層時(shí)直接取箱裝船；當(dāng)目標(biāo)箱不在最上層且非必要翻箱次數(shù)達(dá)到上界時(shí)，將堵塞箱移動(dòng)到離目標(biāo)箱和堆場(chǎng)海側(cè)最近的可用列上。

規(guī)則2目標(biāo)箱不在最上層、非必要翻箱次數(shù)未達(dá)到上界，且箱區(qū)內(nèi)存在堵塞箱時(shí)，選擇目標(biāo)箱最近且堵塞率最高的列頂部箱進(jìn)行翻箱，落箱位選擇離目標(biāo)箱和堆場(chǎng)海側(cè)最近的不堵塞其余箱的列；目標(biāo)箱不在最上層、非必要翻箱次數(shù)未達(dá)到上界，且箱區(qū)不存在堵塞箱時(shí)，選擇目標(biāo)箱最近且集裝箱最少的列頂部箱進(jìn)行翻箱，落箱位選擇離目標(biāo)箱和堆場(chǎng)海側(cè)最近的不堵塞其余箱的列。

表1 編碼方式

2.3 禁忌表與終止條件設(shè)置

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

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

3 算例實(shí)驗(yàn)

3.1 算法有效性

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

3.2 算法規(guī)則對(duì)比和適用性分析

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

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

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

表3 兩種規(guī)模情況下各種規(guī)則結(jié)果對(duì)比

4 結(jié)論

針對(duì)垂岸式集裝箱碼頭出口箱裝船堆場(chǎng)翻箱，考慮非必要翻箱對(duì)場(chǎng)橋作業(yè)時(shí)間和次數(shù)的影響，建立數(shù)學(xué)模型，提出翻箱規(guī)則，設(shè)計(jì)貪婪禁忌搜索算法，通過與LLH算法對(duì)比，驗(yàn)證模型和翻箱規(guī)則的有效性，結(jié)合堆場(chǎng)實(shí)際規(guī)模設(shè)計(jì)兩種箱區(qū)規(guī)模算例，驗(yàn)證翻箱規(guī)則的適用性。結(jié)果表明適當(dāng)?shù)姆潜匾淠苡行Ц纳蒲b船翻箱的箱區(qū)布局，減少場(chǎng)橋操作總時(shí)間，提高作業(yè)效率。由于場(chǎng)橋作業(yè)受水平搬運(yùn)作業(yè)效率影響，下一步研究需要考慮場(chǎng)橋翻箱與水平搬運(yùn)設(shè)備的協(xié)同，提出的翻箱規(guī)則需要在動(dòng)態(tài)環(huán)境中進(jìn)行測(cè)試。