范厚明, 馬曉斌, 彭文豪, 岳麗君, 馬夢(mèng)知

(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院, 遼寧 大連 116026)

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

B—貝位集合,其中b為任一貝位,b∈B,Bh為箱區(qū)h內(nèi)所有貝位集合,bh為箱區(qū)h內(nèi)任一貝位,bhs為箱區(qū)h內(nèi)固定的一個(gè)接力貝位,區(qū)間[1,bhs)表示海側(cè)箱區(qū)貝位,區(qū)間(bhs, |B|]表示陸側(cè)箱區(qū)貝位,bh,bhs∈Bh,Bh∈B

E—層集合,其中e為任一層,e∈E,Eh為箱區(qū)h內(nèi)所有層的集合,eh為箱區(qū)h內(nèi)任一層,eh∈E,Eh∈E

H—箱區(qū)集合,其中h為任一箱區(qū),h∈H

I—失約事件發(fā)生后,場(chǎng)橋任務(wù)集合,其中i為任一任務(wù),Ih1為箱區(qū)h內(nèi)海側(cè)場(chǎng)橋作業(yè)集港箱任務(wù)集合,Ih2為箱區(qū)h內(nèi)海側(cè)場(chǎng)橋作業(yè)進(jìn)口箱任務(wù)集合,Ih3為箱區(qū)h海側(cè)場(chǎng)橋作業(yè)出口箱任務(wù)集合,Ih4為箱區(qū)h內(nèi)陸側(cè)場(chǎng)橋作業(yè)集港箱任務(wù)集合,Ih5為箱區(qū)h內(nèi)陸側(cè)場(chǎng)橋作業(yè)進(jìn)口箱任務(wù)集合,I0為各箱區(qū)中第1個(gè)任務(wù)的集合

Ky—場(chǎng)橋集合,其中ky為任一場(chǎng)橋,Kyh為箱區(qū)h內(nèi)所有場(chǎng)橋的集合,kyh1為箱區(qū)h內(nèi)海側(cè)場(chǎng)橋,kyh2為箱區(qū)h內(nèi)陸側(cè)場(chǎng)橋,kyh1,kyh2∈Kyh,Kyh∈Ky

ly—輸入變量,雙場(chǎng)橋之間的安全貝位間距

N—失約事件發(fā)生時(shí),待作業(yè)的集裝箱集合,其中n為任一集裝箱,N1為待作業(yè)集港箱集合,N2為待作業(yè)進(jìn)口箱集合,N3為待作業(yè)出口箱集合,N1∪N2∪N3=N

Ohbre—輸入變量,不可用箱位,若h箱區(qū)b貝r列e層已堆存集裝箱則為1,否則為0

Pn—輸入變量,集裝箱n優(yōu)先級(jí)

Qhb—輸入變量,h箱區(qū)內(nèi)任一貝內(nèi)集裝箱容量

Qhe—輸入變量,h箱區(qū)內(nèi)任一層內(nèi)集裝箱容量

Qhr—輸入變量,h箱區(qū)內(nèi)任一列內(nèi)集裝箱容量

R—列集合,其中r為任一列,r∈R,Rh為箱區(qū)h內(nèi)所有列的集合,rh為箱區(qū)h內(nèi)任一列,rh∈Rh,Rh∈R

t1—輸入變量,場(chǎng)橋從緩沖支架/箱位上提取/放下1個(gè)集裝箱的耗時(shí)

t2—輸入變量,自動(dòng)堆垛機(jī)(ASC)大車移動(dòng)一個(gè)貝位的時(shí)間

t3—輸入變量,ASC小車移動(dòng)一列的時(shí)間

t4—輸入變量,ASC翻箱一次的時(shí)間

V—失約事件發(fā)生時(shí),作業(yè)完畢的集裝箱集合,V1為已進(jìn)場(chǎng)的集港箱集合,V2為已進(jìn)場(chǎng)的進(jìn)口箱集合,V3為已出場(chǎng)的出口箱集合,V1∪V2∪V3=V

ykyhij—決策變量,若場(chǎng)橋kyh作業(yè)完任務(wù)i后作業(yè)任務(wù)j則為1,否則為0

自動(dòng)化集裝箱碼頭各箱區(qū)同時(shí)具備裝卸船和集疏港作業(yè)功能,除要求疏港箱盡快離港外,集港箱能否及時(shí)按計(jì)劃送達(dá)尤為重要.雖然通過(guò)預(yù)約系統(tǒng)碼頭方可獲取送箱集卡的預(yù)約時(shí)間及集港箱相關(guān)信息,但受各種主客觀因素影響,實(shí)際到場(chǎng)時(shí)間具有不確定性.若送箱集卡未在計(jì)劃規(guī)定的時(shí)間段內(nèi)及時(shí)進(jìn)港,不僅會(huì)導(dǎo)致預(yù)先制定的計(jì)劃失效,還會(huì)因場(chǎng)橋被占用而增加后續(xù)規(guī)定時(shí)間段內(nèi)送箱集卡的交箱等待時(shí)間,甚至?xí)率勾皽陔x港.因此,綜合考慮送箱集卡實(shí)際到場(chǎng)時(shí)間、場(chǎng)橋作業(yè)效率等因素,在優(yōu)化各箱區(qū)場(chǎng)橋作業(yè)待裝船的出口箱、待卸船的進(jìn)口箱和集港箱基礎(chǔ)上,為集港箱分配箱位,確保船舶按時(shí)離港是碼頭亟待解決的問(wèn)題.

預(yù)約系統(tǒng)有利于削減堆場(chǎng)作業(yè)高峰時(shí)段[1],部分專家針對(duì)給定預(yù)約時(shí)段內(nèi)集卡送箱順序不確定問(wèn)題展開(kāi)研究.Gharehgozli等[2]考慮出口箱交箱時(shí)間的動(dòng)態(tài)不確定因素和船舶離港時(shí)間的不確定性,建立并求解以最小化船舶離港時(shí)間為目標(biāo)的數(shù)學(xué)規(guī)劃模型;Yu等[3]分析了外集卡不確定進(jìn)港對(duì)箱區(qū)選擇與出口箱箱位的影響,建立并求解了雙目標(biāo)規(guī)劃模型.錯(cuò)過(guò)預(yù)約時(shí)段到達(dá)的集卡數(shù)量會(huì)隨預(yù)約車輛增多而增多;Galle等[4]在集卡失約條件下,考慮將場(chǎng)橋調(diào)度、箱位分配及翻箱問(wèn)題結(jié)合研究;Torkjazi等[5]設(shè)計(jì)了一種新型集卡預(yù)約系統(tǒng),以平衡每日抵港集卡數(shù)并提供最佳預(yù)約時(shí)間窗;尹延?xùn)|等[6]通過(guò)正態(tài)分布近似模擬失約集卡實(shí)際到達(dá)信息,建立以最小化翻箱數(shù)和場(chǎng)橋移動(dòng)距離為目標(biāo)的數(shù)學(xué)模型,該模型在失約事件發(fā)生后需重新制定箱位分配和場(chǎng)橋調(diào)度計(jì)劃;Sha等[7]針對(duì)場(chǎng)橋的能耗問(wèn)題,建立以場(chǎng)橋能耗最小化為目標(biāo)的整數(shù)規(guī)劃模型;Maldonado等[8]考慮集裝箱船靠泊時(shí)間,以翻箱數(shù)量最少為目標(biāo)建立數(shù)學(xué)模型;文獻(xiàn)[9]中研究了雙目標(biāo)集裝箱倒箱問(wèn)題;范厚明等[10]考慮出口箱進(jìn)出場(chǎng)、預(yù)翻箱等因素對(duì)出口箱箱位分配及場(chǎng)橋調(diào)度的影響,構(gòu)建雙層混合整數(shù)規(guī)劃模型.因關(guān)于多箱區(qū)箱位分配及場(chǎng)橋調(diào)度優(yōu)化的現(xiàn)有成果很少,陳超等[11]提出出口箱箱區(qū)選擇與箱位分配協(xié)調(diào)調(diào)度問(wèn)題,構(gòu)建了箱區(qū)選擇與箱位分配兩階段非線性整數(shù)規(guī)劃模型.

綜上可知,現(xiàn)有關(guān)于場(chǎng)橋調(diào)度的研究?jī)H分析了出口箱集港過(guò)程,較少同時(shí)優(yōu)化船舶裝卸船作業(yè)、出口箱集港作業(yè),但實(shí)際作業(yè)過(guò)程中存在雙場(chǎng)橋同時(shí)作業(yè)進(jìn)出口箱情況,雙場(chǎng)橋之間相互限制;現(xiàn)有針對(duì)箱位分配的研究中僅涉及單個(gè)箱區(qū)內(nèi)的箱位,欠缺在多箱區(qū)之間搜索最優(yōu)箱位的考慮,但同一船舶的集港箱堆存在多個(gè)箱區(qū),各箱區(qū)之間的集裝箱可互換箱位;現(xiàn)有針對(duì)集卡到港時(shí)間不確定性研究多采用預(yù)測(cè)到港時(shí)間和分析到港規(guī)律等方法,但碼頭作業(yè)環(huán)境較復(fù)雜,實(shí)際情況常與預(yù)測(cè)或統(tǒng)計(jì)結(jié)果偏差較大,需針對(duì)實(shí)際集卡到港信息動(dòng)態(tài)調(diào)整調(diào)度方案.因此,針對(duì)送箱集卡失約下多箱區(qū)箱位分配及場(chǎng)橋調(diào)度優(yōu)化問(wèn)題,考慮送箱集卡實(shí)際到港時(shí)間與堆場(chǎng)實(shí)際工作狀況關(guān)系,以最小化失約集卡等待時(shí)間、場(chǎng)橋完工時(shí)間為目標(biāo),構(gòu)建箱位分配及雙場(chǎng)橋調(diào)度優(yōu)化模型.

1 問(wèn)題描述

根據(jù)船舶靠泊計(jì)劃,堆場(chǎng)提前發(fā)布若干個(gè)預(yù)約集港時(shí)段,外集卡預(yù)約成功后需在預(yù)約時(shí)段到達(dá).若送箱集卡錯(cuò)過(guò)預(yù)約時(shí)段即失約到達(dá)堆場(chǎng)時(shí),將對(duì)集港完工時(shí)間、翻箱量及集卡等待時(shí)間產(chǎn)生影響,堆場(chǎng)結(jié)合預(yù)約信息及集卡實(shí)際到場(chǎng)信息,動(dòng)態(tài)調(diào)整箱位分配和場(chǎng)橋調(diào)度計(jì)劃,減少失約影響.

堆場(chǎng)通常按重箱壓輕箱、長(zhǎng)途箱壓短途箱的規(guī)則堆存,且優(yōu)先級(jí)較大的集港箱應(yīng)堆存至上層,否則將產(chǎn)生翻箱作業(yè).失約箱箱位優(yōu)化如圖1所示,同一時(shí)段的集港箱堆存在箱區(qū)7至箱區(qū)10.當(dāng)箱區(qū)7貝39的6號(hào)箱失約,則將失約6號(hào)箱堆存至箱區(qū)8貝39(此位置暫不堆存集裝箱)或箱區(qū)9貝39(箱6與箱11優(yōu)先級(jí)相同),這兩種情形都不會(huì)帶來(lái)額外翻箱;當(dāng)無(wú)法避免翻箱時(shí),堆存至箱區(qū)10貝39位置,此時(shí)翻箱次數(shù)比堆存至初始箱位少.

結(jié)合箱位分配信息,動(dòng)態(tài)調(diào)整的場(chǎng)橋調(diào)度計(jì)劃應(yīng)縮短完工時(shí)間.堆場(chǎng)通常采用兩臺(tái)自動(dòng)堆垛機(jī)(ASC)接力作業(yè)集港箱和進(jìn)出口箱.集卡送箱到箱區(qū)后,陸側(cè)ASC取箱并將其送至接力貝位,海側(cè)ASC在接力貝位提取集港箱放置指定箱位,如圖2所示.進(jìn)口箱作業(yè)過(guò)程與集港箱相反,出口箱只有海側(cè)ASC作業(yè)出場(chǎng)過(guò)程.若雙ASC同時(shí)作業(yè)進(jìn)口箱和出口箱,合理的場(chǎng)橋調(diào)度應(yīng)為:陸側(cè)ASC將集港箱送至接力貝位后,從接力貝位提取進(jìn)口箱放至指定陸側(cè)箱位;海側(cè)ASC將進(jìn)口箱送至接力貝位后,從接力貝位提取集港箱放至指定海側(cè)箱位,或提取出口箱放到海側(cè)交接區(qū).結(jié)合箱位分配計(jì)劃,同時(shí)協(xié)調(diào)場(chǎng)橋調(diào)度計(jì)劃,兼顧翻箱與完工時(shí)間.

圖2 雙ASCs作業(yè)任務(wù)與出口箱流轉(zhuǎn)關(guān)系示意圖

2 模型建立

構(gòu)建動(dòng)態(tài)調(diào)整模型,為預(yù)約到港集裝箱分配箱位,制定雙場(chǎng)橋調(diào)度計(jì)劃實(shí)時(shí)監(jiān)測(cè)集卡到港順序.若出現(xiàn)失約問(wèn)題影響后續(xù)集裝箱箱位,則動(dòng)態(tài)調(diào)整箱位分配和場(chǎng)橋調(diào)度計(jì)劃,研究基于以下假設(shè).

(1) 集港箱可用箱區(qū)數(shù)量已知,可根據(jù)船舶靠泊計(jì)劃確定.

(2) 集港箱箱型一致.

(3) 貝內(nèi)預(yù)留翻箱位,不考慮二次翻箱.

(4) 外集卡和雙ASCs運(yùn)輸過(guò)程中不受外界干擾.

(5) 送箱集卡在預(yù)約時(shí)段內(nèi)到達(dá)數(shù)量足夠多,即場(chǎng)橋不會(huì)等待作業(yè)送箱集卡.

箱位分配和場(chǎng)橋調(diào)度優(yōu)化模型如下:

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

b∈B,r∈R,e∈[2,|E|],

n∈N1∪N2∪V1∪V2

(7)

h∈H,b∈[1,bhs),r∈R

(8)

?h∈H,b∈B, ?r∈R, ?e=2,3,…,|E|, ?z=1,2,…,(e-1)

(9)

?h∈H,n∈N1∪N2,ky∈Ky

(10)

(11)

(12)

(13)

(14)

|N1|+|N2|+|N3|

(15)

(16)

(17)

(18)

h∈H,ky∈Ky

(19)

?i∈Ih2,n∈N2,ky∈Ky

(20)

?i∈Ih5,n∈N2,ky∈Ky

(21)

?i∈Ih1,n∈N1,ky∈Ky

(22)

?i∈Ih4,n∈N1,ky∈Ky

(23)

j∈Ih1∪Ih5,n∈N1∪N2,ky∈Ky

(24)

?i∈Ih4,n∈N1,ky∈Ky

(25)

?i,j∈Ih3,n∈N3,

h∈H,ky∈Ky

(26)

?i∈Ih2,j∈Ih3,n∈N3,

h∈H,ky∈Ky

(27)

M(ykyhij-1), ?i∈Ih1,j∈Ih3,

m∈N1,n∈N3,h∈H,ky∈Ky

(28)

?i,j∈Ih2,h∈H

(29)

?i∈Ih3,j∈Ih2,h∈H

(30)

M(ykyhij-1), ?i∈Ih1,j∈Ih2,

m∈N1,h∈H,ky∈Ky

(31)

M(ykyhij-1), ?i,j∈Ih1,

m∈N1,h∈H,ky∈Ky

(32)

?i∈Ih3,j∈Ih1,h∈H

(33)

?i∈Ih2,j∈Ih1,h∈H

(34)

M(ykyhij-1), ?i,j∈Ih5,m∈N2,

h∈H,ky∈Ky

(35)

?i∈Ih4,j∈Ih5,h∈H

(36)

M(ykyhij-1), ?i,j∈Ih4,h∈H

(37)

M(ykyhij-1), ?i∈Ih5,j∈Ih4,

m∈N2,h∈H,ky∈Ky

(38)

(39)

目標(biāo)函數(shù)式(1)表示最小化場(chǎng)橋的最大完工時(shí)間.約束式(2)～(7)表示箱位分配:約束式(2)表示集港箱只能被分配到一個(gè)箱位,且落箱位在海側(cè)箱區(qū);約束式(3)表示進(jìn)口箱只能被分配到一個(gè)箱位,且落箱位在陸側(cè)箱區(qū);約束式(4)～(6)表示只能在給定空間范圍內(nèi)堆存集裝箱,不能超過(guò)箱區(qū)內(nèi)貝位、列、層容量的限制;約束式(7)表示集裝箱不能懸空堆存.約束式(8)和(9)表示翻箱:約束式(8)表示優(yōu)先級(jí)較大的集港箱堆存在上層,其中M表示無(wú)限大的數(shù);約束式(9)表示翻箱次數(shù).約束式(10)～(16)表示各箱區(qū)場(chǎng)橋緊前緊后任務(wù)邏輯關(guān)系:約束式(10)表示若集裝箱n被堆存在箱區(qū)h則會(huì)被場(chǎng)橋kyh作業(yè);約束式(11)和(12)分別表示海側(cè)場(chǎng)橋和陸側(cè)場(chǎng)橋的任一任務(wù)只有一個(gè)緊后作業(yè);約束式(13)和(14)分別表示海側(cè)場(chǎng)橋和陸側(cè)場(chǎng)橋的任一任務(wù)只有一個(gè)緊前作業(yè);約束式(15)和(16)分別表示海側(cè)場(chǎng)橋和陸側(cè)場(chǎng)橋的任務(wù)量.約束式(17)表示兩個(gè)場(chǎng)橋間留有安全作業(yè)距離.約束式(18)～(38)表示各箱區(qū)場(chǎng)橋作業(yè)任務(wù)時(shí)間邏輯關(guān)系約束:式(18)表示每個(gè)箱區(qū)的場(chǎng)橋從0時(shí)刻同時(shí)開(kāi)始作業(yè);約束式(19)表示場(chǎng)橋作業(yè)出口箱n的結(jié)束作業(yè)時(shí)刻;約束式(20)和(21)分別表示海側(cè)場(chǎng)橋和陸側(cè)場(chǎng)橋作業(yè)進(jìn)口箱n的結(jié)束作業(yè)時(shí)刻;約束式(22)和(23)分別表示海側(cè)場(chǎng)橋和陸側(cè)場(chǎng)橋作業(yè)集港箱n的結(jié)束作業(yè)時(shí)刻;約束式(24)表示同一集裝箱對(duì)應(yīng)的兩個(gè)任務(wù),前一任務(wù)結(jié)束之后,后面的任務(wù)才能被作業(yè);約束式(25)表示集卡到港之后,才可以被陸側(cè)場(chǎng)橋作業(yè);約束式(26)～(28)分別表示當(dāng)出口箱n的緊前任務(wù)所屬集裝箱為出口箱、進(jìn)口箱、集港箱時(shí)的開(kāi)始作業(yè)時(shí)刻;約束式(29)～(31)分別表示當(dāng)海側(cè)場(chǎng)橋作業(yè)的進(jìn)口箱n的緊前任務(wù)所屬集裝箱為進(jìn)口箱、出口箱、集港箱時(shí)的開(kāi)始作業(yè)時(shí)刻;約束式(32)～(34)分別表示當(dāng)海側(cè)場(chǎng)橋作業(yè)的集港箱n的緊前任務(wù)所屬集裝箱為集港箱、出口箱、進(jìn)口箱時(shí)的開(kāi)始作業(yè)時(shí)刻;約束式(35)和(36)分別表示當(dāng)陸側(cè)場(chǎng)橋作業(yè)的進(jìn)口箱的緊前任務(wù)所屬集裝箱為進(jìn)口箱、集港箱時(shí)的開(kāi)始作業(yè)時(shí)刻;約束式(37)和(38)分別表示當(dāng)陸側(cè)場(chǎng)橋作業(yè)的集港箱的緊前任務(wù)所屬集裝箱為集港箱、進(jìn)口箱時(shí)的開(kāi)始作業(yè)時(shí)刻.約束式(39)表示決策變量的取值范圍.

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

雙場(chǎng)橋協(xié)調(diào)調(diào)度問(wèn)題被證明是NP-Hard問(wèn)題,利用CPLEX等商業(yè)軟件無(wú)法在有效時(shí)間內(nèi)解決碼頭實(shí)際需求,Kress等[12]設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法求解集裝箱數(shù)量較多時(shí)的雙場(chǎng)橋調(diào)度方案.基于此研究,考慮失約集港箱在多箱區(qū)箱位之間的分配,設(shè)計(jì)混合遺傳變鄰域搜索算法(Hybrid Genetic Algorithm and Variable Neighborhood Search, HGAVNS)求解,算法流程如圖3所示.

圖3 混合遺傳變鄰域搜索算法

3.1 編碼方式及初始種群生成

(1) 染色體編碼.染色體采用實(shí)數(shù)編碼,編碼長(zhǎng)度為任務(wù)數(shù)量,如圖4所示.其中,第1行表示任務(wù),任務(wù)編號(hào)具有唯一性;第2行表示箱號(hào),1～10表示進(jìn)口箱,11～20表示出口箱,21～30表示集港箱,進(jìn)口箱和集港箱均會(huì)被海側(cè)和陸側(cè)的場(chǎng)橋作業(yè),因此其對(duì)應(yīng)的相同箱號(hào)的任務(wù)有2個(gè);第3行表示作業(yè)上述任務(wù)的場(chǎng)橋編號(hào);第4行表示箱區(qū)編號(hào),同一箱區(qū)有2個(gè)不同的場(chǎng)橋,按照箱區(qū)大小,場(chǎng)橋編號(hào)依次遞增,同一箱區(qū)中編號(hào)小的是陸側(cè)場(chǎng)橋;第五行表示箱位,由5位數(shù)字構(gòu)成,前2位為貝位號(hào),3和4位為列號(hào),第5位為層號(hào),其中,00表示箱區(qū)近陸側(cè)的緩沖支架,41表示箱區(qū)近海側(cè)的緩沖支架,集港箱和進(jìn)口箱分別被放置到陸側(cè)或海側(cè)的緩沖支架后被場(chǎng)橋作業(yè).因出口箱的箱位在裝卸船過(guò)程中已知,故只需分配集港箱和進(jìn)口箱的堆存箱位,集港箱堆存在海側(cè),進(jìn)口箱堆存在陸側(cè).

圖4 染色體結(jié)構(gòu)示意圖

(2) 生成初始種群.將所有集港箱平均分成若干份分配給各個(gè)箱區(qū),在同一箱區(qū)中,將集港箱/進(jìn)口箱分成2個(gè)任務(wù)分別分配給2個(gè)場(chǎng)橋,將出口箱任務(wù)分配給海側(cè)場(chǎng)橋,隨機(jī)生成所有任務(wù)的作業(yè)順序,如圖4第1行所示.在可堆存的箱位中,為集港箱和進(jìn)口箱隨機(jī)挑選箱位,且挑選的箱位是從集港箱區(qū)中所有可堆存的空箱位中隨機(jī)選擇,生成的染色體需滿足式(2)～(8)的約束.按上述規(guī)則生成一定數(shù)量的染色體,構(gòu)成初始種群.

(3) 適應(yīng)度函數(shù).取目標(biāo)函數(shù)值倒數(shù)為適應(yīng)度函數(shù).

3.2 進(jìn)化操作

(1) 交叉算子.計(jì)算初始種群中各染色體的適應(yīng)度并升序排列,選擇相鄰的2個(gè)染色體作為交叉操作中染色體的父代.隨機(jī)生成2個(gè)交叉點(diǎn),交換其染色體基因值,若交叉后出現(xiàn)部分任務(wù)重復(fù)或丟失,則將重復(fù)的染色體刪除,丟失的染色體補(bǔ)充至同箱區(qū),如圖5所示.

圖5 交叉操作圖

(2) 變鄰域結(jié)構(gòu).按照輪盤(pán)賭的方式選擇較優(yōu)的父代染色體,因決策變量涉及場(chǎng)橋調(diào)度、箱區(qū)分配和箱位分配3種,如圖6所示.采用3種類鄰域結(jié)構(gòu):①隨機(jī)找到同一場(chǎng)橋的2個(gè)任務(wù),如任務(wù)3和任務(wù)1,交換其任務(wù)作業(yè)順序;②隨機(jī)選擇一個(gè)集裝箱,如集裝箱25,變化其所屬箱區(qū);③隨機(jī)選擇同一箱區(qū)中2個(gè)集港箱的接力任務(wù),如任務(wù)12和任務(wù)16,交換其箱位.

圖6 變鄰域操作圖

(3) 基因修復(fù).交叉變異過(guò)程中可能因箱位變化產(chǎn)生懸空的集裝箱,采用如下策略進(jìn)行修復(fù):按集港箱到場(chǎng)時(shí)間排序,檢查染色體中堆存在相同箱區(qū)、相同貝位、相同堆棧的若干集港箱,如果堆棧的順序從下往上符合集港箱到場(chǎng)時(shí)間的先后順序,則染色體無(wú)需修復(fù),否則,將同箱區(qū)、同貝位、同棧的若干箱位,按集港箱到場(chǎng)順序從上往下重新分配.

(4) 停止準(zhǔn)則.變鄰域算法中,若變鄰域搜索過(guò)程中,最優(yōu)解連續(xù)未改變的次數(shù)達(dá)到給定最大值,則變鄰域搜索停止;遺傳算法中,若迭代次數(shù)達(dá)到最大值,則算法終止.

3.3 干擾恢復(fù)策略

因碼頭擁堵或集卡出發(fā)時(shí)間太晚等原因?qū)е峦饧ǖ礁蹠r(shí)間不確定,當(dāng)出現(xiàn)集卡失約現(xiàn)象時(shí),需要系統(tǒng)分析和度量其對(duì)場(chǎng)橋調(diào)度和箱位分配方案的影響,整合包括對(duì)完工時(shí)間擾動(dòng)、外集卡等待時(shí)間擾動(dòng)等多類因素,使該擾動(dòng)事件的影響最小.設(shè)完工時(shí)間擾動(dòng)、集卡等待時(shí)間擾動(dòng)的權(quán)重分別為γ1和γ2,設(shè)計(jì)擾動(dòng)度量函數(shù)為

min(γ1f1(s)+γ2f2(s))

(40)

步驟1利用遺傳變鄰域算法生成初始計(jì)劃,若當(dāng)前情景與計(jì)劃有出入,則識(shí)別干擾因素,度量干擾程度.

步驟2確定緊后任務(wù)集,初始化后續(xù)任務(wù)的時(shí)間窗,根據(jù)失約集卡到港時(shí)間擴(kuò)展集裝箱被作業(yè)的時(shí)間窗.

步驟3針對(duì)失約箱計(jì)劃堆存箱區(qū)內(nèi)所有集裝箱重調(diào)度,同時(shí),將失約集卡放入其他箱區(qū),以擾動(dòng)度量函數(shù)的目標(biāo)值最小為目標(biāo),求解約束式(2)～(39)的擾動(dòng)度量函數(shù)目標(biāo)值,取兩者中的較小者為最優(yōu)的落箱位和場(chǎng)橋調(diào)度計(jì)劃.

4 算例實(shí)驗(yàn)

4.1 算例描述

使用MATLAB 2018b編程求解,結(jié)果在Inter Core i5 3.1 GHz CPU計(jì)算機(jī)中求解.箱區(qū)規(guī)模為40貝×10列×5層,每個(gè)貝位預(yù)留4個(gè)翻箱箱位,即每個(gè)貝位有46個(gè)箱位可堆存集裝箱.假設(shè)集港任務(wù)在3個(gè)箱區(qū)內(nèi)進(jìn)行,箱區(qū)內(nèi)的初始堆存信息如表1所示.

各箱區(qū)內(nèi)有兩臺(tái)ASC,場(chǎng)橋間安全距離留有4個(gè)貝位(4貝×6.096 m/貝=24.383 m)[1].單位貝位長(zhǎng)度取7 m,場(chǎng)橋大車移動(dòng)速度為240 m/min,小車移動(dòng)速度為120 m/min,場(chǎng)橋提放一個(gè)集裝箱的時(shí)間為0.5 min,翻箱時(shí)間為2 min/次,陸側(cè)ASC初始位置在陸側(cè)交接區(qū),海側(cè)ASC在海側(cè)交接區(qū).經(jīng)參數(shù)調(diào)試,交叉率為0.8,變異率為0.1,箱量120以下最大遺傳代數(shù)為200,否則為500,種群數(shù)量為200.為保證箱區(qū)主要作業(yè)集港任務(wù),令集港箱、裝船箱與卸船箱箱量按6∶2∶2隨機(jī)生成.

4.2 算例求解和結(jié)果分析

為驗(yàn)證模型的有效性,隨機(jī)生成9個(gè)小規(guī)模算例,采用商業(yè)計(jì)算軟件CPLEX和本文HGAVNS分別對(duì)模型進(jìn)行求解,結(jié)果如表2所示.隨著箱量的增加,CPLEX求解時(shí)間呈現(xiàn)指數(shù)增長(zhǎng),不適用大規(guī)模計(jì)算.HGAVNS與CPLEX精確解之間平均誤差最大為3.55%,當(dāng)箱量增加至60時(shí),求解時(shí)間超過(guò)10 000 s,對(duì)比可見(jiàn)本算法求解性能更好.

表2 CPLEX求解預(yù)優(yōu)化模型與HGAVNS算法對(duì)比表

經(jīng)調(diào)研可知,一些港口集裝箱碼頭(如大連港集裝箱碼頭)現(xiàn)行堆存策略為先到先作業(yè)策略,即根據(jù)已到港口集港箱次序,動(dòng)態(tài)搜索臨近不產(chǎn)生翻箱的箱位,然后分配給集港箱.將本文調(diào)度方法與港口現(xiàn)行調(diào)度方法進(jìn)行對(duì)比,10組對(duì)比結(jié)果如表3所示.由表可知,本文算法適用于不同規(guī)模問(wèn)題,雖求解時(shí)間隨箱量增加相應(yīng)增長(zhǎng),但均在合理時(shí)間內(nèi),最低改善效果為13.85%.

表3 不同規(guī)模集港箱于多箱區(qū)間分配結(jié)果

4.3 干擾恢復(fù)策略對(duì)比

表4 偏離預(yù)約時(shí)段實(shí)驗(yàn)結(jié)果對(duì)比

由表可知,本文策略和策略2優(yōu)于策略1,而本文策略可同時(shí)兼顧外集卡等待時(shí)間和完工時(shí)間.在偏離程度不大情形下,針對(duì)小規(guī)模問(wèn)題,本文策略和策略2在完工時(shí)間和外集卡等待時(shí)間差距不大,隨失約規(guī)模增加,本文策略在完工時(shí)間和外集卡等待時(shí)間優(yōu)勢(shì)凸顯.在外集卡等待時(shí)間上,策略2因失約集卡在該作業(yè)未失約集卡的時(shí)段內(nèi)被作業(yè),增加了后續(xù)任務(wù)集的集卡等待時(shí)間,故劣于本文策略.

4.4 靈敏度分析

圖7 150箱量下f1對(duì)比圖

圖8 150箱量下f2對(duì)比圖

圖9 同權(quán)重下f1對(duì)比圖

圖10 同權(quán)重下f2對(duì)比圖

由圖可知:①在相同擾動(dòng)權(quán)重下,隨著失約規(guī)模增加外集卡等待時(shí)間逐漸減少,完工時(shí)間相差較小,這是因?yàn)橥饧ù罅渴Ъs后增加了可行解的數(shù)量,更有利于找到更優(yōu)解;②在相同箱量、相同失約規(guī)模下,外集卡等待時(shí)間隨γ2的增大而減少,完工時(shí)間相應(yīng)增加,這是因?yàn)榭尚薪庵衅蛲饧ǖ却龝r(shí)間更少的解增多造成的;③在相同γ2下,隨著總箱量增加外集卡等待時(shí)間相應(yīng)增加,這是由于在預(yù)約時(shí)段一定的情況下,集卡失約導(dǎo)致過(guò)多集卡集中到達(dá),可行解數(shù)量減少造成的.

5 結(jié)論

結(jié)合預(yù)約信息和實(shí)際箱區(qū)中需作業(yè)的裝船箱、卸船箱對(duì)雙場(chǎng)橋調(diào)度影響的影響,對(duì)集卡失約下多箱區(qū)箱位分配及雙場(chǎng)橋調(diào)度優(yōu)化進(jìn)行研究,具體結(jié)論如下.

(1) 碼頭通過(guò)預(yù)約機(jī)制能緩解碼頭擁堵,但當(dāng)實(shí)際送箱集卡出現(xiàn)大規(guī)模失約時(shí),預(yù)優(yōu)化方案若不及時(shí)更新將增加集港完工時(shí)間和外集卡等待時(shí)間.

(2) 集港箱的交箱次序?qū)λ拖浼ǖ牡却龝r(shí)間有較大影響,送箱集卡等待時(shí)間和完工時(shí)間隨偏離程度增大而增加.

(3) 在預(yù)約時(shí)段不變的情形下,失約規(guī)模越大對(duì)外集卡等待時(shí)間影響越大,但提出的干擾恢復(fù)策略可同時(shí)兼顧集港完工時(shí)間、外集卡等待時(shí)間.

(4) 堆場(chǎng)增加集卡等待時(shí)間擾動(dòng)的權(quán)重,可在完工時(shí)間增加不大的情形下,進(jìn)一步縮短外集卡等待時(shí)間,提升服務(wù)質(zhì)量.

(5) 本文設(shè)計(jì)的算法求解能力強(qiáng)、求解速度快、求解結(jié)果優(yōu).

(6) 結(jié)合集卡實(shí)際到達(dá)時(shí)間和預(yù)約時(shí)間,在多個(gè)集港箱區(qū)內(nèi)動(dòng)態(tài)調(diào)整集港箱堆存計(jì)劃,可有效減少送箱集卡等待時(shí)間、完工時(shí)間,提高集港效率.

后續(xù)研究重點(diǎn)為集港箱與裝船箱、卸船箱比例關(guān)系對(duì)接力貝位位置的影響,通過(guò)動(dòng)態(tài)調(diào)整接力貝位的位置,提高集港效率.