不確定條件下基于前攝反應的箱區(qū)間多場橋調(diào)度

沈 磊，朱 瑾

（上海海事大學 物流科學與工程研究院,上海 201306）

0 引言

集裝箱吞吐量逐年增長，集裝箱船舶趨于大型化和高速化對碼頭的裝卸效率提出了更高的挑戰(zhàn)。隨著自動化程度的提高，目前港口運營的關鍵從岸邊轉向堆場[1]，場橋作為堆場的核心裝卸設備，如果調(diào)度不合理可能會導致堆場倒箱率上升，碼頭交通擁堵，拖延船舶在港時間。因此，對場橋調(diào)度問題的研究已經(jīng)成為提高碼頭綜合服務能力的重要課題。

目前，國內(nèi)外學者對集裝箱碼頭場橋調(diào)度問題進行了大量研究，大體可以分為兩類：一類是單箱區(qū)內(nèi)的場橋調(diào)度問題，該類文獻的重點都放在貝位或任務箱的被服務順序上；另一類是箱區(qū)間的場橋調(diào)度問題，該類文獻的重點主要放在場橋的分配和轉場優(yōu)化上。文獻[2]把單箱區(qū)內(nèi)的雙場橋調(diào)度問題建模為具有優(yōu)先級約束的非對稱廣義旅行商問題。文獻[3]針對單箱區(qū)內(nèi)的雙場橋調(diào)度問題，全面考慮了非交叉穿越和作業(yè)量平衡等現(xiàn)實約束，重點研究了同裝同卸問題，設計算法對集裝箱任務動態(tài)處理時間進行了計算。文獻[4]在文獻[3]的基礎上，將單個箱區(qū)內(nèi)的雙場橋調(diào)度問題擴展到相鄰箱區(qū)間的三個場橋調(diào)度，在考慮場橋轉場優(yōu)的同時，討論了集裝箱任務處理時間隨調(diào)度順序動態(tài)變化的情況。上述文獻都是在確定性環(huán)境下展開，然而在實際的生產(chǎn)過程中，場橋作業(yè)會受到多種復雜的不確定性因素的影響，比如船舶到港時間延遲，場橋故障，人員操作失誤等。這些不確定性因素會嚴重降低場橋作業(yè)的效率，甚至導致預先制定的調(diào)度方案不可行。因此，提高調(diào)度方案在不確定環(huán)境下的抗干擾能力對碼頭整體的運營管理至關重要。

文獻[5]從連續(xù)時間的角度分析緊急集裝箱任務干擾下的場橋調(diào)度問題，引入滾動窗口的策略將動態(tài)調(diào)度問題分解成靜態(tài)調(diào)度問題進行局部優(yōu)化。文獻[6]針對單個箱區(qū)內(nèi)的單場橋調(diào)度問題，重點考慮卸箱作業(yè)到達時間不確定的情況，以延遲量之和的期望為目標，建立了一個兩階段隨機規(guī)劃模型。文獻[7]研究了任務箱組到達時間和處理量不確定條件下的多場橋調(diào)度問題，著重計算了由于調(diào)整初始調(diào)度而產(chǎn)生的額外損失，設計了一種基于遺傳算法框架的三階段算法來進行求解。以上3篇文獻考慮了不確定因素的影響，但研究的都是一個或多個同種類型的不確定因素，實際場橋調(diào)度過程中往往同時面臨多種類型不確定因素的干擾，如何有效處理不同復雜擾動組合，使之接近生產(chǎn)管理實際，對提高場橋作業(yè)效率有著重要的現(xiàn)實意義。

按照不確定性擾動處理策略的劃分方式，現(xiàn)有研究中的不確定調(diào)度方法主要分為前攝性調(diào)度和反應性調(diào)度兩種。前攝性調(diào)度通過預估調(diào)度過程中可能出現(xiàn)的不確定因素，生成具有魯棒性的初始調(diào)度方案來吸收可預測不確定因素的影響以增強計劃彈性；反應性調(diào)度則針對執(zhí)行過程中出現(xiàn)的突發(fā)干擾進行實時響應，然而前攝性調(diào)度和反應性調(diào)度作為兩個獨立的方法，任何一種方法都無法單獨地處理所有的不確定性。前攝反應決策框架將主動模式下的離線調(diào)度和反應模式下的在線實時調(diào)度相結合，能夠更好地處理多種類型不確定因素的影響，保證調(diào)度計劃的順利執(zhí)行。文獻[8]基于魯棒反應式策略將不確定環(huán)境下的泊位和岸橋聯(lián)合調(diào)度問題分成兩階段來處理，在預調(diào)度階段，通過預留緩沖時間的方法制定魯棒調(diào)度計劃；執(zhí)行階段針對兩個子問題分別設計了兩種不同的策略來應對突發(fā)不確定的干擾。同樣面對集裝箱碼頭泊位和岸橋協(xié)同調(diào)度的困難，文獻[9]提出一種前攝調(diào)度計劃和與之匹配的反應策略相結合的決策框架，先在前攝計劃中采用冗余策略來緩解船舶到港時間不確定的影響，在反應階段，針對不確定信息的實際情況，采用反應策略映射函數(shù)進行修正，并設計雙層決策結構算法進行求解。以上2篇文獻都將前攝反應框架引用到泊位岸橋集成調(diào)度問題中來，并得到了較優(yōu)的調(diào)度方案。但是目前該方法還尚未在場橋調(diào)度中得到運用。因此，本文以多箱區(qū)間的多場橋調(diào)度為對象，綜合考慮任務箱組到達時間、任務箱組待處理量的不確定以及新任務箱組隨機到達兩種類型的不確定因素對于場橋調(diào)度計劃的影響，提出一種基于前攝反應決策框架的兩階段模型并設計改進的離散人工蜂群算法進行求解。

1 問題描述

場橋調(diào)度問題的核心可以歸結為兩部分決策，即1）每個集裝箱任務被分配的場橋和被服務的順序；2）每個集裝箱任務的開始被服務時間。本文研究的是涉及轉場操作的多箱區(qū)間多場橋調(diào)度問題，重點考慮不確定因素的處理，為減小計算復雜度，引入文獻[10]中任務箱組的概念，將來自同一條船舶的集裝箱任務或處于同一堆塊相鄰貝位間可以被集中裝卸的一批集裝箱任務定義為一個任務箱組，不考慮翻箱操作的問題，任務箱組作為場橋的最小作業(yè)單位，堆場布局如圖1所示。

圖1 集裝箱碼頭堆場布局

在港口碼頭中，船舶到港時間的延遲會導致進口箱堆存任務到達時間的延遲，而外部集卡到達時間的不確定可能會導致出口箱卸箱任務到達時間的波動；另一方面，船舶裝卸量和客戶需求量的不確定性會導致堆場裝卸集裝箱任務箱組處理量的波動，因此，針對可預測的不確定因素，本文考慮了任務箱組到達時間和任務箱組處理量的不確定情況。同時，針對不可預測的突發(fā)擾動，考慮新任務箱組隨機到達的情況。

區(qū)別于其他文獻，本文提出了一種基于前攝反應決策框架的兩階段模型來求解以上兩種類型的不確定因素干擾下的箱區(qū)間多場橋調(diào)度問題。在前攝階段，主動地考慮兩個可預測不確定因素的影響，采用場景分析[11]的方法來描述兩個可預測不確定因素，通過有限數(shù)量的離散場景來枚舉動態(tài)環(huán)境中可能出現(xiàn)的各種情形，建立不確定調(diào)度模型，得到一個具有抗干擾性的初始調(diào)度方案；反應階段，場橋在執(zhí)行初始調(diào)度方案的過程中，可能會面臨新任務箱組隨機到達的突發(fā)干擾，此時，以突發(fā)干擾時刻作為觸發(fā)點，對初始魯棒調(diào)度方案中尚未開始處理的任務箱組和新到達的任務箱組進行重調(diào)度，為了提高調(diào)度方案的穩(wěn)定性，避免重復調(diào)整帶來額外損失，本文在優(yōu)化任務箱組處理延遲時間的同時，考慮重調(diào)度方案和初始方案差異程度的穩(wěn)定性測度，減少擾動后因頻調(diào)整調(diào)度方案而帶來的額外損失。

2 數(shù)學模型

2.1 模型假設

1）初始時刻，所有場橋均處于空閑狀態(tài)，即可被調(diào)配到目標任務箱組位置進行裝卸操作；且初始時刻，所有場橋的初始位置已知；

2）每個集裝箱任務的裝卸時間已知，均為一個固定常量；每個任務箱組的處理時間由任務箱組所包含的集裝箱任務數(shù)量所決定；

3）堆場內(nèi)所有場橋的裝卸效率一致，場橋移動速度相同；

4）待處理任務箱組位置確定；每個任務箱組的到達時間和包含的集裝箱數(shù)量在初始調(diào)度計劃制定期間是不確定的。

2.2 符號定義

本文使用的符號及說明如表1所示。

表1 符號定義

前攝階段調(diào)度模型

目標函數(shù)

約束條件

式(1)為前攝階段的目標函數(shù)，在優(yōu)化所有任務箱組完成時間延遲量之和的期望性能目標的同時，通過方差來抑制調(diào)度性能在不同場景下的波動，反映了質(zhì)量魯棒性指標；約束(2)、(3)描述了決策變量πi(ω)、μi(ω)和εi(ω)之間的關系；約束(5)表示場橋的開始處理時間不能早于任務箱組的到達時間；約束(6)反映處理序列中相鄰任務箱組開始被服務時間之間的關系；約束(7)、(8)表示每個任務箱組均被分配給唯一的場橋進行處理且只處理一次；約束(9)描述了場橋作業(yè)的單向性；約束(10)確保了場橋作業(yè)的連續(xù)性；約束(11)、(12)為決策變量的取值范圍。

反應階段調(diào)度模型

目標函數(shù)

約束條件

式(13)為反應階段的目標函數(shù)，以初始調(diào)度方案和重調(diào)度方案中任務箱組完成時間的偏差作為穩(wěn)定性優(yōu)化度量，減少因重調(diào)度而產(chǎn)生的額外損失，體現(xiàn)了解魯棒性指標；約束(14)、(15)對重調(diào)度方案中任務箱組的開始被服務時間進行了約束；約束(16)對干擾發(fā)生時刻正在處理任務箱組的場橋進行了限制；約束(17)～(23)類似于前攝階段的約束(6)～(12)。

3 模型求解

不確定條件下箱區(qū)間多場橋調(diào)度問題可以看成是一個考慮不確定因素影響的帶時間窗的VRP問題，根據(jù)本文第二節(jié)提出的數(shù)學模型，如果場橋待處理任務箱組的到達時間和處理量信息只存在一種場景的話，那么該問題可以簡化為經(jīng)典的確定條件下箱區(qū)間多場橋調(diào)度問題，而這類問題已經(jīng)被證實是一個NP難問題[12]。通常情況下，針對確定環(huán)境下的大規(guī)模箱區(qū)間多場橋調(diào)度問題，采用精確算法或者ILOG CPLEX等通用軟件求解器很難在較短的CPU時間內(nèi)進行求解，更不用說考慮多種不確定因素的箱區(qū)間多場橋調(diào)度問題。人工蜂群算法框架簡單，靈活性好，具有較高的尋優(yōu)效率，近年來廣泛應用于組合優(yōu)化和生產(chǎn)調(diào)度等領域。因此，本文在基本ABC算法的基礎上，結合不確定條件下箱區(qū)間多場橋調(diào)度問題的特點，設計了改進的離散人工蜂群算法對模型進行求解，具體算法如下。

3.1 蜜源編碼

在人工蜂群算法中，蜜源的位置對應問題解空間中的一個可行解，由于基本ABC算法的連續(xù)性，在將其應用于組合優(yōu)化問題時需要將其離散化。本文采用基于調(diào)度順序的兩部分實數(shù)編碼，第一部分表示場橋待處理任務箱組的編號，編號的順序代表任務箱組被服務的順序，第二部分代表場橋的作業(yè)量。如圖2所示為3個場橋處理10個任務箱組的編碼示例。

圖2 基于調(diào)度順序的兩部分編碼

3.2 初始化階段

場橋在任意兩個任務箱組間的移動時間是影響任務箱組開始處理時間和調(diào)度決策的重要因素。為了保證初始蜜源的質(zhì)量和多樣性，首先采用一種直覺規(guī)則的方法來構造一個初始可行解，隨機分配n個任務箱組作為n個場橋的初始作業(yè)任務，以每個場橋的初始任務箱組作為起始點，依據(jù)NTF（Nearest Task First）規(guī)則[13]將剩余的任務箱組分別分配給相應的場橋，從而得到一個初始蜜源個體。對于剩余的蜜源個體采用隨機生成的方法構造，直至滿足蜜源規(guī)模SN。

3.3 自適應鄰域搜索

在標準ABC算法中，跟隨蜂只是對當前解的鄰域進行單一的局部搜索，搜索效率低且隨機性較大，算法收斂時間長。在保持種群多樣性的同時，為提高跟隨蜂階段探索能力，擴大搜索空間，本文設計了包含兩點交換、插入、逆序、位置交叉四種鄰域結構的自適應鄰域搜索策略來產(chǎn)生新解，四種鄰域結構如圖3所示。自適應鄰域搜索的具體操作步驟描述如下：

圖3 四種鄰域結構

1) 確定4種鄰域結構{N1，N2，N3，N4}作為擾動和鄰域深度搜索的鄰域集合；構造鄰域結構向量EV和進化解集合Pitr，EV的長度設置為鄰域結構的數(shù)目，初始時刻EV為4種鄰域結構的隨機排序，Pitr=φ；初始化參數(shù)：設置最大循環(huán)代數(shù)Maxitr和初始蜜源u0，令計數(shù)器k=0，最優(yōu)解uB=u0。

2) 對最優(yōu)解uB進行擾動，即在當前鄰域范圍內(nèi)對uB實施一次隨機的鄰域動作，得到解u'。

3) 從EV中依次選取對應的鄰域結構，采用一步更新原則生成當前個體u'的一個鄰域解u"，比較鄰域解u"和最優(yōu)解uB的優(yōu)劣，若f（u"）＜f（uB），則保留當前鄰域結構，同時將u"存入Pitr，即Pitr=Pitr∪{u"}；否則，將當前鄰域結構從EV中刪除。重復上述操作直至EV中所有的鄰域結構都選取完畢。

4) 更新最優(yōu)解：用Pitr集合中目標值最優(yōu)的解作為當前最優(yōu)解，即uB=u1，u?u1，u2∈Pitr，f（u1）＜f（u2）

5) 更新鄰域結構向量EV：若EV不為空，且尚未填滿，以0.75的概率從保留的鄰域結構中選擇填充，以0.25的概率隨機選擇鄰域結構填充，直至空位填滿；若EV為空，則以原有鄰域結構的一個隨機排列設置當前鄰域結構向量，k=k+1。

6）若達到最大循環(huán)代數(shù)Maxitr，則輸出最優(yōu)解uB；否則跳轉至2）繼續(xù)執(zhí)行。

上述流程中，2）～6）為自適應鄰域搜索過程，通過鄰域結構向量EV的實時更新，算法可以根據(jù)對各鄰域結構搜索結果的分析，自適應地選擇較好的鄰域進行搜索，提高搜索效率；進化解集合Pitr搜集每次循環(huán)中的所有優(yōu)化解進行綜合評價，能夠有效避免一些重復和無效搜索。

3.4 干擾發(fā)生時刻場橋位置時間信息更新

反應階段，面對新任務箱組隨機到達的突發(fā)干擾，需要及時調(diào)整初始調(diào)度方案，合理地安排新任務箱組在調(diào)度方案中的順序。針對尚未開始執(zhí)行的任務箱組和新到達的任務箱組進行重調(diào)度的前提是獲取干擾發(fā)生時刻各場橋的位置和時間信息。

新任務箱組到達時刻t，場橋可能處于四種狀態(tài)，如表2所示，場橋處于狀態(tài)(1)、(3)、(4)時的位置和時間信息很容易得到。

表2 不同狀態(tài)下場橋的位置和時間信息

本節(jié)重點給出場橋位于狀態(tài)(2)，即前往下一個待處理任務箱組的途中，場橋位置信息的計算過程，具體步驟如下：

1) 反應階段，初始魯棒調(diào)度方案中所有任務箱組的信息確定，根據(jù)該場橋調(diào)度序列中所有任務箱組的完成時間信息，找出干擾發(fā)生前完成時間（TC）最接近干擾時刻t的任務箱組R1，TCR1=max{TC|TC≤t}。

2) 根據(jù)最短路徑原則，得到初始調(diào)度方案中場橋從任務箱組R1移動到下一個待處理任務箱組位置的路徑P。

3) 以任務箱組R1位置為起點，計算場橋沿著路徑P移動（t-TCR1）時間所到達的位置L，L即為干擾發(fā)生時刻場橋前往下一個待處理任務箱組途中的位置信息。

3.5 算法總體流程

圖4 算法流程圖

4 數(shù)值實驗

4.1 算法參數(shù)設置

為驗證本文所提出的兩階段模型的有效性和IDABC算法的性能，設計了一系列數(shù)值實驗并與其他優(yōu)化算法和啟發(fā)式規(guī)則進行對比。采用MATLAB編程，在Intel Core i51.80GHz CPU，8GB內(nèi)存電腦上運行。IDABC算法的具體實驗參數(shù)設置如下：SN=50，Limit=50，maxCycle=600。本實驗針對某集裝箱碼頭固定時段內(nèi)（2h）堆場的16個箱區(qū)進行研究，每個箱區(qū)有40個貝位。堆場布局如圖1所示。

4.2 不同任務規(guī)模下的對比實驗

1）前攝階段

通過不同任務箱組規(guī)模下的實驗，進一步驗證所提IDABC算法在前攝階段處理兩個可預測不確定因素的優(yōu)越性，并與GA和標準ABC進行對比（考慮到文獻[7]也研究了任務箱組到達時間和任務箱組待處理量的不確定，故任務箱組和場橋信息參考文獻[7]中的table1，table2，5種場景下的任務箱信息參考table3）。為減少偶然誤差，保證結果真實準確，每個算例運行10次，實驗結果如表3所示。對于3*5和4*6的兩組小規(guī)模算例，上述幾種算法均能夠在較短CPU時間內(nèi)獲得最優(yōu)調(diào)度方案，方案總延遲量為8.72，12.74。隨著任務箱組和場橋數(shù)量的增加，解空間規(guī)模呈指數(shù)級增長，從中等規(guī)模算例3～5和大規(guī)模算例6～8的結果可以看出，雖然標準差差別不大，算法求解的穩(wěn)定性相對于小規(guī)模算例有所下降，但IDABC算法求得的近似最優(yōu)調(diào)方案要明顯優(yōu)于GA算法和標準ABC算法，任務箱組的總延遲量相較于GA平均降低10.53%，相較于標準ABC平均降低15.38%，體現(xiàn)了IDABC算法在求解兩種可預測不確定時的優(yōu)越性。IDABC算法求解算例1的近似最優(yōu)解收斂效果如圖5所示。

表3 前攝階段實驗結果對比

圖5 收斂圖

2）反應階段

反應階段的重調(diào)度是在前攝階段初始魯棒調(diào)度的基礎上進行的，為驗證本文所提方法在處理突發(fā)干擾（即新任務箱組隨機到達的情況）時的有效性，設計了幾組不同批量和到達時間的突發(fā)干擾，新任務箱組到達時間和處理量如表4所示。

表4 新任務箱組到達時間

在集裝箱碼頭實際作業(yè)中，場橋調(diào)度問題大都采用先到先服務（First Come First Service，F(xiàn)CFS）的原則，本實驗選取3種規(guī)模的初始調(diào)度方案，分別采用FCFS、文獻[6]涉及的NTF+EDD（Nearest Task First and Earliest Due Date）啟發(fā)式規(guī)則和本文所提出的IDABC算法對上述6個突發(fā)干擾案例進行求解，實驗結果對比如表5所示，表中DEV代表重調(diào)度方案和初始調(diào)度方案中任務箱組完成時間的偏差，用于衡量調(diào)度方案的穩(wěn)定性。偏差過大會導致碼頭調(diào)度人員頻繁地調(diào)整調(diào)度方案，產(chǎn)生額外的損失，如場橋額外移動成本等。

圖6顯示了三種方法求解以上6個算例的總延遲量，隨著算例規(guī)模的增大，顯然在面對多批次不同時段的連續(xù)干擾時，IDABC算法的優(yōu)勢更加明顯。從表5中可以看出，IDABC算法求得的新調(diào)度方案相對于初始調(diào)度方案的偏差更小，重調(diào)度后方案的穩(wěn)定性更好，進一步驗證了本文所提出方法的有效性與優(yōu)越性。

表5 不同初始調(diào)度規(guī)模下的重調(diào)度結果對比

圖6 不同實驗下的總延遲量對比

5 結語

面對復雜多變的港口環(huán)境，本文針對集裝箱碼頭場橋調(diào)度過程中可能出現(xiàn)的兩種類型的不確定因素，考慮了任務箱組到達時間、任務箱組待處理量的不確定以及新任務箱組隨機到達的情況，并根據(jù)它們對調(diào)度計劃影響程度的不同，提出一種基于前攝反應框架的兩階段模型，旨在獲取能夠同時應對多種類型不確定因素干擾的魯棒調(diào)度方案，為不確定條件下場橋調(diào)度計劃的制定提供決策支持。設計了改進的離散人工蜂群算法對模型進行求解，通過不同規(guī)模的數(shù)值實驗驗證了IDABC算法在處理以上兩種類型不確定因素時的穩(wěn)定性和優(yōu)越性。

本研究重點考慮不確定因素的處理，對非交叉穿越等現(xiàn)實約束進行了理想假設。此外，前攝反應框架中前攝階段調(diào)度與反應階段調(diào)度在應對不確定因素干擾過程中存在的權衡關系直接影響調(diào)度方案解的魯棒性和質(zhì)量魯棒性，對于場橋調(diào)度管理意義重大，需要進一步深入研究。