混堆模式下基于動(dòng)態(tài)規(guī)則NSGA Ⅱ的自動(dòng)堆垛起重機(jī)作業(yè)優(yōu)化

高銀萍，萇道方*，陳俊賢

（1.上海海事大學(xué) 物流科學(xué)與工程研究院，上海 201306；2.南洋理工大學(xué) 機(jī)械與宇航工程學(xué)院，新加坡 639798 新加坡）

0 引言

在“一帶一路”建設(shè)中，港口承擔(dān)著舉足輕重的作用，近年來中國集裝箱吞吐量一直穩(wěn)居世界第一，但是逐步增長的集裝箱吞吐量給碼頭發(fā)展帶來了壓力，也對(duì)碼頭運(yùn)營提出了更高要求。隨著物聯(lián)網(wǎng)、計(jì)算機(jī)通信等技術(shù)的發(fā)展與成熟，自動(dòng)化碼頭成為碼頭發(fā)展的必然趨勢(shì)，自動(dòng)化設(shè)備的投入提高了碼頭生產(chǎn)的安全性。由于人的決策減少，智能系統(tǒng)制定的決策并不能應(yīng)對(duì)實(shí)際作業(yè)過程中發(fā)生的不確定場(chǎng)景。交通事故、擁堵等不確定場(chǎng)景的干涉，外集卡的到達(dá)時(shí)間具備動(dòng)態(tài)性，而根據(jù)外集卡預(yù)計(jì)到達(dá)時(shí)間制定的自動(dòng)堆垛起重機(jī)（Automated Stacking Crane，ASC）作業(yè)計(jì)劃難以適用，如何調(diào)整優(yōu)化ASC 與外集卡的作業(yè)成為提高堆場(chǎng)作業(yè)效率的關(guān)鍵問題。

ASC 是自動(dòng)化集裝箱碼頭堆場(chǎng)內(nèi)用于處理集裝箱的裝卸設(shè)備，而大多傳統(tǒng)碼頭采用的裝卸設(shè)備主要是輪胎式起重機(jī)，有些文獻(xiàn)中也將這類裝卸設(shè)備稱為場(chǎng)橋。目前針對(duì)場(chǎng)橋調(diào)度的文獻(xiàn)主要有：范厚明等［1］針對(duì)出口箱區(qū)分配問題，提出分區(qū)域平衡策略，在此基礎(chǔ)上研究了出口箱區(qū)多場(chǎng)橋聯(lián)合作業(yè)問題，以場(chǎng)橋的移動(dòng)成本和空閑成本最小為目標(biāo)，結(jié)合模擬退火算法與遺傳算法（Genetic Algorithm，GA）求解該問題。Wu等［2］提出了箱區(qū)內(nèi)多場(chǎng)橋的調(diào)度，考慮場(chǎng)橋間的交叉作業(yè)、安全距離等約束，以集卡等待時(shí)間最短為目標(biāo)建立連續(xù)時(shí)間模型，并設(shè)計(jì)啟發(fā)式算法求出近似解。Han等［3］研究了自動(dòng)化碼頭箱區(qū)內(nèi)雙ASC 調(diào)度問題，總結(jié)了ASC 作業(yè)干擾的四種模式，并以完成所有作業(yè)需求的時(shí)間最少為目標(biāo)，建立混合整數(shù)規(guī)劃模型，同時(shí)設(shè)計(jì)遺傳算法求解，驗(yàn)證了其在大規(guī)模算例上的優(yōu)越性。Kress等［4］在保證陸側(cè)集裝箱能準(zhǔn)時(shí)處理作業(yè)的同時(shí)，考慮陸側(cè)與海側(cè)軌道式起重機(jī)之間的非交叉約束，最小化海側(cè)集裝箱的作業(yè)時(shí)間。Speer等［5］將自動(dòng)化起重機(jī)的移動(dòng)和干涉等作業(yè)特征列入自動(dòng)化起重機(jī)調(diào)度算法的考慮因素中，根據(jù)實(shí)際作業(yè)場(chǎng)景中的數(shù)據(jù)構(gòu)建仿真模型，以自動(dòng)化起重機(jī)效率和任務(wù)的平均作業(yè)時(shí)間為評(píng)價(jià)指標(biāo)，比較了四種不同的自動(dòng)化起重機(jī)系統(tǒng)在碼頭的作業(yè)效率。Gharehgozli等［6］以完成所有任務(wù)時(shí)間和ASC 等待時(shí)間最少為目標(biāo)，根據(jù)ASC 調(diào)度方式、集裝箱堆存位置、交互區(qū)域位置等決策變量設(shè)計(jì)多種啟發(fā)式算法，通過仿真實(shí)驗(yàn)研究了箱區(qū)內(nèi)交互區(qū)域?qū)SC 性能的影響。

在混合堆存集裝箱碼頭中，Yu等［7］建立混合整數(shù)線性規(guī)劃模型，以集卡等待成本和等待造成的懲罰成本最小為目標(biāo)，設(shè)計(jì)滾動(dòng)時(shí)域算法來優(yōu)化場(chǎng)橋調(diào)度。鄭紅星等［8］研究混堆模式下多場(chǎng)橋調(diào)度問題時(shí)，考慮了多場(chǎng)橋間的作業(yè)約束與內(nèi)集卡的等待時(shí)間，以內(nèi)集卡等待時(shí)間和場(chǎng)橋移動(dòng)成本最小為目標(biāo)構(gòu)建數(shù)學(xué)模型，并設(shè)計(jì)改進(jìn)的遺傳算法進(jìn)行求解。之后鄭紅星等［9］進(jìn)一步研究了外集卡提箱時(shí)間不確定時(shí)多場(chǎng)橋的調(diào)度問題，以碼頭作業(yè)成本與倒箱量最小為優(yōu)化目標(biāo)，提出滾動(dòng)時(shí)域算法，同時(shí)在每個(gè)時(shí)域中采用嵌入倒箱策略的遺傳算法，得出各時(shí)間段內(nèi)場(chǎng)橋的調(diào)度方案。

關(guān)于不確定調(diào)度的研究有：周磊磊等［10］提出了不確定干擾時(shí)外集卡提箱策略，運(yùn)用滾動(dòng)窗口再調(diào)度機(jī)制優(yōu)化集裝箱的作業(yè)順序。針對(duì)出口箱交箱時(shí)間不確定性時(shí)的場(chǎng)橋調(diào)度問題，邵乾虔等［11］運(yùn)用馬爾可夫鏈對(duì)交箱序列預(yù)測(cè)：第一階段構(gòu)建翻箱次數(shù)最小的模型，設(shè)計(jì)模擬退火算法進(jìn)行求解；第二階段構(gòu)建場(chǎng)橋移動(dòng)距離最小的模型，提出實(shí)時(shí)調(diào)度算法，即根據(jù)出口箱實(shí)際到達(dá)時(shí)間與預(yù)測(cè)序列，修正預(yù)測(cè)序列，進(jìn)行實(shí)時(shí)堆存與調(diào)度。Zheng等［12］采用兩階段隨機(jī)規(guī)劃來解決提箱任務(wù)時(shí)間不確定下的單場(chǎng)橋調(diào)度問題，設(shè)計(jì)基于規(guī)則的啟發(fā)式算法，驗(yàn)證其求解大規(guī)模問題的性能。He等［13］提出了集裝箱作業(yè)任務(wù)的到達(dá)時(shí)間和作業(yè)量等信息不確定時(shí)的場(chǎng)橋調(diào)度問題，通過最小化因不確定因素導(dǎo)致任務(wù)完成時(shí)間的延誤成本和額外損失，設(shè)計(jì)了基于遺傳算法的三階段算法，求解不確定場(chǎng)景下場(chǎng)橋的作業(yè)順序。Zeng等［14］研究了集卡到達(dá)信息部分已知情況下的集裝箱作業(yè)優(yōu)化問題，以集裝箱翻箱量最小為目標(biāo)，優(yōu)化了集裝箱作業(yè)順序和翻箱計(jì)劃，并設(shè)計(jì)了五種啟發(fā)式算法求解該模型。馬夢(mèng)知等［15］就送箱集卡隨機(jī)到港問題，提出送箱集卡預(yù)約和場(chǎng)橋調(diào)度協(xié)同優(yōu)化，以集卡排隊(duì)等待時(shí)間、集卡調(diào)整數(shù)量、所有時(shí)段內(nèi)未完成任務(wù)所需要場(chǎng)橋的作業(yè)時(shí)間和每個(gè)時(shí)段內(nèi)未完成任務(wù)所需要的時(shí)間最小為目標(biāo)，構(gòu)建雙層規(guī)劃模型，設(shè)計(jì)并行遺傳算法求解。為了應(yīng)對(duì)集卡司機(jī)與碼頭之間的信息缺失問題，李娜等［16］在集卡預(yù)約問題中，以集卡預(yù)約提箱配額為研究對(duì)象，最小化箱區(qū)配備的場(chǎng)橋數(shù)量和箱區(qū)內(nèi)集卡的平均等待時(shí)間，并設(shè)計(jì)運(yùn)用非支配排序遺傳算法Ⅱ（Non-dominated Sorting Genetic Algorithm Ⅱ，NSGA Ⅱ）求解。Kucuksayacigil等［17］在求解雙目標(biāo)資源約束的調(diào)度問題時(shí)，改進(jìn)了NSGA Ⅱ并驗(yàn)證了其優(yōu)越性。

在集裝箱碼頭堆場(chǎng)裝卸設(shè)備的研究中，包含了單場(chǎng)橋、多場(chǎng)橋之間的調(diào)度，并考慮了場(chǎng)橋間的作業(yè)約束，以場(chǎng)橋作業(yè)時(shí)間和集卡等待時(shí)間最小為優(yōu)化目標(biāo)，采用遺傳算法等智能優(yōu)化算法進(jìn)行求解，而在研究ASC 不確定調(diào)度時(shí)很少考慮進(jìn)出口集裝箱混合堆存模式的堆場(chǎng)特征。在實(shí)際作業(yè)過程中，動(dòng)態(tài)變化的作業(yè)場(chǎng)景會(huì)影響ASC 效率，例如，外集卡延遲或提前進(jìn)場(chǎng)會(huì)對(duì)實(shí)現(xiàn)制定的ASC 作業(yè)計(jì)劃產(chǎn)生干擾。若外集卡因交通狀況等因素不能按預(yù)計(jì)時(shí)間抵達(dá)堆場(chǎng)，原先計(jì)劃作業(yè)的ASC 會(huì)出現(xiàn)等待時(shí)間長、無作業(yè)等現(xiàn)象，因此需要根據(jù)場(chǎng)景變化實(shí)時(shí)調(diào)整ASC 作業(yè)計(jì)劃，避免ASC 空待、外集卡等待等不必要成本。

因此，本文綜合考慮ASC 處理不同類型集裝箱的需求，以自動(dòng)化碼頭混合堆存模式的堆場(chǎng)為研究對(duì)象，探究外集卡進(jìn)場(chǎng)時(shí)間動(dòng)態(tài)變化場(chǎng)景下ASC 作業(yè)優(yōu)化問題，并建立了最小化ASC 作業(yè)時(shí)間和等待時(shí)間的雙目標(biāo)混合整數(shù)規(guī)劃模型，設(shè)計(jì)了基于動(dòng)態(tài)規(guī)則的非支配排序遺傳算法Ⅱ（Nondominated Sorting Genetic Algorithm Ⅱ based on Dynamic Rules，DRNSGA Ⅱ）求解。

1 問題描述及模型建立

1.1 問題描述

自動(dòng)化碼頭混堆模式下進(jìn)出口集裝箱堆放在同一箱區(qū)，箱區(qū)內(nèi)分別有兩臺(tái)自動(dòng)堆垛起重機(jī)（ASC）完成進(jìn)出口箱的作業(yè)，進(jìn)口集裝箱堆放在箱區(qū)陸側(cè)，出口集裝箱則堆放在箱區(qū)海側(cè)，箱區(qū)中間為進(jìn)出口集裝箱暫存區(qū)，而靠近陸側(cè)的ASC 負(fù)責(zé)外集卡的裝卸集裝箱任務(wù)，靠近海側(cè)的ASC 則負(fù)責(zé)AGV 的裝卸集裝箱任務(wù)。外集卡進(jìn)入堆場(chǎng)主要有三種作業(yè)需求：一是空集卡進(jìn)入堆場(chǎng)提箱，箱區(qū)靠近陸側(cè)的ASC 提起進(jìn)口集裝箱，裝至空集卡上，集卡重載離開；二是重集卡集港，陸側(cè)ASC 卸載集卡上的出口集裝箱，將該集裝箱放置在箱區(qū)的暫存區(qū)，海側(cè)ASC 將此集裝箱從暫存區(qū)提到出口箱區(qū)，集卡空載離開；三是重集卡重進(jìn)重出，重集卡載出口集裝箱進(jìn)場(chǎng)，陸側(cè)ASC 卸載出口集裝箱后，再從暫存區(qū)移動(dòng)到陸側(cè)進(jìn)口箱區(qū)，提起進(jìn)口集裝箱，裝至空集卡上，集卡載進(jìn)口箱離開。外集卡進(jìn)場(chǎng)作業(yè)示意圖如圖1 所示。

在實(shí)際作業(yè)過程中，外集卡不在碼頭運(yùn)營管理范圍內(nèi)，且容易受到碼頭外部道路交通狀況影響，無法按照預(yù)計(jì)時(shí)間抵達(dá)堆場(chǎng)，影響外集卡準(zhǔn)確到達(dá)率。外集卡早于預(yù)計(jì)時(shí)間或晚于預(yù)計(jì)時(shí)間進(jìn)入堆場(chǎng)，均會(huì)干擾碼頭制定的堆場(chǎng)計(jì)劃，影響箱區(qū)內(nèi)ASC 作業(yè)次序。若外集卡早于預(yù)計(jì)時(shí)間到達(dá)碼頭，原計(jì)劃為其指定的ASC 可能正在作業(yè)，不能為其服務(wù)，該集卡則需要在閘口處等待，影響閘口處的道路通暢；若外集卡晚于預(yù)計(jì)時(shí)間到達(dá)碼頭，原計(jì)劃為其指定的ASC 只能等待，導(dǎo)致設(shè)備能耗高。因此，外集卡動(dòng)態(tài)到達(dá)場(chǎng)景對(duì)碼頭的運(yùn)營與成本管理具有負(fù)面影響，在此場(chǎng)景下，有必要?jiǎng)討B(tài)調(diào)整ASC 作業(yè)任務(wù)。

1.2 模型建立

根據(jù)混堆模式下不同外集卡作業(yè)需求，在外集卡到達(dá)時(shí)間具有動(dòng)態(tài)性的場(chǎng)景下，研究ASC 作業(yè)序列優(yōu)化問題，并制定了兩個(gè)優(yōu)化目標(biāo)：一是ASC 總作業(yè)時(shí)間最短，二是ASC 和外集卡的等待時(shí)間最短。第一個(gè)優(yōu)化目標(biāo)的影響因素：一是兩臺(tái)ASC 的干擾，兩臺(tái)ASC 不能相互跨越和相鄰太近；二是ASC 等待外集卡，因外集卡延誤ASC 無法作業(yè)。第二個(gè)優(yōu)化目標(biāo)的影響因素：一是ASC 等待外集卡；二是外集卡等待ASC。在本文問題中，堆場(chǎng)每個(gè)箱區(qū)均有一臺(tái)ASC 專門服務(wù)于外集卡，包括集港、提箱等業(yè)務(wù)需求，各箱區(qū)內(nèi)包含多個(gè)貝位，從陸側(cè)至海側(cè)方向按照編號(hào)計(jì)數(shù)，且每個(gè)箱區(qū)的貝位數(shù)相同。出于安全考慮，相鄰箱區(qū)的ASC 不能同時(shí)作業(yè)同一貝位，如圖2 所示，以防發(fā)生碰撞等狀況，相鄰ASC 作業(yè)時(shí)需保持一定的安全距離。

1.2.1 模型假設(shè)

1）ASC 作業(yè)任務(wù)由堆場(chǎng)計(jì)劃給定，包括ASC 處理的集裝箱所在貝位等信息；

2）每臺(tái)ASC 移動(dòng)速度相同，作業(yè)效率相同；

3）不同箱區(qū)的ASC 不能相互跨越，相鄰ASC 作業(yè)的貝位需要留有兩個(gè)貝位的安全距離；

4）外集卡預(yù)計(jì)到達(dá)時(shí)間已知；

5）所有作業(yè)集裝箱均為普通標(biāo)準(zhǔn)箱；

6）ASC 作業(yè)1 輛外集卡即視為1 次作業(yè)任務(wù)，為一個(gè)工序；

7）作業(yè)過程中不存在翻箱作業(yè)，ASC 可以直接處理目標(biāo)箱；

8）開始時(shí)間計(jì)為0 時(shí)刻。

1.2.2 數(shù)學(xué)符號(hào)定義

1）參數(shù)設(shè)置。

B：箱區(qū)集合；

A：貝位集合，a∈A；

K：外集卡集合，k∈K；

C：ASC 集合，c=1，2，…，C；

N：任務(wù)總數(shù)，n=1，2，…，N；

Tk：外集卡k預(yù)計(jì)到達(dá)時(shí)刻；

：ASCc處理外集卡k作業(yè)時(shí)長；

t：ASC 駛過一個(gè)貝位的時(shí)長；

ωe：權(quán)重；

ωl：權(quán)重；

2）變量。

：ASCc完成外集卡k任務(wù)的時(shí)刻；

：ASCc開始處理外集卡k任務(wù)的時(shí)刻；

：ASCc早于外集卡k開始作業(yè)的時(shí)長；

：ASCc晚于外集卡k開始作業(yè)的時(shí)長；

1.2.3 目標(biāo)函數(shù)建立

其中：式（1）表示ASC 完成所有作業(yè)時(shí)間的最小化；式（2）表示ASC 完成集卡任務(wù)的時(shí)間；式（3）表示ASC 與外集卡兩者等待時(shí)間的最小化。

1.2.4 約束條件建立

其中：式（4）表示每個(gè)貝位a只能由一臺(tái)ASC 進(jìn)行作業(yè)；式（5）表示每個(gè)外集卡的作業(yè)箱只在一個(gè)貝位處；式（6）表示ASC 在第n個(gè)工序時(shí)的作業(yè)狀態(tài)；式（7）～（8）表示每臺(tái)ASC分工作業(yè)，完成所有外集卡k的作業(yè)箱在貝位a處的任務(wù)；式（9）～（10）表示ASC 在一個(gè)工序n里只能完成一個(gè)集卡k的作業(yè)任務(wù)；式（11）表示每臺(tái)ASC 只有處理了第n個(gè)工序，才有可能處理第(n+1)個(gè)工序；式（12）表示ASC 開始處理外集卡k作業(yè)的時(shí)刻至少要大于等于該ASC 之前所有工序的作業(yè)時(shí)間和工序間的移動(dòng)時(shí)間之和；式（13）表示ASC 在兩相鄰工序的開始時(shí)間之差至少要大于等于該ASC 在兩工序間的移動(dòng)時(shí)間以及前一工序的作業(yè)時(shí)間之和；式（14）～（15）表示兩臺(tái)相鄰ASC 的作業(yè)位置需要保持兩個(gè)貝位的安全距離；式（16）～（17）表示ASC 早于和晚于外集卡的等待時(shí)長。

2 算法求解

在求解多目標(biāo)優(yōu)化問題時(shí)，非支配排序遺傳算法Ⅱ（NSGA Ⅱ）表現(xiàn)出較好的性能［18］，NSGA Ⅱ在執(zhí)行選擇、交叉、變異等遺傳操作之前，對(duì)種群中的個(gè)體進(jìn)行分層排序，確定支配與非支配關(guān)系，促使好的個(gè)體有更大的機(jī)會(huì)遺傳到下一代中。同時(shí)，NSGA Ⅱ中提出了個(gè)體的擁擠度來保證種群的多樣性，允許父代種群與子代種群的組合，便于父代中優(yōu)良個(gè)體的遺傳，因此降低了計(jì)算復(fù)雜度并盡可能保留滿意解。結(jié)合混堆模式下集裝箱的作業(yè)需求與外集卡動(dòng)態(tài)到達(dá)的特征，提出ASC 作業(yè)序列的優(yōu)化策略。

本研究設(shè)計(jì)了DRNSGA Ⅱ進(jìn)行模型求解，首先初始化種群，當(dāng)作業(yè)任務(wù)與計(jì)劃發(fā)生偏差時(shí)，依據(jù)相同類型任務(wù)可替換的規(guī)則為ASC 安排新的任務(wù)序列，保證初始解的可靠性；其次對(duì)個(gè)體進(jìn)行非支配排序及遺傳操作，產(chǎn)生子代種群；然后組合父代種群和子代種群，對(duì)其非支配排序和擁擠度計(jì)算，選出合適的個(gè)體作為新的父代種群，進(jìn)行選擇、交叉、變異的遺傳操作；最后通過父代與子代種群的迭代進(jìn)化，保留每一次的合適個(gè)體，找到全局最優(yōu)解。本文所提DRNSGA Ⅱ流程如圖3 所示。

2.1 染色體編碼

以ASC 處理外集卡的工序編號(hào)作為編碼方式，每條染色體的長度為ASC 處理外集卡的任務(wù)總量與ASC 數(shù)量之和，染色體的第一部分包含每臺(tái)ASC 處理任務(wù)的編號(hào)，第二部分則是每臺(tái)ASC 處理的任務(wù)量，染色體的編碼方式如圖4 所示，該條染色體表示有6 個(gè)任務(wù)和2 臺(tái)ASC，且ASC1 處理編號(hào)為1、2、3 的任務(wù)，ASC2 處理編號(hào)為4、5、6 的任務(wù)。

2.2 初始解生成

生成初始解時(shí)，將所有任務(wù)量隨機(jī)分配給ASC，保證每臺(tái)ASC 均有任務(wù)可做。根據(jù)染色體信息，可獲取每個(gè)任務(wù)對(duì)應(yīng)外集卡的預(yù)計(jì)到達(dá)時(shí)間和作業(yè)需求，由于外集卡到達(dá)時(shí)間動(dòng)態(tài)變化，需要對(duì)相關(guān)任務(wù)的染色體按照一定規(guī)則進(jìn)行動(dòng)態(tài)調(diào)整。動(dòng)態(tài)策略的偽代碼如下所示。

首先，確定外集卡抵達(dá)堆場(chǎng)的時(shí)間，若外集卡晚于預(yù)計(jì)到時(shí)間抵達(dá)堆場(chǎng)，則判斷計(jì)劃為該集卡分配的ASC 是否空閑。如果該ASC 正在作業(yè)，那么ASC 繼續(xù)完成作業(yè)并等待遲到的外集卡；如果ASC 空閑，那么在已到達(dá)的外集卡中尋找與遲到外集卡作業(yè)需求相同的替補(bǔ)外集卡。遲到外集卡的情況示例如下：

1）若遲到外集卡為空車進(jìn)港提箱，判斷已到外集卡中是否有進(jìn)入該ASC 所在箱區(qū)內(nèi)提箱的作業(yè)需求。若有相同需求的替補(bǔ)外集卡，優(yōu)先安排ASC 為有相同提箱需求的替補(bǔ)外集卡作業(yè)；否則在已到外集卡中尋找是否有進(jìn)入該ASC 所在箱區(qū)集港需求的外集卡。若有，則安排ASC 為其作業(yè)；否則在已到外集卡中尋找是否有需要進(jìn)入該ASC 所在箱區(qū)集港提箱（重進(jìn)重出需求）的外集卡。若有，則安排ASC 為其作業(yè)；否則此ASC 只能等待外集卡。需要說明的是，在尋找遲到外集卡的替補(bǔ)集卡時(shí)，因重進(jìn)重出作業(yè)時(shí)間長，ASC 優(yōu)先為與延誤外集卡有相同作業(yè)需求的已到外集卡服務(wù)，最后考慮重進(jìn)重出作業(yè)的外集卡。只要已到達(dá)集卡池中有滿足進(jìn)入該ASC 作業(yè)需求的外集卡，則安排ASC 為其作業(yè)，避免ASC 等待。

2）若遲到外集卡為重車集港，判斷已到外集卡中是否有進(jìn)入該ASC 所在箱區(qū)內(nèi)集港的作業(yè)需求。若有相同需求的替補(bǔ)外集卡，優(yōu)先安排ASC 為有相同集港需求的替補(bǔ)外集卡作業(yè)；否則在已到外集卡中尋找是否有需要進(jìn)入該ASC 所在箱區(qū)提箱需求的外集卡。若有，則安排ASC 為其作業(yè)；否則在已到外集卡中尋找是否有需要進(jìn)入該ASC 所在箱區(qū)集港提箱（重進(jìn)重出需求）的外集卡。若有，安排作業(yè)；否則此ASC 只能等待外集卡。

3）若遲到外集卡為重進(jìn)重出需求的集卡，判斷已到外集卡中是否有進(jìn)入該ASC 所在箱區(qū)內(nèi)重進(jìn)重出的作業(yè)需求。若有相同需求的替補(bǔ)外集卡，首先安排ASC 為有相同需求的替補(bǔ)外集卡作業(yè)；否則在已到外集卡中尋找是否有需要進(jìn)入該ASC 所在箱區(qū)集港需求的外集卡。若有其他集港需求的替補(bǔ)外集卡，則安排ASC 為其作業(yè)；否則在已到外集卡中尋找是否有需要進(jìn)入該ASC 所在箱區(qū)提箱的外集卡，有則為其安排ASC 作業(yè)；否則此ASC 只能等待外集卡。需要說明的是，因遲到外集卡的作業(yè)需求是重進(jìn)重出，所以首先安排有相同需求的替補(bǔ)外集卡進(jìn)場(chǎng)作業(yè)，最小化ASC 為原計(jì)劃外集卡服務(wù)和為替補(bǔ)外集卡服務(wù)的時(shí)間差；其次安排有集港需求的替補(bǔ)外集卡作業(yè)，以滿足出口箱裝船業(yè)務(wù)；最后考慮安排有提箱需求的外集卡作業(yè)。

2.3 遺傳操作

根據(jù)適應(yīng)度函數(shù)fit(f)=比較任意兩個(gè)染色體的目標(biāo)函數(shù)值，若染色體1 對(duì)應(yīng)解的目標(biāo)函數(shù)值均優(yōu)于染色體2的對(duì)應(yīng)解，則稱染色體1 的對(duì)應(yīng)解支配染色體2 的對(duì)應(yīng)解，且染色體1 對(duì)應(yīng)解為非支配解，對(duì)個(gè)體進(jìn)行非支配排序。對(duì)于每個(gè)目標(biāo)函數(shù)f，個(gè)體i擁擠度ni=按擁擠度從大至小排序并依次選取合適個(gè)體作為新種群。

交叉操作主要分為兩部分，分別對(duì)染色體的前后兩部分做交叉，交叉過程如圖5 所示。在第一部分任意選取兩個(gè)位置，交換兩條染色體所選位置之間的基因，第一步所選兩條染色體的基因?yàn)? 和1，交換兩條染色體前半部分中的3 和1，第二步所選兩條染色體的基因?yàn)? 和1，交換兩條染色體前半部分中的4 和1，第三步所選兩條染色體的基因?yàn)? 和6，交換兩條染色體前半部分中的5 和6；第二部分則選取兩個(gè)位置，交換ASC 的作業(yè)量。

變異操作的第一步是交換染色體第一部分的任意兩個(gè)基因，第二步是交換任意兩臺(tái)ASC 的作業(yè)量，變異過程如圖6 所示。

經(jīng)過交叉、變異操作后，產(chǎn)生的新種群可能會(huì)出現(xiàn)不可行解，則需要對(duì)其進(jìn)行基因修復(fù)，若兩相鄰ASC 同一時(shí)刻作業(yè)的集裝箱所在貝位不滿足安全距離的約束，可將其中一臺(tái)ASC 的任務(wù)轉(zhuǎn)移給另一臺(tái)ASC 作業(yè)，即染色體第二部分ASC的作業(yè)量做增減變化。

3 算例分析

根據(jù)Hu等［19］研究實(shí)驗(yàn)中的參數(shù)設(shè)置生成算例，設(shè)置種群大小為100，交叉概率為0.9，變異概率為0.3，最大迭代次數(shù)為500。根據(jù)某港口運(yùn)營數(shù)據(jù)，設(shè)置外集卡延遲到達(dá)和提前到達(dá)的比例分別為0.8 和0.2。本文算法編寫軟件為Matlab R2016b，運(yùn)行環(huán)境為Intel Core i5 處理器、內(nèi)存4 GB。

3.1 小規(guī)模算例結(jié)果

任務(wù)量為20 的算例求出的非支配解函數(shù)值如圖7 所示。圖7 中（f1，f2）為目標(biāo)函數(shù)值，f1為ASC 總作業(yè)時(shí)間，f2為ASC與外集卡的等待時(shí)間。非支配解的作業(yè)方案如表1 所示。

表1 中是所求非支配解對(duì)應(yīng)的ASC 作業(yè)方案：第一組方案中每臺(tái)ASC 作業(yè)量分別為5、8、5、2；第二組方案中每臺(tái)ASC 作業(yè)量分別為5、2、7、6；第三組方案中每臺(tái)ASC 作業(yè)量分別為5、5、4、6；第四組方案中每臺(tái)ASC 作業(yè)量分別為3、6、5、6；第五組方案中每臺(tái)ASC 作業(yè)量分別為4、6、3、7；第六組方案中每臺(tái)ASC 作業(yè)量分別為4、6、8、2；第七組方案中每臺(tái)ASC 作業(yè)量分別為6、4、4、6。

表1 非支配解作業(yè)方案Tab.1 Operation schemes of non-dominated solutions

根據(jù)外集卡動(dòng)態(tài)到達(dá)場(chǎng)景，本文提出ASC 動(dòng)態(tài)匹配外集卡作業(yè)任務(wù)的策略，并將其與ASC 隨機(jī)處理外集卡作業(yè)任務(wù)的策略對(duì)比，不同策略下算例求解結(jié)果如圖8 所示。整體上看，雖然存在動(dòng)態(tài)策略下部分非支配解結(jié)果大于隨機(jī)策略的結(jié)果，但動(dòng)態(tài)策略下得出的非支配解大多在隨機(jī)策略下的左下方，解的質(zhì)量明顯優(yōu)于隨機(jī)策略所得結(jié)果，驗(yàn)證所提動(dòng)態(tài)策略的有效性。這是由于針對(duì)外集卡到達(dá)時(shí)間的動(dòng)態(tài)性，本文提出了動(dòng)態(tài)策略即動(dòng)態(tài)調(diào)整ASC 所服務(wù)的外集卡作業(yè)工序，避免了因外集卡未在預(yù)計(jì)到達(dá)時(shí)間內(nèi)進(jìn)場(chǎng)作業(yè)導(dǎo)致車輛與設(shè)備的較長等待，盡可能保證ASC 不間斷作業(yè)，提高了ASC 作業(yè)效率。

3.2 DRNSGA Ⅱ與動(dòng)態(tài)策略的對(duì)比

為了驗(yàn)證DRNSGA Ⅱ在求解本問題時(shí)的有效性，在任務(wù)量為20、50、80 的不同規(guī)模問題下，生成10 個(gè)算例，進(jìn)行多次實(shí)驗(yàn)。實(shí)驗(yàn)1 是采取ASC 動(dòng)態(tài)調(diào)整作業(yè)任務(wù)策略下運(yùn)用DRNSGA Ⅱ進(jìn)行求解；實(shí)驗(yàn)2 采取動(dòng)態(tài)策略和運(yùn)用GA 求解；實(shí)驗(yàn)3 采取隨機(jī)策略運(yùn)用DRNSGA Ⅱ進(jìn)行求解；實(shí)驗(yàn)4 采用隨機(jī)策略和運(yùn)用GA 求解。各算例實(shí)驗(yàn)結(jié)果如表2 所示。F1～F4為4 組實(shí)驗(yàn)的目標(biāo)函數(shù)值（f1，f2），T1～T4為4 組實(shí)驗(yàn)的計(jì)算時(shí)間，P1～P3為實(shí)驗(yàn)1 與其他3 組實(shí)驗(yàn)之間的差值，

表2 四組實(shí)驗(yàn)結(jié)果Tab.2 Results of four experiments

差值P1是動(dòng)態(tài)策略下不同算法的比較，差值P2是運(yùn)用DRNSGA Ⅱ求解時(shí)動(dòng)態(tài)策略與隨機(jī)策略的對(duì)比，P1與P2的平均值均隨著算例規(guī)模的增加而變大，可見本文提出的DRNSGA Ⅱ在求解大規(guī)模問題上的優(yōu)越性；且P2的平均值大于P1的平均值，表明動(dòng)態(tài)策略的選擇對(duì)優(yōu)化結(jié)果的影響更加突出。實(shí)驗(yàn)結(jié)果表明，DRNSGA Ⅱ求解的動(dòng)態(tài)策略下目標(biāo)函數(shù)值優(yōu)于隨機(jī)策略28.2%，并且動(dòng)態(tài)策略下DRNSGA Ⅱ的求解結(jié)果優(yōu)于遺傳算法23.3%。差值P3是不同算法和不同策略的比較，P3的平均值大于P1的平均值和P2的平均值，可見采取隨機(jī)策略時(shí)運(yùn)用GA 求解該問題產(chǎn)生的誤差更大。

實(shí)驗(yàn)1 在任務(wù)規(guī)模為20、50、80 條件下的平均計(jì)算時(shí)間分別106.54 s、165.28 s 和299.67 s，時(shí)間效率均優(yōu)于其他3組實(shí)驗(yàn)，且所求目標(biāo)函數(shù)值優(yōu)于其他解；實(shí)驗(yàn)2 采取與實(shí)驗(yàn)1相同的算例，但運(yùn)用GA 求解，其計(jì)算效率與目標(biāo)函數(shù)值均次于DRNSGA Ⅱ求解的實(shí)驗(yàn)1。區(qū)別在于實(shí)驗(yàn)1 和2 采取動(dòng)態(tài)策略，實(shí)驗(yàn)3 和4 選擇隨機(jī)策略，同等條件下的算例結(jié)果與前兩組結(jié)果有較大差距，ASC 作業(yè)時(shí)間與設(shè)備等待時(shí)間得到了優(yōu)化，表明本文所提動(dòng)態(tài)策略的優(yōu)越性。

在算法求解性能上，DRNSGA Ⅱ求解的目標(biāo)函數(shù)值均優(yōu)于傳統(tǒng)GA 的求解結(jié)果，且隨著算例規(guī)模的增加，DRNSGA Ⅱ的優(yōu)勢(shì)較為明顯。在算法運(yùn)行時(shí)間上，兩種算法中各算例求解時(shí)間的差距較小，這可能是由于DRNSGA Ⅱ中加入了生成初始解的啟發(fā)式規(guī)則，且相較于傳統(tǒng)GA，為保證解的多樣性，DRNSGA Ⅱ中包含對(duì)所有個(gè)體的非支配排序，增加了算法復(fù)雜度，從而需要的運(yùn)行時(shí)間較長，但是整體上，DRNSGA Ⅱ中每組算例計(jì)算時(shí)間效率均優(yōu)于GA。由此表明，針對(duì)外集卡動(dòng)態(tài)到達(dá)場(chǎng)景下ASC 的作業(yè)優(yōu)化問題，本文提出DRNSGA Ⅱ的求解效果優(yōu)于傳統(tǒng)GA。

3.3 DRNSGA Ⅱ與多目標(biāo)粒子群優(yōu)化的對(duì)比

在任務(wù)量為100、150 和200時(shí)，進(jìn)行多次實(shí)驗(yàn)，表3 中給出了算例結(jié)果中最優(yōu)、最差與平均數(shù)據(jù)，用于比較DRNSGA Ⅱ與多目標(biāo)粒子群優(yōu)化（Multi-ObjectiveParticle Swarm Optimization，MOPSO）算法在解決本文問題時(shí)的性能。

表3 DRNSGA Ⅱ與MOPSO算法的對(duì)比結(jié)果Tab.3 Comparison results of DRNSGA Ⅱ and MOPSO algorithm

不同任務(wù)規(guī)模時(shí)，本文所提DRNSGA Ⅱ求解的目標(biāo)函數(shù)值與計(jì)算時(shí)間效率均優(yōu)于MOPSO 算法的結(jié)果，任務(wù)量增加后，兩種算法在求解目標(biāo)函數(shù)值差值的平均值也逐漸由2.8% 增加到6.7%，算法的計(jì)算時(shí)間也在增長，而DRNSGA Ⅱ的計(jì)算時(shí)間少于MOPSO 算法，這是由于提出的動(dòng)態(tài)調(diào)整策略有利于尋找最優(yōu)目標(biāo)函數(shù)值的過程。

圖9 以散點(diǎn)圖模式描述了不同任務(wù)量時(shí)兩種算法的求解結(jié)果，任務(wù)量為100 和150時(shí)，兩種算法求出的目標(biāo)函數(shù)值的散點(diǎn)很接近，差距較??；任務(wù)量為200時(shí)，目標(biāo)函數(shù)值的散點(diǎn)距離增加，從整體增長趨勢(shì)來看，任務(wù)量增加，算法性能差異也有所凸顯。通過3 組不同規(guī)模的算例實(shí)驗(yàn)，驗(yàn)證了本文所提算法在求解本問題時(shí)的優(yōu)勢(shì)。

4 結(jié)語

本文研究了混堆模式下自動(dòng)化碼頭外集卡動(dòng)態(tài)到達(dá)場(chǎng)景下ASC 作業(yè)優(yōu)化問題，構(gòu)建了ASC 作業(yè)時(shí)間最短和ASC 與外集卡等待時(shí)間最短的多目標(biāo)模型，結(jié)合外集卡到達(dá)時(shí)間動(dòng)態(tài)性的特征，設(shè)計(jì)了DRNSGA Ⅱ進(jìn)行求解。由于外集卡到達(dá)碼頭的時(shí)間具有不確定性，為了避免此種場(chǎng)景給碼頭作業(yè)效率帶來的影響，設(shè)計(jì)堆場(chǎng)ASC 動(dòng)態(tài)作業(yè)的規(guī)則，并將這種動(dòng)態(tài)策略嵌入到NSGA Ⅱ中。通過算例驗(yàn)證，根據(jù)動(dòng)態(tài)策略制定的ASC 作業(yè)方案優(yōu)于隨機(jī)策略，ASC 總作業(yè)時(shí)間及設(shè)備的等待時(shí)間都有縮減，同時(shí)比較了DRNSGA Ⅱ、傳統(tǒng)遺傳算法與MOPSO 算法在求解本問題時(shí)的性能，得出本文方法在求解結(jié)果和計(jì)算時(shí)間效率上的優(yōu)越性。

傳統(tǒng)的場(chǎng)橋作業(yè)問題，大多考慮進(jìn)出口集裝箱分開堆存時(shí)場(chǎng)橋的優(yōu)化。而本文提出進(jìn)出集裝箱混合堆存時(shí)自動(dòng)化碼頭的ASC 作業(yè)優(yōu)化問題，并結(jié)合外集卡進(jìn)場(chǎng)時(shí)間的不確定性，根據(jù)進(jìn)出口集裝箱不同的作業(yè)需求，研究ASC 動(dòng)態(tài)優(yōu)化。未來的研究會(huì)進(jìn)一步考慮混堆箱區(qū)內(nèi)的翻箱作業(yè)，將翻箱量列入ASC 作業(yè)優(yōu)化中，研究混堆模式下翻箱量與作業(yè)時(shí)間等多目標(biāo)的ASC 優(yōu)化問題。