自動(dòng)化集裝箱碼頭AGV混合配對(duì)調(diào)度優(yōu)化

包曉瓊，鹿飛燕，胡志華

(1.上海海事大學(xué) 電工電子實(shí)驗(yàn)中心，上海 201306;2.上海海事大學(xué) 物流研究中心，上海 201306)

裝卸搬運(yùn)作業(yè)常見于自動(dòng)化集裝箱碼頭中，即碼頭前沿橋吊將集裝箱卸載至水平運(yùn)輸設(shè)備，水平運(yùn)輸設(shè)備銜接碼頭前沿和堆場(chǎng)，龍門吊將集裝箱裝載至堆場(chǎng)，故又稱之為三級(jí)裝卸搬運(yùn)[1]?！鞍徇\(yùn)”作為“裝”和“卸”的銜接環(huán)節(jié)，其高效運(yùn)作可提高碼頭整體效益。自動(dòng)化導(dǎo)引車(automatic guided vehicle, AGV)，又稱無(wú)人導(dǎo)引車，是自動(dòng)化集裝箱碼頭最常見的水平運(yùn)輸設(shè)備。在搬運(yùn)作業(yè)中，若一臺(tái)40 ft AGV搬運(yùn)一個(gè)20 ft的集裝箱，其裝載率僅為50%，造成資源浪費(fèi)。因此，采用由兩臺(tái)20 ft的AGV配對(duì)搬運(yùn)40 ft的集裝箱或40 ft AGV獨(dú)立搬運(yùn)40 ft的集裝箱，20 ft集裝箱僅由20 ft AGV獨(dú)立搬運(yùn)的新工藝，即為AGV混合配對(duì)調(diào)度。

新工藝的關(guān)鍵是配對(duì)調(diào)度，指多輛運(yùn)輸設(shè)備協(xié)同搬運(yùn)一個(gè)貨物，HU等[2]稱此類運(yùn)輸問(wèn)題為多車輛單任務(wù)問(wèn)題 (multi-vehicle and one-cargo transportation，MOVC)。MOVC常見于大件物流運(yùn)輸和船舶分段運(yùn)輸，如JOO等[3]考慮了配送限制的約束條件，以最小化懲罰時(shí)間為目標(biāo)建立數(shù)學(xué)模型，并設(shè)計(jì)了基于遺傳算法(GA)和自進(jìn)化算法(SEA)的元啟發(fā)式算法。PARK等[4]將船舶分段運(yùn)輸問(wèn)題轉(zhuǎn)化為帶有優(yōu)先級(jí)約束和順序相關(guān)初始時(shí)間的并行調(diào)度問(wèn)題。MOVC對(duì)同步性提出了更高要求，如IOACHIM等[5]將同步性概念應(yīng)用到船舶分段運(yùn)輸，并通過(guò)動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。GSCHWIND[6]考慮節(jié)點(diǎn)同步裝載的運(yùn)輸問(wèn)題，在列生成算法的基礎(chǔ)上設(shè)計(jì)4種分支定界算法并進(jìn)行比較。SALAZAR-AGUILAR等[7]將同步弧路徑問(wèn)題引入除雪作業(yè)中，設(shè)計(jì)了混合整數(shù)規(guī)劃模型。ROUSSEAU等[8]設(shè)計(jì)帶有同步約束的靈活啟發(fā)式算法以研究車輛動(dòng)態(tài)分配問(wèn)題。HU等建立混合整數(shù)規(guī)劃模型，并設(shè)計(jì)貪婪算法和改進(jìn)遺傳算法求解該模型。綜上所述，AGV配對(duì)調(diào)度是帶有同步約束的MOVC問(wèn)題。

多載AGV可以提高AGV裝載率和利用率，針對(duì)此問(wèn)題，GRUNOW等[9]利用運(yùn)輸車輛的有效性，提出了基于優(yōu)先權(quán)調(diào)度算法和MILP模型。LEVITIN等[10]則設(shè)計(jì)了基于LIFO規(guī)則的算法求解多載AGV最短路徑。

基于此，筆者采用由兩臺(tái)20 ft的AGV配對(duì)搬運(yùn)一個(gè)40 ft集裝箱和一臺(tái)40 ft AGV獨(dú)立搬運(yùn)40 ft集裝箱，20 ft集裝箱僅由20 ft AGV搬運(yùn)的新工藝，以研究AGV混合配對(duì)調(diào)度問(wèn)題。以最小化完成時(shí)間和空載時(shí)間為目標(biāo)，建立混合整數(shù)規(guī)劃模型并求解。并設(shè)計(jì)算例，研究AGV和搬運(yùn)任務(wù)的數(shù)量配置、規(guī)格配置與運(yùn)輸時(shí)間的敏感性，以期為優(yōu)化自動(dòng)化集裝箱碼頭AGV配對(duì)調(diào)度方案提供參考。

1 問(wèn)題描述

受限于自動(dòng)化集裝箱碼頭車輛配置且集裝箱裝卸搬運(yùn)作業(yè)密集，AGV裝載率和利用率直接影響碼頭整體效益。筆者采用由兩臺(tái)20 ft的AGV配對(duì)搬運(yùn)一個(gè)40 ft集裝箱和一臺(tái)40 ft AGV獨(dú)立搬運(yùn)40 ft集裝箱的新工藝，其關(guān)鍵點(diǎn)是配對(duì)調(diào)度。配對(duì)調(diào)度分為3個(gè)階段[11]：①選擇，為搬運(yùn)任務(wù)選擇相應(yīng)數(shù)量AGVs；②配對(duì)并搬運(yùn)，AGVs配對(duì)成具有相應(yīng)荷載能力的搬運(yùn)車并將集裝箱從裝載點(diǎn)搬運(yùn)到卸載點(diǎn)；③分離，集裝箱卸載后，AGVs自動(dòng)分離，等待后續(xù)作業(yè)命令。

假設(shè)有4個(gè)搬運(yùn)任務(wù)和3臺(tái)AGV。每個(gè)搬運(yùn)任務(wù)對(duì)應(yīng)一個(gè)集裝箱，集裝箱的裝載位置Pi和卸載位置Di均已知，并引入虛擬起點(diǎn)S和虛擬終點(diǎn)T。任務(wù)1的集裝箱尺寸為40 ft，由一臺(tái)40 ft的AGV將其從裝載位置P1搬運(yùn)至卸載位置D1；任務(wù)2和任務(wù)3的集裝箱尺寸均為20 ft，分別由一臺(tái)20 ft AGV搬運(yùn)；兩臺(tái)20 ft AGV各自完成20 ft搬運(yùn)任務(wù)后，配對(duì)成具有40 ft荷載容量的運(yùn)輸車，將任務(wù)4中40 ft集裝箱由裝載位置P4搬運(yùn)至卸載位置D4?；旌吓鋵?duì)調(diào)度示意圖如圖1所示。

圖1 AGV混合配對(duì)調(diào)度示意圖

現(xiàn)有以下假設(shè)：

假設(shè)1集裝箱尺寸及其裝卸載位置確定。

假設(shè)2AGV尺寸、數(shù)量、位置信息及可調(diào)度時(shí)間確定。

假設(shè)3AGV配對(duì)和分離操作時(shí)間忽略不計(jì)。

假設(shè)4不考慮交通堵塞、AGV電量不足等不確定因素，AGV全程無(wú)故障，勻速行駛且忽略啟動(dòng)時(shí)間。

2 模型構(gòu)建

集合設(shè)置如下：

I20={120,220,…，i20，…,N20}為20 ft搬運(yùn)任務(wù)集合，i20表示搬運(yùn)任務(wù)i的尺寸為20 ft， 即i20∈I20；

I40={140,240,…,i40,…，N40}為40 ft搬運(yùn)任務(wù)集合，i40表示搬運(yùn)任務(wù)i的尺寸為40 ft，即i40∈I40；

I=I20∪I40∪{S,T}為搬運(yùn)任務(wù)總集合，其中S與T分別表示虛擬起點(diǎn)和虛擬終點(diǎn)，即i∈I；

V20={120,220,…,|V20|}為20 ft AGV集合，v20表示第v臺(tái)AGV尺寸為20 ft，即v20∈V20；

V40={140,240,…,|V40|}為40 ft AGV集合，v40表示第v臺(tái)AGV尺寸為40 ft，即v40∈V40；

V=V20∪V40為AGV總集合，即v∈V。

目標(biāo)函數(shù)及約束條件如下：

minf=(fMakespan,fEmpty)

(1)

(2)

fMakespan≥zi,?i

(3)

f≥0,zi≥0,?i

(4)

zi≥Ai,?i

(5)

zi≥Rv+TLv,Pi+Ti,?i,v

(6)

zj+(1-xijv)M≥zi+Tj+TDi,Pj,?i≠j,v

(7)

(8)

(9)

xijv+xjiv≤1,?v

(10)

(11)

(12)

(13)

(14)

(15)

(16)

式(1)為目標(biāo)函數(shù)，表示最小化完成時(shí)間和空載時(shí)間；式(2)為各AVG的空載時(shí)間之和；式(3)～式(7)規(guī)定搬運(yùn)任務(wù)的完成時(shí)間；式(8)～式(10)為作業(yè)流約束，即入度與出度相等；式(11)和式(12)表示虛擬起點(diǎn)和虛擬終點(diǎn)分別是初始任務(wù)和末任務(wù)；式(13)～式(15)規(guī)定了40 ft集裝箱的AGV分配方案；式(16)表示20 ft集裝箱僅分配一臺(tái)20 ft AGV，否則任務(wù)不能被處理，一直處于等待狀態(tài)。

3 算例分析

算例有6臺(tái)AGV 和16個(gè)搬運(yùn)任務(wù)(包含虛擬起點(diǎn)和虛擬終點(diǎn))，任務(wù)完成時(shí)間和AGV空載時(shí)間分別為16 413和34 651，作業(yè)銜接序列如表3所示。第1臺(tái)和第3臺(tái)AGV為40 ft，其余AGV的尺寸為20 ft。20 ft和40 ft集裝箱比例設(shè)置為1:1，其中20 ft集裝箱編號(hào)分別為2、4、6、8、12和14，40 ft集裝箱編號(hào)分別為1、3、5、7、9、11和13。第1臺(tái)40 ft AGV先后獨(dú)立完成40 ft搬運(yùn)任務(wù)7、13和9；第3臺(tái)40 ft AGV獨(dú)立完成第3個(gè)40 ft搬運(yùn)任務(wù)；第2臺(tái)和第4臺(tái)20 ft AGVs配對(duì)完成第5個(gè)40 ft搬運(yùn)任務(wù)；第4臺(tái)和第6臺(tái)20 ft AGVs配對(duì)完成第1個(gè)40 ft搬運(yùn)任務(wù)；第5個(gè)和第6個(gè)20 ft AGVs配對(duì)完成第11個(gè)40 ft搬運(yùn)任務(wù)。20 ft集裝箱均由20 ft AGV獨(dú)立搬運(yùn)。

表1 搬運(yùn)任務(wù)參數(shù)值

表2 AGV參數(shù)設(shè)置

應(yīng)用GUROBI求解器并使用PYTHON語(yǔ)言編譯求解模型，得到AGV配對(duì)調(diào)度時(shí)序圖時(shí)間和

表3 AGV作業(yè)銜接序列

空載時(shí)間。AGV配對(duì)時(shí)序圖如圖2所示，矩形區(qū)域中的數(shù)字表示第v臺(tái)AGV參與完成第i個(gè)搬運(yùn)任務(wù)，矩形的長(zhǎng)度表示運(yùn)輸時(shí)間的長(zhǎng)短。

圖2 AGV配對(duì)時(shí)序圖

4 實(shí)驗(yàn)

為進(jìn)一步分析搬運(yùn)任務(wù)、AGV的規(guī)格、數(shù)量和運(yùn)輸時(shí)間變化對(duì)結(jié)果的影響，在16個(gè)搬運(yùn)任務(wù)和6臺(tái)AGV 算例的基礎(chǔ)上設(shè)計(jì)4組實(shí)驗(yàn)場(chǎng)景，場(chǎng)景描述及參數(shù)調(diào)整如下：

(1)實(shí)驗(yàn)場(chǎng)景1分析AGV規(guī)格配置對(duì)結(jié)果的影響。搬運(yùn)任務(wù)和AGV數(shù)量等參數(shù)保持不變，在原有2∶1配置比例基礎(chǔ)上，按照[1∶5，1∶2，1∶1，5∶1]調(diào)節(jié) 40/20AGV規(guī)格。搬運(yùn)任務(wù)完成時(shí)間和AGV空載時(shí)間變化如圖3所示，可以看出AGV空載時(shí)間對(duì)不同規(guī)格AGV配置比例的敏感性較低，而AGV配置比例對(duì)任務(wù)完成時(shí)間的影響較大。隨著40 ft AGV配置數(shù)量的減少，任務(wù)完成時(shí)間不斷減小，當(dāng)40/20的AGV配置比例為2∶1時(shí)，任務(wù)完成時(shí)間達(dá)到最小，且完成時(shí)間和空載時(shí)間之和最小。因此，當(dāng)搬運(yùn)任務(wù)數(shù)量和AGV數(shù)量已知時(shí)，可通過(guò)調(diào)整AGV規(guī)格配置比例，優(yōu)化調(diào)度方案以減少搬運(yùn)任務(wù)的完成時(shí)間和AGV空載時(shí)間。

圖3 AGV配置比例對(duì)結(jié)果的影響

圖4 集裝箱配置比例對(duì)結(jié)果的影響

(2)實(shí)驗(yàn)場(chǎng)景2分析集裝箱規(guī)格配置對(duì)結(jié)果的影響。搬運(yùn)任務(wù)和AGV數(shù)量等參數(shù)保持不變,在原有1∶1的基礎(chǔ)上，按照[1∶6，2∶5，1∶1，5∶2，6∶1]調(diào)節(jié)40/20集裝箱規(guī)格。搬運(yùn)任務(wù)完成時(shí)間和AGV空載時(shí)間變化如圖4所示，可以看出任務(wù)完成時(shí)間對(duì)不同規(guī)格集裝箱配置比例的敏感性很低，基本沒有受到影響。而隨著配置比例的變化，AGV空載時(shí)間波動(dòng)變化，當(dāng)40/20集裝箱配置比例為1∶1時(shí)，空載時(shí)間和完成時(shí)間之和最小。因此，在AGV數(shù)量和配置比例已知，且搬運(yùn)任務(wù)數(shù)量確定的條件下，調(diào)整集裝箱配置比例可減少任務(wù)完成時(shí)間和AGV空載時(shí)間。

(3)實(shí)驗(yàn)場(chǎng)景3分析集裝箱數(shù)量變化對(duì)結(jié)果的影響。保持40/20集裝箱規(guī)格配置比例1∶1不變，按照-50%，-25%，25%，50%調(diào)節(jié)集裝箱數(shù)量。搬運(yùn)任務(wù)完成時(shí)間和AGV空載時(shí)間的變化如圖5所示，可以看出隨著集裝箱數(shù)量的增加，搬運(yùn)任務(wù)完成時(shí)間持續(xù)上升，而AGV空載時(shí)間呈波動(dòng)變化?？梢夾GV空載時(shí)間對(duì)集裝箱數(shù)量變化的敏感性較強(qiáng)，而搬運(yùn)任務(wù)完成時(shí)間對(duì)集裝箱數(shù)量變化的敏感性較低。

圖5 集裝箱數(shù)量變化對(duì)結(jié)果的影響

(4)實(shí)驗(yàn)場(chǎng)景4分析運(yùn)輸時(shí)間變化對(duì)結(jié)果的影響。保持其他參數(shù)不變，按照-75%，-50%，-25%，25%，50%，75%調(diào)節(jié)運(yùn)輸時(shí)間。搬運(yùn)任務(wù)完成時(shí)間和AGV空載時(shí)間的變化如圖6所示，可以看出隨著運(yùn)輸時(shí)間的增加，完成時(shí)間和空載時(shí)間均呈上升趨勢(shì)，且空載時(shí)間上升幅度大于完成時(shí)間?？梢妼?duì)于運(yùn)輸時(shí)間的變化，空載時(shí)間的敏感性較強(qiáng)，完成時(shí)間的敏感性相對(duì)較低。

圖6 運(yùn)輸時(shí)間變化對(duì)結(jié)果的影響

5 結(jié)論

為了提高自動(dòng)化導(dǎo)引車的空間利用率，針對(duì)40 ft集裝箱搬運(yùn)問(wèn)題，采用由兩臺(tái)20 ft AGV配對(duì)搬運(yùn)和一臺(tái)40 ft AGV獨(dú)立搬運(yùn)的混合配對(duì)調(diào)度新工藝，以最小化完成時(shí)間和空載時(shí)間為目標(biāo)，建立混合整數(shù)規(guī)劃模型并求解。實(shí)驗(yàn)結(jié)果表明，任務(wù)完成時(shí)間對(duì)運(yùn)輸時(shí)間敏感性較低，而空載時(shí)間對(duì)運(yùn)輸時(shí)間敏感性較高。通過(guò)調(diào)整AGV和搬運(yùn)任務(wù)的數(shù)量和規(guī)格，可獲得合理的配置參數(shù)和配對(duì)調(diào)度方案，模型具有良好的可行性。