梁承姬，嚴(yán)亞平，李玲君

(上海海事大學(xué) 物流科學(xué)與工程研究院，上海 201306)

隨著集裝箱吞吐量增加、船舶大型化發(fā)展和高昂油價(jià)等問(wèn)題的出現(xiàn)，大型船舶對(duì)于選擇停泊港口的裝卸效率提出了更高的要求，以達(dá)到縮短船舶在港時(shí)間，降低運(yùn)輸成本的目的。在各種因素的催化下，第1臺(tái)雙40英尺岸橋誕生于2005年，由上海振華港機(jī)制造。此后，這種能同時(shí)抓起 2個(gè)雙 40英尺集裝箱的新式岸橋得到了越來(lái)越廣泛的關(guān)注和應(yīng)用。由于雙40英尺岸橋可以同時(shí)裝卸2個(gè)集裝箱，所以其理論上的裝卸效率比常規(guī)岸橋高50%以上，然而其實(shí)際使用情況卻不是很理想，據(jù)2007年洋山港10臺(tái)雙40英尺岸橋與10臺(tái)常規(guī)岸橋的統(tǒng)計(jì)數(shù)據(jù)相比：雙 40英尺岸橋平均綜合效率比常規(guī)岸橋只提升了5.35%；雙40英尺岸橋投資額較常規(guī)岸橋高15%左右；鋼絲繩維護(hù)成本高70%左右；單箱能耗高25%左右；由于增加了一套起升機(jī)構(gòu)，雙40英尺岸橋故障臺(tái)次約為常規(guī)岸橋的2.3倍[1]。這些成本的增加都需要通過(guò)提高雙 40英尺岸橋的裝卸效率來(lái)解決，而制約雙 40英尺岸橋的效率的一個(gè)重要因素便是岸橋與集卡之間的協(xié)同調(diào)度問(wèn)題。國(guó)內(nèi)外關(guān)于集裝箱碼頭岸橋集卡調(diào)度問(wèn)題的研究主要集中在對(duì)常規(guī)岸橋集卡調(diào)度模型和算法的研究。CAO等[2]將岸橋與集卡整合到一起考慮，打破了以前研究中單獨(dú)考慮某一個(gè)問(wèn)題的模式，并建立了一個(gè)整數(shù)規(guī)劃模型。尚晶等[3]在研究集裝箱裝卸作業(yè)面的集卡調(diào)度問(wèn)題中，將減少集卡的空駛行程作為調(diào)度優(yōu)化目標(biāo)之一。計(jì)明軍等[4]在考慮集卡運(yùn)輸時(shí)間和岸橋作業(yè)時(shí)間的基礎(chǔ)上，提出了以運(yùn)輸時(shí)間最短為目標(biāo)的集卡調(diào)度優(yōu)化模型法。Lee等[5]建立了集卡運(yùn)輸時(shí)間和等待延遲時(shí)間權(quán)重和最小的數(shù)學(xué)模型，并利用啟發(fā)式算法進(jìn)行求解。秦天保等[6]針對(duì)岸橋集卡協(xié)同調(diào)度問(wèn)題，建立混合整數(shù)規(guī)劃(MIP)模型和約束規(guī)劃(CP)模型，設(shè)計(jì)OPL語(yǔ)言使用不同規(guī)模的實(shí)例對(duì)約束規(guī)劃模型和 MIP模型進(jìn)行測(cè)試。TANG等[7]在岸橋集卡聯(lián)合調(diào)度中，運(yùn)用改進(jìn) PSO算法進(jìn)行計(jì)算單項(xiàng)進(jìn)口集裝箱作業(yè)和雙向進(jìn)出口集裝箱作業(yè)問(wèn)題，并與 CPLEX 求解器的結(jié)果進(jìn)行對(duì)比。樂(lè)美龍等[8]建立以單船岸橋最小作業(yè)時(shí)間為目標(biāo)的混合整數(shù)規(guī)劃模型P1，通過(guò)簡(jiǎn)化模型P2求解岸橋調(diào)度模型P1的下限邊界值和排程數(shù)據(jù)，在此基礎(chǔ)上，運(yùn)用基于規(guī)則的啟發(fā)式算法求解模型 P1的岸橋調(diào)度時(shí)序表。錢繼鋒等[9]建立了“岸橋-集卡-堆場(chǎng)”雙向作業(yè)計(jì)劃協(xié)同優(yōu)化模型，并設(shè)計(jì)了混合智能算法對(duì)其求解。Kaveshgar 等[10]利用遺傳算法和貪婪算法來(lái)解決岸橋、集卡的集成調(diào)度問(wèn)題，最終求得集裝箱裝卸作業(yè)的最小完工時(shí)間。Homayouni 等[11]在對(duì)自動(dòng)化集裝箱港口的岸橋、集卡、場(chǎng)橋的集成調(diào)度的研究中，發(fā)現(xiàn)在精確度和調(diào)度方案中，基于模擬退火算法的 SP-AS/RS系統(tǒng)的設(shè)備調(diào)度不如遺傳算法的計(jì)算結(jié)果?？抵久舻萚12]基于 Petri網(wǎng)研究了利用改進(jìn)遺傳算法解決集卡調(diào)度問(wèn)題。這種調(diào)度方法經(jīng)過(guò)分析表明，可以在一定程度上提高裝卸作業(yè)的“重進(jìn)重出”。韓曉龍等[13]針對(duì)集卡到達(dá)的不確定性和動(dòng)態(tài)性提出了新的調(diào)度規(guī)則，建立了岸橋集卡的協(xié)同調(diào)度模型，采用遺傳算法進(jìn)行求解，證明了模型和算法在解決岸橋集卡調(diào)度問(wèn)題上有效。采用改進(jìn)的遺傳算法。李尤豐等[14]采用作業(yè)面裝卸方式，建立了以集卡空駛時(shí)間最小為目標(biāo)的集卡動(dòng)態(tài)調(diào)度模型，采用改進(jìn)的遺傳算法求解，并引入 N6 鄰域方法，設(shè)計(jì)了多種交叉操作和變異操作。關(guān)于雙 40英尺岸橋的集卡調(diào)度研究比較少，尚晶[15]建立以岸橋延遲時(shí)間和集卡空駛時(shí)間為目標(biāo)的集卡調(diào)度模型，設(shè)計(jì)了基于自適應(yīng)交叉和變異概率的改進(jìn)遺傳算法，證明改進(jìn)遺傳算法在求解雙 40英尺岸橋集卡調(diào)度問(wèn)題上有較優(yōu)方案。本文在其研究的基礎(chǔ)上，針對(duì)雙 40英尺岸橋作業(yè)的特點(diǎn)，采用雙循環(huán)的作業(yè)方式，將集卡到達(dá)岸橋的同步性作為裝卸效率的考核目標(biāo)之一，以岸橋的延遲時(shí)間及集卡的空駛時(shí)間、任務(wù)對(duì)的時(shí)間差為目標(biāo)建立考慮雙 40英尺岸橋的集卡調(diào)度模型，并設(shè)計(jì)遺傳算法及啟發(fā)式算法進(jìn)行求解并對(duì)求解結(jié)果進(jìn)行分析。

1 問(wèn)題描述

雙40英尺岸橋可以同時(shí)裝卸2個(gè)40英尺或者4個(gè)20英尺的集裝箱，這表示，岸橋可以同時(shí)對(duì)兩輛集卡進(jìn)行作業(yè)。這對(duì)岸橋和集卡的配合，即集卡的同步性和次序性提出了較高的要求。同步性是指：雙40英尺岸橋在卸船作業(yè)時(shí)需要2個(gè)空集卡同時(shí)到達(dá)岸橋來(lái)裝載進(jìn)口箱至箱區(qū)，而裝船時(shí)需要2個(gè)集卡同時(shí)將堆場(chǎng)的出口集裝箱運(yùn)送至岸橋。次序性是指：集卡的調(diào)度要同時(shí)考慮岸橋的作業(yè)順序，要根據(jù)岸橋的裝卸計(jì)劃來(lái)安排集卡。這些限制條件增加了港口內(nèi)部作業(yè)調(diào)度的復(fù)雜性。

對(duì)于雙40英尺岸橋一次操作的2個(gè)集卡，如果到達(dá)的時(shí)間不同步，一則會(huì)造成前一輛集卡的等待，二則會(huì)使岸橋不能按照計(jì)劃時(shí)間開始工作，且岸橋的后續(xù)所有任務(wù)都會(huì)延遲。

2 模型建立

2.1 模型假設(shè)

由于現(xiàn)實(shí)問(wèn)題的復(fù)雜性，為了便于問(wèn)題求解和模型建立，現(xiàn)設(shè)定如下假設(shè)：

1) 集裝箱的規(guī)格是相同的，集卡一次服務(wù)于一個(gè)集裝箱。而岸橋一次可以服務(wù)2個(gè)40尺箱或4個(gè)20尺箱，為簡(jiǎn)便計(jì)算，設(shè)定2個(gè)20尺或1個(gè)40尺箱為1個(gè)集裝箱。

2) 集卡在移動(dòng)過(guò)程中總是勻速行駛，行駛時(shí)間由距離所得；

3) 船舶的配載符合雙 40英尺岸橋的作業(yè)要求，且出口集裝箱數(shù)和進(jìn)口集裝箱數(shù)都為偶數(shù)，確保雙40英尺岸橋一次操作2個(gè)集裝箱。

2.2 模型參數(shù)及變量

本文的目的是為集裝箱碼頭參與裝卸工作的岸橋和集卡安排合適的數(shù)量。每一對(duì)待裝卸的集裝箱稱之為一個(gè)任務(wù)對(duì)，用i和j來(lái)表示。要裝船的集裝箱的起點(diǎn)位置是它在于堆場(chǎng)的位置，終點(diǎn)位置是對(duì)應(yīng)于負(fù)責(zé)裝船的岸橋的位置。而卸船的集裝箱的起點(diǎn)位置是負(fù)責(zé)卸船的岸橋處，而終點(diǎn)位置是存放于堆場(chǎng)的位置。在一個(gè)船舶裝卸的過(guò)程中，用 J表示要裝卸的集裝箱的集合，n為各個(gè)岸橋要裝卸的任務(wù)的總量，|J|=n。

在此為每一條集卡路徑安排一個(gè)虛擬開始節(jié)點(diǎn)O和一個(gè)虛擬結(jié)束結(jié)點(diǎn)F，對(duì)應(yīng)于虛擬工作，假設(shè)集卡池位于虛擬岸橋處，集卡從集卡池出發(fā)相當(dāng)于集卡位于虛擬岸橋處O開始工作，集卡完成任務(wù)回到集卡池相當(dāng)于集卡位于虛擬岸橋處 F結(jié)束工作，即虛擬開始岸橋O和虛擬結(jié)束岸橋F與集卡數(shù)目相同。參與調(diào)度的每一輛集卡都必須從虛擬工作開始，到虛擬工作結(jié)束。

O虛擬開始岸橋；F虛擬結(jié)束節(jié)岸橋，參與調(diào)度的每一輛集卡都必須從虛擬工作開始，到虛擬工作結(jié)束；T表示在工作中所用到的集卡的集合，|T|=t；Q表示參與裝卸作業(yè)的岸橋的集合，岸橋序號(hào)用k, l表示，|Q|=q；mk表示岸橋k需要完成的集裝箱任務(wù)對(duì)的裝卸總量，mO=mF=t；i和j表示雙40英尺岸橋每次操作的任務(wù)對(duì)，每一個(gè)任務(wù)對(duì)同時(shí)包含2個(gè)小任務(wù)i=(i1,i2)，j=(j1,j2)，岸橋每一次操作的任務(wù)序號(hào)用e, f(e, f=1, 2)表示，ie即表示雙40英尺岸橋操作i任務(wù)對(duì)的第e個(gè)集裝箱；α，β，μ分別表示為岸橋延遲時(shí)間、集卡空駛時(shí)間及任務(wù)對(duì)到達(dá)岸橋處的時(shí)間差的目標(biāo)權(quán)重系數(shù)，由于岸橋不允許延遲，所以：α>>β。

表1 的計(jì)算方法(if堆場(chǎng)表示任務(wù)jf所在的堆場(chǎng)位置)Table 1 Calculation method of (if yard indicate the location of jf in yard)

表1 的計(jì)算方法(if堆場(chǎng)表示任務(wù)jf所在的堆場(chǎng)位置)Table 1 Calculation method of (if yard indicate the location of jf in yard)

前接任務(wù)性質(zhì)kie后繼任務(wù)性質(zhì)ljf clif kie lif kiet裝載 裝載 岸橋k裝載ie的時(shí)間+集卡從岸橋k到j(luò)f堆場(chǎng)的時(shí)間+場(chǎng)橋操作jf的時(shí)間+集卡從jf堆場(chǎng)到岸橋l的時(shí)間集卡從岸橋k到j(luò)f堆場(chǎng)的時(shí)間裝載 卸載 岸橋k裝載ie的時(shí)間+集卡從岸橋k到岸橋l的時(shí)間 集卡從岸橋k到岸橋l的時(shí)間卸載 卸載 岸橋k操作任務(wù)ie的時(shí)間+集卡從岸橋k到ie堆場(chǎng)的時(shí)間+場(chǎng)橋操作任務(wù)ie的時(shí)間+集卡從ie堆場(chǎng)到岸橋l的時(shí)間集卡從ie堆場(chǎng)到岸橋l的時(shí)間卸載 裝載岸橋k操作任務(wù)ie的時(shí)間+集卡從岸橋k到ie堆場(chǎng)的時(shí)間+場(chǎng)橋操作任務(wù)ie的時(shí)間+ie堆場(chǎng)到j(luò)堆場(chǎng)的時(shí)間+場(chǎng)橋操作任務(wù)jf的時(shí)間+集卡從jf堆場(chǎng)到岸橋l的時(shí)間ie堆場(chǎng)到j(luò)f堆場(chǎng)的時(shí)間

決策變量為：

同一集卡在完成雙40英尺岸橋k處的集裝箱ie任務(wù)時(shí)，接著操作雙40英尺岸橋l處的集裝箱jf，其值為1，否則為0。

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

其中目標(biāo)函數(shù)(1)表示所求目標(biāo)為岸橋的延遲時(shí)間、集卡的空駛時(shí)間及操作同一任務(wù)對(duì)的2輛集卡到達(dá)岸橋的時(shí)間差的加權(quán)和最小。約束(2)和約束(3)確保對(duì)于任意一個(gè)任務(wù)只有一個(gè)繼后任務(wù)和一個(gè)繼前任務(wù)；約束(4)和約束(5)表示任意一個(gè)岸橋操作任務(wù)對(duì)的實(shí)際開始時(shí)間在計(jì)劃開始時(shí)間之后；約束(6)表示岸橋在操作同一任務(wù)對(duì)的兩岸集卡都到達(dá)碼頭前沿后開始工作；約束(7)表示同一輛集卡操作的前后相接的2個(gè)任務(wù)開始時(shí)間之間的關(guān)系，M為前一任務(wù)的開始時(shí)間；約束(8)表示岸橋操作任意一個(gè)任務(wù)對(duì)時(shí)的產(chǎn)生的延遲時(shí)間；約束(9)和約束(10)表示虛擬開始結(jié)點(diǎn)的數(shù)目與虛擬結(jié)束結(jié)點(diǎn)的總數(shù)目相同，并且與集卡的數(shù)量相同。

3 算法實(shí)現(xiàn)

3.1 遺傳算法實(shí)現(xiàn)

1) 染色體編碼和個(gè)體選擇

首先將各個(gè)集裝箱任務(wù)進(jìn)行優(yōu)先級(jí)排序，以優(yōu)先級(jí)序號(hào)來(lái)表示各個(gè)集裝箱任務(wù)，染色體中的序號(hào)表示的是任務(wù)優(yōu)先級(jí)。設(shè)開始工作時(shí)，集卡從集卡池 0出發(fā)，經(jīng)過(guò)不同的節(jié)點(diǎn)，完成所有分派的任務(wù)都返回集卡池。由于每一輛集卡表示一條路徑，所以每一條染色體包含多條子路徑，各條子路徑之間以0分割。例如，一條染色體可以表示為如圖1所示。

圖1 一條染色體示例Fig. 1 A set of chromosome samples

由于上述模型的目標(biāo)函數(shù)取的是最小值，所以需要將目標(biāo)函數(shù)映射為適值函數(shù)，令 F =- m in u，從而將求最小化的問(wèn)題轉(zhuǎn)化為求最大化的問(wèn)題。

3) 交叉操作

采用雙切點(diǎn)交叉原則產(chǎn)生子代。在驗(yàn)證子代的合法性時(shí)根據(jù)不同的情況分別采取修復(fù)策略或者拒絕策略，見(jiàn)圖 2。當(dāng)子代中出現(xiàn)的子路徑不等于集卡的數(shù)目或者出現(xiàn)空的子路徑時(shí)，則子代不合法，需要被拒絕；當(dāng)子代中出現(xiàn)子路徑有序號(hào)重復(fù)時(shí)，采用部分映射交叉(PMX)的修復(fù)原則進(jìn)行修復(fù)；當(dāng)子代中出現(xiàn)子路徑中的序號(hào)亂序時(shí)，則進(jìn)行自動(dòng)局部整(如圖3所示)。

上述染色體的各條子路徑如下。

集卡路徑1：集卡池0→節(jié)點(diǎn)1→節(jié)點(diǎn)3→工作完成

集卡路徑2：集卡池0→節(jié)點(diǎn)2→節(jié)點(diǎn)4→工作完成

集卡路徑3：集卡池0→節(jié)點(diǎn)5→節(jié)點(diǎn)6→工作完成

集卡路徑4：集卡池0→節(jié)點(diǎn)7→節(jié)點(diǎn)8→工作完成

個(gè)體選擇概率的分派方法使用的是輪盤賭法，適應(yīng)度值越高被選擇的可能性越大。

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

圖2 交叉操作拒絕策略Fig. 2 Rejection way based on crossover

圖3 交叉操作及修復(fù)操作Fig. 3 Crossover operator and repair operator

4) 變異操作

采用換位變異原則執(zhí)行變異操作。在生成的子代中也會(huì)出現(xiàn)局部?jī)?yōu)先級(jí)序號(hào)亂序的情況，處理方法同交叉操作(如圖4~5)。

圖4 變異操作Fig. 4 Mutation operator

圖5 變異修復(fù)操作Fig. 5 Mutation and repair operator

3.2 多級(jí)目標(biāo)優(yōu)化的啟發(fā)式算法實(shí)現(xiàn)

針對(duì)集裝箱港口雙 40英尺岸橋的工作特點(diǎn)，在此設(shè)計(jì)一個(gè)多級(jí)目標(biāo)優(yōu)化的啟發(fā)式算法，來(lái)與遺傳算法進(jìn)行比較(見(jiàn)圖6)。

圖6 多級(jí)目標(biāo)優(yōu)化的啟發(fā)式算法流程Fig. 6 Multiple target optimization heuristic algorithm process

在所設(shè)計(jì)的啟發(fā)式算法中，綜合考慮了岸橋裝卸集裝箱的作業(yè)順序、同時(shí)作業(yè)的2輛集卡的協(xié)調(diào)問(wèn)題及任務(wù)的選擇分派情況來(lái)制定集卡的實(shí)時(shí)調(diào)度策略。采用多級(jí)優(yōu)化方法，將操作同一個(gè)任務(wù)對(duì)的2輛集卡到達(dá)岸橋處的時(shí)間差作為第一級(jí)優(yōu)化目標(biāo)，將任務(wù)分派結(jié)束后的岸橋延遲時(shí)間及集卡空駛時(shí)間作為第二級(jí)優(yōu)化目標(biāo)。為各級(jí)目標(biāo)設(shè)定不同的權(quán)重，根據(jù)最終目標(biāo)時(shí)間最小化來(lái)決定任務(wù)分派方案。在此啟發(fā)式算法中主要用到2個(gè)策略：

最緊急任務(wù)選擇策略：對(duì)于雙 40英尺岸橋同時(shí)操作的2個(gè)集裝箱，任何一個(gè)集裝箱的延遲都會(huì)對(duì)后續(xù)的安排產(chǎn)生很大的影響，所以雙 40英尺岸橋?qū)τ诩ǖ耐叫耘c協(xié)調(diào)性要求比常規(guī)岸橋的要求更高，最緊急的任務(wù)就是優(yōu)先權(quán)最高的任務(wù)。

集卡分派策略：由于雙 40英尺岸橋?qū)Σ僮魍粋€(gè)任務(wù)對(duì)的兩輛集卡有同步性的要求，在為任務(wù)分配集卡時(shí)，首先以第一級(jí)優(yōu)化目標(biāo)為決策條件。在分派任務(wù)對(duì)的各個(gè)任務(wù)時(shí)，要將任務(wù)分配給集卡同步性最好的集卡，滿足2輛集卡到達(dá)岸橋處的時(shí)間差最小的要求。為了防止分派方案陷入局部最優(yōu)的情況，在分派方案時(shí)采用允許任務(wù)根據(jù)優(yōu)先級(jí)的順序自動(dòng)插入到已分派好任務(wù)的集卡路徑中，后續(xù)任務(wù)將自動(dòng)延時(shí)操作。循環(huán)結(jié)束后進(jìn)行第二級(jí)目標(biāo)的選擇，最終確定解決方案。

4 案例及結(jié)果分析

4.1 案例

本文設(shè)定某港口某時(shí)刻有一艘船舶需要裝卸，有2臺(tái)雙40英尺岸橋參與裝卸任務(wù)，每個(gè)岸橋分配10個(gè)任務(wù)對(duì)，共有40個(gè)集裝箱任務(wù)需要操作，首先為這2臺(tái)岸橋分配4輛集卡。任務(wù)的計(jì)劃開始時(shí)間與工作順序如表2所示。

表2 任務(wù)對(duì)的工作順序Table 2 Work order of couple tasks

表3 集卡行駛時(shí)間及設(shè)備操作時(shí)間Table 3 Vehicle transportation time and equipment operation time

根據(jù)表1的計(jì)算方法及上述數(shù)據(jù)可以得到相鄰2個(gè)工作間的準(zhǔn)備時(shí)間，為模型的求解做準(zhǔn)備。由于案例中涉及到隨機(jī)數(shù)據(jù)的產(chǎn)生，所以對(duì)每一個(gè)結(jié)果都運(yùn)行 10次，然后各自取平均值，目標(biāo)權(quán)系數(shù)設(shè)為：α=0.4，μ=0.5，β=0.1。

4.2 結(jié)果分析

將上述案例用遺傳算法和啟發(fā)式算法分別求解，2種方法分別采用Python編程及C#編程實(shí)現(xiàn)。設(shè)啟發(fā)式算法的最大循環(huán)次數(shù)是200。

表4 案例求解結(jié)果Table 4 Results for case s

由表4可以看出，2種求解方法都可以滿足時(shí)間上的實(shí)時(shí)調(diào)度要求，遺傳算法的求解結(jié)果明顯要優(yōu)于啟發(fā)式算法的求解結(jié)果，其求解的結(jié)果更準(zhǔn)確。這說(shuō)明本遺傳算法的設(shè)計(jì)有效。

但是雙 40英尺岸橋的效率并沒(méi)有得到最大發(fā)揮，仍然存在很大的岸橋延遲時(shí)間，究其根本原因是在此案例中分配的集卡數(shù)量不能很好地滿足雙40英尺岸橋的調(diào)度需求，集卡不能在雙40英尺岸橋準(zhǔn)備好開始工作時(shí)將集裝箱運(yùn)到岸橋處，造成雙40英尺岸橋操作當(dāng)前任務(wù)及后續(xù)任務(wù)的延遲。為了盡量使雙 40英尺岸橋發(fā)揮其效率，需要進(jìn)一步增加集卡的數(shù)量來(lái)配合雙40英尺岸橋的裝卸工作。

4.2.1 集卡數(shù)量對(duì)結(jié)果的影響

為了說(shuō)明不同數(shù)量集卡對(duì)于裝卸效率的影響，利用遺傳算法就上述案例進(jìn)行求解不同數(shù)量集卡條件下的集卡分配問(wèn)題，得到最佳的岸橋－集卡配比。求解結(jié)果數(shù)據(jù)圖形化如圖7所示。

圖7 雙40尺岸橋不同集卡數(shù)量配比各個(gè)指標(biāo)Fig. 7 Indexes under different number of cards for dual 40’quay crane

由圖7可以看出，隨著集卡數(shù)量的增多，目標(biāo)函數(shù)逐漸減小，當(dāng)集卡數(shù)量達(dá)到 11輛時(shí)，目標(biāo)函數(shù)開始趨于穩(wěn)定，說(shuō)明對(duì)于此案例 11臺(tái)集卡足以滿足雙40英尺岸橋工作的需求，當(dāng)集卡數(shù)量大于8臺(tái)時(shí)，集卡的空駛時(shí)間開始回升，這是因?yàn)楫?dāng)集卡增多到一定程度的時(shí)候，由于工作量不是太大，有一部分集卡將不會(huì)進(jìn)行邊裝邊卸的操作，從而增加集卡的空駛時(shí)間。

岸橋的延遲時(shí)間及同任務(wù)組集卡時(shí)間差在集卡數(shù)量大于 11時(shí)，趨于收斂。在港口作業(yè)中，雙40英尺岸橋與集卡相比，雙40英尺岸橋不能有效工作引起的損失遠(yuǎn)大于集卡空駛帶來(lái)的損失，所以經(jīng)過(guò)綜合分析可以得到岸橋－集卡的最佳配比為2:11。

4.2.2 岸橋類型對(duì)結(jié)果的影響

為了說(shuō)明雙 40英尺岸橋與常規(guī)岸橋在工作效率上的差異，將上述案例通過(guò)常規(guī)岸橋進(jìn)行操作，將任務(wù)組的2個(gè)任務(wù)進(jìn)行拆分，一前一后分別等待操作，利用改進(jìn)遺傳算法得到如下結(jié)果，求解結(jié)果見(jiàn)表5。

表5 不同數(shù)量集卡配比的岸橋工作時(shí)間Table 5 Dual 40’ quay crane working time based on different number of cards s

為了更形象地揭示雙 40英尺岸橋與常規(guī)岸橋工作效率的對(duì)比情況，可以對(duì)二者的差值進(jìn)行定量分析，在此引入了一個(gè)比值關(guān)系：

γ=(常規(guī)岸橋最早完工時(shí)間-雙 40英尺岸橋最早完工時(shí)間)/常規(guī)岸橋最早完工時(shí)間。

上述公式表示的是在同等條件下，雙 40英尺岸橋與常規(guī)岸橋相比，工作效率提升的程度。當(dāng) γ為正時(shí)，說(shuō)明雙 40英尺岸橋的工作效率高于常規(guī)岸橋，值越大則說(shuō)明雙 40英尺岸橋作用越明顯。根據(jù)表5，可以計(jì)算得出不同集卡數(shù)量下的γ值，見(jiàn)表6。

表6 不同數(shù)量集卡下的γ值Table 6 γ value under different number of cards

根據(jù)表6中的比值數(shù)據(jù)，可以看出雙40英尺岸橋?qū)τ谔嵘劭谘b卸效率的貢獻(xiàn)。雙 40英尺岸橋的作業(yè)效率始終高于常規(guī)岸橋的作業(yè)效率。當(dāng)集卡的數(shù)目為11時(shí)，γ=0.46接近于0.5，說(shuō)明在港口資源配置合理的情況下，雙 40英尺岸橋可將工作效率提升至接近極限值。

5 結(jié)論

1) 實(shí)驗(yàn)結(jié)果證明了與多級(jí)目標(biāo)優(yōu)化的啟發(fā)式算法相比，遺傳算法在求解雙 40英尺岸橋的集卡調(diào)度問(wèn)題有最優(yōu)方案。

2) 在集卡合理配置的情況下，與常規(guī)岸橋相比，雙40英尺岸橋的作業(yè)效率可提高近50%。

[1] 包起帆, 金茂海. 雙 40英尺集裝箱橋吊的實(shí)踐與探索[J]. 港口科技, 2008, 19(2): 53-55.BAO Qifan, JIN Maohai. The practice of and probing on the double 40′ container bridge crane[J]. Science &Technology of Ports, 2008, 19(2): 53-55.

[2] CAO Jinxin, SHI Qixin, Lee D H. Integrated quay crane and yard truck schedule problem in container terminals[J].Tsinghua Science & Technology, 2010, 15(4): 467-474.

[3] 尚晶, 徐長(zhǎng)生. 基于強(qiáng)化學(xué)習(xí)的集裝箱碼頭卡車調(diào)度策略研究[J]. 武漢理工大學(xué)學(xué)報(bào), 2011, 33(3): 72-76.SHANG Jing, XU Changsheng. Vehicle scheduling in container terminal based on reinforcement learning[J].Journal of Wuhan University of Technology, 2011, 33(3):72-76.

[4] 計(jì)明軍, 靳志宏. 集裝箱碼頭集卡和岸橋協(xié)調(diào)調(diào)度優(yōu)化[J]. 復(fù)旦學(xué)報(bào)(自然科版), 2007, 46(4): 476-480.JI Mingjun, JIN Zhihong. A united optimization of crane scheduling and yard trailer routing in a container terminal[J]. Journal of Fudan University (Natural Science), 2007, 46(4): 476-480.

[5] Lee D H, CAO Jinxin, SHI Qixin, et al. A heuristic algorithm for yard truck scheduling and storage allocation problems[J]. Transportation Research Part E, 2009, 45(5):810-820.

[6] 秦天保, 彭嘉瑤, 沙梅. 基于約束規(guī)劃的岸橋與集卡集成調(diào)度[J]. 計(jì)算機(jī)工程, 2014, 40(5): 196-202.QIN Tianbao, PENG Jiayao, SHA Mei. Integrated quay crane and yard truck scheduling based on constraint programming[J]. Computer Engineering, 2014, 40(5):196-202.

[7] TANG Lixin, ZHAO Jiao, LIU Jiyin. Modeling and solution of the joint quay crane and truck scheduling problem[J]. European Journal of Operational Research,2014, 236(3): 978-990.

[8] 樂(lè)美龍, 趙彥營(yíng), 劉秀玲. 時(shí)間窗下單船岸橋調(diào)度-基于數(shù)學(xué)規(guī)劃和規(guī)則的啟發(fā)式算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2014, 50(9): 242-248.LE Meilong, ZHAO Yanying, LIU Xiuling.Shore-mounted gantry crane scheduling for single vessel under time window-using mathematical programming and rule heuristic algorithm[J]. Computer Engineering and Applications, 2014, 50(9): 242-248.

[9] 錢繼鋒, 朱曉寧, 謝霞. “岸橋—集卡—堆場(chǎng)”雙向作業(yè)協(xié)同模型[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2014, 14(2):138-143.QIAN Jifeng, ZHU Xiaoning, XIE Xia.“Quays, Trailers and Yard” two way operations plan coordinated model[J].Transportation Systems Engineering and Information,2014, 14(2): 138-143.

[10] Kaveshgar N, Huynh N. Integrated quay crane and yard truck scheduling for unloading inbound containers[J].Production Economics, 2015, 159(1): 168-177.

[11] Homayouni S M, Tang S H, Motlagh O. A genetic algorithm for optimization of integrated scheduling of cranes, vehicles, and storage platforms at automated container terminals[J]. Journal of Computational and Applied Mathematics, 2014, 270(1): 545-555.

[12] 康志敏, 吳洪明. 港口集裝箱碼頭集卡優(yōu)化調(diào)度研究[J]. 物流工程與管理, 2011, 33(2): 59-61.KANG Zhimin, WU Hongming. Research on optimized scheduling for container truck at port container wharfs[J].Storage Transportation ＆ Preservation of Commodities,2011, 33(2): 59-61.

[13] 韓曉龍, 牟少莉. 基于CHC 算法的集卡與岸橋協(xié)調(diào)調(diào)度優(yōu)化問(wèn)題[J]. 武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版), 2014, 36(2): 233-236.HAN Xiaolong, MOU Shaoli. Integrated quay crane and yard truck scheduling based on CHC algorithm[J].Journal of Wuhan University of Technology (Information& Management Engineering), 2014, 36(2): 233-236.

[14] 李尤豐, 李勤豐, 劉玉霞, 等. 一種新的集卡動(dòng)態(tài)調(diào)度模型及算法[J]. 南京師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014,37(1): 104-111.LI Youfeng, LI Qinfeng, LIU Yuxia, et al. Dynamic dispatch model of container trucks based on hybrid genetic algorithm[J]. Journal of Nanjing Normal University (Natural Science Edition), 2014, 37(1): 104-111.

[15] 尚晶. 面向雙40英尺岸橋的碼頭集卡調(diào)度模型與算法[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2011, 38(11):84-87.SHANG Jing. Vehicle routing model and algorithm for twin 40 ft quay cranes in container terminals[J]. Journal of Huazhong University of Science and Technology(Nature Science), 2011, 38(11): 84-87.