自動化集裝箱碼頭雙循環(huán)AGV與場橋的集成調(diào)度研究

田 宇，周 強(qiáng)，朱本飛

(武漢理工大學(xué)物流工程學(xué)院，武漢430063)

0 引 言

集裝箱碼頭作為集裝箱運(yùn)輸網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)，其運(yùn)營效率是港口運(yùn)輸系統(tǒng)的瓶頸，體現(xiàn)港口的關(guān)鍵競爭力.自動化集裝箱碼頭相對于傳統(tǒng)碼頭具有高效、環(huán)保、低人力成本等優(yōu)勢，成為集裝箱碼頭未來發(fā)展的必然趨勢.岸橋、自動導(dǎo)引車(AGV)和場橋是自動化集裝箱碼頭裝卸過程的3種重要設(shè)備資源，三者相互關(guān)聯(lián)、相互影響.岸橋位于碼頭前沿，負(fù)責(zé)船舶上集裝箱的裝卸，其裝卸效率決定船舶在港口的滯留時(shí)間.在岸橋裝卸次序表已知的情況下，研究如何使AGV和場橋高效協(xié)同作業(yè)，保證岸橋最小時(shí)間完成船舶裝卸,具有重要的理論意義和實(shí)用價(jià)值.

關(guān)于AGV的調(diào)度問題研究，文獻(xiàn)[1]提出基于調(diào)度優(yōu)先級次序的動態(tài)調(diào)度方法來解決AGV的調(diào)度問題；文獻(xiàn)[2]針對智能倉庫中多AGV調(diào)度的路徑問題進(jìn)行研究，提出改進(jìn)的蟻群算法進(jìn)行求解.關(guān)于自動化集裝箱碼頭AGV與岸橋和場橋的調(diào)度問題，文獻(xiàn)[3]建立最小化AGV行走時(shí)間、岸橋延遲時(shí)間、場橋行走時(shí)間的多目標(biāo)混合整數(shù)規(guī)劃模型，設(shè)計(jì)多層啟發(fā)式和最大匹配啟發(fā)式遺傳算法進(jìn)行求解，通過數(shù)值仿真分析表明最大匹配啟發(fā)式算法在尋優(yōu)和耗時(shí)上優(yōu)于多層啟發(fā)式算法；文獻(xiàn)[4]建立最小完工時(shí)間和AGV最小無效行走時(shí)間的多目標(biāo)數(shù)學(xué)模型，提出混合遺傳和禁忌搜索兩種算法進(jìn)行求解；文獻(xiàn)[5]針對自由路徑AGV的調(diào)度與岸橋和場橋進(jìn)行集成研究，考慮AGV在行走過程中的碰撞問題，提出分層控制方法來實(shí)現(xiàn)岸橋、場橋的優(yōu)化調(diào)度以及AGV的路徑規(guī)劃.關(guān)于AGV與場橋的集成調(diào)度中考慮集裝箱堆場位置分配的問題，文獻(xiàn)[6]在集成研究中考慮的是進(jìn)口箱的堆存位置分配，建立以最小化完工時(shí)間為目標(biāo)的混合整數(shù)規(guī)劃模型，根據(jù)模型的特點(diǎn)設(shè)計(jì)遺傳算法，通過數(shù)值仿真對算法的參數(shù)、性能進(jìn)行分析；文獻(xiàn)[7]考慮進(jìn)出口箱的堆存位置分配，以最小化岸橋延遲時(shí)間和AGV行走時(shí)間為目標(biāo)，提出多目標(biāo)混合整數(shù)規(guī)劃方法和基于模擬退火算法的近似優(yōu)化方法對問題進(jìn)行求解.關(guān)于卸船過程中的AGV與場橋調(diào)度問題，文獻(xiàn)[8]考慮出口箱的堆存位置分配，建立以最小化岸橋和場橋的總工作時(shí)間以及完工時(shí)間為多目標(biāo)的線性和非線性混合整數(shù)規(guī)劃模型，設(shè)計(jì)元啟發(fā)式和遺傳算法進(jìn)行求解；文獻(xiàn)[9]考慮進(jìn)口箱的堆存位置分配，建立以最小完工時(shí)間為目標(biāo)的混合整數(shù)規(guī)劃模型，設(shè)計(jì)遺傳算法進(jìn)行求解.

綜上所述，圍繞AGV與其他裝卸設(shè)備的集成研究中，針對雙循環(huán)AGV(即AGV 不固定服務(wù)某一臺岸橋，可以服務(wù)多臺岸橋的作業(yè)模式)與場橋的集成研究比較少.本文通過對集裝箱任務(wù)統(tǒng)一編號，結(jié)合對裝卸過程中集裝箱的流動特性分析，設(shè)計(jì)基于任務(wù)隨機(jī)搜索機(jī)制的“最早可獲得時(shí)間(Earliest Available Time,EAT)”“最短路徑(Shortest Path,SP)”兩種啟發(fā)式規(guī)則進(jìn)行求解.

1 問題分析與數(shù)學(xué)建模

1.1 問題描述

在集裝箱船舶靠泊后，集裝箱的裝卸流動主要涉及到碼頭的3個(gè)功能區(qū)：岸橋負(fù)責(zé)的碼頭前沿裝卸區(qū)、AGV小車負(fù)責(zé)的運(yùn)輸區(qū)和場橋負(fù)責(zé)的堆場堆存區(qū)，如圖1所示.

圖1 自動化集裝箱碼頭布局示意圖Fig.1 Layout of automated container terminal

在自動化碼頭生產(chǎn)過程中，船舶的配載圖會在裝卸前提前給出，以便提前計(jì)劃出岸橋的裝卸次序表.在裝卸前，進(jìn)口箱被卸載到堆場的堆存位置會預(yù)留出，以便進(jìn)口箱在堆場的臨時(shí)堆存.出口箱在船舶到港之前會被陸續(xù)堆集到堆場，以便船舶靠港后進(jìn)行裝載.一般同一艘船舶的進(jìn)出口箱在堆場的堆存位置分別分配在不同的箱區(qū).集裝箱的流動在裝船過程與卸船過程中是相反的，其中的卸船過程描述如下：

(1)岸橋按照裝卸次序表從船舶上抓取相應(yīng)的進(jìn)口集裝箱，在岸橋裝卸節(jié)點(diǎn)將集裝箱釋放到AGV小車上，岸橋進(jìn)入下一個(gè)任務(wù)的裝卸；

(2)AGV小車將集裝箱運(yùn)到相應(yīng)箱區(qū)的裝卸節(jié)點(diǎn)處，負(fù)責(zé)該箱區(qū)的場橋從AGV 上抓取該集裝箱后，AGV進(jìn)入下一個(gè)任務(wù)的運(yùn)輸；

(3)場橋?qū)⒓b箱從AGV小車上提取后，釋放到堆場相應(yīng)的堆存位置，回到箱區(qū)裝卸節(jié)點(diǎn)處進(jìn)入下一個(gè)任務(wù)的裝卸.

本文的優(yōu)化目標(biāo)是在船舶裝卸過程中，對“AGV的任務(wù)分配”“AGV的路徑規(guī)劃”“場橋的任務(wù)次序”三者同時(shí)做出決策，以便獲得船舶最小完工時(shí)間.

1.2 數(shù)學(xué)模型

(1)假 設(shè).

①岸橋裝卸次序表已知，②進(jìn)、出口箱在船舶和堆場的堆存位置已知，③岸橋和場橋?qū)b箱的操作時(shí)間已知，④AGV在任意兩節(jié)點(diǎn)的行走時(shí)間已知.

(2)參數(shù)及變量.

①參數(shù).

D為進(jìn)口箱集合；L為出口箱集合；Q為岸橋集合，為岸橋總數(shù)量；v為AGV小車指針，為AGV小車的總數(shù)量；n、n′、n″為進(jìn)出口集裝箱任務(wù)編號指針；為總的進(jìn)出口箱數(shù)量；q、q′為岸橋指針；b、b′為堆場箱區(qū)指針；為AGV小車從岸橋q的裝卸節(jié)點(diǎn)到堆場箱區(qū)b裝卸節(jié)點(diǎn)行走的時(shí)間；為AGV小車從岸橋q′的裝卸節(jié)點(diǎn)行走到岸橋q裝卸節(jié)點(diǎn)的行走時(shí)間；為AGV小車從堆場箱區(qū)b裝卸節(jié)點(diǎn)到岸橋q裝卸節(jié)點(diǎn)的行走時(shí)間；為AGV小車從堆場箱區(qū)b裝卸節(jié)點(diǎn)到堆場箱區(qū)b′裝卸節(jié)點(diǎn)的行走時(shí)間；Hn為岸橋裝卸集裝箱n時(shí)所需要的時(shí)間；Kn為場橋裝卸集裝箱n時(shí)所需要的時(shí)間.

②變量.

Un為集裝箱n在岸橋裝卸節(jié)點(diǎn)被交接的時(shí)間點(diǎn)；Vn為集裝箱n在箱區(qū)裝卸節(jié)點(diǎn)被交接的時(shí)間點(diǎn).

(3)模型.

在裝卸過程中，岸橋按照裝卸次序表執(zhí)行裝卸任務(wù)，進(jìn)口箱區(qū)場橋按照“先到先服務(wù)”的原則，出口箱區(qū)場橋按照先滿足岸橋裝卸次序并有AGV可指派的先發(fā)箱.進(jìn)口箱在岸橋裝卸節(jié)點(diǎn)釋放時(shí)間和出口箱在箱區(qū)裝卸節(jié)點(diǎn)釋放時(shí)間情況如圖2所示.

圖2 進(jìn)口箱在岸橋裝卸節(jié)點(diǎn)和出口箱在箱區(qū)裝卸節(jié)點(diǎn)的任務(wù)關(guān)系圖Fig.2 Task relationship of import containers at quay crane handling points and export containers at block handling points

圖2中(a)～(i)表示集裝箱n為進(jìn)口箱，各種情況下進(jìn)口箱n在岸橋裝卸節(jié)點(diǎn)應(yīng)滿足的時(shí)間關(guān)系如下.

(a)當(dāng)前集裝箱n為岸橋的第一個(gè)任務(wù)，且為AGV小車的第一個(gè)任務(wù)時(shí)，即

(b)當(dāng)前集裝箱n不是岸橋的第一個(gè)任務(wù)(前一任務(wù)為進(jìn)口箱n′)，但為AGV小車的第一個(gè)任務(wù)時(shí)，即

(c)當(dāng)前集裝箱n不是岸橋的第一個(gè)任務(wù)(前一任務(wù)為出口箱n′)，但為AGV小車的第一個(gè)任務(wù)時(shí)，即

(d)當(dāng)前集裝箱n是岸橋q的第一個(gè)任務(wù)，但不是AGV小車的第一個(gè)任務(wù)(前一任務(wù)為岸橋q′負(fù)責(zé)的出口箱n′)時(shí)，即

(e)當(dāng)前集裝箱n是岸橋q的第一個(gè)任務(wù)，但不是AGV小車的第一個(gè)任務(wù)(前一任務(wù)為堆存在箱區(qū)b的進(jìn)口箱n′)時(shí)，即

(f)當(dāng)前集裝箱n不是岸橋q的第一個(gè)任務(wù)(前一任務(wù)為進(jìn)口箱n″)，也不是AGV小車的第一個(gè)任務(wù)(前一任務(wù)為堆存在箱區(qū)b的進(jìn)口箱n′)時(shí)，即

(g)當(dāng)前集裝箱n不是岸橋q的第一個(gè)任務(wù)(前一任務(wù)為進(jìn)口箱n″)，也不是AGV小車的第一個(gè)任務(wù)(前一任務(wù)為岸橋q′負(fù)責(zé)的出口箱n′)時(shí)，即

(h)當(dāng)前集裝箱n不是岸橋q的第一個(gè)任務(wù)(前一任務(wù)為出口箱n″)，也不是AGV小車的第一個(gè)任務(wù)(前一任務(wù)為堆存在箱區(qū)b的進(jìn)口箱n′)時(shí)，即

(i)當(dāng)前集裝箱n不是岸橋q的第一個(gè)任務(wù)(前一任務(wù)為出口箱n″)，也不是AGV小車的第一個(gè)任務(wù)(前一任務(wù)為岸橋q′負(fù)責(zé)的出口箱n′)時(shí)，即

確定進(jìn)口箱在岸橋裝卸節(jié)點(diǎn)的交接時(shí)間點(diǎn)后，根據(jù)各進(jìn)口箱區(qū)場橋“先到先服務(wù)”原則確定進(jìn)口箱在箱區(qū)裝卸節(jié)點(diǎn)的交接時(shí)間點(diǎn)Vn,n∈D.

圖2中(j)～(o)表示集裝箱n為出口箱，各種情況下出口箱n流動在箱區(qū)裝卸節(jié)點(diǎn)應(yīng)滿足的時(shí)間關(guān)系如下.

(j)當(dāng)前集裝箱n是箱區(qū)場橋的第一個(gè)任務(wù)，且為AGV小車的第一個(gè)任務(wù)時(shí)，即

(k)當(dāng)前集裝箱n不是箱區(qū)場橋的第一個(gè)任務(wù)(前一任務(wù)為集裝箱n′)，但為AGV小車的第一個(gè)任務(wù)時(shí)，即

(l)當(dāng)前集裝箱n是箱區(qū)b場橋的第一個(gè)任務(wù)，但不是AGV小車的第一個(gè)任務(wù)(前一任務(wù)為堆存于箱區(qū)b′的集裝箱n′)時(shí)，即

(m)當(dāng)前集裝箱n是箱區(qū)b場橋的第一個(gè)任務(wù)，但不是AGV小車的第一個(gè)任務(wù)(前一任務(wù)為岸橋q′負(fù)責(zé)的集裝箱n′)時(shí)，即

(n)當(dāng)前集裝箱n不是箱區(qū)b場橋的第一個(gè)任務(wù)(前一任務(wù)為集裝箱n′)，也不是AGV小車的第一個(gè)任務(wù)(前一任務(wù)為堆存于箱區(qū)b′的集裝箱n″)時(shí)，即

(o)當(dāng)前集裝箱n不是箱區(qū)b場橋的第一個(gè)任務(wù)(前一任務(wù)為集裝箱n′)，也不是AGV小車的第一個(gè)任務(wù)(前一任務(wù)為岸橋q′負(fù)責(zé)的集裝箱n″)時(shí)，即

確定出口箱在岸橋裝卸節(jié)點(diǎn)的交接時(shí)間后，根據(jù)集裝箱在岸橋裝卸節(jié)點(diǎn)遵從岸橋裝卸次序表原則確定出口箱在岸橋裝卸節(jié)點(diǎn)的交接時(shí)間

2 啟發(fā)式遺傳算法

2.1 編 碼

為了方便染色體編碼，將任務(wù)根據(jù)岸橋的裝卸次序表以及岸橋編號從小到大的規(guī)則統(tǒng)一對需要裝卸的任務(wù)進(jìn)行編碼.染色體NRSM=randperm()表示在求解過程中對任務(wù)的搜索機(jī)制.

2.2 目標(biāo)函數(shù)及適應(yīng)度函數(shù)

染色體的編碼表達(dá)求解過程中任務(wù)的搜索機(jī)制，不能直接表達(dá)AGV的任務(wù)集、AGV的路徑以及場橋的任務(wù)次序.根據(jù)岸橋和場橋的服務(wù)規(guī)則，結(jié)合文獻(xiàn)[7]“最近車輛指派”“最早可獲得”規(guī)則，對AGV的指派設(shè)置兩種啟發(fā)式規(guī)則：SP和EAT.SP指所有空閑的AGV中距離該集裝箱裝卸節(jié)點(diǎn)最近的指派規(guī)則.EAT 指所有空閑的AGV中能最早到達(dá)指定集裝箱裝卸節(jié)點(diǎn)的指派規(guī)則.

單個(gè)染色體的求解流程如圖3所示.

圖3 單個(gè)染色體求解流程Fig.3 Solution process of single chromosome

圖3中AAGVZT為5行列的AGV 狀態(tài)矩陣：NAGVZT(1,:)表示各AGV小車當(dāng)前的運(yùn)送任務(wù)編號，為0時(shí)表示可分配任務(wù)；NAGVZT(2,:)表示各AGV小車當(dāng)前任務(wù)在岸橋裝卸節(jié)點(diǎn)交接的實(shí)際時(shí)間點(diǎn)；NAGVZT(3,:)表示各AGV小車當(dāng)前任務(wù)在岸橋裝卸節(jié)點(diǎn)交接的預(yù)估時(shí)間點(diǎn)；NAGVZT(4,:)表示各AGV小車當(dāng)前任務(wù)在對應(yīng)箱區(qū)裝卸節(jié)點(diǎn)交接的預(yù)估時(shí)間點(diǎn)；NAGVZT(5,:)表示各AGV小車當(dāng)前任務(wù)在對應(yīng)箱區(qū)裝卸節(jié)點(diǎn)交接的實(shí)際時(shí)間點(diǎn).

目標(biāo)值為

2.3 交 叉

染色體的交叉采用兩點(diǎn)交叉法.隨機(jī)從種群中選擇染色體作為父代1和父代2，然后隨機(jī)生成兩交叉點(diǎn)并將兩點(diǎn)之間的基因段分別作為子代2和子代1對應(yīng)的基因段，最后將父代1中不同于子代1中的基因逐個(gè)編入子代中的空白基因中.

2.4 變 異

采用換位變異，隨機(jī)生成兩個(gè)基因位置，再將兩個(gè)基因的內(nèi)容進(jìn)行互換.

3 數(shù)值試驗(yàn)及結(jié)果分析

運(yùn)用MATLAB 2016a和CPLEX12.6.1.0，運(yùn)行環(huán)境為windows8，處理器為英特爾i7-4770，處理器頻率為3.4 GHz，運(yùn)行內(nèi)存為8.00 G.

3.1 參數(shù)設(shè)置

堆場的布局如圖1所示，共有6條箱區(qū)，其中1～3為進(jìn)口箱區(qū)，4～6為出口箱區(qū)，進(jìn)出口集裝箱在堆場的箱區(qū)從對應(yīng)進(jìn)出口箱區(qū)中隨機(jī)生成.岸橋?qū)Ω骷b箱的操作時(shí)間Hn∈U[30,180]s，AGV 于任意兩裝卸節(jié)點(diǎn)的行走時(shí)間參照文獻(xiàn)[3]，場橋的操作時(shí)間Kn∈U[60,180]s.遺傳算法的參數(shù)設(shè)置：最大迭代數(shù)為250，種群數(shù)為40，交叉率為0.8，變異率為0.2.

3.2 結(jié)果分析

數(shù)值試驗(yàn)中，每種情況運(yùn)行5個(gè)算例，每個(gè)算例運(yùn)行5次，分別取平均值、最小值、標(biāo)準(zhǔn)方差以及運(yùn)行時(shí)間的平均值對比分析.結(jié)果如圖4～圖9所示.

圖4 EAT 規(guī)則的平均值Fig.4 Average of EAT rule

圖5 SP 規(guī)則的平均值Fig.5 Average of SP rule

圖6 EAT 規(guī)則的最小值Fig.6 Minimum value of EAT rule

圖7 SP 規(guī)則的最小值Fig.7 Minimum value of SP rule

圖8 EAT 規(guī)則的標(biāo)準(zhǔn)方差Fig.8 Sdev of EAT rule

圖9 SP 規(guī)則標(biāo)準(zhǔn)方差Fig.9 Sdev of SP rule

圖4～圖7分別是“任務(wù)量30-岸橋2”“任務(wù)量50-岸橋3”“任務(wù)量70-岸橋4”“任務(wù)量90-岸橋5”時(shí)，AGV數(shù)量從4～10個(gè)的算例平均值、最小值.兩種啟發(fā)式規(guī)則計(jì)算結(jié)果隨著AGV的數(shù)量增加，最大完工時(shí)間會變小，變小的趨勢會變得平緩，說明AGV數(shù)量的增加可以提升碼頭的效率，提升的程度有上限.從圖8和圖9中得到：隨著任務(wù)數(shù)量、岸橋數(shù)量的增加，穩(wěn)定性會有一定程度的下降，但是兩種啟發(fā)式算法的穩(wěn)定性比較理想.圖8中，當(dāng)任務(wù)量小于70、岸橋數(shù)量小于5時(shí)，“最早可獲得時(shí)間”的啟發(fā)式算法隨著AGV數(shù)量的增加，表現(xiàn)良好的穩(wěn)定性.

圖10 兩種啟發(fā)式算法的平均值Fig.10 Average of two heuristic algorithms

圖11 兩種啟發(fā)式算法的最小值Fig.11 Minimum value of two heuristic algorithms

圖10～圖12是不同任務(wù)數(shù)量、岸橋數(shù)量、AGV數(shù)量下平均值、最小值、標(biāo)準(zhǔn)方差下的曲線，可以看出：“最早可獲得時(shí)間”的啟發(fā)式規(guī)則在優(yōu)化目標(biāo)以及求解穩(wěn)定性上都要優(yōu)于“最短路徑”啟發(fā)式算法.圖13是兩種啟發(fā)式算法的求解時(shí)間，兩種算法的求解時(shí)間差別不大，都比較理想；在任務(wù)、岸橋數(shù)量一定的情況下，隨著AGV數(shù)量增加呈下降趨勢.

圖12 兩種啟發(fā)式算法的標(biāo)準(zhǔn)方差Fig.12 Sdev of two heuristic algorithms

圖13 兩種啟發(fā)式算法的求解時(shí)間Fig.13 Solution time of two heuristic algorithms

4 結(jié) 論

針對自動化碼頭雙循環(huán)AGV和場橋調(diào)度問題進(jìn)行集成研究，結(jié)合碼頭的工藝特性，對裝卸過程中集裝箱的流動進(jìn)行分析并建立數(shù)學(xué)模型；設(shè)計(jì)EAT和SP 兩種啟發(fā)式遺傳算法進(jìn)行求解.通過數(shù)值仿真，從平均值、最小值以及標(biāo)準(zhǔn)方差等性能指標(biāo)對兩種算法進(jìn)行對比分析，結(jié)果表明EAT 啟發(fā)式算法優(yōu)于SP啟發(fā)式算法.