考慮實時預(yù)倒箱的出口箱堆場多場橋調(diào)度優(yōu)化

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

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

1 引言

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

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

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

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

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

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

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

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

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

2.1 問題描述

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

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

2.2 模型假設(shè)

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

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

2.3 調(diào)度模型

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

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

圖1 貝位展開圖

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

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

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

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

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

2.4 下界

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

圖3 下界2圖論問題

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

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

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

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

3 混合和聲模擬退火算法

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

3.1 HAS算法流程

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

圖4 算法流程圖

3.2 解的編碼

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

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

3.3 初始化HM及隨機生成

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

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

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

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

圖5 解的編碼示意圖

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

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

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

3.4 和聲微調(diào)

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

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

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

3.5 和聲修復(fù)

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

3.5.1 和聲修復(fù)1

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

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

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

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

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

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

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

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

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

注：臨時“前段和聲”為零向量。

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

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

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

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

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

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

步驟7將個體的前段和聲更新為臨時“前段和聲”。

3.5.2 和聲修復(fù)2

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

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

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

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

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

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

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

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

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

HMCR=179.982/(Tk+199.97)

(54)

(55)

3.7 適應(yīng)度評價

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

(56)

(57)

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

4 數(shù)值實驗

4.1 方案有效性實驗

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

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

(2)算例求解

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

圖7 收斂圖

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

表1 方案對比表

任務(wù)原始數(shù)據(jù)HAS方案RHA方案FCFS方案到達時刻貝棧層壓箱數(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目標值\\45.582.6183.4

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

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

4.2 算例求解

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

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

4.3 算法的有效性實驗

(1)不同規(guī)模下的算例比較實驗

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

表3 算法對比表

(2)不同壓箱量的算例實驗

針對每組算例，采用本文提出的算法進行求解，對比求解耗時和目標值的增長速度。

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

5 結(jié)語

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

表4 不同壓箱量對比表

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