添玉 +王建彬 +范會(huì)方

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

關(guān)鍵詞：

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

中圖分類號(hào)： U691.3

文獻(xiàn)標(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)濟(jì)格局下，如何提高集裝箱碼頭運(yùn)作效率成為當(dāng)前碼頭發(fā)展亟待解決的問(wèn)題。而在碼頭實(shí)際作業(yè)過(guò)程中，碼頭整體作業(yè)效率的提升依賴于岸橋、水平運(yùn)輸車輛、場(chǎng)橋等主要設(shè)備的密切協(xié)作與合理調(diào)度。因此，碼頭設(shè)備調(diào)度問(wèn)題成為當(dāng)前研究的熱點(diǎn)。

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

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

1問(wèn)題描述

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

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

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

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

2.1調(diào)度框架

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

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

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

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

2.2.1假設(shè)條件

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

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

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

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

2.2.2符號(hào)說(shuō)明

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

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

（1）最小化船舶在港時(shí)間

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

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

（2）最小化QC移動(dòng)距離

S2=min knztkn·vk·δkn=

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

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

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

lkn=ztknln

ckn=ztknTen

由于QC不能跨越作業(yè)，某QC k′可能會(huì)因?yàn)槠渌鳂I(yè)需要而被迫移動(dòng)，其位置和空閑時(shí)間更新如下：

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

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

2.3.1假設(shè)條件

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

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

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

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

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

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

2.3.2符號(hào)變量說(shuō)明

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

（19）

k∈{ve}∪Kmki=1φl(shuí)jki=1，l∈{vd}∪K

（20）

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

k∈{vs}∪K；l∈K

（21）

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

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

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

3.1染色體編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟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ù)序列對(duì)LAGV進(jìn)行運(yùn)輸任務(wù)指派，采用以下啟發(fā)式規(guī)則對(duì)LAGV進(jìn)行調(diào)度：①遵循QC作業(yè)順序優(yōu)先原則；②先到先指派。

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

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

3.5選擇、交叉、變異

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

4算例分析

4.1案例說(shuō)明

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

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

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

4.2試驗(yàn)分析

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

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

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

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

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

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

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

a）QC

b）任務(wù)

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

d）調(diào)度策略

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

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

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

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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]樂(lè)美龍， 趙彥營(yíng)， 劉秀玲. 時(shí)間窗下單船岸橋調(diào)度[J]. 計(jì)算機(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é)報(bào)， 2013， 34（3）： 17.

[5]馬超， 梁承姬. 集裝箱碼頭岸橋分配與集卡調(diào)度整合問(wèn)題研究[J]. 廣西大學(xué)學(xué)報(bào)（自然科學(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]錢繼鋒. 集裝箱碼頭“岸橋集卡堆場(chǎng)”作業(yè)計(jì)劃的優(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]樂(lè)美龍， 張清波. 自動(dòng)化碼頭橋吊、自動(dòng)引導(dǎo)車以及龍門吊的聯(lián)合調(diào)度[J]. 青島科技大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2015， 36（5）： 569574.

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

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

[12]余孟齊， 韓曉龍. 有限緩沖空間下岸橋和自動(dòng)升降車的集成調(diào)度[J]. 武漢理工大學(xué)學(xué)報(bào)（信息與管理工程版）， 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