自動化碼頭裝卸混合模式下QC、LAGV及ARMG協(xié)同調度方法

添玉　王建彬,陳晶晶　范會方

摘要：

為解決復雜的自動化碼頭設備協(xié)同調度問題，考慮碼頭各作業(yè)間的相互作用和制約，以最小化船舶在港時間和主要設備作業(yè)成本為目標，構建新的裝卸混合模式下岸橋（quay crane， QC）、頂升式自動引導車（lifting automated guided vehicle， LAGV）及自動化軌道吊（automated rail mounted gantry crane， ARMG）協(xié)同調度的混合整數非線性規(guī)劃模型。提出一種遺傳算法與啟發(fā)式策略結合的協(xié)同調度方法，實現在系統(tǒng)整體性能最優(yōu)情況下的設備作業(yè)序列優(yōu)化。該模型能充分保障QC、LAGV、ARMG之間的協(xié)同性，并引入QC調度的主要約束，更利于與QC調度模型進一步集成。數值試驗證明了該方法的有效性，可為碼頭裝卸作業(yè)調度提供決策支持。

關鍵詞：

自動化碼頭； 自動引導車（AGV）； 自動化軌道吊； 協(xié)同調度； 遺傳算法（GA）

中圖分類號： U691.3

文獻標志碼： A

Abstract：

In order to solve the complex collaborative scheduling problem of automated terminal equipments， considering the interaction and restriction among various operations in terminals， a new mixed integer nonlinear programming model is constructed for quay cranes （QCs）， lifting automated guided vehicles （LAGVs） and automated rail mounted gantry cranes （ARMGs） collaborative scheduling under the mixed loading and unloading mode. The model objectives are to minimize the ship turnround time at a port and to minimize the operation cost of key equipments. A collaborative scheduling method based on the genetic algorithm and the heuristic strategy is proposed to obtain an optimized operation sequence of equipments under the condition of the optimal overall performance of the system. The model fully guarantees the cooperativity of QCs， LAGVs and ARMGs， and the main constraints of QC scheduling are introduced， which is more conducive to the further integration with QC scheduling model. A numerical test is taken to demonstrate the effectiveness of the method. It can provide decision support for loading and unloading operations of automated terminals.

Key words：

automated terminal； automated guided vehicle （AGV）； automated rail mounted gantry crane； collaborative scheduling； genetic algorithm （GA）

0引言

由于集裝箱碼頭裝卸工藝、作業(yè)空間和設備配置等限制，優(yōu)化各環(huán)節(jié)調度成為提高碼頭整體效率的重要途徑。目前，已有學者對包括水平運輸設備在內的集裝箱碼頭集成調度問題進行了研究。CAO等[12]針對出口集裝箱分別建立了解決單個岸橋（quay crane， QC）與多輛集卡協(xié)調分配的混合整數模型和集卡與龍門吊集成調度模型，前者設計了遺傳算法和改進約翰遜規(guī)則的啟發(fā)式算法來提高求解速率，后者基于Benders變異對問題進行求解。秦天保等[3]針對集裝箱QC與集卡集成調度問題，以卸船完工時間最小為目標，采用約束規(guī)劃技術建模求解。CHEN等[4]研究了集裝箱碼頭QC與集卡集成調度問題，建立了帶約束的規(guī)劃模型，并設計了一個三階段算法。韓曉龍等[5]考慮集卡作業(yè)時間不確定和動態(tài)性到達的情況，建立了集卡與QC協(xié)同調度模型并設計了改進的遺傳算法進行求解。TANG等[6]建立了QC與集卡聯合調度模型，并用改進的粒子群算法解決進出口箱裝卸作業(yè)問題。HE等[7]建立了傳統(tǒng)集裝箱碼頭QC、場橋和集卡的集成調度模型，提出了基于仿真的遺傳算法與粒子群算法結合的優(yōu)化方法。

MEERSMANS等[8]最早研究了自動化碼頭多類型設備的集成調度問題，提出了分支定界法及啟發(fā)式算法，但僅考慮了裝船作業(yè)情形。LAU等[9]分析了碼頭核心設備之間的協(xié)調關系，提出了設備集成調度模型，設計分層遺傳算法并結合啟發(fā)式策略進行求解。HOMAYOUNI等[10]提出自動化碼頭自動引導車（automated guided vehicle， AGV）和QC同時調度的混合整數規(guī)劃模型，并設計了兩階段啟發(fā)式遺傳算法進行求解。DKHIL等[11]考慮碼頭多種資源之間的相互作用與制約，提出了QCAGVASC（automated stacking crane）集成模型。LUO等[1213]分別考慮了裝卸同時進行的情形和單卸的情形，研究了自動化碼頭AGV調度規(guī)則和確定集裝箱堆放位置的新方法，通過數值試驗評估算法的有效性。

集裝箱碼頭運作由眾多環(huán)節(jié)相互合作完成，且各環(huán)節(jié)相互影響和制約，但當前絕大多數關于調度的研究集中在傳統(tǒng)碼頭領域，缺乏多類型設備的深度集成，鮮有考慮邊裝邊卸作業(yè)模式及工藝革新造成的調度復雜性。少數研究集成調度的文獻存在的不足有：（1）忽略了QC調度中任務約束的影響；（2）假設場橋作業(yè)序列完全遵從QC裝卸序列。因此，本文將以頂升式自動引導車（lifting automated guided vehicle，LAGV）為水平運輸設備的自動化碼頭裝卸系統(tǒng)作為對象，引入QC調度的主要約束，提出新的QC、LAGV和自動化軌道吊（automated rail mounted gantry crane，ARMG）協(xié)同調度模型和算法，實現系統(tǒng)性能的改善。

1問題描述

碼頭設備資源的調度受碼頭工藝的制約和影響，而碼頭工藝創(chuàng)新為碼頭作業(yè)效率的提升提供了重要的途徑。這里研究雙車QC、LAGV和ARMG組成的新型自動化集裝箱碼頭工藝，其布局見圖1。LAGV所在的QC作業(yè)區(qū)位于QC后伸距下方，各車道為單向行駛，行車方向依據船頭朝向和裝、卸箱量的比例設定，以減少倒箱門現象對車輛和道路的干擾。堆場采用垂直于岸線的布局，堆場海側行駛區(qū)采用雙向車道，相鄰車道行駛方向相反，便于車輛在堆場海側交換區(qū)的進出。緩沖車道位于QC作業(yè)區(qū)與堆場海側交換區(qū)之間，既作為LAGV的臨時等待區(qū)，又作為岸邊與堆場之間的連接通道，以縮短水平運輸距離。

與傳統(tǒng)工藝相比，LAGV負責水平運輸，堆場每個箱區(qū)海側布置由一組支架組成的交換區(qū)，作為集裝箱的臨時緩沖存放點，以緩解水平運輸能力與堆場裝卸能力的矛盾，提高系統(tǒng)作業(yè)效率。然而，交接方式的靈活性增加了設備調度的復雜性，這對調度方法提出了更高要求。

碼頭裝卸系統(tǒng)是一個復雜的、動態(tài)的并行工作系統(tǒng)，其作業(yè)類型包括將進口集裝箱運輸到堆場側和將出口集裝箱運輸到船側。以裝船作業(yè)為例簡述運作決策過程：首先，船舶進港后，碼頭根據船舶配載圖、堆場分配計劃等，制定QC分配和調度計劃；然后，由ARMG從堆場指定位置提取集裝箱，經緩沖支架交給指定LAGV；最后，由指定LAGV運輸集裝箱到指定QC。若LAGV晚到則會造成QC等待，增加船舶的在港時間。卸船過程相反。

顯然，QC裝卸作業(yè)、水平運輸作業(yè)與堆場設備作業(yè)相互關聯，必須制定統(tǒng)籌全局的設備協(xié)同調度計劃。以往大多研究僅考慮單獨裝箱或卸箱作業(yè)，即使涉及QC同時裝卸，也未考慮在堆場箱區(qū)混合堆存情況下如何提高調度協(xié)同性問題。這樣的簡化會極大地降低全局性能。因此，本文研究更一般的情形：在裝卸混合模式下，船舶的進出口集裝箱混合堆存在不同箱區(qū)，QC邊裝邊卸，LAGV靈活服務多臺QC且可雙循環(huán)運輸，同時箱區(qū)的ARMG邊存邊取。調度方案的優(yōu)劣由兩方面因素評價：（1）LAGV自身效率。為降低空駛率，將LAGV總行駛時間作為評價指標。（2）QC和ARMG的效率。集裝箱船在港時間越長，其花費成本就越大，故將船舶在港時間和ARMG移動時間作為評價指標。

2自動化設備集成調度模型

2.1假設條件

（1）集港在裝卸船作業(yè)之前已經完成，疏港在裝卸船作業(yè)之后才進行；（2）計劃期內的船舶配載計劃、泊位計劃、堆場箱位計劃和QC調度計劃已知，這里QC調度的任務以簇[14]形式定義，且簇任務內集裝箱裝卸順序和簇之間的約束關系確定；（3）QC、LAGV和ARMG數量已知，且每個設備一次只處理一個集裝箱；（4）LAGV、ARMG（空/重載）和QC的行駛速度及其裝卸效率已知；（5）進、出口集裝箱允許堆存在堆場同一箱區(qū)，每個箱區(qū)的集裝箱僅由海側ARMG負責裝卸，已知LAGV與任意兩個操作節(jié)點之間的距離，忽略LAGV和ARMG在堆場交換區(qū)等待支架空閑的時間。

2.2符號變量說明

常量符號如下。

K表示QC的集合，Q表示ARMG的集合，V表示LAGV的集合。ve和vd分別表示為ARMG提供初始和結束虛擬任務的虛擬QC，vs和vf分別表示為LAGV提供初始和結束虛擬任務的虛擬QC。mk表示第k臺QC執(zhí)行的任務數量，k∈K。（k，i）為箱任務編號，表示第k臺QC 的第i個箱任務，k∈K，i=1，2，…，mk。eki和dki分別為QC在其作業(yè)區(qū)開始和結束箱任務（k，i）的事件，當箱任務（k，i）為卸船任務時其分別表示QC開始落箱到LAGV上的事件和結束落箱到LAGV上的事件，當箱任務（k，i）為裝船任務時其分別表示QC從LAGV上開始提箱的事件和結束落箱到船上的事件，k∈K，i=1，2，…，mk。 Eaki表示LAGV在堆場海側交換區(qū)開始作業(yè)箱任務（k，i）的事件，當箱任務（k，i）為卸船任務時其表示LAGV開始將箱頂升到支架的事件，當箱任務（k，i）為裝船任務時其表示LAGV開始從支架處接箱的事件，k∈K，i=1，2，…，mk。Ebki表示ARMG在堆場海側交換區(qū)開始作業(yè)箱任務（k，i）的事件，當箱任務（k，i）為卸船任務時其表示ARMG開始從支架上抓箱的事件，當箱任務（k，i）為裝船任務時其表示ARMG開始放箱到支架上的事件，k∈K，i=1，2，…，mk。TC表示有先后順序要求的事件eki的集合，TD表示卸船任務對應的事件eki的集合，TL表示裝船任務對應的事件eki的集合，Nq表示第q臺ARMG執(zhí)行的Ebki的集合，k∈K，i=1，2，…，mk，q∈Q。

變量符號如下。ski表示第k臺QC執(zhí)行eki的實際準備就緒時刻，Hk（i-1）i表示第k臺QC完成ek（i-1）后執(zhí)行eki的全部準備時間，yki表示eki的實際發(fā)生時刻，ψki表示dki的實際發(fā)生時刻，Δwki表示eki與dki發(fā)生時刻的間隔時間，Yaki表示Eaki的發(fā)生時刻，Ybki表示Ebki的發(fā)生時刻，Ski表示eki與Eaki之間的間隔時間，ΔSki表示Eaki與Ebki之間的間隔時間，k∈K，i=1，2，…，mk。Tki，lj表示

ARMG從

Ebki發(fā)生的位置到Eblj發(fā)生的位置的純移動時間，Rki，lj表示ARMG完成Ebki后執(zhí)行Eblj需要的調整時間，k∈{ve}∪K，l∈{vd}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mve=Q。tki，lj表示LAGV從eki發(fā)生的位置到elj發(fā)生的位置耗費的時間，cki，lj表示LAGV完成eki后去執(zhí)行elj需要的調整時間，rki，lj表示eki與Ealj之間LAGV的調整時間，k∈{vs}∪K，l∈{vf}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mvs=V。

決策變量如下。ki，lj為01變量，若同一輛LAGV完成eki后緊接著完成elj則其值為1，否則為0，k∈{vs}∪K，l∈{vf}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mvs=mvf=V。φki，lj為01變量，若同一臺ARMG完成Ebki后緊接著完成Eblj則其值為1，否則為0，k∈{ve}∪K，l∈{vd}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mve=mvd=Q。

2.3目標函數及約束

下式中，除有特殊限定外：

k，l∈K；i=1，2，…，mk；j=1，2，…，ml。

S1=min（maxk∈K ψkmk）

（1）

S2=min k∈{ve}∪K

i

l∈K∪{vd}

j（Tki，ljφki，lj）

（2）

S3=min k∈{vs}∪K i

l∈K∪{vf}

j（tki，ljφki，lj）

（3）

l∈{vf}∪K

jki，lj=1，k∈{vs}∪K

（4）

k∈{vs}∪K

iki，lj=1，l∈{vf}∪K

（5）

l∈{vd}∪K

jφki，lj=1，k∈{ve}∪K

（6）

k∈{ve}∪K

iφki，lj=1，l∈{vd}∪K

（7）

ylj-max（yki+cki，lj，slj）≥M（ki，lj-1），

k∈{vs}∪K

（8）

Yblj-（Ybki+Rki，lj）≥M（φki，lj-1），

k∈{ve}∪K

（9）

Yalj-（yki+rki，lj）≥M（ki，lj-1），

k∈{vs}∪K

（10）

yki≥ski

（11）

ski≥yk（i-1）+Hk（i-1）i， i=2，3，…，mk

（12）

yki≥Yaki+Ski，eki∈TL

（13）

Yaki≥Ybki+ΔSki，eki∈TL

（14）

Yaki≥yki+Ski，eki∈TD

（15）

Ybki≥Yaki+ΔSki，eki∈TD

（16）

Ybki-Yblj≥0，Ebki，Eblj∈Nq；yki>ylj；

eki∈TD；elj∈TL； q∈Q；

若k≠l則eki，elj∈TC

（17）

ψki-yki≥Δwki

（18）

式（1）～（3）為目標函數，分別表示最小化所有QC中最大完工時刻、最小化ARMG總移動時間、最小化LAGV的總行駛時間。式（4）～（7）表示LAGV或ARMG一次只能執(zhí)行一個任務，一個任務一旦由某一ARMG或LAGV執(zhí)行就不能中斷，且每個任務都要被執(zhí)行。式（8）和（9）表示由同一裝卸運輸設備執(zhí)行的相鄰任務的時間邏輯關系，式（8）表示同一輛LAGV完成

eki后去執(zhí)行elj需要有時間cki，lj準備，以及只有LAGV到達和QC自身準備就緒，QC才能開始裝卸集裝箱。式（9）表示同一臺ARMG完成Ebki后去執(zhí)行Eblj需要有時間Rki，lj準備。式（10）表示不同作業(yè)環(huán)節(jié)的時間邏輯關系，如果任務（k，i）和（l，j）是同一輛LAGV的兩個相鄰任務，那么LAGV完成eki后需要時間rki，lj調整才能執(zhí)行Ealj。式（11）表示eki的實際發(fā)生時刻最小為最早可能發(fā)生時刻。式（12）表示QC執(zhí)行ek（i-1）后需時間Hk（i-1）i準備才能執(zhí)行任務eki。式（13）和（14）表示某裝船任務（k，i）的相鄰作業(yè)環(huán)節(jié)間的時間邏輯關系，此類任務的設備操作順序是ARMG—LAGV—QC，因此LAGV完成Eaki的時刻與Eaki和eki的調整時間之和不會超過QC完成eki的時刻，ARMG完成Ebki時刻與Eaki和Ebki的調整時間之和不會超過LAGV完成Eaki的時刻。同理，式（15）和（16）表示某卸船任務（k，i）的相鄰作業(yè)環(huán)節(jié)間的時間邏輯關系，此類任務的設備操作順序是QC—LAGV—ARMG。式（17）表示每一臺ARMG執(zhí)行QC的任務時其作業(yè)順序在先裝后卸情形下需要符合QC作業(yè)順序和其任務約束關系。式（18）表示QC裝卸每個集裝箱需要時間Δwki。

值得注意的是，上述模型與已有文獻相比，主要有3點不同。（1）LAU等[9]的研究將ARMG調度序列歸結為QC調度序列的子序列，意味著ARMG調度必須遵從QC調度，由式（19）約束：

Yki-Ykj≥0，Ebki∈Nq；i>j；q∈Q

（19）

而本文模型考慮船舶集裝箱裝卸混合作業(yè)時ARMG與 QC調度的協(xié)同性，體現在將式（19）放松為式（17），表明ARMG除先裝后卸情形外，可以按照靈活作業(yè)順序操作，無須遵從QC調度序列。（2）所有類似文獻均研究傳統(tǒng)AGV工藝，在堆場箱區(qū)只有AGV與 ARMG剛性銜接，而本文針對緩沖支架系統(tǒng)，特別定義了Yaki和Ybki兩個狀態(tài)變量，增加LAGV、ARMG和支架三者之間銜接的靈活性。（3）考慮QC調度任務約束關系，由式（17）體現，以利于與QC調度模型進一步集成。

3協(xié)同調度方法及算法設計

3.1協(xié)同調度思想

傳統(tǒng)調度方法[9]規(guī)定水平運輸設備和場橋的作業(yè)序列必須遵從QC作業(yè)順序。該方法一般適用于單裝/單卸模式，而在裝卸混合模式下雖然能夠降低集成調度的復雜性，縮小問題解空間，但會忽略設備作業(yè)協(xié)同性，甚至會將最優(yōu)解排除。

本文提出的協(xié)同調度策略的特點在于，要求水平運輸設備必須遵從QC或約束關系的任務順序，而放松ARMG與QC作業(yè)的一致性約束，除QC先裝后卸作業(yè)情形外，允許ARMG自主靈活地確定作業(yè)序列，見圖2。

3.2結合啟發(fā)式策略的遺傳算法設計

在QC作業(yè)序列的基礎上，基于遺傳算法，采用協(xié)同調度策略優(yōu)化ARMG作業(yè)序列，并采用啟發(fā)式LAGV指派策略優(yōu)化車輛運輸任務，見圖3。

3.2.1染色體編碼和解碼

基于QC調度計劃對箱任務采用自然數編碼，每個染色體代表所有箱任務的一種隨機排列，每個自然數代表箱任務編號，染色體長度等于箱任務數量。染色體序列需結合LAGV指派和ARMG調度的啟發(fā)式策略進行解碼，確定各ARMG及LAGV的任務順序。

在上述編碼基礎上，設計ARMG調度序列的啟發(fā)式策略的步驟如下：（1）從編碼序列中抽取每臺ARMG的任務序列，獲得各臺ARMG的隨機箱序列；（2）針對ARMG隨機任務序列中的任意兩個任務，判斷兩個任務是否屬于同一輛QC，若是則轉步驟（3），否則繼續(xù)尋找，直到所有的兩個任務組合都尋找過一次為止；（3）判斷兩個任務是否是同一任務類型，若是則轉步驟（2），否則判斷這兩個任務在QC作業(yè)序列中的作業(yè)順序是否是先裝后卸，若是則將ARMG中這兩個任務的順序調整成QC作業(yè)順序，然后轉步驟（2）。最終獲得符合QC先裝后卸作業(yè)約束的ARMG箱任務序列。

若在裝卸混合模式下存在同箱區(qū)且在同一QC序列中先卸后裝兩個附近的任務，則采用上述啟發(fā)式策略有利于避免各設備的串行完成，實現并行協(xié)同調度，降低過多等待，提高碼頭效率。

碼頭常以船舶在港時間最短為首要目標，因此采用如下3種基于時間型啟發(fā)式規(guī)則的LAGV指派策略，逐一為任意箱任務序列中的集裝箱指派合適的LAGV。LAGV完成當前運輸任務后隨即去執(zhí)行后續(xù)任務；LAGV卸船箱任務的起始位置在QC作業(yè)區(qū)；LAGV裝船箱任務的起始位置在堆場海側交換區(qū)。（1）先到先指派策略：針對某一運輸任務，選擇最快完成前項任務抵達該任務起始位置的LAGV。（2）適合裝箱位置就緒策略：針對某一運輸任務，以起重設備作業(yè)該任務的準備就緒時刻（若裝船，則是ARMG準備就緒時刻；若卸船，則是QC準備就緒時刻）為基準，從所有車輛中選擇完成前項任務后最早抵達該任務起始位置的LAGV。（3）適合QC就緒策略：針對某一運輸任務，以QC就緒時刻為基準，從所有車輛中選擇完成前項任務后最早空駛（卸船箱）或提箱（裝船箱）至QC作業(yè)區(qū)的LAGV。

3.2.2不可行和重復序列的修正策略

隨機生成或迭代更新的染色體可能存在不可行或重復個體的情況，故需進行修正。針對不可行序列的修正策略：將箱任務序列滿足已知QC作業(yè)箱任務順序及簇任務約束關系。針對種群中重復序列的修正策略：搜尋每代的重復個體，并采用部分逆反變異操作生成新的個體替換原染色體，得到新的種群作為下一代。這樣不僅降低重復個體存在的概率，而且保持了種群多樣性。

3.2.3染色體選擇、交叉、變異操作

采用輪盤賭的方法對染色體進行選擇；采用部分匹配交叉（圖4）和部分逆反變異（圖5）的方法對染色體進行交叉、變異操作。

3.2.4適應度函數設置

以最小化箱任務最大結束時刻為首要目標，并通過設置加權系數，將適應度函數設計為一種組合函數，其由箱任務最大結束時刻、QC累計等待時間、每臺QC的箱任務均衡程度、LAGV的總行駛時間和ARMG總移動時間組成。鑒于最小化問題，將適應度函數設為上述組合函數的倒數，具體計算取決于箱任務的LAGV指派以及各設備之間的交接時刻，狀態(tài)更新流程圖見圖6。

4案例驗證與結果分析

4.1案例說明

以采用“雙車QC+ LAGV+ ARMG”工藝系統(tǒng)的青島某自動化集裝箱碼頭為例，碼頭整體布局和水平運輸交通規(guī)則見圖1。LAGV所在的QC作業(yè)區(qū)共7條行車道，每條車道寬4 m，其中4條為裝卸車道，3條為穿越車道，裝卸車道成對布置，并與穿越車道相間隔。堆場海側行駛區(qū)共有6條雙向車道，且相鄰車道行駛方向相反。各裝卸運輸設備的速度見表1。

某船需要裝卸的進出口集裝箱在船上的位置及簇任務劃分和約束關系可通過船舶配載計劃獲得。假設QC調度計劃已知，QC抓/放箱操作時間均為10 s，QC小車在QC作業(yè)區(qū)與船之間的水平行駛時間為40 s，且在QC作業(yè)區(qū)車道上的行駛方向為逆時針方向；ARMG初始位置在堆場海側交換區(qū)（包含4個緩沖支架和1個空車道），堆場數量為10個，每個堆場僅海側ARMG工作；LAGV初始位置在緩沖車道，各設備完成各自所有任務后必須回到初始位置。

考慮算法運算效率，通過多次組合試驗確定算法相關參數。初始種群大小為50，最大遺傳代數為100，交叉概率為0.85，變異概率為0.1。本文試驗均采用MATLAB R2014a編程實現算法，并在Intel（R） Core（TM） i76700HQ CPU @2.6 GHz處理器、8 GB內存的電腦上運行得到試驗結果。

4.2協(xié)同調度求解結果分析

4.2.1算法的優(yōu)化性能分析及魯棒性分析

設計7組中等規(guī)模仿真算例，從計算時間和結果進行比較，驗證所提算法的優(yōu)化性能。采用CPLEX 12.2求解器和遺傳算法分別求解算例。在CPLEX求解過程中，將模型的非線性約束式（8）劃分成2個線性約束，結果見表2。表2中最后一列顯示了采用本文算法得到的加權目標函數值與最優(yōu)值之間的偏差。試驗發(fā)現，計算耗時隨著任務數的增加快速上升，對30個以上的箱任務問題無法在有效時間內得到結果，而用遺傳算法盡管不能獲得最優(yōu)解，但其解與最優(yōu)解的偏差在適當范圍內，且在大規(guī)模任務的計算效率上具有優(yōu)勢。

不同任務規(guī)模和LAGV數量下算法的魯棒性變化如圖7所示：魯棒性指標在適當范圍（0～4%）內波動，其最大值為3.90%，平均值為2.47%，說明算法有較好的魯棒性。

4.2.2結果比較分析

根據設置的案例數據，采用結合啟發(fā)

式策略的遺傳算法對自動化設備協(xié)同調度模型進行求解。試驗選擇2個因素作為變量：LAGV數量，設置在8與24之間；每個計劃期內的任務規(guī)模，設置成40、50、60、70和80。所需其他數據（如LAGV初始位置、集裝箱類型及其在堆場中的位置）均采用隨機模擬方式產生。因此，不同變量因素下有多種組合，每種組合隨機產生10組數據，每組數據重復試驗操作5次，取其平均值來減少算法誤差。

4.2.2.1協(xié)同調度方法的比較分析

為分析系統(tǒng)性能的靈敏性，將LAGV數量和每個計劃期內的任務規(guī)模作為變化因素，得到不同調度方法的結果，見圖8。在給定LAGV數量的情況下，2種調度方法的加權目標函數值均隨著任務規(guī)模的增加而增加，但平均每個任務的加權目標函數值在下降。這表明任務規(guī)模變大時系統(tǒng)將獲得更好的性能。但實際上，由于碼頭各種中斷事件的發(fā)生，如起重機或LAGV等設備故障，不可避免地需要進行再調度。因此，可結合實際情況，選取一個適當的任務規(guī)模以權衡計算量和系統(tǒng)性能的損失。在給定任務規(guī)模和LAGV數量的情況下，本文提出的協(xié)同調度方法的加權目標函數值小于傳統(tǒng)調度方法的加權目標函數值。這表明，在碼頭實際管理中，充分優(yōu)化ARMG作業(yè)序列有助于提高其與QC和LAGV之間的協(xié)調性，達到系統(tǒng)整體性能平均8.7%的提升。

4.2.2.2不同LAGV指派策略比較分析

圖9為不同LAGV指派策略對整體調度結果的影響。在3種LAGV指派策略下，隨著LAGV數量的增多平均每個任務的加權目標函數值均在下降。圖9中的數據表明，不同的LAGV指派策略無絕對的優(yōu)劣，不同的策略適合不同的設備配置比例。由此可見，在碼頭實際管理中，根據設備配置比例合理利用不同LAGV指派策略比利用單一LAGV指派策略效果更好，更有助于碼頭整體效率的提升。

圖10為不同LAGV指派策略對QC等待時間的影響。在LAGV和QC配置比例較小時：LAGV本屬于瓶頸資源，采用先到先指派策略更易造成無效等待，從而加劇水平運輸設備的緊缺性，最終導致其他QC過多等待；采用適合QC就緒策略，即始終選擇適合的QC，有助于減少QC等待時間。因此，在此情形下采用適合QC就緒策略的效果優(yōu)于采用適合裝箱位置就緒策略的效果。在LAGV和QC配置比例較大時，這兩種策略對QC等待時間的影響無明顯差異。

圖11為不同LAGV指派策略對ARMG移動時間的影響。在LAGV和QC配置比例較小時，LAGV本屬于瓶頸資源，采用先到先指派策略和適合裝箱位置就緒策略更易導致LAGV等待發(fā)生，從而加劇水平運輸運力的緊張，導致其他ARMG過多等待，進而影響到ARMG的調度序列，使得重進重出比例下降，因此此時采用適合QC就緒策略效果較好。在LAGV與QC配置比例較大時，QC和ARMG效率成為關鍵，而采用先到先指派策略有助于減少LAGV空駛率，從而提升運力，最終配合ARMG優(yōu)

化作業(yè)序列，降低移動時間，因此此時先到先指派策略優(yōu)于適合裝箱位置就緒策略。

圖12為不同LAGV指派策略對LAGV行駛時間的影響。采用先到先指派策略，即選擇最早到達的、最近的LAGV有利于減少空駛率，從而更有利于降低LAGV行駛成本。相對于適合裝箱位置就緒策略，適合QC就緒策略的目的在于減少無效等待時間，故空駛率不會太高；相對于先到先指派策略，適合QC就緒策略用在卸箱任務時容易產生較高空駛率，且用于裝船任務時更傾向于選擇無效時間最短的車輛，故空駛率較高。總之，從車輛行駛成本看，適合QC就緒策略是3種指派策略中的一個折中策略，其目的在于優(yōu)化QC等待時間。因此，如圖12所示，該策略下的曲線變化平緩，且位于其他兩種策

略對應的曲線之間。

5結束語

碼頭設備的協(xié)同調度有利于減少船舶在港時間，提高碼頭整體作業(yè)效率。本文在以往研究的基礎上構建新的協(xié)同調度模型并設計改進的遺傳算法進行求解，其創(chuàng)新之處在于：考慮了LAGV結合具有有限堆場緩存空間的自動化集裝箱碼頭裝卸新工藝的作業(yè)特點；考慮了裝卸混合模式下設備調度的協(xié)同性；引入了QC調度的主要約束。最終通過數值試驗與傳統(tǒng)調度方法的對比驗證了本文模型和算法的有效性。

參考文獻：

[1]

CAO Jinxin， SHI Qixin， LEE DerHorng. Integrated quay crane and yard truck schedule problem in container terminals[J]. Tsinghua Science & Technology， 2010， 15（4）： 467474.

[2]CAO Jinxin， LEE DerHorng， CHEN Jianghang， et al. The integrated yard truck and yard crane scheduling problem： Benders decompositionbased methods[J]. Transportation Research Part E： Logistic & Transportation Review， 2010， 46（3）： 344353.

[3]秦天保， 彭嘉瑤， 沙梅. 帶任務順序約束的岸橋集卡集成調度約束規(guī)劃模型[J]. 上海海事大學學報， 2013， 34（3）： 17.

[4]CHEN Lu， LANGEVIN A， LU Zhiqiang. Integrated scheduling of crane handling and truck transportation in a maritime container terminal[J]. European Journal of Operational Research， 2013， 225（1）： 142152.

[5]韓曉龍， 牟少莉. 基于CHC算法的集卡與岸橋協(xié)調調度優(yōu)化問題[J]. 武漢理工大學學報（信息與管理工程版）， 2014， 36（2）： 233236.

[6]TANG Lixin， ZHAO Jiao， LIU Jiyin. Modeling and solution of the joint quay crane and truck scheduling problem[J]. European Journal of Operational Research， 2014， 236（3）： 978990.

[7]HE Junliang， HUANG Youfang， YAN Wei， et al. Integrated internal truck， yard crane and quay crane scheduling in a container terminal considering energy consumption[J]. Expert Systems with Applications， 2015， 42（5）： 24642487.

[8]MEERSMANS P J M， WAGELMANS A P M. Effective algorithms for integrated scheduling of handling equipment at automated container terminals[R]. Rotterdam： Erasmus University， 2001.

[9]LAU H Y K， ZHAO Ying. Integrated scheduling of handling equipment at automated container terminals[J]. Annals of Operations Research， 2008， 112（2）： 665682.

[10]HOMAYOUNI S M， HONG T S， ISMAIL N， et al. A genetic algorithm for optimization of simultaneous scheduling of AGVs and QCs in container terminals[C/OL]//11th Asia Pacific Industrial Engineering and Management System. Melaka， Malaysia， December 710， 2010. http：//www.apiems.org/archive/apiems2010/paper.php.

[11]DKHIL H， YASSINE A， CHABCHOUB H. Optimization of container handling systems in automated maritime terminal[J]. Studies in Computational Intelligence， 2013， 457： 301312.

[12]LUO Jiabin， WU Yue. Modelling of dualcycle strategy for container storage and vehicle scheduling problems at automated container terminals[J]. Transportation Research Part E： Logistics & Transportation Review， 2015， 79： 4964.

[13]LUO Jiabin， WU Yue， MENDES A B. Modelling of integrated vehicle scheduling and container storage problems in unloading process at an automated container terminal[J]. Computers & Industrial Engineering， 2016， 94： 3244.

[14]BIERWIRTH C， MEISEL F. A survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research， 2010， 202（3）： 615627.

（編輯趙勉）