不確定條件下基于前攝反應的箱區間多場橋調度

沈 磊，朱 瑾

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

0 引言

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

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

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

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

1 問題描述

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

圖1 集裝箱碼頭堆場布局

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

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

2 數學模型

2.1 模型假設

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

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

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

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

2.2 符號定義

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

表1 符號定義

前攝階段調度模型

目標函數

約束條件

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

反應階段調度模型

目標函數

約束條件

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

3 模型求解

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

3.1 蜜源編碼

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

圖2 基于調度順序的兩部分編碼

3.2 初始化階段

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

3.3 自適應鄰域搜索

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

圖3 四種鄰域結構

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

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

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

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

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

6）若達到最大循環代數Maxitr，則輸出最優解uB；否則跳轉至2）繼續執行。

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

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

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

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

表2 不同狀態下場橋的位置和時間信息

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

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

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

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

3.5 算法總體流程

圖4 算法流程圖

4 數值實驗

4.1 算法參數設置

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

4.2 不同任務規模下的對比實驗

1）前攝階段

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

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

圖5 收斂圖

2）反應階段

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

表4 新任務箱組到達時間

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

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

表5 不同初始調度規模下的重調度結果對比

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

5 結語

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

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