邱亞　梁承姬　張悅

摘要：為提高自動(dòng)化集裝箱碼頭堆場(chǎng)中自動(dòng)化軌道吊（automated stacking crane，ASC）的作業(yè)效率，研究箱區(qū)動(dòng)態(tài)接力點(diǎn)對(duì)雙ASC作業(yè)效率的影響。考慮雙ASC作業(yè)過(guò)程中的安全距離、相互沖突等因素，建立以最小化雙ASC最長(zhǎng)完工時(shí)間為目標(biāo)的混合整數(shù)規(guī)劃模型，利用遺傳算法對(duì)該模型進(jìn)行求解。與固定貝位接力模式進(jìn)行對(duì)比，結(jié)果表明，相較于固定貝位接力模式，動(dòng)態(tài)接力點(diǎn)模式下雙ASC的作業(yè)效率更高。在不同規(guī)模算例背景下，將遺傳算法與CPLEX的計(jì)算結(jié)果進(jìn)行對(duì)比，驗(yàn)證了遺傳算法的有效性。

關(guān)鍵詞：自動(dòng)化集裝箱碼頭; 自動(dòng)化軌道吊; 動(dòng)態(tài)接力點(diǎn); 遺傳算法

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

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

Coordination scheduling of twin automated stacking cranes under dynamic relay point mode

QIU Ya， LIANG Chengji， ZHANG Yue

（Institute of Logistics Science & Engineering， Shanghai Maritime University， Shanghai 201306， China）

Abstract：

In order to improve the operation efficiency of automated stacking cranes （ASCs） in the automated container terminal yards， the influence of dynamic relay points in the block on the operation efficiency of twin ASCs is studied. Considering the safety distance and conflicts in the operation process of twin ASCs， a mixed integer programming model aiming at minimizing the longest completion time of twin ASCs is established， which is solved by the genetic algorithm. Compared with the fixed shell relay mode， the results show that the twin ASCs are more efficient under the dynamic relay point mode. In the background of different scale examples， the calculation results from the genetic algorithm and CPLEX are compared to verify the effectiveness of the genetic algorithm.

Key words：

automated container terminal; automated stacking crane; dynamic relay point; genetic algorithm

0 引 言

集裝箱運(yùn)輸?shù)母咚侔l(fā)展正在改變世界港口、船舶和裝卸工藝的傳統(tǒng)格局。與傳統(tǒng)集裝箱碼頭不同，自動(dòng)化集裝箱碼頭的堆場(chǎng)采用垂岸式的布局，每個(gè)箱區(qū)有兩臺(tái)自動(dòng)化軌道吊（automated stacking crane， ASC）分別負(fù)責(zé)海側(cè)和陸側(cè)作業(yè)。因此，ASC與自動(dòng)導(dǎo)引小車 （automated guided vehicle， AGV）或外集卡的交接只能發(fā)生在箱區(qū)的兩端。隨著集裝箱碼頭的發(fā)展，碼頭作業(yè)效率的瓶頸已經(jīng)從碼頭前沿轉(zhuǎn)移到了后方的堆場(chǎng)。ASC是堆場(chǎng)中主要的調(diào)度設(shè)備，其作業(yè)效率很大程度上影響了堆場(chǎng)的作業(yè)效率?？紤]到本文所研究的并行式雙ASC之間不可相互穿越的特性，對(duì)雙ASC實(shí)行合理高效的調(diào)度是非常有必要的。

國(guó)內(nèi)外學(xué)者對(duì)傳統(tǒng)碼頭場(chǎng)橋和自動(dòng)化集裝箱碼頭ASC的調(diào)度做了很多的研究。初良勇等[1]考慮場(chǎng)橋作業(yè)的時(shí)間及成本，建立了集裝箱場(chǎng)橋的智能調(diào)度優(yōu)化數(shù)學(xué)模型，并設(shè)計(jì)了基于遺傳算法（genetic algorithm，GA）的模型求解策略。劉志雄等[2]針對(duì)多場(chǎng)橋調(diào)度問(wèn)題，提出一種混合演化策略算法，通過(guò)與其他算法的結(jié)果對(duì)比，證明了該算法在優(yōu)化多場(chǎng)橋調(diào)度問(wèn)題時(shí)的有效性。CHANG等[3]為實(shí)現(xiàn)場(chǎng)橋全局最優(yōu)調(diào)度，提出一種新的動(dòng)態(tài)滾動(dòng)范圍決策策略，并用啟發(fā)式算法和仿真模型的計(jì)算結(jié)果驗(yàn)證了所提方法的有效性和效率。裴磊磊等[4]在考慮ASC之間協(xié)調(diào)性、交接區(qū)容量限制的基礎(chǔ)上，采用GA與仿真相結(jié)合的方法對(duì)混合整數(shù)模型進(jìn)行求解，得出最短的作業(yè)總時(shí)間和最小的ASC間行駛距離之差。盧毅勤[5]考慮了AGV的行駛速度和ASC作業(yè)時(shí)間的不確定性，建立了AGV與ASC的聯(lián)合調(diào)度優(yōu)化模型，并采用改進(jìn)的粒子群優(yōu)化算法進(jìn)行求解。HE等[6]考慮了船舶到達(dá)時(shí)間的不確定性，研究了任務(wù)組到達(dá)時(shí)間和處理量不確定情況下場(chǎng)橋的調(diào)度問(wèn)題。CARLO等[7]針對(duì)并行式雙ASC在作業(yè)過(guò)程中發(fā)生沖突時(shí)的優(yōu)先級(jí)問(wèn)題提出了14條優(yōu)先級(jí)規(guī)則，并量化所選優(yōu)先級(jí)規(guī)則的影響，得出最優(yōu)的優(yōu)先級(jí)規(guī)則組合。NG等[8]研究了同一箱區(qū)多場(chǎng)橋作業(yè)相互干擾的問(wèn)題，并開(kāi)發(fā)了一種基于動(dòng)態(tài)規(guī)劃的啟發(fā)式算法來(lái)解決場(chǎng)橋的調(diào)度問(wèn)題。PARK等[9]為提高ASC的作業(yè)效率，在考慮翻箱的情況下，提出了基于啟發(fā)式算法和局部搜索的雙ASC實(shí)時(shí)調(diào)度方法，以實(shí)現(xiàn)AGV和外集卡的等待時(shí)間最短的目標(biāo)。鄭紅星等[10]設(shè)計(jì)了混合和聲模擬退火算法，并采用實(shí)時(shí)預(yù)倒箱來(lái)降低倒箱對(duì)場(chǎng)橋作業(yè)的影響，以此減少船舶裝船作業(yè)時(shí)間。徐飛慶[11]將場(chǎng)橋調(diào)度問(wèn)題轉(zhuǎn)化為一個(gè)基于軟時(shí)間窗的車輛路徑優(yōu)化問(wèn)題，在考慮節(jié)能減排的基礎(chǔ)上，實(shí)現(xiàn)場(chǎng)橋調(diào)度過(guò)程中能耗成本和延誤成本最低的目標(biāo)。SHA等[12]從低碳角度探討場(chǎng)橋調(diào)度問(wèn)題，提出了一種整數(shù)規(guī)劃模型，以最小化場(chǎng)橋的總能耗。

針對(duì)接力區(qū)的研究如下：黃繼偉等[13]為解決雙ASC存取箱作業(yè)沖突問(wèn)題，在箱區(qū)內(nèi)設(shè)置接力區(qū)，最小化雙ASC最長(zhǎng)完工時(shí)間，并用GA進(jìn)行求解。KRESS等[14]研究了在ASC不可相互穿越的條件下，在箱區(qū)內(nèi)設(shè)置接力區(qū)，并提出一種動(dòng)態(tài)規(guī)劃算法和相關(guān)的波束搜索啟發(fā)式算法進(jìn)行求解。GHAREHGOZLI等[15]為研究堆場(chǎng)內(nèi)接力區(qū)的設(shè)置對(duì)ASC作業(yè)的影響，以最小化ASC的完工時(shí)間或等待時(shí)間為目標(biāo)，對(duì)接力區(qū)集裝箱堆放位置以及接力區(qū)的有無(wú)、大小、數(shù)量等展開(kāi)研究。

已有的研究多數(shù)針對(duì)固定貝位接力模式，而很少考慮不同接力模式對(duì)ASC作業(yè)效率的影響。本文采用動(dòng)態(tài)接力點(diǎn)的雙ASC接力模式對(duì)進(jìn)出口集裝箱進(jìn)行作業(yè)調(diào)度。在對(duì)雙ASC的調(diào)度研究中，以最小化雙ASC的最長(zhǎng)完工時(shí)間為目標(biāo)，建立混合整數(shù)規(guī)劃模型，用GA和CPLEX對(duì)不同規(guī)模算例進(jìn)行求解，并與固定貝位接力模式的調(diào)度結(jié)果進(jìn)行對(duì)比。

1 問(wèn)題描述

在自動(dòng)化集裝箱碼頭，ASC只能在箱區(qū)的兩端與AGV或外集卡進(jìn)行交接作業(yè)。為提高ASC的利用率，避免雙ASC出現(xiàn)忙閑不一的情況，對(duì)雙ASC實(shí)行有效的調(diào)度就顯得尤為重要。由于本文所研究的雙ASC不可相互穿越，在已有的固定貝位接力模式下，接力點(diǎn)固定在箱區(qū)的中間，雙ASC的作業(yè)范圍受到限制，只能在接力區(qū)的某一側(cè)進(jìn)行作業(yè)。然而，在動(dòng)態(tài)接力點(diǎn)模式下，接力點(diǎn)不固定，陸側(cè)ASC可到海側(cè)作業(yè)，海側(cè)ASC也可到陸側(cè)作業(yè)。

雙ASC的動(dòng)態(tài)接力點(diǎn)模式可分解為兩個(gè)階段：第一階段，一側(cè)ASC將需要接力的任務(wù)箱放至動(dòng)態(tài)接力點(diǎn)，這個(gè)階段為主作業(yè);第二階段，另一側(cè)ASC從動(dòng)態(tài)接力點(diǎn)提走任務(wù)箱并放至目標(biāo)位置，這個(gè)階段為接力作業(yè)。在雙ASC的動(dòng)態(tài)接力過(guò)程中，如果任務(wù)箱的起點(diǎn)和終點(diǎn)在箱區(qū)的同一側(cè)（即都在圖1虛線的左側(cè)或右側(cè)），那么這個(gè)任務(wù)箱由該側(cè)的ASC獨(dú)立完成;如果任務(wù)箱的起點(diǎn)和終點(diǎn)不在箱區(qū)的同一側(cè)，那么就需要ASC接力完成，即海側(cè)（陸側(cè)）ASC將任務(wù)箱放至動(dòng)態(tài)接力點(diǎn)，陸側(cè)（海側(cè)）ASC結(jié)束正在進(jìn)行的任務(wù)后去完成接力任務(wù)。

相較于已有的固定貝位接力，本文研究的雙ASC動(dòng)態(tài)接力體現(xiàn)在接力點(diǎn)的不固定上。如果某側(cè)ASC有任務(wù)箱a需要接力，找到該ASC的下一個(gè)任務(wù)箱b所在位置，將a箱放至靠近箱區(qū)中間位置且與b箱所在位置相隔一個(gè)貝位處，這樣就確定了接力點(diǎn)。如圖1所示，以任務(wù)箱起點(diǎn)在海側(cè)為例，1號(hào)箱的起始位置在海側(cè)，終點(diǎn)位置在陸側(cè)，由于起點(diǎn)與終點(diǎn)不在同側(cè)，所以海側(cè)ASC將1號(hào)箱放至距其下一個(gè)任務(wù)2號(hào)箱一個(gè)貝位處，等待陸側(cè)ASC過(guò)來(lái)完成接力，此時(shí)海側(cè)ASC離開(kāi)并進(jìn)行下一個(gè)任務(wù)作業(yè)。起點(diǎn)在陸側(cè)的任務(wù)箱作業(yè)原理相同。在雙ASC作業(yè)過(guò)程中可能會(huì)出現(xiàn)ASC互相干擾的情況，如圖2所示：由于2臺(tái)ASC不能相互跨越，且海側(cè)作業(yè)優(yōu)先級(jí)高于陸側(cè)作業(yè)優(yōu)先級(jí)，一旦2臺(tái)ASC發(fā)生作業(yè)沖突，海側(cè)ASC就優(yōu)先于陸側(cè)ASC進(jìn)行作業(yè)，在此過(guò)程中，陸側(cè)ASC要與海側(cè)ASC保持一定的安全距離。

2 模型建立

本文考慮雙ASC不可跨越以及作業(yè)過(guò)程中保持安全距離等因素，建立混合整數(shù)規(guī)劃模型。為得到雙ASC最長(zhǎng)完工時(shí)間的最小值，假設(shè)：（1）接力區(qū)存儲(chǔ)空間足夠大;（2）ASC在移動(dòng)時(shí)始終保持勻速，不考慮加速或減速;（3）不考慮ASC小車的移動(dòng);（4）ASC提箱與放箱所用的時(shí)間一致，并且為固定值;（5）在ASC作業(yè)過(guò)程中不考慮翻箱;（6）ASC在交接點(diǎn)作業(yè)時(shí)無(wú)須等待。

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

n為總?cè)蝿?wù)數(shù)量;K為ASC的集合，K={1，2}，k∈K;Jk為第k臺(tái)ASC的任務(wù)集;J為所有ASC的任務(wù)集，J=J1∪J2;A為同一任務(wù)拆分后的子任務(wù)對(duì){i，j}的集合，A={（i，j）|i∈Jk，j∈Jk′，k≠k′};P1為目標(biāo)箱在初始位置提箱任務(wù)的集合;D1為主作業(yè)中在接力點(diǎn)放箱任務(wù)的集合;P2為接力作業(yè)中目標(biāo)箱在接力點(diǎn)提箱任務(wù)的集合;D2為接力作業(yè)中目標(biāo)箱在目的地放箱任務(wù)的集合;P=P1∪P2;D=D1∪D2;v為ASC的移動(dòng)速度;l為單位貝位的長(zhǎng)度;si為任務(wù)i的開(kāi)始時(shí)刻;ti為任務(wù)i的操作完成時(shí)刻;B為單箱區(qū)總的貝位數(shù)，b=1，2，…，B;Tij為ASC從任務(wù)i的結(jié)束位置移動(dòng)到任務(wù)j的初始位置所需時(shí)間，當(dāng)i=j時(shí)，表示ASC從一個(gè)任務(wù)的起點(diǎn)移動(dòng)到終點(diǎn)的時(shí)間;oi為操作提箱任務(wù)i或放箱任務(wù)i所需的時(shí)間;σ為雙ASC作業(yè)的安全距離;bik為ASC k作業(yè)任務(wù)i時(shí)所在的貝位;h（1）i∈{0，1}，若bi1為海側(cè)交接點(diǎn)則h（1）i=1，否則h（1）i=0;h（2）i∈{0，1}，若bi2為陸側(cè)交接點(diǎn)則h（2）i=1，否則h（2）i=0;M為足夠大的數(shù)。

決策變量：x（k）ij∈{0，1}，若ASC k以（i，j）的順序進(jìn)行作業(yè)則x（k）ij=1，否則x（k）ij=0;u（k）i∈{0，1}，若ASC k從任務(wù)i開(kāi)始作業(yè)則u（k）i=1，否則u（k）i=0;w（k）i∈{0，1}，若ASC k在任務(wù)i結(jié)束作業(yè)則w（k）i=1，否則w（k）i=0;y（k）tb∈{0，1}，若ASC k在時(shí)刻t處于貝位b則y（k）tb=1，否則y（k）tb=0。

2.2 目標(biāo)函數(shù)及約束條件

式（1）是目標(biāo)函數(shù)，表示最小化雙ASC的最長(zhǎng)完工時(shí)間;式（2）表示每個(gè)接力任務(wù)的主作業(yè)只進(jìn)行一次操作;式（3）表示每個(gè)接力任務(wù)的接力作業(yè)最多進(jìn)行一次操作;式（4）和（5）確保ASC 1和ASC 2的移動(dòng)路徑從箱區(qū)的兩端開(kāi)始，在最后一個(gè)任務(wù)處結(jié)束;式（6）表示ASC從一個(gè)任務(wù)移動(dòng)到下一個(gè)任務(wù)所需要的時(shí)間;式（7）表示同一任務(wù)的操作完成時(shí)刻約束;式（8）保證任務(wù)間作業(yè)的連續(xù)性;式（9）表示任意兩個(gè)任務(wù)之間的起止時(shí)間關(guān)系;式（10）表示接力點(diǎn)的提箱操作應(yīng)當(dāng)在這個(gè)接力點(diǎn)放箱操作完成之后再進(jìn)行;式（11）和（12）確保一臺(tái)ASC每次只能作業(yè)一個(gè)任務(wù)箱;式（13）保證一個(gè)任務(wù)總的作業(yè)時(shí)間由ASC的移動(dòng)時(shí)間與操作時(shí)間組成;式（14）確保交接點(diǎn)處的任務(wù)靠近哪一側(cè)就只能由那一側(cè)對(duì)應(yīng)的ASC完成;式（15）表示對(duì)于由同一任務(wù)拆分而來(lái)的兩個(gè)任務(wù)，先完成主作業(yè)，后完成接力作業(yè);式（16）保證雙ASC在作業(yè)過(guò)程中保持安全距離。

3 算法設(shè)計(jì)

GA是一種常用的元啟發(fā)式算法，雙ASC的動(dòng)態(tài)接力問(wèn)題是NP難問(wèn)題，而GA對(duì)該類問(wèn)題具有良好的適應(yīng)性，因此本文采用GA進(jìn)行求解。

3.1 染色體編碼與解碼

染色體采用實(shí)數(shù)編碼的形式，整數(shù)部分表示集裝箱的任務(wù)編號(hào)，小數(shù)部分表示接力作業(yè)的不同階段。染色體長(zhǎng)度為任務(wù)箱量，即ASC作業(yè)任務(wù)數(shù)。編碼時(shí)，首先對(duì)ASC和集裝箱任務(wù)進(jìn)行編號(hào)，海側(cè)ASC編號(hào)為1，陸側(cè)ASC編號(hào)為2。為滿足式（4）和式（5）約束，ASC 1和ASC 2的第一個(gè)任務(wù)的初始貝位必須是貝位1和貝位42（見(jiàn)第4.1節(jié)）。將染色體的前半段設(shè)置為需要ASC 1完成的任務(wù)，后半段設(shè)置為需要ASC 2完成的任務(wù)，以滿足式（13）約束。對(duì)于不需要接力的任務(wù)，一個(gè)任務(wù)對(duì)應(yīng)一臺(tái)ASC，對(duì)于需要接力的任務(wù)，其作業(yè)的2個(gè)階段需要2臺(tái)ASC共同完成。如圖3所示：7.1表示任務(wù)7的第一個(gè)階段，由ASC 1完成;7.2表示任務(wù)7的第二個(gè)階段，由ASC 2完成。

解碼過(guò)程分為2個(gè)階段，首先根據(jù)對(duì)應(yīng)基因位將任務(wù)分配至2臺(tái)ASC，然后按照任務(wù)段中的任務(wù)順序依次解碼，得到ASC 1和ASC 2對(duì)應(yīng)的集裝箱作業(yè)序列。在圖3所示的染色體中，解碼得到ASC 1的作業(yè)序列為{2，7.1，6，10.2，9，8，5}，ASC 2的作業(yè)序列為{3，7.2，10.1，1，4}。

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)為f（u）=1/Cmax，其中Cmax為ASC最長(zhǎng)完工時(shí)間的最小值。

3.3 遺傳操作

3.3.1 選擇操作

本文的選擇操作采取精英保留的策略，將種群中適應(yīng)度值大的前10%的個(gè)體保留下來(lái)，與隨機(jī)產(chǎn)生的90%的新個(gè)體形成新種群。

3.3.2 交叉操作

由于本文染色體的集裝箱任務(wù)部分由海側(cè)ASC和陸側(cè)ASC完成，所以交叉時(shí)也將其分為海側(cè)ASC作業(yè)序列和陸側(cè)ASC作業(yè)序列2部分進(jìn)行交叉，且每個(gè)部分都采用雙切點(diǎn)交叉法。根據(jù)交叉概率，每次從上一代個(gè)體中選擇2個(gè)個(gè)體作為父代，如圖4a所示：在每個(gè)父代個(gè)體的海側(cè)ASC作業(yè)序列部分隨機(jī)生成2個(gè)交叉點(diǎn)①和②，將這兩個(gè)交叉點(diǎn)之間的基因值進(jìn)行交換;在每個(gè)父代個(gè)體的陸側(cè)ASC作業(yè)序列部分隨機(jī)生成2個(gè)交叉點(diǎn)③和④，也將這兩個(gè)交叉點(diǎn)之間的基因值進(jìn)行交換。得到的新個(gè)體見(jiàn)圖4b。

3.3.3 變異操作

本文采用逆轉(zhuǎn)變異法，即在每臺(tái)ASC的作業(yè)序列中隨機(jī)選2個(gè)點(diǎn)，將其基因值進(jìn)行交換。同樣地，由于染色體的集裝箱任務(wù)部分由海側(cè)ASC和陸側(cè)ASC完成，所以變異時(shí)也將其分為海側(cè)ASC作業(yè)序列和陸側(cè)ASC作業(yè)序列2部分進(jìn)行變異。圖5為變異操作示意圖。

3.3.4 修復(fù)操作

經(jīng)過(guò)交叉和變異操作后，可能會(huì)產(chǎn)生一些不可行的染色體，因此需要進(jìn)行基因修復(fù)。本文設(shè)計(jì)的基因修復(fù)規(guī)則如下：

規(guī)則1：如果新種群中產(chǎn)生了不滿足式（14）約束的個(gè)體，即染色體中出現(xiàn)了接力任務(wù)的接力作業(yè)開(kāi)始時(shí)間早于主作業(yè)的完成時(shí)間的情況，則此條染色體需要修復(fù)，將相關(guān)基因值的位置進(jìn)行調(diào)整。

規(guī)則2：對(duì)于不需要接力的任務(wù)以及由需要接力的任務(wù)拆分而來(lái)的2個(gè)子任務(wù)，ASC只能對(duì)該任務(wù)作業(yè)一次，即2臺(tái)ASC對(duì)應(yīng)的作業(yè)序列中的基因值都各不相同。如果ASC 1或ASC 2對(duì)應(yīng)的染色體作業(yè)序列中有2個(gè)基因值相同（如圖4b所示），則需要基因修復(fù)。修復(fù)結(jié)果如圖4c所示。

4 算例分析

4.1 參數(shù)設(shè)置

某自動(dòng)化集裝箱碼頭的堆場(chǎng)采用兩端式雙ASC的布置，一個(gè)箱區(qū)有40個(gè)貝位，設(shè)海側(cè)交接點(diǎn)為貝位1，陸側(cè)交接點(diǎn)為貝位42，從海側(cè)至陸側(cè)貝位號(hào)依次遞增。海側(cè)ASC的起始位置為貝位1，陸側(cè)ASC的起始位置為貝位42。2臺(tái)同型號(hào)的ASC協(xié)同作業(yè)，在移動(dòng)過(guò)程中保持勻速，并且速度相同，安全距離為1個(gè)貝位，放箱操作和提箱操作的時(shí)間為70 s。以20個(gè)集裝箱任務(wù)為例，輸入的數(shù)據(jù)見(jiàn)表1。

交叉和變異算子對(duì) GA性能有重要影響，問(wèn)題類型的不同導(dǎo)致算法參數(shù)值的選取存在差異。為找到適當(dāng)?shù)慕徊婧妥儺愃阕拥膮?shù)值，本文對(duì)動(dòng)態(tài)接力點(diǎn)模式下雙ASC的調(diào)度問(wèn)題進(jìn)行多次實(shí)驗(yàn)。設(shè)置種群數(shù)量為100，最大迭代次數(shù)為100，實(shí)驗(yàn)在Intel（R） Core（TM）i5的處理器、內(nèi)存4 GB的PC上進(jìn)行，在MATLAB 2018a平臺(tái)上編程實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果如表 2 所示：在所有備選參數(shù)中，當(dāng)交叉概率Pc=0.9，變異概率Pm= 0.2時(shí)算法性能最佳。在后面的數(shù)值實(shí)驗(yàn)中本文將采用此組交叉和變異參數(shù)值進(jìn)行計(jì)算。

4.2 兩種模式下的結(jié)果分析

4.2.1 動(dòng)態(tài)接力點(diǎn)模式下雙ASC調(diào)度結(jié)果

圖6為動(dòng)態(tài)接力點(diǎn)模式下ASC的移動(dòng)路線圖，當(dāng)雙ASC發(fā)生作業(yè)沖突時(shí)，陸側(cè)ASC等待海側(cè)ASC完成作業(yè)后再進(jìn)行作業(yè)。動(dòng)態(tài)接力點(diǎn)模式下雙ASC的最長(zhǎng)完工時(shí)間為3 078 s，雙ASC的具體調(diào)度結(jié)果見(jiàn)表3。圖7為動(dòng)態(tài)接力點(diǎn)模式下調(diào)度結(jié)果的甘特圖，其中每個(gè)矩形兩側(cè)的部分是ASC提放箱的時(shí)間，中間部分是ASC移動(dòng)的時(shí)間（或移動(dòng)加等待的時(shí)間），任務(wù)7～14為接力任務(wù)，由2臺(tái)ASC共同完成。

4.2.2 固定貝位接力模式下雙ASC調(diào)度結(jié)果

圖8為固定貝位接力模式下ASC移動(dòng)路線圖，從圖8可以看出雙ASC在作業(yè)過(guò)程中未發(fā)生沖突，海（陸）側(cè)ASC只能在海（陸）側(cè)移動(dòng)，不能到另一側(cè)進(jìn)行作業(yè)。固定貝位接力模式下雙ASC的最長(zhǎng)完工時(shí)間為3 251 s，雙ASC的具體調(diào)度結(jié)果見(jiàn)表4。圖9為固定貝位接力模式下調(diào)度結(jié)果的甘特圖。

由表3和4可知，動(dòng)態(tài)接力點(diǎn)模式下雙ASC的完工時(shí)間為3 078 s，相較于固定貝位接力模式，雙ASC的作業(yè)效率提高了5.3%。從ASC的作業(yè)效率看，在相同任務(wù)量的情況下，動(dòng)態(tài)接力點(diǎn)模式優(yōu)于固定貝位接力模式。從圖6和8可以看出，在固定貝位接力模式下，ASC的移動(dòng)范圍有一定的局限性，而動(dòng)態(tài)接力點(diǎn)模式下ASC的移動(dòng)范圍沒(méi)有局限，這更有利于ASC間的相互協(xié)作。在圖7和9中可以更直觀地看出每個(gè)任務(wù)的作業(yè)時(shí)間以及ASC間的沖突情況，雖然動(dòng)態(tài)接力點(diǎn)模式中有干擾發(fā)生，但ASC整體的完工時(shí)間是優(yōu)于固定貝位接力模式的。

為進(jìn)一步驗(yàn)證動(dòng)態(tài)接力點(diǎn)模式的有效性，本文設(shè)置不同規(guī)模的算例，并用GA和CPLEX對(duì)不同作業(yè)模式、不同規(guī)模的算例進(jìn)行求解，結(jié)果見(jiàn)表5。

從表5可以看出：在不同任務(wù)量下，GA和CPLEX求出的ASC完工時(shí)間相差不大;由于CPLEX對(duì)大規(guī)模算例求解較慢，所以當(dāng)任務(wù)量大于等于50時(shí)，本文設(shè)置CPLEX的求解時(shí)間的上限為14 000 s，即運(yùn)行時(shí)間到達(dá)14 000 s后，算法停止運(yùn)行;對(duì)于任務(wù)量為200的算例，由于CPLEX的內(nèi)存不足，所以無(wú)法在可接受的范圍內(nèi)求出最優(yōu)解。通過(guò)對(duì)比GA和CPLEX的計(jì)算結(jié)果能夠得出，GA計(jì)算出的結(jié)果是有效并且能被接受的，可以作為最優(yōu)解。

5 結(jié) 論

本文針對(duì)自動(dòng)化集裝箱碼頭堆場(chǎng)單箱區(qū)雙自動(dòng)化軌道吊（ASC）的接力問(wèn)題進(jìn)行了研究?？紤]了雙ASC不可跨越以及作業(yè)過(guò)程中保持安全距離等因素，以最小化雙ASC的最長(zhǎng)完工時(shí)間為目標(biāo)，建立混合整數(shù)規(guī)劃模型，并設(shè)計(jì)遺傳算法（GA）進(jìn)行求解。在算例分析部分，本文設(shè)計(jì)了不同規(guī)模的算例，計(jì)算結(jié)果表明，與固定貝位接力模式相比，在動(dòng)態(tài)接力點(diǎn)模式下雙ASC的最長(zhǎng)完工時(shí)間更短，作業(yè)效率更高。然而，在實(shí)際操作中，ASC作業(yè)過(guò)程中的翻箱以及ASC與自動(dòng)導(dǎo)引小車（AGV）和外集卡的協(xié)調(diào)等問(wèn)題都會(huì)影響ASC的作業(yè)效率，在后續(xù)研究中可以考慮雙ASC與AGV和外集卡的聯(lián)合調(diào)度，使研究更加具有現(xiàn)實(shí)意義。

參考文獻(xiàn)：

[1]初良勇， 阮志毅， 李淑娟. 基于遺傳算法的港口集裝箱堆場(chǎng)場(chǎng)橋智能調(diào)度優(yōu)化[J]. 中國(guó)航海， 2018， 41（1）： 48-52.

[2]劉志雄， 李俊， 張煜， 等. 基于混合演化策略算法的多場(chǎng)橋調(diào)度優(yōu)化[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2016， 33（5）： 242-247.

[3]CHANG Daofang， JIANG Zuhua， YAN Wei， et al. Developing a dynamic rolling-horizon decision strategy for yard crane scheduling[J]. Advanced Engineering Informatics， 2011， 25： 485-494. DOI： 10.1016/j.aei.2011.02.003.

[4]裴磊磊， 萇道方. 基于仿真優(yōu)化的自動(dòng)化集裝箱碼頭雙ARMG調(diào)度研究[J]. 廣西大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017， 42（2）： 500-510. DOI： 10.13624/j.cnki.issn.1001-7445.2017.0500.

[5]盧毅勤. 自動(dòng)化碼頭堆場(chǎng)設(shè)備聯(lián)合調(diào)度不確定優(yōu)化[J]. 計(jì)算機(jī)仿真， 2019， 36（8）： 325-328.

[6]HE Junliang， TAN Caimao， ZHANG Yuting， et al. Yard crane scheduling problem in a container terminal considering risk caused by uncertainty[J]. Advanced Engineering Informatics， 2019， 39： 14-24. DOI： 10.1016/j.aei.2018.11.004.

[7]CARLO H J， MARTNEZ-ACEVEDO F L. Priority rules for twin automated stacking cranes that collaborate[J]. Computers & Industrial Engineering， 2015， 89： 23-33. DOI： 10.1016/j.cie.2015.04.026.

[8]NG W C， MAK K L. Yard crane scheduling in port container terminals[J]. Applied Mathematical Modelling， 2005， 29： 263-276. DOI： 10.1016/j.apm.2004.09.009.

[9]PARK T， CHOE R， OK S M， et al. Real-time scheduling for twin RMGs in an automated container yard[J]. OR Spectrum， 2010， 32： 593-615. DOI： 10.1007/s00291-010-0209-0.

[10]鄭紅星， 劉保利， 匡海波， 等. 考慮實(shí)時(shí)預(yù)倒箱的出口箱堆場(chǎng)多場(chǎng)橋調(diào)度優(yōu)化[J]. 中國(guó)管理科學(xué)， 2018， 26（9）： 85-96. DOI： 10.16381/j.cnki.issn1003-207x.2018.09.009.

[11]徐飛慶. 基于軟時(shí)間窗的集裝箱碼頭場(chǎng)橋調(diào)度研究[J]. 物流工程與管理， 2016， 38（3）： 23-26. DOI： 10.3969/j.issn.1674-4993.2016.03.008.