預倒出口箱區(qū)的多場橋調(diào)度優(yōu)化

鄭紅星，王 杰，姚 琳

(大連海事大學 交通運輸工程學院，遼寧 大連 116026)

0 引言

在集裝箱碼頭中，出口集裝箱堆場的作業(yè)效率直接影響整個碼頭的服務水平，研究該類堆場的效率改進策略是當前集裝箱港口關(guān)注的核心問題之一。為此，很多碼頭常常在出口集裝箱堆場中進行預翻作業(yè)，以減少場橋在堆場中由于翻箱作業(yè)帶來的額外耗時。因此，在預倒過程中如何科學有效地安排場橋預倒作業(yè)，進而提高裝船效率，是出口箱堆場研究的熱點問題。

目前，針對堆場場橋調(diào)度問題，國內(nèi)外已有很多學者進行了深入細致的研究。鑒于場橋作業(yè)時間因素直接影響場橋作業(yè)效率，本文將已有文獻按處理時間因素的方法不同，分為以下三類：A類——不考慮場橋抓箱時間，只考慮場橋在作業(yè)過程中行走路徑的時長；B類——確定翻箱次序，場橋抓取目標箱的時長等于單獨提該箱的時間加上其翻箱時間；C類——根據(jù)經(jīng)驗翻箱，在船舶裝載時按照船舶配積載圖進行翻箱工作。

在A類文獻中，李麗麗[1]針對現(xiàn)場場橋調(diào)度問題，考慮利用最短路徑和動態(tài)規(guī)劃求解現(xiàn)場場橋調(diào)度，提出了一種組合路徑優(yōu)化算法，建立了場橋部署優(yōu)化模型，給出了基于遺傳算法的求解過程。Chang等[2]研究了單個箱區(qū)內(nèi)的雙場橋調(diào)度問題，以場橋延遲任務數(shù)最小化為目標，建立了整數(shù)規(guī)劃模型， 并設計了基于滾動時域的啟發(fā)式算法。劉新[3]針對集裝箱碼頭在不同時段的運行量，每個箱段內(nèi)實時分配現(xiàn)場場橋問題?？紤]到船舶在碼頭最前端的裝卸作業(yè)中岸橋和堆場的工作量的平衡，以減少岸橋的等待時間優(yōu)化現(xiàn)場橋資源配置為目標，建立場橋的多目標整數(shù)規(guī)劃模型，并且計算場橋運行時間的變化和最小運行完成時間。周文杰[4]研究了任務序列下的場橋路徑優(yōu)化問題，考慮每個子任務和后續(xù)操作中的場橋的五個子任務，選擇具有最小移動距離的貝位號，采用動態(tài)規(guī)劃方法建立模型并在完成所有任務后確定場橋的貝位號順序。韓曉龍等[5]結(jié)合裝載方案研究了場橋調(diào)度優(yōu)化問題，以場橋行走路徑最短為目標，建立了現(xiàn)場橋梁調(diào)度模型。李淑娟等[6]研究了場橋作業(yè)與集卡銜接優(yōu)化問題，目標使場橋和集卡之間的等待時間最短，場橋和場橋之間??的距離最短，并根據(jù)模型的特點設計了模擬退火算法。范厚明等[7]研究了出口箱箱位分配和場橋調(diào)度的分區(qū)域平衡問題，考慮了場橋間相互干涉的現(xiàn)實約束， 建立了現(xiàn)場場橋的非加載時間優(yōu)化模型，平衡了每個場橋的工作量。

在B類文獻中，鄭紅星等[8]研究了混堆箱區(qū)某一時段內(nèi)的多場橋調(diào)度問題，考慮了內(nèi)外集卡的場橋間不可跨越和保持安全距離、優(yōu)先級等因素，構(gòu)建了多場橋調(diào)度模型，同時設計了混合遺傳算法用于求解，文中各目標箱的提取操作時間不盡相同。鄭紅星等[9]研究了箱區(qū)運營成本優(yōu)化問題，以最大限度地降低可變運營成本為目標，構(gòu)建了混合模式下多箱和場橋聯(lián)合調(diào)度的非線性數(shù)學規(guī)劃模型并設計了算法求解。張笑菊等[10]針對混堆堆場的集裝箱碼頭裝船順序優(yōu)化問題，考慮船舶一個貝位的同步裝卸作業(yè)，以單臺場橋在單個箱區(qū)內(nèi)移動時間和翻箱時間最小為目標，構(gòu)建了出口集裝箱裝船順序優(yōu)化模型并設計了啟發(fā)式算法。范厚明等[11]研究了出口箱區(qū)場橋營運成本優(yōu)化問題，考慮場橋作業(yè)量均衡和場橋間安全距離，以場橋移動成本和空閑成本之和等可變營運成本最小為目標，建立集裝箱堆場箱位重分配及多場橋調(diào)度聯(lián)合優(yōu)化模型，設計了模擬退火遺傳算法，并對箱區(qū)內(nèi)不同規(guī)模的出口量進行了實驗分析。郭文文等[12]研究了出口箱裝船順序及場橋行駛路徑聯(lián)合優(yōu)化問題。以作業(yè)時間衡量裝船順序產(chǎn)生的倒箱量及場橋行駛路徑,構(gòu)建了以作業(yè)時間最短為目標的整數(shù)規(guī)劃模型,設計均衡倒箱量和場橋作業(yè)時間的啟發(fā)式算法對模型進行求解。高鵬等[13]研究了集裝箱堆場提箱作業(yè)優(yōu)化問題，在分析倒箱移動路徑的基礎上，通過倒箱搬運過程的優(yōu)化使總作業(yè)成本最小，提出了提箱作業(yè)優(yōu)化模型，并且設計了算法求解。馮媛君等[14]研究了集裝箱碼頭堆場翻箱與外集卡提箱順序同步優(yōu)化問題，以碼頭的作業(yè)成本和外集卡的延誤成本之和最小為目標，建立堆場翻箱與外集卡提箱順序同步優(yōu)化模型，優(yōu)化外集卡的提箱順序、龍門吊的任務分配以及翻箱方案。設計了基于動態(tài)規(guī)劃的啟發(fā)式算法求解模型，并利用算例對模型與算法的有效性進行了驗證。

在C類文獻中，邵乾虔[15]為解決集卡預約模式的問題，首先提出了 “動態(tài)優(yōu)先行李箱概率” 的定義并給出了其推導過程； 在此基礎上以行李箱積存最少為目標，構(gòu)建了行李箱路徑的動態(tài)優(yōu)化模型，開發(fā)了動態(tài)行李箱啟發(fā)式算法。邵乾虔等[16]針對出口箱預翻箱問題，結(jié)合出口箱堆場作業(yè)時間，建立了以最小化預翻箱量和場橋堆存作業(yè)移動距離為目標的數(shù)學模型，并給出了求解算法。王偉[17]研究多場橋調(diào)度優(yōu)化問題，考慮到箱間隔中場橋過渡的問題和反向箱因子的影響，以最小化內(nèi)置卡與懲罰因子的時間偏差為目標，構(gòu)造了一種非線性規(guī)劃模型，并設計了算法求解。初良勇等[18]研究集裝箱碼頭調(diào)度問題，據(jù)典型集裝箱的實際數(shù)據(jù)，以碼頭調(diào)度效率最高為目標，設計并驗證了基于遺傳算法的模型求解策略。董小妹等[19]研究了集裝箱翻箱優(yōu)化問題，以貝位利用率最大為目標，建立了集裝箱堆場異貝之間翻箱問題的數(shù)學模型，并選擇采用雜合啟發(fā)式算法構(gòu)造算法求解流程，尋求滿意解。

綜上，國內(nèi)外對多場橋調(diào)度的文獻中，A類文獻最多，而B類研究次之，C類文獻最少；但近年來C類文獻逐年增多，是當前相關(guān)研究的焦點之一。就研究方法而言，A類文獻以考慮場橋在作業(yè)過程中行走路徑時長最短為優(yōu)化目標，并設計相應的啟發(fā)式算法求解；但考慮經(jīng)驗翻箱影響的文獻較少，很多都未提及作業(yè)場橋的具體任務序列；而在實際裝船作業(yè)中，由于出口堆場箱區(qū)中壓箱的實際限制，且提箱需按照固定次序，多場橋協(xié)調(diào)工作時可能需在作業(yè)過程中翻箱，故翻箱的耗時對裝船的效率影響很大，很少有文獻在研究場橋調(diào)度時集成考慮該因素。B類文獻在考慮經(jīng)驗倒箱的前提下，當船舶裝載時按照配積載圖進行倒箱工作，一般以倒箱操作時間最短為優(yōu)化總目標構(gòu)建數(shù)學模型，并設計啟發(fā)式算法求解，但大多數(shù)文獻僅僅考慮單臺場橋的作業(yè)，研究多場橋調(diào)度的文獻較少。C類文獻不考慮場橋抓箱時間，只以場橋在作業(yè)過程中行走路徑最短為優(yōu)化目標來確定倒箱次序，并設計啟發(fā)式算法進行求解，但大多數(shù)忽略了操作過程中的翻箱作業(yè)時間與場橋抓箱時間。因此，本文以一初始出口集裝箱箱區(qū)為研究對象，為減少裝船時必需翻箱的耗時，在獲知配載圖后，研究如何調(diào)度多臺場橋?qū)⒋b船的集裝箱預倒至一空閑箱區(qū)效率最高，兼顧作業(yè)過程中的翻箱和落位。

另經(jīng)煙臺港、大連港和天津港等地的實際調(diào)研，為安全起見，堆場翻箱一般遵循如下經(jīng)驗規(guī)則，即：

(1)在不壓下一個待提箱的前提下，必翻箱應先放至該貝位層高最低的箱位；

(2)若該貝位最低層高不唯一，優(yōu)先向排數(shù)最高的箱位翻倒，即6排>5排>…>1排；

(3)若所提目標箱位為滿垛3層高(所有排都放滿三層)，則不向第1排和目標箱位指令相鄰的排翻倒。

區(qū)別已有文獻，本文研究的問題具有以下顯著特點：(1)考慮翻箱經(jīng)驗規(guī)則對多場橋調(diào)度的影響；(2)深入場橋調(diào)度細節(jié)，即不僅給出每臺場橋在各時間窗服務的總時長，并給出對應的具體作業(yè)貝位。(3)梳理場橋分配、目標箱優(yōu)先級和場橋調(diào)度之間的反饋關(guān)系，進而構(gòu)建相應的線性規(guī)劃模型，并設計了分支定價算法進行求解。

1 問題與模型

1.1 問題描述

在集裝箱碼頭裝船作業(yè)中，由于出口集裝箱的初始堆垛次序與船舶裝載的次序不同，且很多港口一般采用船到即卸裝的作業(yè)方式，因此常常導致大量的翻箱作業(yè)，在很大程度上影響了碼頭的裝船效率。為此，堆場時常會選擇在適當?shù)臅r機對出口箱區(qū)進行預倒，即將待出口箱提前倒至一空閑箱區(qū)，該箱區(qū)的堆垛方式為船舶配載圖的倒序；但由于碼頭作業(yè)繁忙，預倒箱區(qū)的作業(yè)效率至關(guān)重要。基于此，針對某一初始出口箱區(qū)，如何在最短的作業(yè)時間內(nèi)完成待裝船箱的預倒作業(yè)，是提高碼頭裝船效率的有效手段。

在碼頭預倒箱作業(yè)中，初始出口箱堆場的場橋調(diào)度計劃至關(guān)重要，其既要保證預倒箱作業(yè)的快速高效，又要確保場橋作業(yè)過程中的安全。為此，在預倒箱作業(yè)過程中，為確保未來裝船時不再翻箱，需按固定的提箱次序?qū)⒋b船的集裝箱倒至另一箱區(qū)，既要使作業(yè)場橋行走的路徑最短，又要嚴格遵循經(jīng)驗翻箱規(guī)則。

對于箱區(qū)中的次目標箱即壓箱的最終位置狀態(tài)，本文不予考慮。因為本文以場橋作業(yè)總行走時間最小為優(yōu)化目標建立模型，只要翻箱作業(yè)滿足經(jīng)驗規(guī)則，場橋行走時間就只與次目標箱的個數(shù)呈正相關(guān)，具有比例關(guān)系。綜上本文不予考慮。

因此，本文問題可描述為：在固定的計劃期內(nèi)，某出口箱堆場箱區(qū)提箱的配載計劃已知，將待提箱提前翻倒至一空閑箱區(qū)，使其裝船前以船舶配載圖的倒序堆垛?？紤]兩臺場橋同時作業(yè)過程中始終保持一定的距離并且不得交叉作業(yè)的現(xiàn)實約束，在滿足作業(yè)過程中多場橋調(diào)度需遵循經(jīng)驗翻箱規(guī)則，確定場橋作業(yè)過程中的貝位號序列和在相對應貝位上所需要提取的目標箱時間以及所需提取的目標箱，目標是使場橋在完成所有任務時總的行走時間最短。本文將需要進行調(diào)度的集裝箱稱為目標箱，其中，待提箱稱為主目標箱，將主目標箱上的壓箱稱為該箱的次目標箱。

以某箱區(qū)為例，其貝位展開圖如圖1示：

圖1 貝位展開圖

已知局部船舶配載圖如下所示。

圖2 船舶配載圖側(cè)視圖

圖3 船舶配載圖

經(jīng)倒箱后翻倒至一空閑箱區(qū)，使其裝船前以船舶配載圖的倒序堆垛，如下所示：

圖4 裝船前堆垛圖

1.2 模型假設

基于上述的問題描述及特征分析，下面將建立問題的整數(shù)規(guī)劃模型，模型滿足如下假設條件。

假設1貝位1為場橋1的始發(fā)節(jié)點，貝位9為場橋2始發(fā)節(jié)點。場橋可選擇任意1條從始發(fā)節(jié)點到終到節(jié)點的可達路徑，包括重復路線路徑以及翻箱作業(yè)路徑。

假設2兩臺場橋同時作業(yè)時場橋間不可跨越且保持一定安全距離，假設作業(yè)安全距離3貝。

假設3場橋在進行抓箱，移動等操作時，間隔時間緊鄰，無空余。

1.3 數(shù)學模型構(gòu)建

常量說明:Q為可直接提箱的所有目標箱的集合；Nh為第h個需要翻箱的所有節(jié)點的集合；Wj為j箱的作業(yè)時間；F為所有節(jié)點集合；P為場橋節(jié)點集合；R為子目標箱節(jié)點集合；R′為主目標箱節(jié)點集合；FZ為虛擬終點集合；m為場橋數(shù)；L為需要翻箱的個數(shù)；n為目標箱總數(shù)；Sij為場橋間安全距離；Dt為場橋間行走距離D所用的時間；M為充分大整數(shù)；M0為移動速度；Nhv為第h個需要翻箱的第v個節(jié)點集合；Dhv為第h個需要翻箱的第v個節(jié)點集合所對應到達邊數(shù)。

狀態(tài)變量說明:Pwi表示i箱所在貝位，不為箱節(jié)點則為0；Ri表示第i號節(jié)點若為主目標箱則取1，否則為0；Fti表示i箱對應場橋就緒時刻，若為非主目標箱則為M；LTik表示第k號場橋作業(yè)i箱的完成時間，若不為箱節(jié)點則取非負；Xijk表示若k號場橋由節(jié)點i移至節(jié)點j則取1，否則取0；Cijkk′表示若LTik′>LTik成立則其值取1，否則取0；Eijkk′表示若場橋k′作業(yè)i箱，同時k作業(yè)j箱發(fā)生沖突，則其值取1，否則取0；Gijkk′表示若場橋k’作業(yè)i箱，同時k作業(yè)j箱發(fā)生沖突，不足安全距離，則其值取1，否則取0；Pijkk′表示若場橋k’作業(yè)i箱，同時k作業(yè)j箱發(fā)生沖突，若k’優(yōu)先于k，則其值取1，否則取0；Bhv表示若第h個需要翻箱的第v個節(jié)點集合被遍歷，則其值取1，否則取0；xij表示若從節(jié)點i到節(jié)點j路線被占用則其值取1，否則取0。

決策變量說明:TTi為i箱對應場橋在各時間窗服務的總時長。

采用上述定義的參數(shù)和變量，問題的整數(shù)規(guī)劃模型可如下表示：

目標函數(shù)：

約束條件：

LTik≥Sij×Xijk+LTik-(1-Xijk)×Wj

(1)

(2)

Xijk=0,i∈F;k∈P

(3)

(4)

(5)

(6)

(7)

(8)

j∈Dhv,h∈L,v∈Q,i∈R,k∈P

(9)

(10)

(11)

(12)

(13)

i,j∈R,k,k′∈P

(14)

u,i,j∈R,k,k′∈P

(15)

Pwi

M+(1-Eijkk′)×M,i,j∈F,k,k′∈P

(16)

Pwi>Pwj+D-Gijkk′×M-(1-Eijkk′)×M,i,j∈F,k,k′∈P

(17)

LTik>LTik′+Wj-Cijkk′×M-Eijkk′×M,i,j∈F,k,k′∈P

(18)

LTik′=LTik-Wj-Cijkk′×

M-(1-Eijkk′)×M,i,j∈F,k,k′∈P

(19)

LTik>LTik′-Cijkk′×M,i,j∈F,k,k′∈P

(20)

LTik′=LTik-Wj-Cijkk′×M-Eijkk′×M,i,j∈F,k,k′∈P

(21)

LTik>LTik′-Wi+Wj-(1-Pijkk′)×

M-(1-Gijkk′)×M,i,j∈F,k,k′∈P

(22)

LTik

M+(1-Gijkk′)×M,i,j∈F,k,k′∈P

(23)

(24)

TTi≥0,FTi≥0,i∈F

(25)

其中：目標函數(shù)為場橋在完成任務時總的行走時間，包含裝載時間與翻箱時間；公式(1)～(3)使得場橋?qū)δ繕讼涞奶嵯渥鳂I(yè)在對應集卡就緒后進行，同時保證各臺場橋依次順序作業(yè)各目標箱的完成時刻大小關(guān)系；公式(4)～(6)滿足需要翻箱的貝位所有的主目標箱全部被場橋作業(yè)至少一次；公式(7)～(10)滿足需要倒箱的貝位所有的次目標箱全部被場橋作業(yè)至少一次；公式(11)～(13)滿足各個場橋均以其對應的場橋節(jié)點為起點；公式(14)～(15)滿足各棧位的目標箱通過場橋從上至下依次完成作業(yè)；公式(16)～(23)保證各場橋間不發(fā)生沖突，并且場橋之間不能跨越，提箱次序固定；公式(24)為目標函數(shù)的運算公式；公式(25)保證變量的取值范圍。

2 求解算法

以上述大型碼頭堆場為例，考慮碼頭對場內(nèi)有16個貝位，共有2個場橋?qū)Χ褕鰞?nèi)集裝箱進行操作。其中場橋堆場基本信息如下：跨距 6 棧，堆垛高度 5 層，移動時間 0.1 分/貝，裝載任務 3 分，倒箱需 2 分。21個目標箱，其中11個集裝箱存在壓箱現(xiàn)象。因此，該模型包括約2000個0-1變量，25000個約束，是一個大規(guī)模整數(shù)規(guī)劃模型，很難在有效的時間內(nèi)直接求得最優(yōu)解甚至可行解。因此，需要在研究問題結(jié)構(gòu)特征的基礎上，設計更加高效的求解算法。

本文采用狀態(tài)參量標記目標箱，即在所有圖中，目標箱i都有各自的狀態(tài)，文中設為(S，G，T，i)，各個元素矢量的解釋如下：

S為路徑元素：用來記錄場橋訪問過的子路徑的頂點集合。S={0,S1,S2,Si,…,SN,d},0與d為目標箱所在的位置與其堆場，路徑矢量為m+2位，為0-1變量；其中，若Sn為1時，表示此路徑被訪問過，否則為0。

G為所提箱型，所提箱分為主目標箱與次目標箱兩種類型,每種箱型有3個優(yōu)先級。

T為總時間：用于記錄所提箱的總時長，即定價子問題的目標函數(shù)值。

i表示目標箱：作為目標箱的標簽由于標記目標箱。

針對上文的模型進行分析，發(fā)現(xiàn)約束(1)～(13)與約束(14)～(23)完全無關(guān)，因此該模型可視為一個線性規(guī)劃問題。由于多場橋可選路徑數(shù)量是非常巨大的，無法一一枚舉，因此采用分支定價算法定價生成新的線性子問題，并依次求解，包含的資源約束主要是場橋的位置約束。

2.1 分支定價算法求解

本文通過Danzig-Wolfe分解原理(以下稱為“D-W分解原理”),把這兩種約束分解開，即利用凸組合定理把原來的問題轉(zhuǎn)化為主規(guī)劃問題(以下稱為“MP問題”),和若干個子問題。

通過運用D-W分解原理，可將原問題轉(zhuǎn)變?yōu)樵瓎栴}的MP問題。在目標函數(shù)已知,且上述函數(shù)的總時長與等待時長呈正相關(guān)性的情況下，滿載、翻箱時間自可知；最終時長與場橋等待時間有直接關(guān)系，并由場橋等待時間決定。因此，由目標函數(shù)

MinimizeΣi∈R′TTi

(26)

依下列規(guī)則進行轉(zhuǎn)化。

規(guī)則為將模型轉(zhuǎn)變?yōu)榧瘎澐帜Ｐ秃螅捎昧猩煞ㄇ蠼?。采用以下?guī)則進行剪枝，即表示一個頂點自然狀態(tài)的標簽時刻都在變化，其內(nèi)部的每一個元素都將發(fā)生變化，只有所有狀態(tài)滿足所有的約束均最優(yōu)，才可視為有效的標簽并保留，否則將其刪除。

例如針對同一個目標箱，其狀態(tài)時時發(fā)生變化，可能同時多個狀態(tài)滿足上述約束，如(S,G,T,i)，(S′,G′,T′,i)等；因此，本文規(guī)定：若條件(1)S≤S′，(2)T≤T′兩個條件同時成立且至少一個嚴格滿足，則認為狀態(tài)(S,G,T,i)優(yōu)化于狀態(tài)(S′,G′,T′,i)，刪除狀態(tài)(S′,G′,T′,i)；若存在多種狀態(tài)，則進行多次比較，直至找出最優(yōu)的一個狀態(tài)代入樹節(jié)點。

定義如下參數(shù)：

可得到新的子約束如下:

(27)

xij=Σt∈Txijt×Ut,?i,j∈F

(28)

(29)

將公式(27)帶入公式(28)可得:

xij=Σt∈Txijt×Ut=Σt∈TΣk∈Pxijt×Ut

(30)

TTi=xij×(Dt+Bj)

(31)

將公式(30)帶入公式(31)可得:

Σi∈R′TTi=Σi∈R′xij×(Dt+Bj)

=Σi,j∈R′(Dt+Bj)×

(32)

再定義Qt=Σt∈TΣk∈P(Dt+Bj)×xijt并代入公式(32)可得:

ΣΣi,j∈F(Dt+Bj)×xijt

=Σt∈TΣk∈PQt×xijt=Σt∈TQt×Ut

(33)

至此原問題完全轉(zhuǎn)化為MP問題。

(34)

令?it=Σj∈Fxijt，代入公式(34)可得:

(35)

最終原問題的MP問題如下:

minΣt∈TQt×Ut

(36)

s.t.Σt∈T?it×Ut=1,?i∈F

(37)

(38)

(39)

其定價子問題的約束實為對場橋行走路徑的約束，可通過其約束求等待時間。定義(36)參數(shù)如下：定義yi為目標箱i的路徑標記，若目標箱i被此路徑使用則為1，否則為0；C為此場橋所對應的檢驗數(shù)；λ1為公式(37)的對偶變量；λ2為公式(38)的對偶變量，則:c=Σi∈FTTi-Σi∈Fλiyi-λ0求解(36)最小值問題時，需找出其定價子問題檢驗數(shù)(c)為負的列，依次代入原問題，并將這些檢驗數(shù)為負的列一一加入其主問題模型，且作為樹節(jié)點加入，反復添加，直至所有的檢驗數(shù)小于0為止。最終得到如下函數(shù):

minc=Σi∈FTi-Σi∈Fλiyi-λ0

(40)

s.t.Σj∈Fxij=yi,?i∈F

(41)

Σj∈Fxji=yj,?i∈F

(42)

Σj∈Fxij=1,?i∈F

(43)

Σj∈Fxj0=1

(44)

xij∈{0,1},?i,j∈P,i≠j

(45)

yi∈{0,1},?∈P

(46)

目標函數(shù)(40)表示為原問題目標所求得的檢驗數(shù)最小的列，其定價子問題為許多個結(jié)構(gòu)基本相同，參數(shù)基變量有所區(qū)別的定價子問題所組成的。

為滿足經(jīng)驗翻箱規(guī)則，將以下目標規(guī)劃函數(shù)并入原問題中作為目標約束：

Ghl表示某個貝位中的目標箱，h表示其層數(shù)，l表示其排數(shù)，h′，l′表示變更后的層數(shù)排數(shù)，若此層此排存在箱子，則Ghl=1， 見如下目標函數(shù)作為約束并入原問題:

(47)

(48)

l′≠l-1,h,l≤3,h,l∈P

(49)

其中(48)滿足在不壓下一個目標箱的前提下，翻倒指令應先放至該貝位層高最低的箱位；若該貝位最低層高不唯一，優(yōu)先向排數(shù)最高的箱位翻到，即6排>5排>…>1排；

其中(49)滿足若所提目標箱位為滿垛3層高(所有排都放滿三層)，則不向第1排和目標箱位指令相鄰的排翻倒。

2.2 上下界的選取

本文設計貪婪算法確定上界，將所有提箱，倒箱時間依次進行排序，優(yōu)先選擇時間較短的作業(yè)；若時間相同，則選擇相隔貝位較遠的作業(yè)，將所有目標箱提出后的時間總和作為上界。

本文設計近似衡量算法確定下界，考慮主目標箱均可在集卡就緒后直接進行提箱作業(yè)(不考慮壓箱)。將解空間進行放大，保證同貝同棧情況被合理轉(zhuǎn)化，并且轉(zhuǎn)化后作業(yè)全部箱所需的總時間變少或不變，求得時間總和即為下界。

下界的解空間是原問題解空間的子集，使得下界最優(yōu)值必位于原問題最優(yōu)解之下或與之相同；同貝同棧情況下，適當原問題減少約束條件，保證轉(zhuǎn)化后作業(yè)全部箱所需的總時間變少或不變，因此本文給出的下界一定是原問題下界。

2.3 算法流程

分支定價法外部是分支定界法，內(nèi)部是列生成法，把大型的線性規(guī)劃問題分解為MP問題，再求解有范圍的MP問題(稱為“RMP問題”)。通過求解RMP問題產(chǎn)生的新的子列，進而求解大型的線性規(guī)劃問題以下列出了分支定價法的流程：

Step1初始化搜索樹，加入根節(jié)點，在計算過程中選取根節(jié)點用此根節(jié)點的信息對RMP問題進行初始化，然后通過列生成法解決RMP問題得到對偶變量，轉(zhuǎn)到step1。

Step2根據(jù)對偶變量解決定價子問題，檢查檢驗數(shù)是否小于0，如果是，則重新選擇新的節(jié)點并刪去此節(jié)點，否則，再檢查RMP問題的解是否為整數(shù)如果為整數(shù)，轉(zhuǎn)到step2。

Step3把RMP問題的解與上界對比若比上界小則更新上界，并進行剪枝操作，否則進行分支并把當前節(jié)點從搜索樹中刪去，把子節(jié)點加入搜索樹，轉(zhuǎn)到step3。

Step4再檢驗搜索樹是否為空，如果為空，則結(jié)束，如果不為空，則在搜索樹上選取節(jié)點，重新操作，回到step1。

具體步驟圖如下所示：

圖5 算法步驟

3 算例分析

3.1 方案求解

在出口箱堆場某箱區(qū)中，已知計劃期內(nèi)(據(jù)天津港等地的實地調(diào)查數(shù)據(jù)可知，場橋作業(yè)計劃約1h滾動一次，故本文取計劃期為1h)。結(jié)合港口實地調(diào)查數(shù)據(jù)以及適應度評價公式的特點，本文所有的實驗都運行在3.10GHz Intel Core 2 CPU和4GB內(nèi)存的雙核計算機上，采用Python 3.6.5進行編碼。經(jīng)計算本文所運用的分支定價算法結(jié)果如表1所示：

表1 實驗結(jié)果

場橋路徑為：場橋1:貝位5→貝位1→貝位5→貝位2→貝位8→貝位3→貝位4→貝位7→貝位4→貝位5

場橋2:貝位12→貝位9→貝位10→貝位11→貝位12→貝位13→貝位16→貝位15→貝位14

最終總等待時長為74分鐘

3.2 方案對比

為驗證本文方法得到場橋作業(yè)方案的有效性，分別同采用先到先服務方案和不考慮實時預翻箱的文獻[9]中方案進行對比分析，如表2所示?？梢钥闯?，F(xiàn)CFS方案的目標值最大，場橋作業(yè)總等待時間最長；不考慮實時預翻箱的RHA方案效果居中，較FCFS方案好，但是改進有限；本文給出的分支定價方案效果最好，總等待時間較RHA方案降低10.4%。

表2 方案對比

分支定價算法求解中規(guī)模算例的實驗結(jié)果：

表3 方案評價

本文加大問題規(guī)模以證明算法的可行性。將貝位數(shù)加大分別為16、20、24、28個，將場橋數(shù)分別增加為2、3、4、5個，求得實驗結(jié)果并觀察運算速度如表3所示。

隨著問題規(guī)模的加大，分支節(jié)點增多，計算時間也有所增加。主要由于大規(guī)模的算例限制主問題和價格子問題的規(guī)模也變大，因而更難求解。

不同壓箱量的算例實驗如表4所示：

表4 實驗評價

從表4可以看出，在10個算例中，目標函數(shù)值和求解耗時都隨著壓箱量的增加而增加，且對于總時間的影響因素較大。目標值于壓箱量從32到34時有一個突增點，這是由于在壓箱量為34時，隨著主目標箱及提箱時刻分布的不同，場橋的運作超過極限，全部處于忙碌狀態(tài)。而求解耗時增加較為平緩，表明算法求解時間相對穩(wěn)定，沒有隨壓箱量的增加而成指數(shù)型增長。

單貝位壓箱量對實驗結(jié)果的影響如表5所示：

表5 實驗評價

從表5可以看出，單貝位的壓箱數(shù)的增加對于總時間影響因素較小；在壓箱數(shù)為4時突增，這是由于目標箱壓于最底層，翻箱次數(shù)較多引起的。

4 結(jié)語

(1)針對預翻出口箱區(qū)的多場橋調(diào)度優(yōu)化問題，構(gòu)建了以場橋作業(yè)總行走時間最小為優(yōu)化目標的線性規(guī)劃模型，以實施預翻作業(yè)的某一出口箱區(qū)為研究對象，在待提箱作業(yè)次序已知的前提下，考慮作業(yè)場橋間保持安全距離且不可跨越，以及滿足翻箱經(jīng)驗規(guī)則等現(xiàn)實約束，側(cè)重作業(yè)過程中實時翻箱，揭示了多場橋調(diào)度優(yōu)化對堆場翻倒操作系統(tǒng)作業(yè)效率的巨大影響，有助于縮短預倒作業(yè)時間，進而提高裝船效率。

(2)針對模型規(guī)模較大的特點，設計了分支定價算法進行求解：首先利用列生成法和D-W分解原理通過剪枝來獲得滿足約束條件的節(jié)點，然后將原問題轉(zhuǎn)變?yōu)榈葍r的主問題和若干子問題，最后采用貪婪算法與近似衡量算法確定上下界；相較于其它文獻的啟發(fā)式算法，該算法在時間上有較大的優(yōu)勢，且其改進策略具有較強的適用性，可為其他類似問題的求解提供參考。

(3)算例實驗結(jié)果表明，隨著貝位數(shù)的增多，調(diào)度的總時間呈正增長趨勢；隨著場橋數(shù)的增多，調(diào)度的總時呈負增長趨勢，但下降趨勢較慢；隨著壓箱數(shù)量的增加，調(diào)度總時間明顯增加，且上升趨勢較快，目標箱均在最底層時，時間最長；貝位分布越緊密，增加場橋數(shù)可明顯提高效率，但場橋數(shù)量不宜超過3臺。因此，在碼頭堆場實際作業(yè)中，為更有效的進行預倒箱作業(yè)，可在集港時盡量將等待裝載到一艘船的集裝箱集中放置，盡可能避免將其堆放于底層，且每個待預倒箱區(qū)配置2～3臺場橋為宜。

在未來的研究中，本算法可用于研究內(nèi)集卡、場橋和岸橋集成調(diào)度的實時預翻箱優(yōu)化問題。