鄭紅星，劉保利，匡海波，閆 敘

(大連海事大學(xué)交通運(yùn)輸管理學(xué)院，遼寧 大連 116026)

1 引言

由于我國大多數(shù)集裝箱港口是進(jìn)口箱和出口箱分開堆放的，在現(xiàn)有岸邊作業(yè)系統(tǒng)和水平運(yùn)輸系統(tǒng)一定的情況下，出口箱堆場的作業(yè)效率直接影響著整個(gè)碼頭的服務(wù)水平，研究該類堆場的效率提升策略是當(dāng)前集裝箱港口研究的熱點(diǎn)。作為堆場中重要的作業(yè)設(shè)備—場橋，對其如何科學(xué)有效地安排調(diào)度來提高裝船效率，是出口箱堆場亟需解決的問題。

目前，針對出口箱堆場場橋調(diào)度問題，國內(nèi)外有很多學(xué)者進(jìn)行了深入的研究。鑒于倒箱因素直接影響場橋作業(yè)的時(shí)長，本文將已有文獻(xiàn)按處理該因素的方法不同，分為以下三類：A類——不考慮倒箱影響，只考慮場橋在作業(yè)過程中抓取待提箱的時(shí)長；B類——固定倒箱次序，在作業(yè)過程中場橋抓取某個(gè)待提箱的時(shí)長等于單獨(dú)提該箱的時(shí)間加上其倒箱時(shí)間，倒箱時(shí)間或直接給出，或按單箱翻倒時(shí)間與壓箱數(shù)乘積計(jì)算；C類——提前控制倒箱，在船舶裝船作業(yè)開始之前或按配載圖提前倒箱，或通過箱位優(yōu)化確定最少倒箱數(shù)的堆存方案。

在A類文獻(xiàn)中，Kim等[1]以出口集裝箱作業(yè)序列為研究對象，以場橋在各箱區(qū)間總移動(dòng)時(shí)間最小為目標(biāo)，構(gòu)建了單臺場橋作業(yè)調(diào)度的混合整數(shù)規(guī)劃模型。Mak等[2]研究了混堆堆場內(nèi)的多場橋調(diào)度問題，考慮了集裝箱的提箱準(zhǔn)備時(shí)間、提箱作業(yè)時(shí)間、場橋移動(dòng)時(shí)間及因場橋間干擾引起的等待時(shí)間，以多臺場橋作業(yè)完成時(shí)刻之和最小為目標(biāo)，構(gòu)建了混合整數(shù)規(guī)劃模型，設(shè)計(jì)了一種遺傳算法與禁忌搜索算法相結(jié)合的混合優(yōu)化算法。Chang Daofang等[3]研究了單個(gè)箱區(qū)內(nèi)的雙場橋調(diào)度問題，建立了以最小化延遲任務(wù)數(shù)為目標(biāo)的整數(shù)規(guī)劃模型，并設(shè)計(jì)了基于滾動(dòng)時(shí)域的啟發(fā)式算法。樂美龍等[4]針對出口箱堆場，考慮場橋不可跨越與保持安全距離等現(xiàn)實(shí)約束，以多場橋完成所有裝卸任務(wù)的總時(shí)間最短為目標(biāo)，并設(shè)計(jì)了兩階段算法，最終給出了一個(gè)任務(wù)分配和排序方案。Li Wenkai等[5]研究了單個(gè)箱區(qū)內(nèi)的多場橋調(diào)度問題，以最小所有集裝箱的提箱提前時(shí)間、提箱延遲時(shí)間及存箱延遲時(shí)間的加權(quán)和為優(yōu)化目標(biāo)，構(gòu)建了連續(xù)型混合整數(shù)線性規(guī)劃模型，并設(shè)計(jì)了滾動(dòng)時(shí)域算法，實(shí)驗(yàn)表明所提出的算法可有效求解大規(guī)模算例。Wu Yong等[6]針對與Li Wenkai等[5]相同的問題，將提箱延遲任務(wù)數(shù)引入至目標(biāo)函數(shù)中，提出了一種基于集群-重新分配思想的啟發(fā)式算法。韓曉龍等[7]研究了集裝箱碼頭裝船作業(yè)中的場橋調(diào)度問題，結(jié)合配載計(jì)劃，建立了提箱作業(yè)總完成時(shí)間最短為目標(biāo)的場橋調(diào)度模型。范厚明等[8]提出了出口箱箱位分配和場橋調(diào)度的分區(qū)域平衡策劃方法，考慮了場橋間相互干涉的現(xiàn)實(shí)約束，對場橋非裝卸時(shí)間進(jìn)行了優(yōu)化，并均衡了各場橋的作業(yè)任務(wù)量。

在B類文獻(xiàn)中，Chen Lu等[9]研究了出口箱堆場內(nèi)的多場橋調(diào)度問題，同時(shí)考慮了場橋間作業(yè)干擾、場橋在多個(gè)箱區(qū)內(nèi)的轉(zhuǎn)場情況和場橋于單個(gè)箱區(qū)內(nèi)的排序情況等，以所有集裝箱的最遲提箱完成時(shí)刻最小為優(yōu)化目標(biāo)，構(gòu)建了混合整數(shù)規(guī)劃模型，并分別提出了遺傳算法和禁忌搜索算法兩種啟發(fā)式算法用于求解。鄭紅星等[10]研究了混堆箱區(qū)某時(shí)段內(nèi)的多場橋調(diào)度問題，考慮了內(nèi)外集卡的優(yōu)先級、場橋間不可跨越和保持安全距離等因素，構(gòu)建了多場橋調(diào)度模型，并設(shè)計(jì)了混合遺傳算法用于求解，文中各任務(wù)箱的提取操作時(shí)間不盡相同。梁承姬等[11]研究了混堆堆場內(nèi)某箱區(qū)的場橋調(diào)度問題，建立了以場橋裝卸完工時(shí)間最小為目標(biāo)的優(yōu)化模型，并設(shè)計(jì)了相應(yīng)的優(yōu)化算法，該文中將各任務(wù)箱的提取時(shí)間視為已知，但各不相同。雖然上述文獻(xiàn)考慮的是混堆，但沒有外集卡的裝船階段可看成出口箱堆場。鄭紅星等[12]為解決混堆裝船箱區(qū)內(nèi)的多場橋調(diào)度問題開發(fā)了一種滾動(dòng)時(shí)域算法，重點(diǎn)考慮內(nèi)外集卡的不同優(yōu)先級別和倒箱因素對場橋調(diào)度問題的影響，在減少集卡等待成本的同時(shí)降低了倒箱量；且該文中倒箱的處理方法屬于按單箱翻倒時(shí)間與壓數(shù)乘積計(jì)算。張笑菊等[13]針對混堆堆場的集裝箱碼頭裝船順序優(yōu)化問題，考慮船舶一個(gè)貝位集裝箱的同貝同步裝卸作業(yè)，以單臺場橋在單個(gè)箱區(qū)內(nèi)移動(dòng)時(shí)間和翻箱時(shí)間最小為目標(biāo)，構(gòu)建了出口集裝箱裝船順序優(yōu)化模型并設(shè)計(jì)了啟發(fā)式算法，提高了場橋與岸橋的作業(yè)效率。Jin Jiangang等[14]以場橋作業(yè)成本和移動(dòng)成本之和最小為目標(biāo)，對場橋空間分配和場橋配置整合優(yōu)化問題進(jìn)行了研究，構(gòu)建了整數(shù)線性規(guī)劃模型，明確了各時(shí)段內(nèi)場橋的工作區(qū)域。

在C類文獻(xiàn)中，Lee等[15]將裝船前的出口集裝箱翻箱問題定義為預(yù)翻箱問題，并提出整數(shù)規(guī)劃模型和近鄰搜索算法，有效地解決了以翻箱次數(shù)最少為目標(biāo)的堆場翻箱問題。朱明華等[16]基于給定出口箱堆場集裝箱的堆存狀態(tài)和裝船順序，建立了以倒箱量最少和場橋代價(jià)最低為目標(biāo)的數(shù)學(xué)模型，提出了定向搜索算法進(jìn)行求解。周鵬飛等[17]針對交箱序列的動(dòng)態(tài)不確定性，建立了出口箱堆場中具體箱位分配模型，在優(yōu)化翻箱量的同時(shí)縮短了場橋大車行走距離。邵乾虔等[18]結(jié)合出口箱堆場作業(yè)時(shí)間，建立了以最小化預(yù)翻箱量和場橋堆存作業(yè)移動(dòng)距離為目標(biāo)的數(shù)學(xué)模型，并給出了求解算法。

同時(shí)，鑒于出口箱堆場的核心作業(yè)是內(nèi)集卡提箱裝船，研究該類堆場的場橋調(diào)度需著重考慮內(nèi)集卡作業(yè)效率對其的影響。有關(guān)集卡的研究一直是國內(nèi)外學(xué)者研究的熱點(diǎn)，其中Amini等[19]為優(yōu)化集裝箱碼頭集卡擁堵問題，針對集裝箱交叉堆放的情況下，構(gòu)建了多目標(biāo)線性規(guī)劃模型并結(jié)合三種啟發(fā)式算法進(jìn)行求解。張芳芳等[20]考慮了堆場可存儲(chǔ)位置動(dòng)態(tài)變化的因素，以內(nèi)集卡完成任務(wù)的總時(shí)間最小為目標(biāo)，構(gòu)建了集卡調(diào)度模型并采用四種不同的改進(jìn) PSO 算法進(jìn)行求解。趙金樓等[21]分別以集卡行駛距離和集卡任務(wù)間空載距離最小為目標(biāo)，提出了集卡兩階段路徑優(yōu)化模型，在考慮集卡數(shù)量和作業(yè)順序的影響下提高堆場作業(yè)效能。

綜上，已有關(guān)于場橋調(diào)度的文獻(xiàn)大都以場橋行走路徑最短、場橋作業(yè)完成時(shí)間最短為優(yōu)化目標(biāo)，其中忽略倒箱的文獻(xiàn)較多，直接將倒箱時(shí)間加入場橋作業(yè)過程的文獻(xiàn)較少，而考慮提前控制倒箱的文獻(xiàn)近年來逐漸增加。但在實(shí)際作業(yè)中限于集港時(shí)出口箱抵達(dá)時(shí)機(jī)同配載計(jì)劃的不匹配，倒箱對場橋作業(yè)的時(shí)長影響很大，必須在調(diào)度過程中加以考慮；同時(shí)由于提前倒箱作業(yè)場橋數(shù)量的不足、場地和時(shí)間的限制、裝船的時(shí)限要求等因素，提前控制倒箱和箱位分配很難實(shí)現(xiàn)，因此需考慮在場橋作業(yè)過程中的實(shí)時(shí)預(yù)倒箱。在有關(guān)集卡調(diào)度的文獻(xiàn)中，大都以集卡行駛距離最短和總作業(yè)時(shí)間最短等為目標(biāo)，少有考慮內(nèi)集卡等待時(shí)間上限和由于場橋倒箱而產(chǎn)生的延誤時(shí)間，而在出口箱堆場伴有倒箱的裝船作業(yè)中，為盡可能減少岸橋等待內(nèi)集卡的時(shí)間，需重點(diǎn)考慮如何采用實(shí)時(shí)預(yù)倒箱來加快內(nèi)集卡的周轉(zhuǎn)。

區(qū)別已有文獻(xiàn)，本文在現(xiàn)有研究的基礎(chǔ)上，針對出口箱堆場的場橋調(diào)度優(yōu)化問題，從降低內(nèi)集卡等待時(shí)間的角度出發(fā)，兼顧內(nèi)集卡提箱的等待容忍限度，重點(diǎn)考慮基于配載計(jì)劃中待提箱上壓箱翻倒的時(shí)機(jī)和分配，視倒箱為作業(yè)過程的另一類別的任務(wù)，將倒箱任務(wù)和提箱任務(wù)集成優(yōu)化，最終給出優(yōu)化的場橋作業(yè)調(diào)度計(jì)劃，其中包括多臺場橋的行走路徑和實(shí)時(shí)預(yù)倒箱方案。

2 調(diào)度模型及下界

2.1 問題描述

一般而言，預(yù)先獲知船舶的抵港計(jì)劃、船期和配載計(jì)劃后，碼頭會(huì)為其配備合理數(shù)量的岸橋，并分配合適的泊位。從作業(yè)重要性上來看，泊位和岸橋是最重要的資源。因此，就出口箱堆場而言，如何高效地進(jìn)行提箱作業(yè)，使得船舶的在泊時(shí)間最小，同時(shí)實(shí)現(xiàn)岸橋利用率的最大化，是出口箱堆場中多場橋調(diào)度的核心目的。

本文的問題可描述為：在固定的計(jì)劃期內(nèi)，某船擬從出口箱堆場某箱區(qū)提箱的配載計(jì)劃已知，考慮待提箱的提箱次序固定、多臺場橋作業(yè)過程中不可跨越和保持一定安全距離等現(xiàn)實(shí)約束，側(cè)重作業(yè)過程中的實(shí)時(shí)預(yù)倒箱，兼顧內(nèi)集卡的等待上限，使得帶有懲罰因子的內(nèi)集卡總提箱等待時(shí)間最少。

2.2 模型假設(shè)

本文將待提箱稱為主計(jì)劃箱，將主計(jì)劃箱上的壓箱稱為該箱的子計(jì)劃箱。

模型假設(shè)如下：(1)計(jì)劃期內(nèi)主計(jì)劃箱對應(yīng)內(nèi)集卡就緒時(shí)刻均由往返規(guī)律預(yù)知；(2)只考慮20英尺單一箱型；(3)場橋間不可跨越且須留有安全距離；(4)箱區(qū)內(nèi)主計(jì)劃箱的箱位分布、配積載圖及場橋作業(yè)能力等均已知；(5)提箱作業(yè)須在對應(yīng)內(nèi)集卡就緒后進(jìn)行；(6)倒箱原則是不壓計(jì)劃期內(nèi)的主計(jì)劃箱。

2.3 調(diào)度模型

以某箱區(qū)為例，其貝位展開圖見圖1示，原問題轉(zhuǎn)化為圖論問題見圖2示。

考慮轉(zhuǎn)化過程中涉及的多主計(jì)劃箱位于同貝同棧的情況，圖2右側(cè)即為Bay4轉(zhuǎn)化情況(假設(shè)C3箱計(jì)劃提箱時(shí)刻早于C5箱)，可見C3箱雖為主計(jì)劃箱，但對其的作業(yè)可能不為提箱作業(yè)，而是提取其他箱時(shí)所需的倒箱作業(yè)。

圖1 貝位展開圖

圖2 原調(diào)度的圖論問題

本文將原調(diào)度問題轉(zhuǎn)化為圖論問題如圖2所示，其中實(shí)線框內(nèi)計(jì)劃箱節(jié)點(diǎn)代表原問題中多主計(jì)劃箱位于同貝同棧的轉(zhuǎn)化情況，虛線框內(nèi)計(jì)劃箱節(jié)點(diǎn)代表原問題中多主計(jì)劃箱位于同貝異棧的轉(zhuǎn)化情況(若兩種情況都存在則仍用實(shí)線框表示)；1、2號節(jié)點(diǎn)為起點(diǎn)，代表原問題中場橋；3號節(jié)點(diǎn)為終點(diǎn)，代表原問題中場橋作業(yè)完成；4至46號節(jié)點(diǎn)為各貝位計(jì)劃箱轉(zhuǎn)化后所對應(yīng)的節(jié)點(diǎn)。本文調(diào)度問題轉(zhuǎn)化為由起點(diǎn)出發(fā)，遍歷全部中間節(jié)點(diǎn)最終匯集至終點(diǎn)的圖論問題；同時(shí)在圖論問題基礎(chǔ)上，引入原問題各箱間作業(yè)約束、場橋現(xiàn)實(shí)約束等。

參數(shù)定義為：M充分大的正數(shù)；QTi為i箱對應(yīng)集卡就緒時(shí)刻，不為主計(jì)劃箱節(jié)點(diǎn)時(shí)取M；Dij節(jié)點(diǎn)(i,j)間的距離，以移動(dòng)時(shí)間衡量；Bj為j箱的作業(yè)時(shí)間，不為箱節(jié)點(diǎn)時(shí)取0；C內(nèi)集卡懲罰因子；ξ內(nèi)集卡等待上限；n計(jì)劃箱總數(shù)；D場橋間安全距離；Dt場橋行走距離D所用時(shí)長；BWi為i箱所在貝位，不為箱節(jié)點(diǎn)時(shí)取0；Q實(shí)線框外的所有計(jì)劃箱集合；Rh第h個(gè)實(shí)線框內(nèi)的所有節(jié)點(diǎn)集合(節(jié)點(diǎn)集合同轉(zhuǎn)化情況相對應(yīng))；F所有節(jié)點(diǎn)集合；P場橋節(jié)點(diǎn)集合；R子計(jì)劃箱節(jié)點(diǎn)集合；R′主計(jì)劃箱節(jié)點(diǎn)集合；FZ虛擬終點(diǎn)集合；Pk第k號場橋?yàn)楸３謭鰳蜷g現(xiàn)實(shí)作業(yè)約束而無法到達(dá)的點(diǎn)集；m場橋數(shù)；L實(shí)線框數(shù)；Yhv第h個(gè)實(shí)線框內(nèi)第v個(gè)節(jié)點(diǎn)集合；Shv第h個(gè)實(shí)線框第v個(gè)節(jié)點(diǎn)集合所對應(yīng)到達(dá)邊總數(shù)；Zi若第i號節(jié)點(diǎn)為主計(jì)劃箱節(jié)點(diǎn)則取1，否則取0。

變量定義為：FTik第k號場橋作業(yè)i箱的完成時(shí)刻，若不為箱節(jié)點(diǎn)則取非負(fù)；Xijk若第k號場橋由節(jié)點(diǎn)i移至節(jié)點(diǎn)j則取1，否則取0；Aik若第k號場橋作業(yè)i箱的等待時(shí)間小于ξ則取1，否則取0；Cijkk′若滿足FTik′≥FTjk則取1，否則取0；Eijkk′若場橋k′作業(yè)i箱同場橋k作業(yè)j箱的作業(yè)時(shí)間發(fā)生沖突則取1，否則取0；Gijkk′在場橋k′作業(yè)i箱同場橋k作業(yè)j箱作業(yè)時(shí)間發(fā)生沖突的條件下，若這兩個(gè)場橋間不滿足安全距離約束則取1，否則取0；Pijkk′在場橋k′作業(yè)i箱同場橋k作業(yè)j箱時(shí)作業(yè)時(shí)間發(fā)生沖突且不滿足安全距離約束的條件下，若場橋k′先于場橋k作業(yè)則取1，否則取0；Whv第h個(gè)實(shí)線框第v個(gè)節(jié)點(diǎn)集合被遍歷則取1，否則取0；TTi為i箱對應(yīng)內(nèi)集卡帶有懲罰因子的等待時(shí)間。

(1)

s.t.:FTjk≥Dij*Xijk+FTik-(1-Xijk)*M+Bj,i,j∈F;k∈P

(2)

(3)

Xiik=0,i∈F;k∈P

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

FTjk≥FTik′-Cijkk′*M,i,j∈F;k,k′∈P

(21)

FTik′≥FTjk-(1-Cijkk′)*M,i,j∈F;k,k′∈P

(22)

FTjk≥FTik′+Bj-Cijkk′*M-Eijkk′*M,i,j∈F;k,k′∈P

(23)

FTik′≥FTjk-Bj-Cijkk′*M-(1-Eijkk′)*M,i,j∈F;k,k′∈P

(24)

BWi≤BWj+D+(1-Gijkk′)*M+(1-Eijkk′)*M,i,j∈F;k,k′∈P

(25)

BWi≥BWj+D-Gijkk′*M-(1-Eijkk′)*M,i,j∈F;k,k′∈P

(26)

FTjk≥FTik′-Bi+Bj-(1-Pijkk′)*M-(1-Gijkk′)*M,i,j∈F;k,k′∈P

(27)

FTjk≤FTik′-Bi+Bj+Pijkk′*M+(1-Gijkk′)*M,i,j∈F;k,k′∈P

(28)

(29)

(30)

Xijk=0,i∈F;j∈Pk;k∈P

(31)

FTik-QTi-ξ≤(1-Aik)*M,i∈F;k∈P

(32)

FTik-QTi-ξ≥-Aik*M,i∈F;k∈P

(33)

TTi≥FTik-QTi-(1-Aik)*M,i∈F;k∈P

(34)

TTi≥(FTik-QTi)*C-Aik*M,i∈F;k∈P

(35)

TTi≥0,FTik≥0,i∈F;k∈P

(36)

式(1)目標(biāo)函數(shù)為帶有懲罰因子的內(nèi)集卡總等待時(shí)間；式(2)～(4)保證各場橋順次作業(yè)各計(jì)劃箱的完成時(shí)刻大小關(guān)系，且場橋?qū)χ饔?jì)劃箱的提箱作業(yè)在對應(yīng)集卡就緒后進(jìn)行；式(5)～(7)保證實(shí)線框外的所有計(jì)劃箱均被某一場橋作業(yè)一次；式(8)～(9)表示變量Whv為1時(shí)實(shí)線框h中節(jié)點(diǎn)集合v的到達(dá)邊大于1，否則其到達(dá)邊為0；式(10)～(13)保證各實(shí)線框內(nèi)僅有一個(gè)節(jié)點(diǎn)集合被遍歷，且該節(jié)點(diǎn)集合內(nèi)的所有計(jì)劃箱均被某一場橋作業(yè)一次；式(14)～(16)保證各場橋均以對應(yīng)的場橋節(jié)點(diǎn)作為起點(diǎn)，并滿足起點(diǎn)的圖論約束；式(17)～(18)保證終點(diǎn)滿足圖論約束；式(19)保證各棧位的計(jì)劃箱由場橋從上至下依次作業(yè)；式(20)保證主計(jì)劃箱按集卡到達(dá)順序由場橋依次完成提箱作業(yè)；式(21)～(22)表示場橋間作業(yè)完成時(shí)刻大小同變量Cijkk′間的對應(yīng)關(guān)系；式(23)～(24)表示場橋間作業(yè)時(shí)間是否發(fā)生沖突同變量Eijkk′間的對應(yīng)關(guān)系；式(25)～(26)表示場橋間是否作業(yè)時(shí)間發(fā)生沖突且不滿足安全距離同變量Gijkk′間的對應(yīng)關(guān)系；式(27)～(28)表示在不滿足現(xiàn)實(shí)約束的條件下，場橋作業(yè)先后次序同變量Pijkk′間的對應(yīng)關(guān)系；式(29)～(30)保證各計(jì)劃箱作業(yè)完成時(shí)刻的取值；式(31)保證各場橋的作業(yè)范圍；式(32)～(35)保證不同內(nèi)集卡等待時(shí)間下，帶有懲罰因子的等待時(shí)間取值；式(36)保證變量范圍。

2.4 下界

本文首先給出近似衡量算法有效性的下界1，即考慮主計(jì)劃箱均可在集卡就緒后直接進(jìn)行提箱作業(yè)(不考慮壓箱)。下界1存在的必要是：無論何種規(guī)模均可給出下界?？紤]到下界1的精確性，本文在原問題基礎(chǔ)上松弛場橋間保持安全距離及不可跨越約束，并將同貝同棧情況合理轉(zhuǎn)化，原圖論問題轉(zhuǎn)化為新圖論問題(下界2)如圖3所示。

圖3 下界2圖論問題

對本文提出的下界2做簡要說明。本文在原問題基礎(chǔ)上松弛了場橋間保持安全距離及不可跨越的因素，將解空間進(jìn)行放大，下界2解空間是原問題解空間的子集，使得下界2最優(yōu)解必位于原問題最優(yōu)解之下或與之相同；同時(shí)，同貝同棧情況被合理轉(zhuǎn)化，保證轉(zhuǎn)化后作業(yè)全部箱所需的總時(shí)間變少或不變，因此本文給出下界2最優(yōu)解一定是原問題最優(yōu)解的下界。

參數(shù)定義為：QTi為i箱對應(yīng)集卡就緒時(shí)刻，不為主計(jì)劃箱節(jié)點(diǎn)時(shí)取M；Dij節(jié)點(diǎn)(i,j)間距離；Bj為i箱作業(yè)時(shí)間，不為箱節(jié)點(diǎn)時(shí)取0；M充分大正數(shù)；C內(nèi)集卡懲罰因子；ξ內(nèi)集卡等待上限；n計(jì)劃箱數(shù)；Q計(jì)劃箱節(jié)點(diǎn)集合；F所有節(jié)點(diǎn)集合；P場橋節(jié)點(diǎn)集合；R子計(jì)劃箱節(jié)點(diǎn)集合；m場橋數(shù)；Zi若第i號節(jié)點(diǎn)為主計(jì)劃箱節(jié)點(diǎn)取1，否則取0。

變量定義為：FTi第i箱完成時(shí)刻，若非箱節(jié)點(diǎn)則取非負(fù)；Xij由節(jié)點(diǎn)i移至節(jié)點(diǎn)j時(shí)取1，否則取0；Ahi衡量節(jié)點(diǎn)i懲罰因子取值，h取1或2分別對應(yīng)兩種懲罰情況；TTi為i箱對應(yīng)內(nèi)集卡帶有懲罰因子的等待時(shí)間。

(37)

s.t.FTj≥Dij*Xij+FTi-(1-Xij)*M+Bj,i,j∈F

(38)

FTj≥QTj+Bj-(1-Zj)*M,j∈F

(39)

FTk=0,k∈P

(40)

Xii=0,i∈F

(41)

(42)

(43)

(44)

(45)

(46)

FTi≤FTi+1,i∈R

(47)

(48)

FTi-QTi-ξ≤(1-A1i)*M,i∈F

(49)

A1i+A2i=1,i∈F

(50)

TTi≥FTi-QTi-(1-A1i)*M,i∈F

(51)

TTi≥(FTi-QTi)*C-(1-A2i)*M,i∈F

(52)

TTi≥0,FTi≥0,i∈F

(53)

式(37)目標(biāo)函數(shù)為帶有懲罰因子的內(nèi)集卡總等待時(shí)間；式(38)～(41)保證場橋作業(yè)連續(xù)性，且內(nèi)集卡提箱作業(yè)在其就緒后進(jìn)行；式(42)～(44)保證各起點(diǎn)及箱節(jié)點(diǎn)的圖論約束；式(45)～(46)保證終點(diǎn)的圖論約束；式(47)～(48)保證各箱節(jié)點(diǎn)間的作業(yè)約束；式(49)～(52)保證不同集卡等待時(shí)間下，帶有懲罰因子的等待時(shí)間取值；式(53)保證變量的取值范圍。

3 混合和聲模擬退火算法

考慮到CPLEX僅可在小規(guī)模算例時(shí)對調(diào)度模型進(jìn)行求解，本文設(shè)計(jì)了混合和聲模擬退火算法(簡稱HAS算法)，即以SA算法為基本框架，融入HS算法中記憶庫(HM)及群體操作思想。同進(jìn)口箱堆場相比，由于船舶配積載圖事先已知，出口箱堆場內(nèi)的主計(jì)劃箱提箱次序固定，鑒于此本文設(shè)計(jì)了和聲修復(fù)策略；同時(shí)，為有效提升算法性能，設(shè)計(jì)了隨溫度而變化的動(dòng)態(tài)參數(shù)。

3.1 HAS算法流程

本文HAS算法流程如圖4所示，HM中包括M個(gè)個(gè)體，且每次迭代產(chǎn)生M-1個(gè)個(gè)體，同HM中M-1個(gè)非最優(yōu)個(gè)體按Metropolis接受準(zhǔn)則取舍，并記錄全局最優(yōu)解。

圖4 算法流程圖

3.2 解的編碼

本文解的編碼采用浮點(diǎn)與整數(shù)編碼結(jié)合策略，具體解的編碼片段如圖5所示。其中前段和聲為主、子計(jì)劃箱被分配作業(yè)的順序(各箱按主計(jì)劃箱及其子計(jì)劃箱所在層位從上至下依次標(biāo)號，如1.1、1.2、1.3 等)，后段和聲為各箱作業(yè)時(shí)所對應(yīng)場橋的序號。

以圖5的某個(gè)體片段為例對解的編碼做簡要說明，首先，本文中每個(gè)標(biāo)號均對應(yīng)一個(gè)集裝箱，但一個(gè)集裝箱可能具有多個(gè)標(biāo)號(如多主計(jì)劃箱位于同貝同棧)。其次，本文解的編碼中各標(biāo)號(集裝箱)的排序按其開始作業(yè)順序先后排序，如圖5中的3.1一定在1.2之前作業(yè)。最后，前段和聲同后段和聲長度相同。

3.3 初始化HM及隨機(jī)生成

本文初始化HM及隨機(jī)生成策略相同，為保證產(chǎn)生個(gè)體的可行性，設(shè)計(jì)了產(chǎn)生M個(gè)個(gè)體的步驟如下：

步驟1初始化，個(gè)體數(shù)k=1，主計(jì)劃箱的次序數(shù)i=1；

步驟2依次生成第1個(gè)作業(yè)次序i.j，其中j=1,2,…,G(i)+1，G(i)為i箱的壓箱數(shù)；

步驟3令i=i+1，依次生成第i個(gè)作業(yè)次序i.j，其中j=1,2,…,G(i)，并將第i個(gè)作業(yè)次序隨機(jī)插入至第1個(gè)作業(yè)次序中；之后，將i.j置于第1個(gè)作業(yè)次序的最后，其中j=G(i)+1，

圖5 解的編碼示意圖

步驟4若i小于主計(jì)劃箱數(shù)，則轉(zhuǎn)至步驟3；否則，轉(zhuǎn)至步驟5；

步驟5將更新后的第1個(gè)作業(yè)次序作為第k個(gè)個(gè)體的前段和聲序列；同時(shí)，第k個(gè)個(gè)體后段和聲的場橋序列隨機(jī)生成，轉(zhuǎn)至步驟6；

步驟6令k=k+1，若k≤M，則令i=1，轉(zhuǎn)至步驟2；否則，結(jié)束。

3.4 和聲微調(diào)

本文新個(gè)體產(chǎn)生涉及三種方案，分別為和聲微調(diào)、最優(yōu)微調(diào)(對全局最優(yōu)和聲微調(diào))以及隨機(jī)生成和聲。本文和聲微調(diào)采用四種單親變換策略，分別是兩點(diǎn)互換策略、正向移位策略、反向移位策略以及逆序變換策略?？紤]到前段和聲同后段和聲的微調(diào)策略是分開進(jìn)行的，本文以某前段和聲片段為例對四種策略做簡要說明如圖6所示。

從圖6可以看出和聲微調(diào)的四種策略均可能使原個(gè)體變?yōu)椴豢尚?，需引入和聲修?fù)策略。其次，前、后段和聲有某種聯(lián)系，如各箱因其所在位置不同，而僅可由特定場橋作業(yè)，因此僅由前段和聲進(jìn)行四種策略，會(huì)降低最優(yōu)解產(chǎn)生的概率。綜上，考慮到迭代初期和聲前后段的關(guān)聯(lián)度較低，而在后期和聲的前后段關(guān)系基本形成。本文在算法后期引入“最優(yōu)微調(diào)”策略，包括上述圖6中前三種策略，且“最優(yōu)微調(diào)”均為前、后段和聲同時(shí)進(jìn)行變換策略。

圖6 和聲微調(diào)策略示意

3.5 和聲修復(fù)

針對各主計(jì)劃箱及其子計(jì)劃箱間作業(yè)順序約束、各主計(jì)劃箱間作業(yè)順序約束，本文設(shè)計(jì)了和聲修復(fù)1；考慮場橋間保持安全距離以及不可跨越因素，本文設(shè)計(jì)了和聲修復(fù)2(注：在算法中適應(yīng)度計(jì)算部分也會(huì)考慮場橋間現(xiàn)實(shí)約束，和聲修復(fù)2起輔助作用)。

3.5.1 和聲修復(fù)1

考慮到各箱間的作業(yè)約束同場橋序號無關(guān)，和聲修復(fù)1僅針對前段和聲而進(jìn)行。以某一新個(gè)體為例，具體和聲修復(fù)1(包括兩部分)的步驟如下：

(1)和聲修復(fù)1的第一部分

步驟1初始化，令i=1，j=1；

步驟2提取個(gè)體前段和聲第j位箱；

步驟3若其為第i個(gè)主計(jì)劃箱或其子計(jì)劃箱，則將第j位箱記錄到臨時(shí)信息矩陣中，對應(yīng)其位置j記錄到臨時(shí)位置矩陣中；否則不記錄；令j=j+1；

步驟4若j大于前段和聲長度，則轉(zhuǎn)至步驟5；否則轉(zhuǎn)至步驟2；

步驟5將臨時(shí)信息矩陣中的信息升序排序后，依次按臨時(shí)位置矩陣的原位置替換到原和聲中；清空臨時(shí)信息矩陣、臨時(shí)位置矩陣；

步驟6令i=i+1，若i大于主計(jì)劃箱數(shù)n，則結(jié)束；否則，令j=1，轉(zhuǎn)至步驟2。

(2)和聲修復(fù)1的第二部分(對第一部分修復(fù)后的個(gè)體進(jìn)行再次修復(fù))

注：臨時(shí)“前段和聲”為零向量。

步驟1初始化，令j=L，m=L，k=n(其中L為前段和聲長度，n為主計(jì)劃箱數(shù))；

步驟2提取個(gè)體第j位的箱，若該箱是子計(jì)劃箱，則轉(zhuǎn)至步驟3；否則轉(zhuǎn)至步驟4；

步驟3令臨時(shí)“前段和聲”的第m位等于個(gè)體前段和聲第j位的箱，m=m-1，j=j-1，若j<1，則轉(zhuǎn)至步驟7；否則轉(zhuǎn)至步驟2；

步驟4若該箱是第k個(gè)主計(jì)劃箱，則令k=k-1轉(zhuǎn)至步驟3；否則轉(zhuǎn)至步驟5；

步驟5若k大于第j位箱對應(yīng)的主計(jì)劃箱號，則轉(zhuǎn)至步驟6；否則，令j=j-1，若j<1，則轉(zhuǎn)至步驟7；若j≥1，轉(zhuǎn)至步驟2；

步驟6記錄X為第j位箱所對應(yīng)的主計(jì)劃箱序號與k的差值，依次產(chǎn)生第k個(gè)至第k-X個(gè)主計(jì)劃箱，并依次放入臨時(shí)“前段和聲”中，令k=k-X-1，m=m-X-1，j=j-1，若j<1，則轉(zhuǎn)至步驟7；否則，轉(zhuǎn)至步驟2；

步驟7將個(gè)體的前段和聲更新為臨時(shí)“前段和聲”。

3.5.2 和聲修復(fù)2

本文的場橋相關(guān)約束，需在和聲修復(fù)中進(jìn)行有效的限制，具體和聲修復(fù)2步驟如下：

步驟1初始化，令p=1，j=1+L(其中L為前段和聲長度)；

步驟2提取第p個(gè)和聲第j位場橋序號，記錄場橋序號z；

步驟3若第p個(gè)和聲第j-L位箱所在的貝位，屬于第z號場橋作業(yè)范圍，則轉(zhuǎn)到步驟5；否則，轉(zhuǎn)到步驟4；

步驟4將第p個(gè)和聲的第j位場橋序號隨機(jī)更新為可服務(wù)此計(jì)劃箱的場橋序號；

步驟5令j=j+1，若j>2×L，則轉(zhuǎn)到步驟6；否則，轉(zhuǎn)到步驟2；

步驟6令p=p+1，若p大于和聲總個(gè)數(shù)，則結(jié)束；否則，轉(zhuǎn)到步驟2；

3.6 動(dòng)態(tài)參數(shù)的設(shè)定

本文對HMCR、PAR兩個(gè)參數(shù)進(jìn)行了改進(jìn)，引入了隨溫度而變化的動(dòng)態(tài)參數(shù)，使算法在不同的搜索時(shí)期發(fā)揮出不同的搜索性能。通過多次實(shí)驗(yàn)對比后，對參數(shù)HMCR采用反比例曲線Y=k/(x+b)+a,(k>0,b>0)進(jìn)行改進(jìn)，使HMCR由0.6向0.9快速收斂，以增加算法初期的全局搜索能力，和算法中、后期的局部搜索能力。對參數(shù)PAR采用Logistic曲線：Y=1/(K+a*bx),(a>0,00)進(jìn)行改進(jìn)，使PAR值由0.7向0.3大體上呈S型收斂，保證算法在前期充分進(jìn)行和聲前后段的關(guān)聯(lián)匹配；同時(shí)，增強(qiáng)了算法后期對全局最優(yōu)解的改進(jìn)能力，提升算法后期的搜索精度。具體的改進(jìn)見公式(54)～(55)示。

HMCR=179.982/(Tk+199.97)

(54)

(55)

3.7 適應(yīng)度評價(jià)

適應(yīng)度評價(jià)見公式(56)～(57)示。

(56)

(57)

公式(56)～(57)中，QWi為懲罰因子的取值；FTi為第i個(gè)內(nèi)集卡提箱完成時(shí)刻；QTi為第i個(gè)內(nèi)集卡計(jì)劃提箱時(shí)刻；ξ為內(nèi)集卡等待上限；C為等待時(shí)間超過等待上限的懲罰值；Xk為第k個(gè)個(gè)體；Fitness(Xk)為第k個(gè)個(gè)體的適應(yīng)度；n為主計(jì)劃箱數(shù)。

4 數(shù)值實(shí)驗(yàn)

4.1 方案有效性實(shí)驗(yàn)

(1)算例原始數(shù)據(jù)

在出口箱堆場某箱區(qū)中，已知計(jì)劃期內(nèi)(據(jù)天津港等地的實(shí)地調(diào)查數(shù)據(jù)可知，場橋作業(yè)計(jì)劃約1h滾動(dòng)一次，故本文取計(jì)劃期為1h)內(nèi)集卡的提箱信息如表1中原始數(shù)據(jù)一欄所示。場橋相關(guān)信息如下：跨距6棧，堆垛高度5層，移動(dòng)時(shí)間0.1分/貝，裝載任務(wù)3分，倒箱需2分，作業(yè)安全距離3貝。結(jié)合港口實(shí)地調(diào)查數(shù)據(jù)以及適應(yīng)度評價(jià)公式的特點(diǎn)，取內(nèi)集卡等待上限ξ為10分、懲罰因子C為10。

(2)算例求解

文中算法的相關(guān)參數(shù)取值如下：(降溫系數(shù)，內(nèi)循環(huán)次數(shù)，初溫，終溫，記憶庫大小)=(0.96，30，100，0.01，5)，所有的實(shí)驗(yàn)都運(yùn)行在3.10GHz Intel Core 2 CPU 和4GB內(nèi)存的雙核計(jì)算機(jī)上，采用MATLAB R2014a編碼。經(jīng)計(jì)算，本文提出的HAS算法搜索過程如圖7所示，搜索到5800代左右時(shí)，目標(biāo)收斂于45.5分，求解耗時(shí)121.29秒；場橋?qū)崟r(shí)行走路徑如圖8所示，可以看出，場橋路徑無交叉點(diǎn)且始終保持安全距離。

圖7 收斂圖

圖8 場橋?qū)崟r(shí)行走路徑

表1 方案對比表

任務(wù)原始數(shù)據(jù)HAS方案RHA方案FCFS方案到達(dá)時(shí)刻貝棧層壓箱數(shù)完成時(shí)刻等待時(shí)長完成時(shí)刻等待時(shí)長完成時(shí)刻等待時(shí)長1224215.23.275752664119312.46.4115391231012312314.65.64148440173173173517543220.33.324724.37.361914541223245245723942126329.46.429.56.58271552230334737.110.19321051135337537510381344141343543511434441463485485124713321503525525135172325435875871455923158363.48.463.28.21557342060361.44.466.89.8目標(biāo)值\\45.582.6183.4

為驗(yàn)證本文方法得到場橋作業(yè)方案的有效性，分別同采用先到先服務(wù)方案和不考慮實(shí)時(shí)預(yù)倒箱的鄭紅星等[22]中的方案(在該文中，目標(biāo)函數(shù)基本一致，不涉及內(nèi)集卡時(shí)同本文問題相同)進(jìn)行對比分析，如表1所示?？梢钥闯?，F(xiàn)CFS方案的目標(biāo)值最大，內(nèi)集卡作業(yè)總等待時(shí)間最長，且有一個(gè)內(nèi)集卡超過等待上限；不考慮實(shí)時(shí)預(yù)倒箱的RHA方案效果居中，無內(nèi)集卡超限，較FCFS方案好，但是改進(jìn)有限；本文給出的HAS方案效果最好，總等待時(shí)間較RHA方案降低44.92%，同下界1的相對偏差為1.11%。

表2 調(diào)度模型的CPLEX求解結(jié)果

4.2 算例求解

本文通過CPLEX Studio IDE 12.5對原調(diào)度模型進(jìn)行編碼求解，隨機(jī)生成了30個(gè)算例，考慮小規(guī)模下2、4、6、8、10個(gè)主計(jì)劃箱和5個(gè)壓箱以及大規(guī)模下12、14、16、18、20個(gè)主計(jì)劃箱和10個(gè)壓箱(考慮出口箱堆場作業(yè)實(shí)際，在1h內(nèi)單臺場橋最大作業(yè)箱量應(yīng)少于20)。其中，各主計(jì)劃箱的位置均隨機(jī)生成，對應(yīng)貝號、棧號和層高分別為區(qū)間[1,16]、[1,6]和[1,5]內(nèi)的隨機(jī)整數(shù)；同時(shí)，各主計(jì)劃箱的就緒時(shí)刻按經(jīng)驗(yàn)分布給出，其上的壓箱數(shù)為[1,4]內(nèi)的隨機(jī)整數(shù)，得到的結(jié)果如表2所示。

從表2可以看出，CPLEX的求解時(shí)間隨著問題規(guī)模的增大呈指數(shù)型增長，且當(dāng)規(guī)模為Ins6_5_2時(shí)出現(xiàn)求解時(shí)間超過1小時(shí)的情況。這主要是由于原調(diào)度問題出現(xiàn)了多主計(jì)劃箱位于同貝同棧的情況，由圖論轉(zhuǎn)化規(guī)則可知，轉(zhuǎn)化后的圖論點(diǎn)數(shù)呈跳躍式增長，無法在合理的時(shí)間內(nèi)給出最優(yōu)解，故針對6個(gè)主計(jì)劃箱及以上的情況應(yīng)采用啟發(fā)式算法進(jìn)行求解。

4.3 算法的有效性實(shí)驗(yàn)

(1)不同規(guī)模下的算例比較實(shí)驗(yàn)

為驗(yàn)證HAS算法的有效性，結(jié)合4.2中的實(shí)際算例，給出算法對比如表3所示。針對每一算例，將本文HAS算法目標(biāo)值同下界進(jìn)行對比分析。從表3中可以看出，在小規(guī)模算例下，目標(biāo)值同下界1的平均相對偏差為4.88%，同下界2的平均相對偏差為0.35%，說明本文提出的HAS算法在小規(guī)模算例下具有優(yōu)良的計(jì)算效果。在大規(guī)模算例下，目標(biāo)值同下界1的平均相對偏差為9.13%，同下界2的平均相對偏差為4.16%；而在最后6個(gè)算例下，目標(biāo)值同下界1的平均相對偏差依然控制在10.1%，說明本文提出的HAS算法在大規(guī)模算例下依然可以找到近似最優(yōu)的滿意解，驗(yàn)證了算法的有效性。從求解耗時(shí)來看，在個(gè)別算例中存在突變點(diǎn)，這主要是由于算例中出現(xiàn)了多主計(jì)劃箱位于同貝同棧的情況，增加了算法的求解耗時(shí)，求解耗時(shí)整體上呈線性趨勢增長，說明算法在不同規(guī)模下仍具有較好的穩(wěn)定性。

表3 算法對比表

(2)不同壓箱量的算例實(shí)驗(yàn)

針對每組算例，采用本文提出的算法進(jìn)行求解，對比求解耗時(shí)和目標(biāo)值的增長速度。

從表4可以看出，在15個(gè)算例中，目標(biāo)函數(shù)值和求解耗時(shí)都隨著壓箱量的增加而增加。目標(biāo)值于壓箱量從20到25時(shí)有一個(gè)拐點(diǎn)，這是由于在壓箱量為25時(shí)，隨著主計(jì)劃箱及提箱時(shí)刻分布的不同，內(nèi)集卡可用于預(yù)倒箱的空閑時(shí)間逐漸減少，導(dǎo)致個(gè)別內(nèi)集卡超限。而求解耗時(shí)增加較為平緩，表明算法求解時(shí)間相對穩(wěn)定，沒有隨壓箱量的增加而成指數(shù)型增長。

5 結(jié)語

考慮現(xiàn)實(shí)約束，側(cè)重作業(yè)過程中的實(shí)時(shí)預(yù)倒箱，本文構(gòu)建了集裝箱碼頭出口箱堆場多場橋調(diào)度的混合整數(shù)規(guī)劃模型，揭示了實(shí)時(shí)預(yù)倒箱對堆場系統(tǒng)作業(yè)效率的巨大影響。針對CPLEX求解調(diào)度模型時(shí)存在的問題，本文設(shè)計(jì)了融入多種改進(jìn)策略的HAS算法對模型進(jìn)行求解。為驗(yàn)證算法的有效性，文中給出了調(diào)度問題的兩個(gè)下界。數(shù)值實(shí)驗(yàn)表明，此方法可較好地解決集裝箱碼頭出口箱堆場的多場橋調(diào)度問題。

表4 不同壓箱量對比表

未來研究可拓展為內(nèi)集卡、場橋和岸橋集成調(diào)度中的實(shí)時(shí)預(yù)倒箱問題。