自動化碼頭起重機和自帶提升功能的AGV的集成調(diào)度

添玉 +王建彬 +范會方

摘要：為深入研究新工藝帶來的自動化碼頭設(shè)備集成調(diào)度問題，針對自動化碼頭的一種自帶提升功能的自動導(dǎo)引小車（LAGV）和緩沖支架系統(tǒng)，提出新的設(shè)備集成調(diào)度框架?？紤]不同設(shè)備之間的相互關(guān)聯(lián)和制約的協(xié)同關(guān)系，將岸橋分配調(diào)度與LAGV、場橋調(diào)度分開，合理定義兩種任務(wù)（兩個問題）的劃分方式，建立兩個多目標(biāo)混合整數(shù)規(guī)劃模型。設(shè)計一種具有內(nèi)外層關(guān)聯(lián)的適應(yīng)度函數(shù)的雙層遺傳算法。相對傳統(tǒng)聯(lián)合調(diào)度算法，該算法平衡了計算復(fù)雜性與調(diào)度均衡性。最后的數(shù)值試驗證明了模型和算法的有效性。從岸橋數(shù)量、任務(wù)規(guī)模、AGV數(shù)量和調(diào)度策略等對岸橋等待時間的影響上，對采用LAGV的系統(tǒng)和采用傳統(tǒng)AGV的系統(tǒng)進行比較，為自動化碼頭裝卸作業(yè)調(diào)度提供決策支持。

關(guān)鍵詞：

自動化碼頭； 自動導(dǎo)引小車（AGV）； 集成調(diào)度； 遺傳算法（GA）； 啟發(fā)式策略

中圖分類號： U691.3

文獻標(biāo)志碼： A

Integrated scheduling of cranes and AGVs with lifting function in automated container terminals

TIAN Yu1， WANG Jianbin1， FANG Huifang2

（1. Logistics Engineering College， Shanghai Maritime University， Shanghai 201306， China；

2. Software Automation Department， ZPMC Electric， Shanghai 200125， China）

Abstract：

In order to further study the issue of integrated equipment scheduling caused by new techniques in automated terminals for automated guided vehicles with lifting platforms （called LAGV） and buffer support system in automated terminal， a new integrated scheduling framework is proposed. Considering the interrelated and constrained cooperativeness relations among different equipments， it is divided into two problems， the quay crane allocation/scheduling problem and the LAGV and yard crane scheduling problem. By reasonably defining the division of two tasks （two problems）， two multiobjective mixedinteger programming models are established sequentially. A twolayer genetic algorithm is developed， where a fitness function is proposed to interlink two layers. The algorithm leads to the tradeoff between the computational complexity and the scheduling equilibrium compared with traditional joint scheduling algorithms. A numerical test is carried out in order to evaluate the performance of the model and algorithm. The system adopting LAGVs is compared with the system adopting traditional AGVs through investigating the influence of the number of quay cranes， the scale of tasks and the number & scheduling strategies of AGVs on the waiting time of quay cranes. The results provide decision support for automated terminal handling operations.

Key words：

automated terminal； Automated Guided Vehicle （AGV）； integrated scheduling； Genetic Algorithm （GA）； heuristic strategy

0引言

在新的全球經(jīng)濟格局下，如何提高集裝箱碼頭運作效率成為當(dāng)前碼頭發(fā)展亟待解決的問題。而在碼頭實際作業(yè)過程中，碼頭整體作業(yè)效率的提升依賴于岸橋、水平運輸車輛、場橋等主要設(shè)備的密切協(xié)作與合理調(diào)度。因此，碼頭設(shè)備調(diào)度問題成為當(dāng)前研究的熱點。

目前，國內(nèi)外專家對集裝箱碼頭優(yōu)化調(diào)度問題已經(jīng)做了大量的研究。文獻[13]僅研究碼頭單個環(huán)節(jié)調(diào)度，通過模型構(gòu)建、算法設(shè)計及案例分析研究碼頭設(shè)備調(diào)度問題，但未考慮碼頭多個環(huán)節(jié)之間的相互影響。文獻[49]在研究集裝箱碼頭設(shè)備調(diào)度問題時，考慮了多環(huán)節(jié)作業(yè)之間的相互作用和制約，建立了多類型設(shè)備集成調(diào)度模型。碼頭新工藝的出現(xiàn)對調(diào)度問題產(chǎn)生了很大影響，文獻[1012]針對碼頭新工藝下的設(shè)備調(diào)度問題，采用構(gòu)建模型、仿真模型及實驗分析等方法進行研究。endprint

當(dāng)前的研究主要針對碼頭一種或兩種設(shè)備的聯(lián)合調(diào)度，且大多數(shù)集中在傳統(tǒng)碼頭領(lǐng)域，缺乏將不同新工藝用于碼頭設(shè)備集成調(diào)度的深入研究。本文建立岸橋（QC）、自帶提升功能的自動導(dǎo)引小車（LAGV）和支架、自動化場橋（AYC）集成調(diào)度混合整數(shù)規(guī)劃模型，并設(shè)計雙層遺傳算法對問題進行求解。

1問題描述

圖1展示了自動化碼頭的一種新工藝布局，其裝卸運輸系統(tǒng)由4部分組成：QC，LAGV，緩沖支架以及AYC。QC負責(zé)船舶裝卸，LAGV負責(zé)水平運輸，AYC負責(zé)場區(qū)的存/取操作。作為連接水平運輸和堆場操作的柔性機制，緩沖支架減少水平運輸設(shè)備和自動化軌道吊相互等待時間，緩解水平運輸能力與自動化軌道吊裝卸堆放能力之間的矛盾，提高系統(tǒng)作業(yè)效率，但也增加了設(shè)備調(diào)度復(fù)雜性。

考慮任務(wù)執(zhí)行過程中各裝卸環(huán)節(jié)的銜接以及各裝卸設(shè)備之間存在時空非同步性影響，分析碼頭裝卸作業(yè)調(diào)度系統(tǒng)，可知各子環(huán)節(jié)調(diào)度存在目標(biāo)沖突、

裝卸資源請求沖突、響應(yīng)結(jié)果沖突。因此，QC調(diào)度問題、水平運輸調(diào)度問題、AYC調(diào)度問題相互影響、緊密關(guān)聯(lián)，必須在有效解決上述沖突的情況下合理協(xié)調(diào)各種調(diào)度決策才能達到最優(yōu)的整體運作效果。

2集成調(diào)度模型

2.1調(diào)度框架

對于集裝箱裝卸任務(wù)的劃分，BIERWIRTH等[13]將其分為5種：①基于貝位區(qū)域；②基于單個貝位；③基于堆垛的任務(wù)；④基于集裝箱簇；⑤基于單個集裝箱。

定義兩層調(diào)度子問題的不同任務(wù)劃分方式：上層采用集裝箱簇作為任務(wù)定義，既避免由于基于單個集裝箱任務(wù)定義導(dǎo)致的QC各種十分復(fù)雜的干擾約束的出現(xiàn)，和任務(wù)量的龐大造成求解時間和空間復(fù)雜度指數(shù)性增加，又不會因任務(wù)定義太大而導(dǎo)致QC作業(yè)難以均衡；下層是AGV和場橋的調(diào)度，采用基于單個集裝箱的任務(wù)定義，有利于AGV運輸?shù)撵`活性和場橋重進重出的高效率，也便于與上層進行任務(wù)單位的銜接。

如圖2所示，設(shè)備集成調(diào)度框架是在已知船舶配載計劃、QC屬性、任務(wù)屬性的情況下，通過基于簇任務(wù)的QC分配與調(diào)度模型求解各QC的箱任務(wù)序列，為基于箱任務(wù)序列的自動化設(shè)備集成調(diào)度模型提供一定的輸入條件，而將后者求解出的箱任務(wù)結(jié)束時刻反饋給前者，作為QC調(diào)度的評估，不斷重復(fù)該邏輯，最后得到各設(shè)備的最優(yōu)任務(wù)序列。

2.2基于簇任務(wù)的QC分配與調(diào)度模型

2.2.1假設(shè)條件

（1）計劃期內(nèi)船舶泊位計劃已知，船舶上貝位連續(xù)分布，且每個貝位在岸線方向上的長度相同；

（2）每個集裝箱簇任務(wù)所在貝位、作業(yè)類型、最短理想作業(yè)時間、先后作業(yè)順序、簇內(nèi)集裝箱的作業(yè)順序均已知；

（3）單船設(shè)有同時作業(yè)最多和最少Q(mào)C數(shù)；

（4）所有QC在同一軌道上水平勻速移動且不能跨越作業(yè)，相鄰QC之間滿足安全距離要求。

2.2.2符號說明

K為QC的集合，K={1，2，…，k，…，C}；T為計劃期內(nèi)時間段的集合，T={1，2，…，t，…，P}；Ω為所有簇任務(wù)集合，Ω={1，2，…，n，…，N}，用m表示同臺QC上任務(wù)n的前任務(wù)；ψ為不能同時作業(yè)的簇任務(wù)集合；Φ為有作業(yè)先后順序要求的簇任務(wù)集合；Rmin和Rmax分別表示為船舶分配的最少和最多QC數(shù)；Ta為船舶到達時刻；Tb為船舶靠泊時刻；Tn為簇任務(wù)n的理想最短作業(yè)時間；ln為簇任務(wù)n的位置，用貝位編號表示；Δl為相鄰QC的安全距離，用間隔貝位數(shù)表示，通常為一個貝位；vk為第k臺QC的水平移動速度，m/min，k∈K；M為一個充分大的正整數(shù)；Ts和Te分別表示船舶開始作業(yè)和結(jié)束作業(yè)時刻；Tsn，Ten分別為簇任務(wù)n的真實開始時刻和結(jié)束時刻，Tsn為簇任務(wù)n的允許作業(yè)時刻；ckn為第k臺QC服務(wù)簇任務(wù)n后的空閑時刻，每次任務(wù)完成后立即更新；lkn為第k臺QC完成簇任務(wù)n時位于碼頭岸線上的位置，每次任務(wù)完成后立即更新；δkn為第k臺QC為完成簇任務(wù)n移動到合適位置所需的時間；xtk為01變量，若第t時段有第k臺QC為船舶進行裝卸作業(yè)，則為1，否則為0；ztkn為01變量，若第t時段有第k臺QC為簇任務(wù)n作業(yè)，則為1，否則為0；fn1n2為01變量，若簇任務(wù)n2開始作業(yè)時，簇任務(wù)n1已經(jīng)完成，則為1，否則為0，n1，n2∈Ω。

2.2.3目標(biāo)函數(shù)

（1）最小化船舶在港時間

S1=min（Te-Ta）=min（（Te-Ts）+（Ts-Ta））

其中：Te-Ts表示船舶的裝卸作業(yè)時間；Ts-Ta表示船舶的等待作業(yè)時間，包含等待泊位時間和等待岸橋時間。

（2）最小化QC移動距離

S2=min knztkn·vk·δkn=

min knT（ztkn（|lkn-lkn′|+

k′|ln-（k-k′）Δl-l′k′n′|））

當(dāng)進行裝卸作業(yè)時，QC的狀態(tài)是不斷變化的，當(dāng)?shù)趉臺QC對船舶上的簇任務(wù)n進行作業(yè)時，其位置和再次空閑時刻需要更新：

lkn=ztknln

ckn=ztknTen

由于QC不能跨越作業(yè)，某QC k′可能會因為其他作業(yè)需要而被迫移動，其位置和空閑時間更新如下：

l′kn=ztkn（ln-（k-k′）Δl）

c′kn=ztkn（c′kn′+ln-（k-k′）Δl-l′k′n′/vk）

2.2.4約束條件

Ts≥Tb （1）

Te≥max（Ten），n∈Ω （2）

Rmin≤kxtk≤Rmax，t∈T （3）

nztkn=xtk，t∈T；k∈K；n∈Ω （4）

tkztkn≥Tn，n∈Ω （5）

zt1k1n+zt2k2n=1，t1，t2∈{Tsn，…，Ten}；endprint

k1，k2∈K，k1≠k2； n∈Ω （6）

Tsn≥max{（ckm+δkn）ztkn，Tsn}，

t∈T；k∈K；m，n∈Ω （7）

Ten≥Tsn+Tn，n∈Ω （8）

fn1n2+fn2n1=1，（n1，n2）∈ψ （9）

Ten1-Tsn2≤0，（n1，n2）∈Φ （10）

Ten1≤Tsn2+M（1-zt1kn1zt2kn2fn1n2），

t1，t2∈T； k∈K； n1，n2∈Ω （11）

（lk2n2-lk1n1）（ln2-ln1）ztk1n1ztk2n2≥0 （12）

xt，k-1+xt，k+1-xt，k={-1，0，1}，

t∈T； k-1，k，k+1∈K （13）

式（1）表示船舶的開始作業(yè)時刻必須大于其靠泊時刻。式（2）表示所有簇任務(wù)作業(yè)完成時間即為船舶結(jié)束作業(yè)的時間。式（3）表示每個時刻為船舶服務(wù)的船舶數(shù)量在一定范圍內(nèi)。式（4）表示在單位時間內(nèi)一臺QC只能為一個任務(wù)服務(wù)。式（5）表示每個簇任務(wù)都配置了相應(yīng)的QC作業(yè)，并且QC作業(yè)時間應(yīng)滿足簇任務(wù)所需的裝卸作業(yè)時間要求。式（6）表示有且僅有一臺QC為簇任務(wù)n服務(wù)。式（7）表示簇任務(wù)n的開始作業(yè)時刻。式（8）表示簇任務(wù)n的作業(yè)結(jié)束時刻。式（9）表示對不能同時作業(yè)的簇任務(wù)的限定。式（10）表示有先后順序的簇任務(wù)在時間上的關(guān)系。式（11）表示兩個簇任務(wù)由同一臺QC服務(wù)時，其作業(yè)時間需要滿足的關(guān)系。式（12）表示QC不能在同一船舶的兩個作業(yè)之間交叉作業(yè)。式（13）表示任意時間若有多臺QC為該船舶服務(wù)，則QC必須連續(xù)，即滿足QC不能跨越原則。

2.3基于箱任務(wù)序列的自動化設(shè)備集成調(diào)度模型

2.3.1假設(shè)條件

（1）集港在裝卸船作業(yè)過程之前已經(jīng)完成，疏港在裝卸船作業(yè)過程之后進行。

（2）通過QC調(diào)度模型得到每臺QC所負責(zé)的簇任務(wù)和箱任務(wù)序列。

（3）調(diào)度計劃期內(nèi)，已知每個箱任務(wù)操作類型（裝/卸），在船上和堆場的裝卸位置。

（4）QC，LAGV和AYC的可用數(shù)量已知，且每個設(shè)備一次只處理一個集裝箱。

（5）LAGV，AYC空/重載和QC的速度以及各個設(shè)備的裝卸效率。

（6）每個堆場箱區(qū)僅岸側(cè)AYC負責(zé)裝卸船；不考慮LAGV堵塞情況；已知LAGV和AYC在任何兩個操作節(jié)點位置之間的距離。

2.3.2符號變量說明

ve和vd分別表示提供AYC初始和結(jié)束虛擬任務(wù)的虛擬岸橋。vs和vf分別表示提供LAGV初始和結(jié)束虛擬任務(wù)的虛擬岸橋。Q為AYC的集合。V為LAGV的集合。P為堆場岸側(cè)交換區(qū)的集合。mk為第k臺QC執(zhí)行的任務(wù)數(shù)量，k∈K。eki為QC在作業(yè)區(qū)開始作業(yè)箱任務(wù)（k，i）事件，當(dāng)箱任務(wù)（k，i）為卸船任務(wù)時，表示QC開始放箱到LAGV；當(dāng)箱任務(wù)（k，i）為裝船任務(wù)時，表示QC開始從LAGV上抓箱；（k，i）為箱任務(wù)編號，代表第k臺QC的第i個箱任務(wù)，k∈K，i=1，…，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。Ebki為AYC在堆場岸側(cè)交換區(qū)開始作業(yè)箱任務(wù)（k，i）事件，當(dāng)箱任務(wù)（k，i）為卸船任務(wù)時，表示AYC開始從支架上抓箱；當(dāng)箱任務(wù)（k，i）為裝船任務(wù)時，表示AYC開始放箱到支架，k∈K。TL為裝船任務(wù)的事件eki的集合，k∈K，即eki∈TL。TD為卸船任務(wù)的事件eki的集合，k∈K，即eki∈TD。TC為事件eki集合中有先后順序要求的任務(wù)集合，k∈K，即eki∈TC。Nq為第q臺AYC執(zhí)行Ebki的集合，k∈K，q∈Q。Np為第p個堆場岸側(cè)交換區(qū)事件Eaki的集合，k∈K，p∈P。ski為第k臺QC執(zhí)行事件eki的實際準(zhǔn)備就緒時刻，k∈K。Hkik（i-1）為第k臺QC完成ek（i-1）后執(zhí)行eki的全部準(zhǔn)備時間，k∈K，i≠1。yki為事件eki的實際發(fā)生時刻，k∈K。Yaki為事件Eaki的發(fā)生時刻，k∈K。Ybki為事件Ebki的發(fā)生時刻，k∈K。Tljki為從Ebki發(fā)生的位置到Eblj發(fā)生的位置之間AYC的純移動時間，k∈{ve}∪K，l∈{vd}∪K，j=1，…，ml，mve=mvd=|Q|。Gljki表示AYC完成Ebki后執(zhí)行Eblj需要調(diào)整的時間，k∈{ve}∪K，l∈{vd}∪K。 tljki為從eki發(fā)生的位置到elj發(fā)生的位置LAGV的純運行時間，k∈{vs}∪K，l∈{vf}∪K，mvs=mvf=|V|。cljki為LAGV完成eki后去完成elj的調(diào)整時間，k∈{vs}∪K，l∈{vf}∪K。Sljki為eki與Ealj兩個事件間的調(diào)整時間，k∈{vs}∪K，l∈{vf}∪K。Ski為eki與Eaki兩個事件間的調(diào)整時間，k∈K。ΔSki為Eaki與Ebki兩個事件間的間隔時間，k∈K。ljki為01變量，若同一輛LAGV完成eki后緊接著完成elj，則其值為1，否則為0，k∈{vs}∪K，l∈{vf}∪K。φljki為01變量，若同一臺AYC完成Ebki后緊接著完成Eblj，則其值為1，否則為0，k∈{ve}∪K，l∈{vd}∪K。

2.3.3目標(biāo)函數(shù)及約束

i=1，…，mk；j=1，…，ml

S3=min k∈Kmki=1（yki-ski）+ （14）

S4=min k∈{ve}∪Kmki=1l∈K∪{vd}mlj=1Tljkiφljki （15）

S5=min k∈{vs}∪Kmki=1l∈K∪{vf}mlj=1tljkiljki （16）endprint

l∈{vf}∪Kmlj=1ljki=1，k∈{vs}∪K

（17）

k∈{vs}∪Kmki=1ljki=1，l∈{vf}∪K

（18）

l∈{vd}∪Kmlj=1φljki=1，k∈{ve}∪K

（19）

k∈{ve}∪Kmki=1φljki=1，l∈{vd}∪K

（20）

ylj-max（yki+cljki，slj）≥M（ljki-1），

k∈{vs}∪K；l∈K

（21）

Yblj-（Ybki+Gljki）≥M（φljki-1），

k∈{ve}∪K；l∈K

Yalj-（yki+Sljki）≥M（ljki-1），

（22）

k∈{vs}∪K；l∈K （23）

yki-yk（i-1）≥ski-sk（i-1），k∈K；i≠1 （24）

yki≥ski，k∈K （25）

ski≥yk（i-1）+Hkik（i-1），k∈K；i≠1 （26）

yki≥Yaki+Ski，eki∈TL；k∈K （27）

Yaki≥Ybki+ΔSki，eki∈TL；k∈K （28）

Yaki≥yki+Ski，eki∈TD；k∈K （29）

Ybki≥Yaki+ΔSki，eki∈TD；k∈K （30）

Ybki-Ybkj≥0，

Ebki，Ebkj∈Nq；k∈K；

i>j；q∈Q （31）

Ybki-Yblj≥0，Ebki，Eblj∈Nq；k，l∈K；

eki，elj∈TC；yki>ylj；q∈Q （32）

式（14）～（16）為目標(biāo)函數(shù)，分別表示最小化QC延遲時間、最小化AYC總移動時間、最小化LAGV的總運行時間。式（17）～（20）表示LAGV或AYC一次只能執(zhí)行一個任務(wù)，一個任務(wù)一旦由某個AYC或LAGV執(zhí)行就不能中斷，且每個任務(wù)都要被執(zhí)行。式（21）和（22）表示由同一裝卸運輸設(shè)備執(zhí)行的相鄰任務(wù)的時間邏輯關(guān)系，式（21）表示同一輛LAGV完成eki后去執(zhí)行elj需要有時間cljki準(zhǔn)備及岸橋時間準(zhǔn)備，式（22）表示同一臺AYC完成Ebki后去執(zhí)行Eblj需要有時間tljki準(zhǔn)備。式（23）表示作業(yè)不同環(huán)節(jié)的時間邏輯關(guān)系，如果任務(wù)（k，i）和（l，j）是同一輛LAGV的兩個相鄰任務(wù)，那么LAGV完成eki后需要時間Sljki調(diào)整去完成Eblj。式（24）表示同一臺QC執(zhí)行相鄰任務(wù)的調(diào)整時間應(yīng)滿足QC執(zhí)行所需作業(yè)的時間。式（25）表示eki的實際發(fā)生時刻最小為最早可能發(fā)生時刻。式（26）表示QC執(zhí)行ek（i-1）后需時間Hkik（i-1）準(zhǔn)備才能執(zhí)行任務(wù)eki。式（27）和（28）表示對于同一裝船任務(wù)（k，i），作業(yè)相鄰環(huán)節(jié)的時間邏輯關(guān)系，此類任務(wù)的設(shè)備操作順序是：AYC→LAGV→QC，因此AYC完成Ebki時刻與Eaki和Ebki的調(diào)整時間之和不會超過LAGV完成Eaki的時刻，LAGV完成Eaki的時刻與Eaki和eki的調(diào)整時間之和不會超過QC完成eki的時刻。同理，式（29）和（30）表示對于同一卸船任務(wù)（k，i），其作業(yè)相鄰環(huán)節(jié)的時間邏輯關(guān)系。此類任務(wù)的設(shè)備操作順序是：QC→LAGV→AYC。式（31）表示每臺AYC的任務(wù)執(zhí)行順序需要符合QC任務(wù)序列中的順序。式（32） 表示每臺AYC執(zhí)行具有約束關(guān)系的任務(wù)必須符合它們的先后順序。

3雙層多目標(biāo)遺傳算法設(shè)計

上述模型中的調(diào)度子問題均為NP難問題，本文設(shè)計雙層多目標(biāo)遺傳算法求解：外層優(yōu)化QC簇任務(wù)作業(yè)序列；內(nèi)層基于外層的QC箱任務(wù)序列優(yōu)化LAGV和AYC的任務(wù)序列，然后計算相關(guān)的評價指標(biāo)值并將其反饋到外層，作為外層染色體的評價準(zhǔn)則；通過內(nèi)外層遺傳算法的協(xié)調(diào)確定最優(yōu)的集成調(diào)度方案。其算法流程見圖3。

3.1染色體編碼

主要考慮兩個位串編碼，外層位串表示QC分配調(diào)度的簇任務(wù)序列， 內(nèi)層位串表示LAGV和AYC調(diào)度中的箱任務(wù)序列；內(nèi)外層均采用自然數(shù)對染色體編碼，每個染色體代表所有任務(wù)的一個隨機排列，每個自然數(shù)代表任務(wù)編號，染色體長度等于任務(wù)數(shù)量。

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

隨機生成或迭代更新的染色體可能存在不可行或重復(fù)個體的情況，因此需進行修正。

針對不可行序列的修正策略：外層簇任務(wù)序列根據(jù)不同時、有先后關(guān)系的簇任務(wù)約束進行染色體的修正；而內(nèi)層遺傳算法是在外層遺傳算法獲得的可行QC的作業(yè)序列的基礎(chǔ)上進行的，因此內(nèi)層箱任務(wù)序列需要與外層所得的QC作業(yè)箱任務(wù)序列一致。

步驟1按外層算法所得的每個QC作業(yè)箱任務(wù)序列修正隨機產(chǎn)生的箱任務(wù)序列，得到符合每個QC作業(yè)序列的箱任務(wù)序列。

步驟2按簇任務(wù)約束關(guān)系來修正箱任務(wù)順序。根據(jù)QC調(diào)度序列，不同時、有先后關(guān)系的簇任務(wù)若由同一臺QC完成，那么已經(jīng)在步驟1中修正。若它們不由同一臺QC完成，則應(yīng)修正編碼使其滿足約束關(guān)系。采取下列方式修正：

①對先后順序關(guān)系簇任務(wù)集合，直接按先后順序展開組成箱任務(wù)序列，找到其箱序列編碼中的位置直接替換；

②對不同時的簇任務(wù)集合，先找出其在簇序列中的先后位置，并按位置先后展開組成箱任務(wù)序列，再找其在箱序列編碼中的位置并替換。

步驟3重復(fù)上述兩步修復(fù)策略，直到新的箱任務(wù)序列不再變化為止。

對種群中重復(fù)序列的修正策略：由于算法內(nèi)外層任務(wù)均采取統(tǒng)一編碼方式，在種群中會不可避免地產(chǎn)生重復(fù)的個體，不利于算法收斂精度，因此搜尋每代的重復(fù)個體，并采用部分逆反變異操作生成新的個體替換原染色體，得到新的種群作為下一代。這樣不僅能降低重復(fù)個體存在的概率，而且能保持種群多樣性。endprint

3.3集成調(diào)度的啟發(fā)式策略

本文算法設(shè)計思想是將遺傳算法與有效的啟發(fā)式策略相結(jié)合，將由內(nèi)外層編碼得到的可行序列作為任務(wù)選擇QC或AGV，AYC的順序，依此順序采用下面的QC調(diào)度策略和AGV，AYC調(diào)度策略，逐一為當(dāng)前任務(wù)分配合適的設(shè)備，直到所有任務(wù)完成分配。

QC調(diào)度策略見圖4。

QC調(diào)度策略的具體步驟如下：

步驟1初始化船舶開始作業(yè)時刻（即靠泊時刻），QC的位置和可用時間，簇任務(wù)在船上的貝位、任務(wù)量和相關(guān)約束。

步驟2若可用QC數(shù)大于或等于船舶作業(yè)QC最小數(shù)，則隨機選擇一組連續(xù)的QC分配給船舶，轉(zhuǎn)步驟3；否則推遲船舶開始作業(yè)時刻。

步驟3考慮QC和任務(wù)屬性，逐一為簇任務(wù)n分配作業(yè)QC。首先檢查簇任務(wù)n左右兩側(cè)距其最近的QC，若需要等待時間相同則優(yōu)先選擇距離更近的QC，若需要等待時間不同則選擇等待時間較短的QC，并更新簇任務(wù)n的開始作業(yè)和結(jié)束作業(yè)時刻以及QC位置和再次空閑時刻。

步驟4如此循環(huán)執(zhí)行步驟3，為簇任務(wù)n+1分配QC，直到為所有簇任務(wù)分配QC完畢，得到QC分配和調(diào)度簇任務(wù)序列。

AYC調(diào)度策略：在給定QC作業(yè)箱任務(wù)順序后，AYC的作業(yè)序列與QC作業(yè)序列一致。

LAGV調(diào)度策略：根據(jù)箱任務(wù)序列對LAGV進行運輸任務(wù)指派，采用以下啟發(fā)式規(guī)則對LAGV進行調(diào)度：①遵循QC作業(yè)順序優(yōu)先原則；②先到先指派。

3.4適應(yīng)值函數(shù)選擇

適應(yīng)值函數(shù)由目標(biāo)函數(shù)加權(quán)和的倒數(shù)確定。外層為船舶在港時間（箱任務(wù)最大完成時刻）與QC移動距離的歸一化加權(quán)和倒數(shù)；內(nèi)層為箱任務(wù)最遲結(jié)束時刻、每臺QC的箱任務(wù)均衡程度、QC總延遲時間、LAGV的總運行時間和AYC總移動時間的歸一化加權(quán)和倒數(shù)。

3.5選擇、交叉、變異

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

4算例分析

4.1案例說明

以采用新工藝的青島某自動化碼頭為例。該碼頭總岸線長2 088 m，每個40英尺集裝箱貝位在岸線上跨度為12 m，碼頭共有7臺QC可供分配，假定QC初始位置均勻分布于碼頭岸線上。堆場采用垂直岸線布置，本案例涉及8個箱區(qū)，每個箱區(qū)配備兩臺AYC，岸側(cè)場橋負責(zé)裝卸船的存取箱，陸側(cè)場橋負責(zé)配合外部集卡集疏港，各箱區(qū)岸側(cè)均設(shè)置一組支架的交換區(qū)。設(shè)置支架數(shù)量為5條，并預(yù)留一條無支架裝卸車道。水平交通組織中的各類車道數(shù)量和寬度是根據(jù)QC后伸距以及LAGV參數(shù)設(shè)定的，車道布局見圖7。QC下裝卸車道為單行道，行車方向是依據(jù)船頭朝向和裝卸箱量的比例設(shè)定的，以減少倒箱門現(xiàn)象對車輛和道路的干擾。緩沖車道允許雙向行駛，以縮短車輛在岸邊與堆場之間的運行距離；高速相鄰車道行駛方向相反，便于車輛在箱區(qū)岸側(cè)交換區(qū)的進出，水平交通規(guī)則見圖7。

假設(shè)各AYC和LAGV初始位置均設(shè)置在各箱區(qū)支架交換區(qū)。各設(shè)備完成其所有作業(yè)后回到初始位置，各裝卸運輸設(shè)備參數(shù)見表1。QC平均作業(yè)效率每小時不低于36個循環(huán)，假設(shè)QC抓/放箱操作時間均為10 s，QC小車在QC交換區(qū)與船舶之間的平均水平運行時間為40 s。某艘船?？吭诰喟毒€100 m處，靠泊時刻為計劃期的第60 min，隨機生成該船需要裝卸作業(yè)的簇任務(wù)以及箱任務(wù)，包括任務(wù)數(shù)量、在船上和堆場中的位置、各任務(wù)之間不同時、

有先后順序等的約束關(guān)系。

4.2試驗分析

本文算法采用MATLAB R2012b編程實現(xiàn)，并在Intel（R） Core（TM） 2Quad CPU Q9500 @2.83 GHz處理器，RAM 2GB電腦上運行。通過多次初步試驗確定有關(guān)的參數(shù)：（1）外層。種群大小50；最大遺傳代數(shù)100；交叉概率0.85；變異概率0.10。（2）內(nèi)層。種群大小50；最大遺傳代數(shù)100；交叉概率0.80；變異概率0.05。

為了評估新工藝的集成調(diào)度模型和算法，首先設(shè)計8組中等規(guī)模仿真算例驗證所提算法的性能。為實現(xiàn)建模與算法的分離，將模型的非線性約束轉(zhuǎn)換成線性約束，采用MATLAB中的YALMIP工具箱結(jié)合CPLEX12.2求解器，求解QC調(diào)度模型，其中計劃期的時間單位設(shè)置成所有簇任務(wù)的裝卸時間需求最小值，再根據(jù)QC調(diào)度結(jié)果求解自動化設(shè)備集成調(diào)度模型。表2最后一列顯示了本文算法的加權(quán)目標(biāo)函數(shù)值與最優(yōu)值之間的偏差。試驗發(fā)現(xiàn)，CPLEX的計算耗時隨著任務(wù)數(shù)的增加快速上升，30個以上箱任務(wù)的問題無法在有效的時間內(nèi)得到結(jié)果（最后兩組算例的時間都超過了4 h），而雙層遺傳算法盡管不能獲得最優(yōu)解，但在大規(guī)模任務(wù)的計算效率上具有優(yōu)勢。

為分析系統(tǒng)的靈敏性，選取LAGV數(shù)和計劃期長度（任務(wù)數(shù)）作為變化因素，試驗結(jié)果見圖8?？梢钥闯?，在給定LAGV數(shù)的條件下，加權(quán)目標(biāo)函數(shù)值隨著計劃期長度的增加而增加，但任務(wù)的平均值在下降。這表明，計劃期越長，系統(tǒng)越能獲得更好的性能。然而計算更多任務(wù)數(shù)將花費更多時間。在實際中，由于碼頭各種中斷事件的發(fā)生，如起重機或AGV等設(shè)備故障，會不可避免地需要進行再調(diào)度。因此，可以結(jié)合實際情況，選取一個適當(dāng)?shù)挠媱澠谝詸?quán)衡計算量和系統(tǒng)性能的損失。此外，在給定計劃期的條件下，LAGV數(shù)會影響系統(tǒng)性能，特別是對某具體算例，存在最優(yōu)的數(shù)量配置。決定加權(quán)目標(biāo)函數(shù)值變化的因素除LAGV數(shù)外，還包括任務(wù)的信息及其在QC上的序列。

為分析集成調(diào)度的效果，采用雙層遺傳算法，模擬3臺QC，8輛LAGV，8臺AYC，10個簇任務(wù)，44個裝卸箱任務(wù)條件下各設(shè)備作業(yè)序列的優(yōu)化。圖9呈現(xiàn)了QC理想調(diào)度（QC無等待）與集成調(diào)度得到的各QC任務(wù)的開始和結(jié)束時刻（圖9a）中矩形塊為簇任務(wù)編號，圖9b）中矩形塊為箱任務(wù)編號）。

圖9a）顯示在集成調(diào)度的情況下，各QC作業(yè)比較均衡并均存在等待，說明LAGV和AYC的調(diào)度影響了QC調(diào)度結(jié)果；較單環(huán)節(jié)調(diào)度，集成調(diào)度協(xié)調(diào)了各環(huán)節(jié)之間的沖突，對碼頭資源整合有重要借鑒作用。圖9b）顯示QC累積等待時間在各QC之間分endprint

配的非均衡性，因為LAGV和AYC的調(diào)度目標(biāo)之一是在最小化船舶在港時間的情況下使各QC任務(wù)完成時間盡量均衡，減少任務(wù)多的QC的作業(yè)延遲。

選擇3種變化因素對比在新工藝“LAGV+支架”與傳統(tǒng)AGV工藝下集成調(diào)度的結(jié)果。第1個因素是QC數(shù)量，設(shè)定為2，3，4；第2個因素是簇任務(wù)規(guī)模，設(shè)定為3，5，7，10；第3個因素是水平運輸設(shè)備的數(shù)量，設(shè)定為4，8，12，18，24，44。此外，比較了兩種常見LAGV調(diào)度策略的影響。每種組合試驗次數(shù)為10次，試驗結(jié)果見圖10。

a）QC

b）任務(wù)

c）水平運輸設(shè)備

d）調(diào)度策略

由圖10a）可知：當(dāng)QC和（L）AGV的配置比例增大時，采用“LAGV+支架”工藝較采用AGV可明顯降低QC等待時間；當(dāng)該比例減少時，“LAGV+支架”工藝的緩沖作用發(fā)揮不明顯，QC等待時間差別不大。

由圖10b）可知：兩種工藝下的QC等待時間均隨著任務(wù)規(guī)模增大而增加，采用“LAGV+支架”工藝較采用AGV的QC等待時間短；在設(shè)備配置一定的情況下，當(dāng)任務(wù)規(guī)模為中等時，采用“LAGV+支架”工藝較AGV工藝的優(yōu)勢更明顯。

由圖10c）可知：當(dāng)水平運輸設(shè)備不夠充足時，兩種工藝下的QC等待時間均隨著（L）AGV數(shù)量的增加而減少；“LAGV+支架”工藝下的QC等待時間比相應(yīng)的AGV工藝下的QC等待時間短。但是，隨著（L）AGV數(shù)量繼續(xù)增加，QC等待時間趨于穩(wěn)定。在水平運輸設(shè)備不充足的情況下，采用“LAGV+支架”工藝較AGV工藝有更明顯的優(yōu)勢。

由圖10d）可知：在縮短QC等待時間上，本文算法采用的策略a（選擇最早空閑的最近的一輛LAGV完成待作業(yè)任務(wù)）較策略b（選擇最近兩輛LAGV中最早到達的一輛LAGV完成待作業(yè)任務(wù)）具有明顯優(yōu)勢。分析可知，采用策略b一方面會導(dǎo)致緊急任務(wù)得不到及時作業(yè)，另一方面會導(dǎo)致某些LAGV處于閑置狀態(tài)，水平運輸設(shè)備任務(wù)量不均衡，進而導(dǎo)致QC等待時間過長。

5結(jié)束語

考慮碼頭裝卸作業(yè)各環(huán)節(jié)和緩沖系統(tǒng)的調(diào)度，以最小化船舶在港時間為整體目標(biāo)，建立了自動化設(shè)備集成調(diào)度框架和相關(guān)模型。設(shè)計了雙層遺傳算法結(jié)合啟發(fā)式策略對模型進行求解。結(jié)果表明：設(shè)備協(xié)同調(diào)度較單環(huán)節(jié)獨立調(diào)度能改善岸橋（QC）調(diào)度均衡性；“支架+自帶提升功能的自動導(dǎo)引小車（LAGV）”工藝在中等任務(wù)規(guī)模、QC與車輛配比較大條件下，具有明顯的優(yōu)勢。研究結(jié)果可為碼頭設(shè)備的調(diào)度提供重要的決策支持。下一步的研究工作中將會考慮LAGV路徑規(guī)劃和能量約束的影響。

參考文獻：

[1]KIM Jeongmin， CHOE Ri， RYU Kwang Ryel. Multiobjective optimization of dispatching strategies for situationadaptive AGV operation in an automated container terminal[C]//Research in Adaptive and Convergent Systems. ACM， 2013： 16.

[2]樂美龍， 趙彥營， 劉秀玲. 時間窗下單船岸橋調(diào)度[J]. 計算機工程與應(yīng)用， 2014， 50（9）： 242248.

[3]HE Junliang， HUANG Youfang， YAN Wei. Yard crane scheduling in a container terminal for the tradeoff between efficiency and energy consumption[J]. Advanced Engineering Informatics， 2015， 29（1）： 5975.

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

[5]馬超， 梁承姬. 集裝箱碼頭岸橋分配與集卡調(diào)度整合問題研究[J]. 廣西大學(xué)學(xué)報（自然科學(xué)版）， 2015， 40（3）： 643650.

[6]CHEN Lu， LANGEVIN Andre， 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.

[7]錢繼鋒. 集裝箱碼頭“岸橋集卡堆場”作業(yè)計劃的優(yōu)化[D]. 北京： 北京交通大學(xué)， 2014.

[8]DKHIL Hamdi， YASSINE Adnan， CHABCHOUB Habib. Optimization and simulation of container handling systems in automated maritime terminal[J]. Studies in Computational Intelligence， 2013， 457： 301312.

[9]樂美龍， 張清波. 自動化碼頭橋吊、自動引導(dǎo)車以及龍門吊的聯(lián)合調(diào)度[J]. 青島科技大學(xué)學(xué)報（自然科學(xué)版）， 2015， 36（5）： 569574.

[10]宓為建， 李央央， 胡鴻韜. 集裝箱堆場分配與自動化裝載小車路徑聯(lián)合優(yōu)化[J]. 上海海事大學(xué)學(xué)報， 2015， 36（4）： 1621.

[11]湯鵬飛， 梁承姬， 丁一， 等. 考慮岸橋緩存區(qū)的ALV調(diào)度優(yōu)化問題研究[J]. 廣西大學(xué)學(xué)報（自然科學(xué)版）， 2015， 40（6）： 15401550.

[12]余孟齊， 韓曉龍. 有限緩沖空間下岸橋和自動升降車的集成調(diào)度[J]. 武漢理工大學(xué)學(xué)報（信息與管理工程版）， 2016， 38（1）： 101105.

[13]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.

（編輯賈裙平）endprint