鐘祾充，李文鋒，賀利軍，張 煜，周 勇

(武漢理工大學(xué) 交通與物流工程學(xué)院，湖北 武漢 430063)

0 引言

多式聯(lián)運(yùn)是全球貨運(yùn)重要的運(yùn)輸方式。當(dāng)前，全球集裝箱運(yùn)輸量驟增，亟需多式聯(lián)運(yùn)作業(yè)效率不斷提高。集裝箱碼頭是多式聯(lián)運(yùn)的重要樞紐，提高碼頭的作業(yè)效率是提高多式聯(lián)運(yùn)整體效率的關(guān)鍵所在。為集裝箱任務(wù)合理分配設(shè)備和資源，從而獲得高效的調(diào)度方案，具有重要的工程價(jià)值。

岸橋、集卡、場(chǎng)橋、泊位、堆場(chǎng)是集裝箱碼頭作業(yè)的重要作業(yè)設(shè)備和資源。岸橋負(fù)責(zé)海側(cè)集裝箱的裝卸，堆場(chǎng)為陸側(cè)集裝箱提供存儲(chǔ)空間，場(chǎng)橋負(fù)責(zé)堆場(chǎng)作業(yè)，集卡負(fù)責(zé)集裝箱運(yùn)輸。每個(gè)階段的作業(yè)效率均對(duì)碼頭接卸轉(zhuǎn)運(yùn)總時(shí)間產(chǎn)生重要影響。

結(jié)合港口裝卸作業(yè)特點(diǎn)，當(dāng)前港口調(diào)度的研究可分為單階段調(diào)度和多階段調(diào)度。單階段調(diào)度問(wèn)題主要包括：港口泊位分配[1]、岸橋作業(yè)調(diào)度[2]、運(yùn)輸車輛調(diào)度[3]、堆場(chǎng)資源的配置與調(diào)度[4]等。多階段調(diào)度問(wèn)題同時(shí)考慮多個(gè)密切關(guān)聯(lián)的作業(yè)環(huán)節(jié)，大部分是兩階段聯(lián)合調(diào)度。比如，針對(duì)岸橋與集卡建立混合整數(shù)規(guī)劃模型[5]，針對(duì)集卡與場(chǎng)橋建立二層規(guī)劃模型[6]，針對(duì)泊位-堆場(chǎng)資源進(jìn)行聯(lián)合分配[7-8]，以及岸橋指派與泊位分配的集成調(diào)度[9-10]等。也有針對(duì)岸橋、集卡、場(chǎng)橋三階段作業(yè)展開(kāi)的聯(lián)合調(diào)度優(yōu)化研究[11-15]。其中，文獻(xiàn)[15]將3個(gè)階段的作業(yè)抽象為混合流水車間調(diào)度問(wèn)題，但沒(méi)有考慮集卡在場(chǎng)橋的空閑時(shí)間，也沒(méi)有考慮岸橋的特殊作業(yè)性質(zhì)。

在對(duì)港口調(diào)研時(shí)發(fā)現(xiàn)，岸橋在對(duì)船舶裝卸作業(yè)時(shí)，時(shí)常出現(xiàn)空閑的情況。這使得港口的資源浪費(fèi)巨大，增加了港口作業(yè)成本。為了充分利用昂貴成本的岸橋，港口對(duì)岸橋提出零空閑的需求。同時(shí)，隨著港口不斷向自動(dòng)化、綠色化等方向發(fā)展，港口調(diào)度對(duì)低碳綠色、低成本等方面提出了更高要求。多目標(biāo)優(yōu)化成為港口調(diào)度的一大難題，針對(duì)港口多目標(biāo)調(diào)度[11-12,15]等的研究文獻(xiàn)正在快速增加。其中，文獻(xiàn)[11]構(gòu)建岸橋、集卡、場(chǎng)橋3種設(shè)備的調(diào)度優(yōu)化模型，同時(shí)優(yōu)化所有船舶的總出發(fā)延誤時(shí)間和所有任務(wù)的總作業(yè)能耗。

求解港口調(diào)度問(wèn)題的方法主要分為4類：精確算法、啟發(fā)式算法、基于規(guī)則的啟發(fā)式算法、仿真方法。KARAM等[12]設(shè)計(jì)了基于拉格朗日松弛的精確算法求解三階段的聯(lián)合調(diào)度問(wèn)題。LIANG等[14]設(shè)計(jì)了一種基于規(guī)則的啟發(fā)式算法求解泊位—岸橋聯(lián)合調(diào)度問(wèn)題。文獻(xiàn)[15]針對(duì)低碳型集裝箱碼頭連續(xù)泊位-岸橋分配問(wèn)題，采用多目標(biāo)高效非支配排序的遺傳算法對(duì)其進(jìn)行求解。文獻(xiàn)[16]設(shè)計(jì)三階段啟發(fā)式算法求解三階段聯(lián)合調(diào)度問(wèn)題。LIU[17]研究了一種迭代啟發(fā)式算法求解混合整數(shù)規(guī)劃模型，以最小化集裝箱裝卸的總成本，包括提速成本、延誤成本、船舶罰款成本和操作成本。HE等[11]采用集成仿真優(yōu)化的方法進(jìn)行了研究?？梢钥闯?，相較于精確算法和仿真算法，啟發(fā)式算法被更多地用于求解港口高度優(yōu)化問(wèn)題。文獻(xiàn)中針對(duì)不同的港口問(wèn)題，進(jìn)行了針對(duì)性的算法設(shè)計(jì)。問(wèn)題的變化和復(fù)雜性的增加將會(huì)影響算法編碼解碼的方式，也會(huì)影響算法的計(jì)算效率。

布谷鳥(niǎo)算法(Cuckoo Cearch, CS)是一種元啟發(fā)式搜索，由YANG等[18]于2009年開(kāi)發(fā)。CS具有較強(qiáng)的魯棒性和通用性，為復(fù)雜的調(diào)度優(yōu)化提供了新方法。該算法根據(jù)布谷鳥(niǎo)產(chǎn)卵行為提出3個(gè)假設(shè)并建立數(shù)學(xué)模型，引入昆蟲(chóng)的飛行軌跡萊維飛行機(jī)制，能夠快速有效求解連續(xù)優(yōu)化問(wèn)題。然而，由于CS的連續(xù)搜索特性，CS在離散優(yōu)化問(wèn)題中應(yīng)用有限。直到2014年，OUARAB等[19]首次提出使用CS解決旅行商問(wèn)題。此后，越來(lái)越多的研究涉及離散CS求解旅行商、0-1背包等組合優(yōu)化問(wèn)題，但關(guān)于設(shè)計(jì)離散CS求解更復(fù)雜的多目標(biāo)港口調(diào)度優(yōu)化問(wèn)題的研究仍較少。

綜上所述，考慮港口的三階段聯(lián)合調(diào)度和零空閑岸橋作業(yè)約束，有助于從整體優(yōu)化港口作業(yè)并降低成本。針對(duì)港口作業(yè)特征，借鑒車間調(diào)度領(lǐng)域的混合零空閑調(diào)度理論[20]，以總完工時(shí)間和總作業(yè)成本為優(yōu)化目標(biāo)，本文提出多目標(biāo)集裝箱碼頭三階段混合零空閑柔性流水作業(yè)調(diào)度問(wèn)題(three-stage Mixed No-idle Flexible Flow Scheduling Problem in Container Terminal, MNFFSP_CT)，并構(gòu)建其數(shù)學(xué)模型。MNFFSP_CT是一個(gè)典型的NP難離散優(yōu)化問(wèn)題?？紤]問(wèn)題的多目標(biāo)特性及離散特性，設(shè)計(jì)一種帶間歇啟動(dòng)的多鄰域局部搜索的改進(jìn)離散布谷鳥(niǎo)(Improved Discrete Cuckoo Search, IDCS)算法，使得IDCS算法能夠直接優(yōu)化離散問(wèn)題。最后，通過(guò)實(shí)驗(yàn)，驗(yàn)證模型的有效性和算法高效性。

1 問(wèn)題描述

集裝箱碼頭的作業(yè)包括裝船和卸船兩個(gè)過(guò)程，裝船與卸船的作業(yè)過(guò)程相反。以集裝箱卸船為例，描述港口作業(yè)過(guò)程(如圖1)。假設(shè)有H個(gè)標(biāo)準(zhǔn)集裝箱，需要從船舶轉(zhuǎn)存到碼頭堆場(chǎng)。用O1工序表示岸橋作業(yè)階段，O2工序表示集卡運(yùn)輸階段，O3工序表示場(chǎng)橋作業(yè)階段。如圖2所示，每個(gè)集裝箱h∈{1,2,…,H}都將依次經(jīng)歷O1→O2→O3三個(gè)工序，且均只經(jīng)歷一次。同工序的機(jī)器屬于同構(gòu)機(jī)，符合柔性流水車間調(diào)度問(wèn)題的問(wèn)題特征。但港口的三階段作業(yè)仍有額外的實(shí)際作業(yè)約束，描述如下：

(1)考慮到實(shí)際港口的岸橋作業(yè)成本遠(yuǎn)高于集卡的作業(yè)成本，港口對(duì)岸橋提出零空閑作業(yè)時(shí)間的要求。

(2)接到轉(zhuǎn)運(yùn)任務(wù)的集卡到達(dá)岸橋位置，岸橋?qū)⒓b箱裝載到等候中的集卡。集卡將集裝箱運(yùn)輸?shù)椒霞b箱儲(chǔ)存需求的堆場(chǎng)。此時(shí)若沒(méi)有空閑可提供作業(yè)的場(chǎng)橋，集卡則需要負(fù)載集裝箱在堆場(chǎng)等待，直到有完成上一個(gè)任務(wù)的場(chǎng)橋出現(xiàn)。當(dāng)集卡釋放集裝箱，并完成當(dāng)前任務(wù)，若沒(méi)接到下一項(xiàng)轉(zhuǎn)運(yùn)任務(wù)，則回到集卡池等候，若接到下一項(xiàng)轉(zhuǎn)運(yùn)任務(wù)，空載回到泊位等待岸橋裝載集裝箱。

(3)根據(jù)每個(gè)場(chǎng)橋的當(dāng)前作業(yè)情況，為負(fù)載集卡分配場(chǎng)橋。

綜上所述，傳統(tǒng)的柔性流水車間調(diào)度問(wèn)題無(wú)法準(zhǔn)確地描述港口三階段作業(yè)問(wèn)題，其實(shí)際約束更加復(fù)雜。結(jié)合零空閑作業(yè)特征的岸橋，本文引入混合零等待柔性流水車間調(diào)度問(wèn)題的基礎(chǔ)模型，在此基礎(chǔ)上進(jìn)一步深刻描述問(wèn)題，提出基于港口三階段作業(yè)的混合零等待柔性流水車間調(diào)度問(wèn)題(MNFFSP_CT)。

可將問(wèn)題細(xì)分為以下幾個(gè)子問(wèn)題：①集裝箱作業(yè)順序調(diào)度問(wèn)題；②集卡任務(wù)分配和開(kāi)機(jī)數(shù)量的確定；③岸橋任務(wù)分配和開(kāi)機(jī)數(shù)量的確定；④場(chǎng)橋任務(wù)分配和開(kāi)機(jī)數(shù)量的確定。

模型假設(shè)如下：

(1)每臺(tái)岸橋的大車移動(dòng)能力一致，小車作業(yè)能力一致；

(2)每輛集卡的作業(yè)能力一致，所有集卡在所有岸橋和場(chǎng)橋間共享；

(3)每臺(tái)場(chǎng)橋的大車移動(dòng)能力一致，小車作業(yè)能力一致；

(4)不考慮集卡碰撞問(wèn)題；

(5)集卡在集裝箱碼頭單向行駛，從泊位b到堆場(chǎng)s的路徑與從堆場(chǎng)s到泊位b的路徑形成閉環(huán)路；

(6)泊位、堆場(chǎng)沒(méi)有集裝箱堆存緩沖區(qū)；

(7)船舶的集裝箱轉(zhuǎn)運(yùn)任務(wù)具有優(yōu)先級(jí)別，資源優(yōu)先滿足該任務(wù)需求；

(8)不考慮堆場(chǎng)翻箱倒箱導(dǎo)致的場(chǎng)橋工作時(shí)間；

(9)在作業(yè)期間，岸橋、集卡、場(chǎng)橋都是勻速作業(yè)，作業(yè)速度、功率給定；

(10)所有岸橋、集卡、場(chǎng)橋均是從零時(shí)刻開(kāi)始。

2 數(shù)學(xué)模型

2.1 符號(hào)定義

j為集卡；h為需要卸載的集裝箱；b為泊位；qb為岸橋；s為堆場(chǎng)；rs為場(chǎng)橋。

2.2 參數(shù)定義

2.3 相關(guān)系數(shù)

θqb為岸橋qb在作業(yè)狀態(tài)的成本系數(shù)；βqb為岸橋qb的開(kāi)機(jī)成本；θj1為集卡j在負(fù)載作業(yè)狀態(tài)的成本系數(shù)；θj0為集卡j在空載作業(yè)狀態(tài)的成本系數(shù)；θj為集卡j在等待狀態(tài)的成本系數(shù)；βj為集卡j的開(kāi)機(jī)成本；θrs0為場(chǎng)橋rs在等待狀態(tài)的成本系數(shù)；θrs1為場(chǎng)橋rs在作業(yè)狀態(tài)的成本系數(shù)；βrs為場(chǎng)橋rs的開(kāi)機(jī)成本。

2.4 變量

ITrs為場(chǎng)橋rs的總空閑時(shí)間；

ARh,j為集卡j負(fù)載集裝箱h到達(dá)堆場(chǎng)的時(shí)刻；

ATh,j為集卡j負(fù)載集裝箱h在堆場(chǎng)的等待時(shí)間；

RTh,j為集卡j在堆場(chǎng)釋放集裝箱h的時(shí)刻；

C1,max為當(dāng)前集裝箱岸橋階段完工的最大完工時(shí)刻；

C2,max為當(dāng)前集裝箱集卡運(yùn)輸階段完工的最大完工時(shí)刻；

C3,max為當(dāng)前集裝箱場(chǎng)橋階段完工的最大完工時(shí)刻；

Cmax為Ω最大完工時(shí)刻；

TC為Ω全部完工的總成本。

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

min(Cmax,TC)。

(1)

(2)

TC=TCQ+TCJ+TCR；

(3)

(4)

(5)

(6)

(7)

式(1)為目標(biāo)函數(shù)集合，總完工時(shí)間Cmax和總作業(yè)成本TC；式(2)表示Ω最后一項(xiàng)任務(wù)的完工時(shí)間；式(3)表示Ω三個(gè)階段的總作業(yè)成本；式(4)表示Ω在工序O1的作業(yè)成本；式(5)表示Ω在工序O2的作業(yè)成本；式(6)表示Ω在工序O3的作業(yè)成本；式(7)表示場(chǎng)橋rs完成Ωrs的工序O3所產(chǎn)生的空閑總時(shí)間。

2.6 約束

(8)

(9)

式中:Jw≤J；j∈{1,2,…,J}。

(10)

式(8)表示每個(gè)開(kāi)機(jī)作業(yè)岸橋被分配的集裝箱之和為任務(wù)集裝箱總量；式(9)表示每個(gè)開(kāi)機(jī)集卡被分配的集裝箱數(shù)量之和為任務(wù)集裝箱總量；式(10)表示每個(gè)開(kāi)機(jī)作業(yè)場(chǎng)橋被分配的集裝箱數(shù)量之和為任務(wù)集裝箱總量。

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

j∈{1,2,…,jw}。

(20)

式(15)要求集裝箱必須完成岸橋作業(yè)之后才能進(jìn)行集卡運(yùn)輸；式(16)表示工序O2包括以下三個(gè)部分：集卡負(fù)載集裝箱從泊位到堆場(chǎng)，在堆場(chǎng)等待場(chǎng)橋作業(yè)，作業(yè)從堆場(chǎng)回到泊位；式(17)要求任意集裝箱在集卡運(yùn)輸階段僅被一輛集卡作業(yè)一次，不能被重復(fù)作業(yè)；式(18)要求集卡j在完成前一個(gè)集裝箱轉(zhuǎn)運(yùn)任務(wù)之后，才可以重回泊位接受下一個(gè)集裝箱的轉(zhuǎn)運(yùn)任務(wù)；式(19)要求下一個(gè)集裝箱分配給最先完成前一個(gè)集裝箱作業(yè)的集卡；式(20)要求場(chǎng)橋的作業(yè)開(kāi)始時(shí)間必須在完成上一個(gè)任務(wù)之后且有集卡負(fù)載集裝箱任務(wù)等待作業(yè)。

(21)

(22)

(23)

式(21)要求任意集裝箱只被其中一臺(tái)場(chǎng)橋作業(yè)一次；式(22)要求場(chǎng)橋rs在完成前一個(gè)集裝箱作業(yè)任務(wù)之后，才可以進(jìn)行下一個(gè)集裝箱的作業(yè)任務(wù)；式(23)要求下一個(gè)集裝箱分配給最先完成前一個(gè)集裝箱作業(yè)的場(chǎng)橋。

3 問(wèn)題求解方法

在MNFFSP_CT中，包括集裝箱作業(yè)調(diào)度、岸橋分配、集卡分配、場(chǎng)橋分配4個(gè)子問(wèn)題。需要考慮集裝箱的排序，集裝箱對(duì)應(yīng)的集卡、岸橋、場(chǎng)橋，以及各類設(shè)備的開(kāi)機(jī)數(shù)量。本文提出一種改進(jìn)的布谷鳥(niǎo)算法求解MNFFSP_CT，算法包括以下4個(gè)部分：①針對(duì)集裝箱的單鏈編碼；②針對(duì)岸橋、集卡、場(chǎng)橋的三鏈解碼，用于滿足設(shè)備分配需求；③離散化的萊維飛行更新機(jī)制和個(gè)體拋棄機(jī)制，使算法直接應(yīng)用于離散組合問(wèn)題；④基于快速非支配排序策略(Fast Non-dominated sorting, FND)[22]的間歇啟動(dòng)多鄰域局部搜索策略，可以平衡算法的全局和局部搜索能力，幫助算法跳出局部最優(yōu)，同時(shí)減少計(jì)算資源的浪費(fèi)。IDCS求解MNFFSP_CT流程圖如圖3所示。

3.1 單鏈編碼

3.2 三鏈解碼

C1,max計(jì)算如下：

(24)

(25)

(26)

C3,max的計(jì)算如下：

(27)

(28)

ARh,j、ATh,j的計(jì)算如下：

(29)

(30)

3.3 解的表達(dá)

3.4 甘特圖示例

表1 集裝箱在3個(gè)作業(yè)階段的作業(yè)時(shí)間

最終，根據(jù)編碼解碼規(guī)則，獲得H=3,b=1,s=1,W=[1,3,1]的其中一種可行解：

其甘特圖如圖4所示。

3.5 改進(jìn)離散布谷鳥(niǎo)算法(IDCS)

3.5.1 離散全局搜索

離散化的萊維飛行更新機(jī)制：

(31)

(32)

(33)

基于拋棄概率的離散更新機(jī)制：

(34)

3.5.2 基于FND間歇啟動(dòng)的多鄰域局部搜索

多鄰域局部搜索是提高搜索精度的有效策略。為避免同一區(qū)域的較優(yōu)個(gè)體消耗過(guò)多的計(jì)算資源，設(shè)計(jì)每完成50次迭代啟動(dòng)1次多鄰域局部搜索。多鄰域局部搜索如算法1所示，其搜索對(duì)象為當(dāng)前種群FND分層后前N×β個(gè)個(gè)體，其中N=Popsize,β=0.3。該搜索策略基于3種鄰域局部搜索設(shè)計(jì)：Swap局部搜索操作、Insert局部搜索操作、2-opt局部搜索操作。隨機(jī)選擇序列兩個(gè)不同的位置p1

算法1多鄰域局部搜索。

輸入：非支配解X；

輸出：更新后的解X。

1: %%%%擾動(dòng)階段

2: 設(shè)置 k=0

3: while k<3 do

4: 隨機(jī)選取位置u和v, u≠v

5: π(X)=Insert(π(X),v,u); k=k+1

6: end while

7: %%%%探索階段

8: 設(shè)置 k=0

9: while k<3 do

10: 隨機(jī)選取位置u和v, u≠v, t=0

11: while t<20 do

12: if t=0 then

13: π(X)=Insert(π(X),v,u)

14: else if t=1 then

15: π(X)=swap(π(X),v,u)

16: else if t=2 then

17: π(X)=2-opt(π(X),v,u)

18: end if

19: ifX′Xthen

20:π(X′)π(X);k=k+1

21: else

22: t=t+1

23: end if

24: end while

25: end while

4 仿真實(shí)驗(yàn)分析

由于碼頭使用的設(shè)備數(shù)量取決于當(dāng)前轉(zhuǎn)運(yùn)任務(wù)的集裝箱數(shù)量，不同數(shù)量的任務(wù)需要通過(guò)實(shí)驗(yàn)獲得設(shè)備最佳資源配置組合。實(shí)驗(yàn)的第一部分，為相同任務(wù)提供不同數(shù)量的設(shè)備，對(duì)比其優(yōu)化結(jié)果，獲得每種數(shù)量的最佳資源配置組合；第二部分實(shí)驗(yàn)基于最佳資源配置組合，進(jìn)行多個(gè)算法對(duì)比，證明模型準(zhǔn)確性和IDCS算法可行性高效性；第三部分實(shí)驗(yàn)根據(jù)某港口各階段實(shí)際作業(yè)數(shù)據(jù)，通過(guò)IDCS算法求解80個(gè)集裝箱數(shù)量的MNFFSP_CT，碼頭任務(wù)轉(zhuǎn)運(yùn)效率遠(yuǎn)高于80個(gè)集裝箱/小時(shí)。所有算法和測(cè)試程序均用Delphi10.2編程實(shí)現(xiàn)。操作系統(tǒng)為Win10，處理器為Intel(R)Core(TM)i5-4210U 1.70 GHz，內(nèi)存為4 GB。

第二部分實(shí)驗(yàn)基于以上7組不同集裝箱數(shù)量的最佳資源組合，將IDCS算法與CS、改進(jìn)的帶精英策略的快速非支配排序遺傳算法(Improved fast elitist Nondominated Sorting Genetic Algorithm, INSGA-II)[23]、蛙跳算法(Shuffled Frog-Leaping Algorithm, SFLA)[24]、人工蜂群算法(Artificial Bee Colony algorithm, ABC)[25]比較。

其中CS、INSGA-II、SFLA、ABC均采用與IDCS同樣的編碼解碼方式，且CS使用最大順序值(Largest-Order-Value, LOV)規(guī)則[26]將連續(xù)個(gè)體映射到離散個(gè)體。其中IDCS和CS的參數(shù)：種群大小Popsize、最大步長(zhǎng)系數(shù)αmax、個(gè)體拋棄概率Pa。使用正交試驗(yàn)設(shè)計(jì)(Design of Orthogonal Experiment, DOE)[27]作為參數(shù)整定方法，選取中等規(guī)模問(wèn)題(4,20,6)_80作為參數(shù)設(shè)置實(shí)驗(yàn)對(duì)象，將上述3個(gè)參數(shù)分為4個(gè)級(jí)別，參數(shù)選擇量表為L(zhǎng)16(43)的正交試驗(yàn)，每個(gè)參數(shù)組合下的測(cè)試問(wèn)題分別進(jìn)行20個(gè)獨(dú)立運(yùn)行試驗(yàn)，最終得到Popsize=20、αmax=0.8、Pa=0.1能夠使算法的搜索能力穩(wěn)定發(fā)揮。

以上每種算法對(duì)7組問(wèn)題的求解都是獨(dú)立運(yùn)行30次，每種算法的每次獨(dú)立運(yùn)行時(shí)間均為50×Hms。

采用的分析指標(biāo)是文獻(xiàn)[28]中提出的多目標(biāo)分析指標(biāo)為R_NDS(Sr)，Sr指算法r所得Pareto解集，R_NDS(Sr)是算法r中未被支配的個(gè)體數(shù)占算法r中總的Pareto解集個(gè)體數(shù)的比率。

R_NDS(Sr)=1意味著Sr中所有的Pareto個(gè)體都不被支配，若R_NDS(Sr)=0.9意味著Sr中90%的Pareto個(gè)體都不被支配。本文中每個(gè)問(wèn)題規(guī)模的數(shù)據(jù)結(jié)果可以在表2～表5中找到：表2是IDCS算法和CS算法的對(duì)比數(shù)據(jù)，表3是IDCS算法和INSGA-II算法的對(duì)比數(shù)據(jù)，表4是IDCS算法和ABC算法的對(duì)比數(shù)據(jù)，表5是IDCS算法和SFLA算法的對(duì)比數(shù)據(jù)。

表2 IDCS算法和CS算法的R_NDS對(duì)比數(shù)據(jù)

表3 IDCS算法和INSGA-II算法的R_NDS對(duì)比數(shù)據(jù)

表4 IDCS算法和ABC算法的R_NDS對(duì)比數(shù)據(jù)

表5 IDCS算法和SFLA算法的R_NDS對(duì)比數(shù)據(jù)

表2～表5加粗的數(shù)據(jù)說(shuō)明該算法在該問(wèn)題規(guī)模上所獲得的不被支配的解多于另一個(gè)算法。例如表2～表4，在所有規(guī)模中IDCS都優(yōu)于另一種算法。在表5中，只有(1,11,1)_10、(1,11,3)_40、(4,20,6)_80、(5,25,8)_120等問(wèn)題規(guī)模中，IDCS略優(yōu)于SFLA，而且另外3個(gè)規(guī)模下的結(jié)果差距不大，說(shuō)明IDCS算法僅略優(yōu)于SFLA算法，特別是在求解更高規(guī)模時(shí)，IDCS算法優(yōu)勢(shì)不明顯，這為后面針對(duì)大規(guī)模的算例進(jìn)行算法改進(jìn)提供思路。總體而言，IDCS算法得到的解集更優(yōu)，證明了IDCS算法求解多目標(biāo)MNFFSP_CT的有效性。

第三部分實(shí)驗(yàn)基于某港口實(shí)際案例，為80個(gè)集裝箱數(shù)量的接卸轉(zhuǎn)運(yùn)任務(wù)分配資源設(shè)備，并獲得滿足需求的優(yōu)解。

某集裝箱碼頭各階段實(shí)際轉(zhuǎn)運(yùn)時(shí)間范圍：岸橋作業(yè)時(shí)間范圍為[100, 140]，場(chǎng)橋作業(yè)時(shí)間范圍為[135, 175]，集卡從泊位到堆場(chǎng)的運(yùn)輸時(shí)間范圍為[300, 333]，堆場(chǎng)到泊位的時(shí)間范圍為[261, 300]。設(shè)置H=80的接卸轉(zhuǎn)運(yùn)任務(wù)，在時(shí)間范圍內(nèi)，采用隨機(jī)生成的方式，獲得每個(gè)設(shè)備對(duì)不同集裝箱的作業(yè)時(shí)間。

顯然，該集裝箱港口的作業(yè)調(diào)度問(wèn)題和資源分配問(wèn)題符合多目標(biāo)MNFFSP_CT問(wèn)題模型。將IDCS算法用于求解80個(gè)集裝箱的多目標(biāo)MNFFSP_CT，獲得滿足min(Cmax,TC)且Cmax小于3 600 s的優(yōu)化轉(zhuǎn)運(yùn)方案。其中Cmax為

集裝箱作業(yè)順序及每個(gè)集裝箱所分配的岸橋、集卡、場(chǎng)橋如表6所示，數(shù)據(jù)形式為“集裝箱編號(hào)(岸橋編號(hào)，集卡編號(hào)，場(chǎng)橋編號(hào))”。

表6 80個(gè)集裝箱的集裝箱作業(yè)順序及每個(gè)集裝箱所分配的岸橋、集卡、場(chǎng)橋

這一結(jié)果表明多目標(biāo)MNFFSP_CT問(wèn)題符合集裝箱碼頭實(shí)際作業(yè)需求，且IDCS算法可快速有效地求解實(shí)際問(wèn)題多目標(biāo)MNFFSP_CT問(wèn)題，獲得較優(yōu)作業(yè)方案。

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

多式聯(lián)運(yùn)對(duì)集裝箱碼頭的接卸轉(zhuǎn)運(yùn)效率提出了更高的要求。為滿足岸橋零空閑作業(yè)需求，綜合考慮碼頭各階段作業(yè)，以最小化最大完工時(shí)間和作業(yè)成本為優(yōu)化目標(biāo)，提高接卸轉(zhuǎn)運(yùn)效率。研究?jī)?nèi)容及結(jié)論如下：

(1)針對(duì)岸橋零空閑作業(yè)需求，聯(lián)合三階段多并行作業(yè)特性，提出三階段混合零空閑柔性流水作業(yè)調(diào)度模型(MNFFSP_CT)，并通過(guò)設(shè)計(jì)大中小7個(gè)規(guī)模集裝箱轉(zhuǎn)運(yùn)問(wèn)題，獲得每個(gè)規(guī)模下最佳資源配置組合。通過(guò)實(shí)驗(yàn)驗(yàn)證了模型的準(zhǔn)確性。

(2)基于MNFFSP_CT，設(shè)計(jì)包含4部分的改進(jìn)離散布谷鳥(niǎo)(IDCS)算法，實(shí)現(xiàn)了對(duì)多目標(biāo)MNFFSP_CT問(wèn)題的有效求解。與CS、INSGA-II、SFLA、ABC多目標(biāo)算法對(duì)比，驗(yàn)證了算法的高效性。但在更大規(guī)模上的求解，還需要進(jìn)一步優(yōu)化。

(3)通過(guò) IDCS求解80個(gè)集裝箱的MNFFSP_CT，可獲得高于80個(gè)集裝箱/小時(shí)的轉(zhuǎn)運(yùn)速率，總完工時(shí)間小于 3 600 s。對(duì)實(shí)際集裝箱碼頭有實(shí)際的工程意義。

本文從整體角度對(duì)港口進(jìn)行聯(lián)合調(diào)度優(yōu)化，松弛每個(gè)作業(yè)階段的作業(yè)約束，例如岸橋作業(yè)部分岸橋的多機(jī)協(xié)同防沖突調(diào)度問(wèn)題、堆場(chǎng)部分可能存在的翻箱倒箱問(wèn)題等。在未來(lái)的研究中，同時(shí)考慮港口的三階段混合零空閑柔性流水作業(yè)調(diào)度問(wèn)題與各階段的約束，既可以滿足集裝箱的調(diào)度優(yōu)化，也可以滿足各個(gè)階段設(shè)備的問(wèn)題特征，使求解方案更加接近實(shí)際需求。