田 宇，周 強，朱本飛

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

0 引 言

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

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

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

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

1.1 問題描述

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

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

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

(1)岸橋按照裝卸次序表從船舶上抓取相應的進口集裝箱，在岸橋裝卸節(jié)點將集裝箱釋放到AGV小車上，岸橋進入下一個任務的裝卸；

(2)AGV小車將集裝箱運到相應箱區(qū)的裝卸節(jié)點處，負責該箱區(qū)的場橋從AGV 上抓取該集裝箱后，AGV進入下一個任務的運輸；

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

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

1.2 數(shù)學模型

(1)假 設.

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

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

①參數(shù).

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

②變量.

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

(3)模型.

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

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

圖2中(a)～(i)表示集裝箱n為進口箱，各種情況下進口箱n在岸橋裝卸節(jié)點應滿足的時間關系如下.

(a)當前集裝箱n為岸橋的第一個任務，且為AGV小車的第一個任務時，即

(b)當前集裝箱n不是岸橋的第一個任務(前一任務為進口箱n′)，但為AGV小車的第一個任務時，即

(c)當前集裝箱n不是岸橋的第一個任務(前一任務為出口箱n′)，但為AGV小車的第一個任務時，即

(d)當前集裝箱n是岸橋q的第一個任務，但不是AGV小車的第一個任務(前一任務為岸橋q′負責的出口箱n′)時，即

(e)當前集裝箱n是岸橋q的第一個任務，但不是AGV小車的第一個任務(前一任務為堆存在箱區(qū)b的進口箱n′)時，即

(f)當前集裝箱n不是岸橋q的第一個任務(前一任務為進口箱n″)，也不是AGV小車的第一個任務(前一任務為堆存在箱區(qū)b的進口箱n′)時，即

(g)當前集裝箱n不是岸橋q的第一個任務(前一任務為進口箱n″)，也不是AGV小車的第一個任務(前一任務為岸橋q′負責的出口箱n′)時，即

(h)當前集裝箱n不是岸橋q的第一個任務(前一任務為出口箱n″)，也不是AGV小車的第一個任務(前一任務為堆存在箱區(qū)b的進口箱n′)時，即

(i)當前集裝箱n不是岸橋q的第一個任務(前一任務為出口箱n″)，也不是AGV小車的第一個任務(前一任務為岸橋q′負責的出口箱n′)時，即

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

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

(j)當前集裝箱n是箱區(qū)場橋的第一個任務，且為AGV小車的第一個任務時，即

(k)當前集裝箱n不是箱區(qū)場橋的第一個任務(前一任務為集裝箱n′)，但為AGV小車的第一個任務時，即

(l)當前集裝箱n是箱區(qū)b場橋的第一個任務，但不是AGV小車的第一個任務(前一任務為堆存于箱區(qū)b′的集裝箱n′)時，即

(m)當前集裝箱n是箱區(qū)b場橋的第一個任務，但不是AGV小車的第一個任務(前一任務為岸橋q′負責的集裝箱n′)時，即

(n)當前集裝箱n不是箱區(qū)b場橋的第一個任務(前一任務為集裝箱n′)，也不是AGV小車的第一個任務(前一任務為堆存于箱區(qū)b′的集裝箱n″)時，即

(o)當前集裝箱n不是箱區(qū)b場橋的第一個任務(前一任務為集裝箱n′)，也不是AGV小車的第一個任務(前一任務為岸橋q′負責的集裝箱n″)時，即

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

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

2.1 編 碼

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

2.2 目標函數(shù)及適應度函數(shù)

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

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

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

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

目標值為

2.3 交 叉

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

2.4 變 異

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

3 數(shù)值試驗及結果分析

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

3.1 參數(shù)設置

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

3.2 結果分析

數(shù)值試驗中，每種情況運行5個算例，每個算例運行5次，分別取平均值、最小值、標準方差以及運行時間的平均值對比分析.結果如圖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ī)則的標準方差Fig.8 Sdev of EAT rule

圖9 SP 規(guī)則標準方差Fig.9 Sdev of SP rule

圖4～圖7分別是“任務量30-岸橋2”“任務量50-岸橋3”“任務量70-岸橋4”“任務量90-岸橋5”時，AGV數(shù)量從4～10個的算例平均值、最小值.兩種啟發(fā)式規(guī)則計算結果隨著AGV的數(shù)量增加，最大完工時間會變小，變小的趨勢會變得平緩，說明AGV數(shù)量的增加可以提升碼頭的效率，提升的程度有上限.從圖8和圖9中得到：隨著任務數(shù)量、岸橋數(shù)量的增加，穩(wěn)定性會有一定程度的下降，但是兩種啟發(fā)式算法的穩(wěn)定性比較理想.圖8中，當任務量小于70、岸橋數(shù)量小于5時，“最早可獲得時間”的啟發(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是不同任務數(shù)量、岸橋數(shù)量、AGV數(shù)量下平均值、最小值、標準方差下的曲線，可以看出：“最早可獲得時間”的啟發(fā)式規(guī)則在優(yōu)化目標以及求解穩(wěn)定性上都要優(yōu)于“最短路徑”啟發(fā)式算法.圖13是兩種啟發(fā)式算法的求解時間，兩種算法的求解時間差別不大，都比較理想；在任務、岸橋數(shù)量一定的情況下，隨著AGV數(shù)量增加呈下降趨勢.

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

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

4 結 論

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