集裝箱碼頭失約集卡出口箱落箱位選擇優(yōu)化

尹延冬，靳志宏

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

近年來(lái)，隨著中國(guó)進(jìn)出口貿(mào)易額持續(xù)增長(zhǎng)，2020年集裝箱吞吐量高達(dá)2.64億標(biāo)準(zhǔn)箱，比2019年增長(zhǎng)了1.2%。隨著集裝箱吞吐量的增長(zhǎng)以及船舶大型化的發(fā)展，集裝箱港口之間的競(jìng)爭(zhēng)日趨激烈，在堆場(chǎng)空間資源有限的港口，只有擴(kuò)建碼頭堆場(chǎng)空間或提高碼頭管理水平和作業(yè)效率才能提高港口的核心競(jìng)爭(zhēng)力。然而在空間資源已經(jīng)充分利用的碼頭堆場(chǎng)，擴(kuò)建堆場(chǎng)并不現(xiàn)實(shí)。所以只有在現(xiàn)有空間資源的基礎(chǔ)上，優(yōu)化堆存方案，提高堆場(chǎng)作業(yè)效率，才能提高港口的核心競(jìng)爭(zhēng)力。在集裝箱港口中，經(jīng)常出現(xiàn)集卡在某一時(shí)間段內(nèi)集中到達(dá)的情況，并因此會(huì)造成碼頭擁擠排隊(duì)、等待集卡尾氣排放增加、人和機(jī)械設(shè)備超負(fù)荷工作等現(xiàn)象。為解決這一問(wèn)題，港口通常采取集港高峰期收費(fèi)、規(guī)定集卡到達(dá)時(shí)間段等方法。集卡預(yù)約系統(tǒng)是各國(guó)為解決這一問(wèn)題而普遍采取的一種方法，通過(guò)預(yù)約系統(tǒng)碼頭可以提前做作業(yè)準(zhǔn)備計(jì)劃，合理分配堆場(chǎng)資源。集卡可以選擇合適的時(shí)間送箱，避免出現(xiàn)某一時(shí)段集卡集中到達(dá)造成碼頭擁堵的現(xiàn)象，因此集卡預(yù)約系統(tǒng)可以提高碼頭的運(yùn)營(yíng)效率。但在實(shí)際集港過(guò)程中，因?yàn)橐恍┎淮_定性因素預(yù)約系統(tǒng)有時(shí)并不能有效發(fā)揮其作用。如預(yù)約集卡在集港過(guò)程中會(huì)因?yàn)榻煌?、天氣或者人為等原因失約，不能在預(yù)約時(shí)段內(nèi)準(zhǔn)時(shí)到達(dá)。如果不對(duì)失約集卡進(jìn)行處理，集卡預(yù)約系統(tǒng)將形同虛設(shè)。因此應(yīng)及時(shí)對(duì)失約事件進(jìn)行處理，減小失約事件對(duì)碼頭的影響。

現(xiàn)階段集裝箱碼頭出口箱堆存優(yōu)化問(wèn)題的研究按照作業(yè)階段分類(lèi)可以分為集港前的堆存優(yōu)化和集港后的碼頭的裝船作業(yè)效率優(yōu)化兩方面。其中集港前的堆存優(yōu)化問(wèn)題主要以?xún)?yōu)化堆存時(shí)出口箱落箱位的選擇為主，碼頭的裝船作業(yè)效率優(yōu)化方面主要以減少裝船作業(yè)時(shí)的預(yù)翻箱數(shù)為主。

在出口箱落箱位選擇優(yōu)化方面，Kim等[1]考慮了箱重因素，以最小化翻箱數(shù)為目標(biāo)建立了實(shí)時(shí)決策最小生成樹(shù)模型，并用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解；Lin等[2]以最小化場(chǎng)橋移動(dòng)距離和作業(yè)時(shí)間為目標(biāo)，建立了雙目標(biāo)規(guī)劃模型，并設(shè)計(jì)了自適應(yīng)啟發(fā)式算法進(jìn)行求解。Luo等[3]針對(duì)出口箱的箱位分配問(wèn)題，考慮集卡作業(yè)與箱位分配的協(xié)調(diào)優(yōu)化問(wèn)題，以最小化船舶在港等待時(shí)間為優(yōu)化目標(biāo)建立了混合整數(shù)規(guī)劃模型，并基于模型特點(diǎn)設(shè)計(jì)了遺傳算法進(jìn)行求解。Gharehgozli等[4]考慮船舶離港時(shí)間的不確定性，建立了以最小化翻箱數(shù)為目標(biāo)的數(shù)學(xué)模型，并設(shè)計(jì)了模擬退火算法進(jìn)行求解。Chang等[5]以平衡街區(qū)間作業(yè)量和翻箱數(shù)為優(yōu)化目標(biāo)，建立了兩階段調(diào)度模型，并設(shè)計(jì)了算法進(jìn)行求解。Shen等[6]為了實(shí)現(xiàn)堆場(chǎng)的實(shí)時(shí)調(diào)度性，將機(jī)器學(xué)習(xí)方法應(yīng)用到了某一個(gè)特定貝位內(nèi)的出口箱堆存問(wèn)題中，并在可接受時(shí)間范圍內(nèi)得到了優(yōu)化方案。

李隋凱等[7]針對(duì)自動(dòng)化碼頭中出口箱進(jìn)場(chǎng)堆存作業(yè)問(wèn)題，使用動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)了一種多階段動(dòng)態(tài)規(guī)劃算法。實(shí)驗(yàn)結(jié)果表明，該算法可使翻箱數(shù)在原基礎(chǔ)上降低20%。黃子釗等[8]針對(duì)自動(dòng)化碼頭中出口箱的箱位分配問(wèn)題，以最小化街區(qū)不均衡程度和翻箱數(shù)為目標(biāo)建立了多目標(biāo)混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了基于強(qiáng)化學(xué)習(xí)的超啟發(fā)式算法進(jìn)行求解。周鵬飛等[9]提出了一種出口箱交箱次序與箱位分配的三維圖表示法，并在此基礎(chǔ)上構(gòu)建了基于圖的以最小化場(chǎng)橋作業(yè)成本和翻箱數(shù)為目標(biāo)的優(yōu)化模型，并設(shè)計(jì)了改進(jìn)禁忌搜索算法；周鵬飛等[10]在進(jìn)出口箱混合堆存下，以最小化壓箱量和龍門(mén)吊移動(dòng)距離及箱位偏移量為優(yōu)化目標(biāo)，建立了干擾恢復(fù)模型，并設(shè)計(jì)了局部加速的改進(jìn)禁忌搜索算法。邵乾虔等[11]通過(guò)馬爾可夫預(yù)測(cè)方法將不確定交箱次序轉(zhuǎn)為一定概率保證下的確定交箱次序，建立了兩階段優(yōu)化模型，并設(shè)計(jì)了靜態(tài)和動(dòng)態(tài)求解算法，通過(guò)仿真實(shí)驗(yàn)證明了模型和算法的有效性。范厚明等[12]在集卡預(yù)約機(jī)制下，為緩解高峰時(shí)段下集卡不規(guī)律到達(dá)所導(dǎo)致的擁堵問(wèn)題，以降低碼頭堆場(chǎng)運(yùn)營(yíng)成本為原則，建立了以最小化調(diào)用集卡數(shù)量為目標(biāo)的優(yōu)化模型。馬夢(mèng)知等[13]針對(duì)送箱集卡隨機(jī)到港引起的場(chǎng)橋作業(yè)不均衡問(wèn)題，建立了以最小化總時(shí)間成本為目標(biāo)的雙層規(guī)劃模型，并設(shè)計(jì)了遺傳算法求解。邵乾虔等[14]構(gòu)建了以時(shí)間殘值矩陣為核心的線性仿真數(shù)學(xué)模型，并基于該模型提出了碼頭集疏港聯(lián)動(dòng)預(yù)約模式。

在提高碼頭的裝船作業(yè)效率方面，Maldonado等[15]為了減少預(yù)翻箱數(shù)，以最小化船舶在港等待時(shí)間為優(yōu)化目標(biāo)建立了箱位分配模型，并設(shè)計(jì)了算法進(jìn)行求解。Zheng等[16]研究了在進(jìn)出口箱混合堆存的堆場(chǎng)中，街區(qū)內(nèi)只有一臺(tái)場(chǎng)橋時(shí)的作業(yè)問(wèn)題。以場(chǎng)橋作業(yè)總延遲時(shí)間最小化為目標(biāo)函數(shù)，建立了兩階段規(guī)劃模型，并設(shè)計(jì)了基于一定規(guī)則的啟發(fā)式算法進(jìn)行求解。Zheng等[17]研究了在進(jìn)出口箱混合堆存的堆場(chǎng)中，同一街區(qū)內(nèi)有兩臺(tái)場(chǎng)橋同時(shí)作業(yè)的問(wèn)題。在兩臺(tái)場(chǎng)橋作業(yè)時(shí)會(huì)發(fā)生干擾的前提下，建立了以場(chǎng)橋作業(yè)總延遲時(shí)間最小化為目標(biāo)的數(shù)學(xué)模型，并設(shè)計(jì)了啟發(fā)式算法進(jìn)行求解。Galls等[18]以最小化堆場(chǎng)作業(yè)時(shí)間和提箱作業(yè)時(shí)間為目標(biāo)，建立了混合整數(shù)規(guī)劃模型，并提出了基于鄰域搜索的啟發(fā)式算法進(jìn)行求解，在堆場(chǎng)作業(yè)和裝船作業(yè)兩個(gè)方面同時(shí)完成了優(yōu)化和改進(jìn)。Msakni等[19]以單個(gè)出口箱為作業(yè)單位，建立了碼頭岸橋作業(yè)調(diào)度優(yōu)化模型，并設(shè)計(jì)了基于圖搜索和割平面法的算法，并求得了問(wèn)題的精確解。

鄭紅星等[20]在保持場(chǎng)橋間安全距離的強(qiáng)約束條件下，建立了以場(chǎng)橋行駛時(shí)間最小為優(yōu)化目標(biāo)的線性規(guī)劃模型，并設(shè)計(jì)了分支定價(jià)法進(jìn)行求解?？嘴n[21]建立了平衡預(yù)翻箱和翻箱量的出口箱堆場(chǎng)多資源協(xié)同優(yōu)化雙層規(guī)劃模型，上層模型以最小化裝船時(shí)間為目標(biāo)，建立了出口箱落箱位分配模型。下層模型根據(jù)上層模型生成的堆存方案生成預(yù)翻箱方案。鄭紅星等[22]以最小化內(nèi)集卡等待時(shí)間為目標(biāo)，建立了帶有懲罰因子的混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了混合和聲模擬退火算法，實(shí)現(xiàn)了實(shí)時(shí)預(yù)翻箱。

在現(xiàn)有的研究成果中，對(duì)上述中外文獻(xiàn)綜述梳理可以看出，針對(duì)出口箱堆場(chǎng)作業(yè)優(yōu)化問(wèn)題的研究主要集中于以下兩個(gè)方面，分別是堆存階段的箱位選擇問(wèn)題和裝船階段的提箱優(yōu)化問(wèn)題。對(duì)問(wèn)題的切入點(diǎn)大致可以分為降低翻箱率、最小化場(chǎng)橋或者集卡移動(dòng)距離、平衡街區(qū)設(shè)備之間的作業(yè)量等，存在的主要問(wèn)題有多數(shù)研究直接將集裝箱的到達(dá)信息作為確定的已知條件，或者根據(jù)預(yù)約信息來(lái)近似確定集裝箱的到達(dá)順序。然而實(shí)際作業(yè)中集裝箱的到達(dá)順序難以確定，存在著一定的不確定性，所以這些研究無(wú)法有效解決實(shí)際作業(yè)中出口箱的遲到、早到帶來(lái)的擾動(dòng)。針對(duì)集卡到達(dá)的不確定性，一些學(xué)者通過(guò)先建立確定性模型，再使用滾動(dòng)調(diào)度的方法進(jìn)行處理。如徐偉宣等[23]在滾動(dòng)調(diào)度的基礎(chǔ)上，研究了進(jìn)出口箱混合堆存下箱位分配問(wèn)題。但是由于滾動(dòng)調(diào)度方法本身的周期性，使其在調(diào)度周期內(nèi)的調(diào)度方案性能較差，從而影響調(diào)度效果。

因此現(xiàn)針對(duì)集卡到達(dá)存在一定不確定性的特點(diǎn)，以失約發(fā)生后對(duì)失約箱的響應(yīng)與處理為切入點(diǎn)，建立以最小化翻箱數(shù)和場(chǎng)橋移動(dòng)距離為優(yōu)化目標(biāo)的模型，并設(shè)計(jì)基于鄰域搜索的實(shí)時(shí)調(diào)度啟發(fā)式算法進(jìn)行求解。力求幫助港口方在出現(xiàn)失約事件時(shí)，能夠?qū)κЪs箱做出實(shí)時(shí)調(diào)度，降低失約事件對(duì)碼頭作業(yè)的影響。

1 問(wèn)題描述

為了提高港口的運(yùn)營(yíng)效率，港口通常采用集卡預(yù)約系統(tǒng)。預(yù)約系統(tǒng)下的出口箱集港的過(guò)程可以大致分為客戶(hù)向港口申請(qǐng)預(yù)約交箱、港口方編制出口箱堆存方案以及出口箱入港堆存3個(gè)階段。通過(guò)集卡預(yù)約信息可以獲得集裝箱的數(shù)量、箱型、尺寸、掛靠港口以及預(yù)約交箱次序等信息，港口根據(jù)這些信息編制初始堆存計(jì)劃。實(shí)際交箱時(shí)，港口根據(jù)初始堆存計(jì)劃，將出口箱放置到指定位置，并由場(chǎng)橋完成后續(xù)作業(yè)。

集裝箱某街區(qū)內(nèi)的初始堆存計(jì)劃示意圖如圖1所示。根據(jù)預(yù)約信息，如果集卡能夠準(zhǔn)時(shí)交箱，那么該棧位內(nèi)的堆存示意圖如圖1棧5中所示，括號(hào)外數(shù)字代表集裝箱的交箱次序，括號(hào)內(nèi)的數(shù)字代表集裝箱的翻箱權(quán)重。翻箱權(quán)重由預(yù)約信息中的集裝箱的重量和目的港確定，即由Fi=Zgi+zi確定。其中Fi為第i個(gè)出口箱的翻箱權(quán)重，gi為第i個(gè)出口箱的目的港，zi為第i個(gè)出口箱的質(zhì)量。翻箱權(quán)重越大越早裝船。此時(shí)該方案為最優(yōu)方案，翻箱數(shù)為0，場(chǎng)橋沒(méi)有額外的移動(dòng)距離。如果集港過(guò)程中某個(gè)集裝箱的交箱時(shí)間早于或者晚于其他的集裝箱，如圖1棧2中所示，則會(huì)造成翻箱。同時(shí)，場(chǎng)橋移動(dòng)距離和集裝箱的交箱次序是緊密相關(guān)的，隨著交箱次序的變動(dòng)，場(chǎng)橋可能產(chǎn)生額外的移動(dòng)距離。

當(dāng)失約事件發(fā)生時(shí)，如圖2所示為箱4遲到，如果不對(duì)失約箱進(jìn)行處理，直接將其放置在預(yù)約信息中對(duì)應(yīng)位置，將會(huì)增加額外的場(chǎng)橋移動(dòng)距離和翻箱數(shù)。而通過(guò)本文算法可以將其放置在合理的位置，如圖3所示，從而減少失約事件對(duì)碼頭整體作業(yè)的影響。

圖1 街區(qū)內(nèi)堆存計(jì)劃示意圖Fig.1 Sketch map of the stacking plan in a block

圖2 失約發(fā)生前堆存狀態(tài)Fig.2 Stacking status before no-showing event occur

圖3 對(duì)失約箱進(jìn)行箱位再分配Fig.3 Slot relocation of the no-showing container

2 模型構(gòu)建

2.1 前提假設(shè)

(1)出口箱均為20 in(1 in=30.48 cm)標(biāo)準(zhǔn)集裝箱。

(2)待分配街區(qū)為指定某一個(gè)街區(qū)。

(3)根據(jù)集卡預(yù)約信息，集裝箱的預(yù)約交箱時(shí)間、重量、目的港等信息已知，初始堆存方案根據(jù)預(yù)約信息已知。

(4)按照裝船時(shí)長(zhǎng)途箱和重箱優(yōu)先裝船的原則，以短途箱壓長(zhǎng)途箱、輕箱壓重箱的方法計(jì)算翻箱權(quán)重。

(5)實(shí)際交箱時(shí)間與預(yù)約交箱的時(shí)間差值近似服從正態(tài)分布N(tk,σ),tk為出口箱k的預(yù)約交箱時(shí)間，不同取值的σ用來(lái)模擬生成不同失約等級(jí)的集卡實(shí)際到達(dá)信息。

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

I={i|i=1,2,…,|I=E1+E2|}：出口集裝箱的集合。

B={b|b=1,2,…,|B|}：街區(qū)內(nèi)貝位的集合。

L={l|l=0,1,…,|L|}：貝位中棧的集合。

H={h|h=0,1,…,|H|}：棧內(nèi)層數(shù)的集合。

Vb：貝位b的額定存放箱量。

α：調(diào)整系數(shù)。

β：調(diào)整系數(shù)。

E1：失約事件發(fā)生時(shí)，已進(jìn)場(chǎng)的出口箱數(shù)。

E2：失約事件發(fā)生時(shí)，待進(jìn)場(chǎng)的出口箱數(shù)。

Fi：第i個(gè)出口箱的翻箱權(quán)重。

gi：第i個(gè)出口箱的目的港編號(hào)。

A：一個(gè)充分大的正數(shù)。

Zi：第i個(gè)出口箱的質(zhì)量，Z為最大質(zhì)量等級(jí)。

Fi=Zgi+zi：翻箱權(quán)重計(jì)算公式。

yi：第i個(gè)出口箱所在的貝位。

Gb：失約事件發(fā)生時(shí)，貝位b中已堆存的出口箱量。

2.3 混合整數(shù)規(guī)劃模型構(gòu)建

式(1)為最小化場(chǎng)橋移動(dòng)距離和翻箱量。

(1)

(2)

約束條件：

(3)

(4)

l=1,2,…,L

(5)

3,…,H(6)

(7)

ARbl(h-t)≥0

(8)

…,E1+E2

(9)

(10)

ωi≥0，ξi≥0，ψ≥0，ζ≥0，i=1,2,…,

E1+E2

(11)

2.4 模型驗(yàn)證

以鹽田集裝箱碼頭數(shù)據(jù)為基礎(chǔ)，初始堆存方案利用集卡預(yù)約信息得出，不同失約等級(jí)的集卡到達(dá)信息由正態(tài)分布N(tk,σ)模擬生成，根據(jù)碼頭實(shí)際操作經(jīng)驗(yàn)，α取0.4，β取0.6。算法的開(kāi)發(fā)平臺(tái)為MATLAB2019a，運(yùn)行環(huán)境為CPU-AMD3900X 3.8 GHz，64 G。每組數(shù)據(jù)均為10次實(shí)驗(yàn)求得結(jié)果的平均值。

本模型可用CPLEX求解，分別取區(qū)段規(guī)模為1個(gè)貝位×3個(gè)?！?層，2個(gè)貝位×3個(gè)棧×3層，1個(gè)貝位×5個(gè)?！?層，2個(gè)貝位×4個(gè)?！?層，3個(gè)貝位×4個(gè)?！?層，25個(gè)貝位×6個(gè)?！?層，6個(gè)不同規(guī)模進(jìn)行對(duì)比。對(duì)比結(jié)果如表1所示。

針對(duì)小規(guī)模問(wèn)題，CPLEX能夠取得模型的最優(yōu)解，證明了本文模型的有效性。但隨著規(guī)模的增大，算法時(shí)間消耗程指數(shù)式增長(zhǎng)。在CPLEX求解箱量規(guī)模為3×4×3時(shí)，算法耗時(shí)為6.2 h，不符合實(shí)際操作要求。本文算法與最優(yōu)解比較接近，時(shí)間消耗也比CPLEX解決大規(guī)模問(wèn)題要小，同時(shí)也能解決大規(guī)模問(wèn)題，能夠滿(mǎn)足實(shí)際要求。

3 算法設(shè)計(jì)與數(shù)值實(shí)驗(yàn)

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

針對(duì)現(xiàn)實(shí)規(guī)模問(wèn)題，現(xiàn)有商業(yè)軟件無(wú)法在有限時(shí)間內(nèi)求得最優(yōu)解。為此，提出了基于鄰域搜索的啟發(fā)式算法。預(yù)約信息已知，初始堆存方案根據(jù)預(yù)約信息得出，并將初始堆存方案作為啟發(fā)式算法的初始解。每一個(gè)出口箱到達(dá)，就對(duì)其進(jìn)行判斷，如果其到達(dá)次序與預(yù)約信息相符，即按照初始堆存方案進(jìn)行；如果不相符，即發(fā)生失約，則對(duì)失約箱進(jìn)行箱位再分配。

集港過(guò)程中，假設(shè)共有i個(gè)出口箱預(yù)約交箱，每個(gè)出口箱交箱時(shí)刻視作一個(gè)決策節(jié)點(diǎn)，共做出i次決策。設(shè)S為預(yù)約交箱次序，Si為第i個(gè)到達(dá)的出口箱，P為出口箱實(shí)際到達(dá)次序，Pi為第i個(gè)實(shí)際到達(dá)的出口箱，Mi為第i個(gè)出口箱到達(dá)時(shí)當(dāng)前堆場(chǎng)的狀態(tài)，Ni為第i個(gè)出口箱到達(dá)前堆場(chǎng)的堆存方案。

表1 本文算法與CPLEX結(jié)果對(duì)比Table 1 Comparisons between this article’s algorithm and CPLEX

每當(dāng)一個(gè)出口箱到達(dá)時(shí)，將P與S做一次對(duì)比，如果一致，則按當(dāng)前堆存方案執(zhí)行；如果不一致，即Pi≠Si且P(1,2,…,i-1)=S(1,2,…,i-1),則對(duì)該失約箱進(jìn)行箱位再分配。箱位再分配時(shí)首先對(duì)失約箱產(chǎn)生其再分配集合Qi，Qi中包括失約箱與預(yù)約信息中失約箱所在貝位內(nèi)尚未堆存集裝箱的箱位交換集合以及失約箱與其他貝位中空箱位的交換集合。模型目標(biāo)函數(shù)作為評(píng)估函數(shù)對(duì)Qi中的解進(jìn)行評(píng)估，選擇目標(biāo)函數(shù)值最小的解為最優(yōu)解，其對(duì)應(yīng)的箱位為當(dāng)前失約箱i的分配箱位。在狀態(tài)Mi的基礎(chǔ)上堆存失約出口箱i后生成Mi+1，并更新堆存方案為Ni+1。

基于鄰域搜索的啟發(fā)式算法的具體步驟如下。

步驟1通過(guò)預(yù)約信息生成的初始堆存方案作為初始解，i=0，Q0=φ，N0為初始堆存方案，M0為空堆場(chǎng)。

步驟2若i=I，則算法終止，輸出最終堆存方案。否則i=i+1。

步驟3判斷實(shí)際到達(dá)次序Pi和預(yù)約次序Si是否匹配，若匹配，則按照當(dāng)前堆存計(jì)劃Ni進(jìn)行；若不匹配，轉(zhuǎn)至步驟4。

步驟4根據(jù)當(dāng)前堆存狀態(tài)Mi及預(yù)約信息生成失約箱i的可分配區(qū)域Qi，模型目標(biāo)函數(shù)作為評(píng)估函數(shù)對(duì)Qi中的解進(jìn)行評(píng)估，選擇目標(biāo)函數(shù)值最小的解為最優(yōu)解，若箱位不唯一則等概率選擇其中一個(gè)，其對(duì)應(yīng)的箱位為當(dāng)前失約箱的分配箱位。

步驟5確定失約箱i的最優(yōu)堆存箱位，更新堆存狀態(tài)Mi+1和堆存方案Ni+1。轉(zhuǎn)至步驟2。

設(shè)m、n均為出口箱編號(hào)，則設(shè)計(jì)該啟發(fā)式算法中需要滿(mǎn)足以下5個(gè)原則。

(1)針對(duì)失約箱i，將失約出口箱i及其在預(yù)約信息中所在貝位bi中未進(jìn)場(chǎng)的出口箱加入到集合C，則箱位交換對(duì)為(m,n)。

(2)l為失約箱i在街區(qū)中可分配的含有空箱位的棧位，bi為出口箱i所在的貝位，l∈Vi=[max(0,bi-1),min(bi+1,B)]，使空棧位的選擇在合理的范圍內(nèi)。

(3)搜索鄰域集合包括箱位交換以及箱位和空箱位的交換，即Qi=(m,n)+(m,l)。

(4)可交換箱對(duì)(m,n)滿(mǎn)足，|km-kn|+|Fm-Fn|≤15，km和kn分別為箱m、n的交箱次序，F(xiàn)m和Fn分別是箱m、n的翻箱權(quán)重，避免箱位交換過(guò)程中產(chǎn)生較大的作業(yè)成本。

(5)若Qi中包含(m1,n1)(m2,n2)，則m1≠m2≠n1≠n2，除去不滿(mǎn)足條件的不可行解。算法流程圖如圖4所示。

3.2 算法對(duì)比

3.2.1 策略1：按原計(jì)劃進(jìn)行

即雖然出現(xiàn)失約事件，仍然按照原堆存方案執(zhí)行。

3.2.2 策略2：傳統(tǒng)作業(yè)算法

即基于貪婪算法思想的啟發(fā)式算法。

步驟1通過(guò)預(yù)約信息生成的初始堆存方案作為初始解，i=0，Q0=φ，N0為初始堆存方案，M0為空堆場(chǎng)。

步驟2若i=I，則算法終止，輸出最終堆存方案。否則i=i+1。

步驟3判斷實(shí)際到達(dá)次序Pi和預(yù)約次序Si是否匹配，若匹配，則按照當(dāng)前堆存計(jì)劃Ni進(jìn)行；若不匹配，轉(zhuǎn)至步驟4。

步驟4判斷場(chǎng)橋當(dāng)前所在貝位內(nèi)是否有空箱位，若存在則將所有可交換對(duì)加入到Qi中，模型目標(biāo)函數(shù)作為評(píng)估函數(shù)對(duì)Qi中的解進(jìn)行評(píng)估，選擇目標(biāo)函數(shù)值最小的解為最優(yōu)解，若箱位不唯一則等概率選擇其中一個(gè)，其對(duì)應(yīng)的箱位為當(dāng)前失約箱的分配箱位。若場(chǎng)橋當(dāng)前所在貝位內(nèi)無(wú)空箱位，則依次選擇判斷相鄰貝位內(nèi)是否有空箱位，直到找到一個(gè)空箱位。

步驟5確定失約箱i的最優(yōu)堆存箱位，更新堆存狀態(tài)Mi+1和堆存方案Ni+1。轉(zhuǎn)至步驟2。

策略2相比于本文算法并沒(méi)有充分利用預(yù)約信息，不能從全局出發(fā)，而是基于貪婪算法思想，通過(guò)就近原則達(dá)到局部最優(yōu)。

3.3 大規(guī)模算例實(shí)驗(yàn)

如表2所示給出了在失約等級(jí)3下，本文算法與策略1、策略2的結(jié)果對(duì)比?？梢钥闯霰疚乃惴ê筒呗?均明顯優(yōu)于策略1。針對(duì)小規(guī)模問(wèn)題，本文算法和策略2差異不大。但隨著箱量規(guī)模的增大，當(dāng)箱量規(guī)模在5×6×6以上時(shí)，本文算法在翻箱數(shù)上開(kāi)始明顯優(yōu)于策略2，且規(guī)模越大優(yōu)勢(shì)越明顯。而場(chǎng)橋移動(dòng)距離劣于后者，是因?yàn)椴呗?總體遵循就近堆存原則。二者算法耗時(shí)均符合實(shí)際操作要求。

在箱量規(guī)模為18×6×6，失約等級(jí)為3下，本文算法迭代圖如圖5所示，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為模型目標(biāo)函數(shù)值。算法呈階梯狀收斂，算法消耗時(shí)間為12.3 s，在循環(huán)186次后達(dá)到收斂，說(shuō)明本文算法可以較短時(shí)間內(nèi)實(shí)現(xiàn)實(shí)時(shí)調(diào)度，并且收斂值相較于初始值有明顯改善。

3.3.1 情景1：同一失約等級(jí)時(shí)，對(duì)比不同箱量規(guī)模下兩種算法算例結(jié)果

如圖6所示為在失約等級(jí)3時(shí)，不同箱量下兩種算法模型目標(biāo)函數(shù)值對(duì)比圖。可以看出，小規(guī)模算例下兩者總成本差距不大，隨著算例規(guī)模的增大，本文算法開(kāi)始明顯優(yōu)于策略2。其原因在于小規(guī)模箱量下，無(wú)法充分發(fā)揮本文算法基于預(yù)約信息對(duì)失約事件的實(shí)時(shí)調(diào)度性。隨著箱量規(guī)模的增大，本文算法的全局最優(yōu)性相較于策略2的局部最優(yōu)性開(kāi)始凸顯優(yōu)勢(shì)，并且隨著箱量規(guī)模的增大，優(yōu)勢(shì)會(huì)越來(lái)越大。

圖4 基于鄰域搜索的啟發(fā)式算法流程圖Fig.4 Flow chart of heuristic algorithm based on neighborhood search

表2 本文算法與兩種傳統(tǒng)策略結(jié)果對(duì)比Table 2 Comparisons between proposed algorithm and two traditional strategy

3.3.2 情景2：同一失約等級(jí)時(shí)，對(duì)比不同箱量規(guī)模下兩種算法場(chǎng)橋移動(dòng)距離和翻箱數(shù)

如圖7所示為在失約等級(jí)3時(shí)，不同箱量規(guī)模下兩種算法場(chǎng)橋移動(dòng)距離和翻箱數(shù)對(duì)比圖。當(dāng)箱量規(guī)模較小時(shí)，本文算法和策略2在場(chǎng)橋移動(dòng)距離和翻箱數(shù)上的差距很小。隨著箱量規(guī)模的增大，兩種算法在場(chǎng)橋移動(dòng)距離和翻箱數(shù)上都有所增加，本文算法在場(chǎng)橋移動(dòng)距離上增加較快，策略2在翻箱數(shù)上增加較快。基于就近堆存原則的策略2在場(chǎng)橋移動(dòng)距離上一直優(yōu)于本文算法，但在翻箱數(shù)上一直遜于本文算法，鑒于實(shí)際作業(yè)中翻箱作業(yè)成本高于場(chǎng)橋移動(dòng)成本，實(shí)驗(yàn)結(jié)果可以接受。

圖5 啟發(fā)式算法收斂圖Fig.5 Convergence graph of heuristic algorithm

3.3.3 情景3：同一箱量規(guī)模時(shí)，對(duì)比不同失約等級(jí)下兩種算法場(chǎng)橋移動(dòng)距離和翻箱數(shù)

如圖8所示，在箱量為18×6×6的箱量規(guī)模下，隨著失約等級(jí)的增大，失約到達(dá)的出口箱越來(lái)越多，策略2不能針對(duì)失約出口箱進(jìn)行有效處理，所以與本文算法在翻箱數(shù)上的差距越來(lái)越明顯。在失約等級(jí)6時(shí)，本文算法相較于策略2在翻箱數(shù)上有33.3%的優(yōu)化率，具有較高的實(shí)用性。由于策略2遵循就近堆存原則，所以場(chǎng)橋移動(dòng)距離在各個(gè)失約等級(jí)上一直優(yōu)于本文算法，但是在有效降低翻箱數(shù)的前提下，總目標(biāo)函數(shù)值本文算法結(jié)果一直優(yōu)于策略2，即實(shí)驗(yàn)結(jié)果可以接受。

3.3.4 情景4：同一箱量規(guī)模時(shí)，對(duì)比不同失約等級(jí)下兩種算法算例結(jié)果

如圖9所示為取算例為18×6×6的箱量規(guī)模，不同失約等級(jí)下，兩種算法目標(biāo)函數(shù)值對(duì)比。可以看出隨著規(guī)模的增大，本文算法相對(duì)于策略2的改進(jìn)效果越來(lái)越明顯，在失約等級(jí)1時(shí)，本文算法相對(duì)于策略2僅有7.5%的改進(jìn)率。而在失約等級(jí)6時(shí)，有20.91%的改進(jìn)率。這是因?yàn)楫?dāng)σ較小時(shí)，出口箱的實(shí)際到達(dá)序列和預(yù)約信息差異較小，所以本文算法優(yōu)勢(shì)不明顯。隨著σ的增大，實(shí)際交箱時(shí)間和預(yù)約交箱時(shí)間有較大差異時(shí)，本文算法能夠?qū)κЪs出口箱合理分配其落箱位，降低翻箱數(shù)和場(chǎng)橋移動(dòng)距離，從而降低失約事件對(duì)碼頭作業(yè)系統(tǒng)整體的擾動(dòng)。

圖8 同一箱量規(guī)模、不同失約等級(jí)下，兩種算法場(chǎng)橋移動(dòng)距離和翻箱數(shù)對(duì)比Fig.8 Contrast graph of the number of reshuffles and gantry-crane traveling distance for two algorithm under the same container scale and different no-showing level

圖9 同一箱量規(guī)模、不同失約等級(jí)下，兩種算法算例結(jié)果對(duì)比Fig.9 Contrast graph for two algorithm under the same container scale and different no-showing level

3.3.5 情景5：不同情形下，本文算法相較于傳統(tǒng)算法策略2算例實(shí)驗(yàn)結(jié)果改進(jìn)分布圖

本文算法和傳統(tǒng)算法策略2的算例實(shí)驗(yàn)結(jié)果的改進(jìn)分布圖如圖10～圖12所示。在失約等級(jí)3，箱量規(guī)模為18×6×6時(shí)，本文算法得到的所有算例結(jié)果中，較優(yōu)解占比為90%，最大改進(jìn)程度為36.62%，平均改進(jìn)程度為17.22%。而在箱量規(guī)模為5×6×6時(shí)，最大改進(jìn)程度和平均改進(jìn)程度分別是47.21%和14.68%，較優(yōu)解所占比重為86%。數(shù)據(jù)顯示，相同失約等級(jí)下，隨著箱量規(guī)模的增大，算法的改進(jìn)效果越明顯，較優(yōu)算例所占比重也越大。在箱量規(guī)模為18×6×6下，在失約等級(jí)6時(shí)，較優(yōu)解所占比重為97%，最大改進(jìn)程度和平均改進(jìn)程度分別為44.45%和21.21%。綜上可知，隨著失約等級(jí)和箱量規(guī)模的增加，本文算法相較于傳統(tǒng)算法策略2的改進(jìn)程度越來(lái)越大。

圖10 箱量規(guī)模為5×6×6、失約等級(jí)為3時(shí)，算法相對(duì)改進(jìn)程度分布圖Fig.10 Relative improvement ratio graph of two algorithm when container scale is 5×6×6 and no-showing level is 3

圖11 箱量規(guī)模為18×6×6、失約等級(jí)為3時(shí)，算法相對(duì)改進(jìn)程度分布圖Fig.11 Relative improvement ratio graph of two algorithm when container scale is 18×6×6 and no-showing level is 3

圖12 箱量規(guī)模為18×6×6、失約等級(jí)為6時(shí)，算法相對(duì)改進(jìn)程度分布圖Fig.12 Relative improvement ratio graph of two algorithm when container scale is 18×6×6 and no-showing level is 6

4 結(jié)論與展望

集卡預(yù)約系統(tǒng)可以有效緩解碼頭擁堵問(wèn)題，提高碼頭作業(yè)效率。但集卡常常因?yàn)楦鞣N現(xiàn)實(shí)原因不能準(zhǔn)時(shí)到達(dá)而導(dǎo)致失約事件的發(fā)生。對(duì)于港口方而言，雖然集卡預(yù)約系統(tǒng)可以大幅降低碼頭擁堵出現(xiàn)的情況，但是在失約事件發(fā)生時(shí)，針對(duì)失約出口箱一定要設(shè)計(jì)出可以實(shí)時(shí)選擇失約出口箱落箱位的調(diào)度機(jī)制。這樣才能完成對(duì)失約事件的快速響應(yīng)處理，降低失約事件的發(fā)生對(duì)整個(gè)碼頭系統(tǒng)的擾動(dòng)，進(jìn)而提高碼頭的作業(yè)效率。

通過(guò)對(duì)失約出口箱的落箱位再分配，研究了不同箱量規(guī)模、不同失約等級(jí)下的集卡到達(dá)對(duì)碼頭作業(yè)的影響。建立了以最小化場(chǎng)橋移動(dòng)距離和翻箱數(shù)為目標(biāo)的數(shù)學(xué)模型，設(shè)計(jì)了基于鄰域搜索的啟發(fā)式算法，并通過(guò)設(shè)計(jì)規(guī)則優(yōu)化了算法的搜索方向和空間，使其計(jì)算時(shí)間在可接受范圍內(nèi)并能得出滿(mǎn)意解。算例實(shí)驗(yàn)中展示了不同箱量規(guī)模、不同失約等級(jí)下，場(chǎng)橋移動(dòng)距離和翻箱數(shù)以及模型目標(biāo)函數(shù)值的對(duì)比，并得出了以下結(jié)論。

(1)集裝箱的交箱次序?qū)謪^(qū)內(nèi)的場(chǎng)橋移動(dòng)距離和翻箱數(shù)的影響較大，在集卡預(yù)約系統(tǒng)下，隨著失約等級(jí)的升高，算例實(shí)驗(yàn)表明相較于準(zhǔn)時(shí)到達(dá)或者低失約等級(jí)下，高失約等級(jí)下的翻箱數(shù)和場(chǎng)橋移動(dòng)距離都有較大的升高幅度。在箱量規(guī)模為18×6×6下，失約等級(jí)6相較于失約等級(jí)1在場(chǎng)橋移動(dòng)距離和翻箱數(shù)上分別有213%和440%的提高，說(shuō)明了集裝箱的交箱次序?qū)Τ隹谙涞亩汛嬗酗@著影響。

(2)實(shí)驗(yàn)結(jié)果表明本文算法相較于傳統(tǒng)算法有較大改進(jìn)，且改進(jìn)程度隨著箱量規(guī)模、失約等級(jí)的提高而提高，在算例為18×6×6箱量規(guī)模時(shí)，不同失約等級(jí)下，模型目標(biāo)函數(shù)值平均有15.70%的改進(jìn)率，最大有20.91%的改進(jìn)率。在失約等級(jí)3時(shí)，不同規(guī)模箱量下平均有11.12%的改進(jìn)率，最大有19.2%的改進(jìn)率。在不同情形下，本文算法相較于傳統(tǒng)算法策略2算例實(shí)驗(yàn)結(jié)果改進(jìn)分布圖也驗(yàn)證了本文模型及算法的有效性，為進(jìn)一步的研究打下了基礎(chǔ)。

后續(xù)研究擬從以下3個(gè)方面展開(kāi)。一是考慮進(jìn)口箱或者進(jìn)出口箱混合堆存下箱位分配問(wèn)題；二是嘗試結(jié)合裝船信息，將岸橋及內(nèi)集卡等其他資源聯(lián)系起來(lái)協(xié)同優(yōu)化；三是嘗試結(jié)合預(yù)約信息與歷史實(shí)際到達(dá)信息，得到一定概率統(tǒng)計(jì)下的模擬到達(dá)信息，進(jìn)而提高算例的真實(shí)性。