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

摘要：

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

關(guān)鍵詞：

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

中圖分類號： U691.3

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

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

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

1問題描述

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

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

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

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

2自動化設(shè)備集成調(diào)度模型

2.1假設(shè)條件

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

2.2符號變量說明

常量符號如下。

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

變量符號如下。ski表示第k臺QC執(zhí)行eki的實際準(zhǔn)備就緒時刻，Hk（i-1）i表示第k臺QC完成ek（i-1）后執(zhí)行eki的全部準(zhǔn)備時間，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需要的調(diào)整時間，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需要的調(diào)整時間，rki，lj表示eki與Ealj之間LAGV的調(diào)整時間，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目標(biāo)函數(shù)及約束

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

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

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

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

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

（19）

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

3協(xié)同調(diào)度方法及算法設(shè)計

3.1協(xié)同調(diào)度思想

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

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

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

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

3.2.1染色體編碼和解碼

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

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

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

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

3.2.2不可行和重復(fù)序列的修正策略

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

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

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

3.2.4適應(yīng)度函數(shù)設(shè)置

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

4案例驗證與結(jié)果分析

4.1案例說明

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

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

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

4.2協(xié)同調(diào)度求解結(jié)果分析

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

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

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

4.2.2結(jié)果比較分析

根據(jù)設(shè)置的案例數(shù)據(jù)，采用結(jié)合啟發(fā)

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

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

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

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

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

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

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

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

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

略對應(yīng)的曲線之間。

5結(jié)束語

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

參考文獻(xiàn)：

[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]秦天保， 彭嘉瑤， 沙梅. 帶任務(wù)順序約束的岸橋集卡集成調(diào)度約束規(guī)劃模型[J]. 上海海事大學(xué)學(xué)報， 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é)調(diào)調(diào)度優(yōu)化問題[J]. 武漢理工大學(xué)學(xué)報（信息與管理工程版）， 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.

（編輯趙勉）