集裝箱碼頭岸橋突發(fā)故障情況下裝卸船作業(yè)重調(diào)度研究

夏孟玨 史學(xué)鑫 李美貞

摘要：為解決在集裝箱碼頭岸橋突發(fā)故障情況下裝卸船作業(yè)的快速重調(diào)度問題，考慮故障岸橋?qū)ζ渌稑蜃鳂I(yè)的時空約束，在滿足作業(yè)安全和作業(yè)順序的要求下，以最小化最大完工時間為目標，構(gòu)建裝卸船作業(yè)重調(diào)度序貫決策模型。為求解該模型，對基于離散事件仿真的蒙特卡洛樹搜索（Monte Carlo tree search， MCTS）算法進行改進。仿真實驗證明，提出的裝卸船作業(yè)重調(diào)度方法有效，能夠保證在岸橋突發(fā)故障情況下裝卸船作業(yè)的有序進行。

關(guān)鍵詞：

岸橋調(diào)度; 不確定性; 重調(diào)度; 岸橋故障; 蒙特卡洛樹搜索（MCTS）算法

中圖分類號：? U691+.3

文獻標志碼：? A

Study on handling operation rescheduling under sudden

malfunction of container terminal quay cranes

XIA Mengjue1a， SHI Xuexin1b， LI Meizhen2

（1. a. Institute of Logistics Science & Engineering; b. Logistics Engineering College， Shanghai Maritime

University， Shanghai 201306， China; 2. Xiamen Container Terminal Group Co.， Ltd.， Xiamen 361006， Fujian， China）

Abstract：

In order to solve the problem of rapid rescheduling of handling operation under sudden malfunction of container terminal quay cranes， the time and space constraints of the malfunctioning quay cranes on the other quay crane operations are considered， and a sequential decision model of handling operation rescheduling is built to minimize the maximum completion time under meeting the requirements of operation safety and operation sequence. To solve the model， the Monte Carlo tree search （MCTS） algorithm based on discrete event simulation is improved. Simulation experiments prove that the proposed handling operation rescheduling method is effective and ensures the orderly handling operation under sudden malfunction of container terminal quay cranes.

Key words：

quay crane scheduling; uncertainty; rescheduling; quay crane malfunction; Monte Carlo tree search （MCTS） algorithm

0 引 言

岸橋作為集裝箱碼頭最終完成裝卸船作業(yè)的輸出端設(shè)備，其裝卸作業(yè)效率直接決定了集裝箱碼頭的輸出峰值效率。因此，在作業(yè)過程中對岸橋進行合理調(diào)度，保持全岸線岸橋作業(yè)分配均衡對提升集裝箱碼頭生產(chǎn)作業(yè)效率具有重要的現(xiàn)實意義[1]。

國內(nèi)外學(xué)者對岸橋調(diào)度問題進行了系統(tǒng)且較為深入的研究。在確定條件下，KASM等[2-3]以最小化服務(wù)時間為目標，分別提出非穿越條件下單40英尺（1英尺=0.304 8 m）和雙40英尺岸橋調(diào)度的混合整數(shù)規(guī)劃模型，并提出一種分步啟發(fā)式算法進行求解。SUN等[4]提出基于Benders分解框架的新方法解決岸橋調(diào)度問題。LIANG等[5]建立了岸橋分路計劃和岸橋作業(yè)計劃耦合模型，并提出一種循環(huán)迭代方法進行求解。MSAKNI等[6]提出以具體的集裝箱為決策單元的岸橋調(diào)度問題，以最小化停泊時間為目標建立岸橋調(diào)度模型，并提出一種構(gòu)造啟發(fā)式算法進行求解。部分學(xué)者還提出邊界二級動態(tài)規(guī)劃算法、拉格朗日松弛算法等[7-8]對岸橋調(diào)度問題進行求解。

目前對確定條件下的岸橋調(diào)度問題研究較多，而實際上由于集裝箱碼頭作業(yè)系統(tǒng)的復(fù)雜性，以及極端天氣、船期變動、設(shè)備故障等不確定因素，裝卸船作業(yè)過程會受到影響。這些不確定因素可分為漸變不確定因素和突變不確定因素。針對漸變不確定因素，周鵬飛等[9]研究了在船舶抵港時間不確定條件下，以最小化船舶平均等待時間為目標的碼頭泊位岸橋分配問題，并設(shè)計遺傳算法進行求解。侯艷芬[10]研究了服務(wù)時間可變條件下相鄰泊位的岸橋動態(tài)調(diào)度問題，建立集裝箱排隊模型和岸橋調(diào)度仿真模型，通過案例仿真分析岸橋調(diào)度策略。張思等[11]研究了作業(yè)時間不確定條件下的岸橋調(diào)度問題，建立不確定作業(yè)時間的岸橋調(diào)度混合整數(shù)隨機規(guī)劃模型，并通過對比粒子群優(yōu)化算法與禁忌搜索算法對不同規(guī)模算例的求解效果發(fā)現(xiàn)，粒子群優(yōu)化算法對大規(guī)模算例的求解效果優(yōu)于禁忌搜索算法的求解效果。

在影響裝卸船作業(yè)的突變不確定因素中，岸橋突發(fā)故障以其不可預(yù)測性和突發(fā)性直接影響集裝箱碼頭全岸線岸橋作業(yè)分配均衡，這就需要對現(xiàn)有調(diào)度方案進行較大的調(diào)整，即需要進行裝卸船作業(yè)重調(diào)度。目前，在其他領(lǐng)域已有針對設(shè)備故障情況下重調(diào)度問題的研究[12-14]，而針對集裝箱碼頭設(shè)備故障發(fā)生后重調(diào)度問題的研究較少。

針對不確定決策問題，常采用隨機規(guī)劃方法[15]、模糊規(guī)劃方法、魯棒優(yōu)化方法[16]和序貫決策方法進行建模。馬爾科夫決策過程（Markov decision process，MDP）作為序貫決策的一種條件特例，常用于帶有不確定因素的動態(tài)控制問題的決策過程描述[17]。

綜上所述，目前研究多聚焦于確定條件下的岸橋調(diào)度問題，部分研究雖關(guān)注不確定條件下的岸橋調(diào)度問題，但對顯著影響裝卸船作業(yè)進程的突發(fā)岸橋故障情況下的岸橋調(diào)度問題研究較少。已有研究多采用的混合整數(shù)規(guī)劃模型和智能算法能夠在單船決策中取得較好的效果，而對決策效率要求較高的岸橋突發(fā)故障情況下全岸線岸橋重調(diào)度問題可能存在決策效率低和決策效果不佳等問題。因此，本文針對集裝箱碼頭岸橋突發(fā)故障情況下裝卸船作業(yè)重調(diào)度問題，考慮岸橋故障情況下的作業(yè)約束和作業(yè)時長的不確定性，選用MDP進行建模，進行全岸線岸橋作業(yè)調(diào)度和重調(diào)度研究。

1 問題描述及建模

1.1 問題描述

集裝箱碼頭岸橋在裝卸船作業(yè)時突發(fā)故障會導(dǎo)致其作業(yè)停滯，影響作業(yè)進程，從而影響船期，而船期延遲又會帶來其他一系列影響。因此，在岸橋突發(fā)故障時，需要根據(jù)當(dāng)前作業(yè)情況，對集裝箱碼頭全岸線作業(yè)任務(wù)進行重新分配。岸橋突發(fā)故障情況下的裝卸船作業(yè)重調(diào)度要考慮以下4點：（1）被停用的故障岸橋在空間上影響其兩側(cè)岸橋的作業(yè)。如圖1（QC表示岸橋）所示：在進行作業(yè)重調(diào)度時，要考慮故障岸橋的空間位置及其變化對其他岸橋作業(yè)的影響。當(dāng)QC2突發(fā)故障時，要為QC2留出滿足作業(yè)安全距離要求的停放空間，并為維持岸橋作業(yè)分配均衡，QC2的作業(yè)任務(wù)需要由QC1和QC3協(xié)助完成。這就造成QC1和QC3的作業(yè)任務(wù)增加，當(dāng)這些任務(wù)對應(yīng)的場內(nèi)作業(yè)位置存在重疊時，作業(yè)任務(wù)之間的沖突就增加了。

（2）重調(diào)度是全岸線作業(yè)的重新調(diào)度。為保證作業(yè)進程，故障岸橋的作業(yè)任務(wù)要由其緊鄰岸橋分擔(dān)，其緊鄰岸橋作業(yè)任務(wù)增加;為維持岸橋作業(yè)分配均衡，其他外側(cè)岸橋要分擔(dān)其緊鄰岸橋的部分作業(yè)任務(wù)。

（3）重調(diào)度時效要求高。岸橋一發(fā)生故障就停止作業(yè)，這就需要盡快生成新的調(diào)度方案，減少突發(fā)事件的影響。為此，需要高效率的算法。

（4）岸橋故障排除后要重新投入使用，這就需要再次生成新的調(diào)度方案。該故障排除后的重調(diào)度過程不是故障發(fā)生后重調(diào)度的逆過程，而任務(wù)分配約束與初始無故障時的一致。

基于以上考慮，設(shè)計岸橋突發(fā)故障情況下裝卸船作業(yè)重調(diào)度的動態(tài)決策模型。該模型以最小化裝卸船作業(yè)最大完成時間為目標，在岸橋故障約束下進行全岸線岸橋重調(diào)度。在重調(diào)度決策中，考慮各任務(wù)作業(yè)時間的不確定性，在集裝箱碼頭裝卸船作業(yè)規(guī)律已知的條件下，基于集裝箱碼頭歷史作業(yè)數(shù)據(jù)，使用經(jīng)驗分布擬合作業(yè)時間的概率分布，模擬集裝箱碼頭生產(chǎn)作業(yè)過程，實現(xiàn)對不確定作業(yè)過程的有效描述。

為更好地描述岸橋故障發(fā)生后和故障排除后岸橋作業(yè)調(diào)度的動態(tài)不確定過程，選用MDP對問題進行建模。MDP主要由狀態(tài)st、動作at、回報值R和狀態(tài)轉(zhuǎn)移函數(shù)f構(gòu)成，如圖2所示。

系統(tǒng)采取動作at將狀態(tài)st轉(zhuǎn)移至狀態(tài)st+1，該過程中系統(tǒng)各狀態(tài)因素服從狀態(tài)轉(zhuǎn)移函數(shù)f。MDP使用結(jié)合概率分布的狀態(tài)轉(zhuǎn)移函數(shù)能更直觀地表述作業(yè)時間的不確定性。通過歷史作業(yè)數(shù)據(jù)使用經(jīng)驗分布擬合作業(yè)時間的概率分布，相比于混合整數(shù)規(guī)劃模型，該表述更貼近實際作業(yè)過程，從而能獲得更優(yōu)的決策結(jié)果。

采用MDP建模要求問題具有馬爾科夫性即無后效性。對于裝卸船作業(yè)重調(diào)度問題，當(dāng)岸橋突發(fā)故障時，集裝箱碼頭系統(tǒng)作業(yè)僅與故障發(fā)生時的狀態(tài)相關(guān)，該狀態(tài)可完全觀測，因此裝卸船作業(yè)重調(diào)度問題無后效性，可使用MDP進行建模。

1.2 模型假設(shè)

岸橋作業(yè)安全距離已知，案例中設(shè)定岸橋作業(yè)安全距離為2個40英尺貝位長度，即2個40英尺集裝箱長度。

在初始調(diào)度時，各岸橋初始作業(yè)位置為其初始作業(yè)任務(wù)所在位置，進行初始作業(yè)前的岸橋移動時間并入裝船作業(yè)準備時間中;重調(diào)度后，岸橋需要的移動時間并入下一作業(yè)任務(wù)的執(zhí)行時間中，通過狀態(tài)轉(zhuǎn)移過程進行處理。

1.3 符號說明

集合：C為岸橋集合，c∈C;L為任務(wù)集合，l∈L;V為所有待裝卸船的集合，v∈V;T為時刻集合，t∈T，其中t0表示作業(yè)開始時刻，te表示作業(yè)完成時刻。

目標變量：F表示最大完工時間，即所有任務(wù)完成的時間τte，可觀測獲得。

決策變量：Xlc（t）為0-1變量，Xlc（t）=1表示在時刻t由岸橋c開始執(zhí)行任務(wù)l，否則Xlc（t）=0。

已知參數(shù)和觀測量：Bl（t）為0-1變量，為已知量，Bl（t）=1表示在時刻t任務(wù)l在作業(yè)中，否則Bl（t）=0;El（t）為0-1變量，為已知量，El（t）=1表示在時刻t任務(wù)l已完成，否則El（t）=0;Mc（t）為0-1變量，為已知量，Mc（t）=1表示在時刻t岸橋c在故障維修中，否則Mc（t）=0;Ol（t）表示任務(wù)l在時刻t的岸線作業(yè)位置，不同船舶任務(wù)的岸線作業(yè)位置按照船舶靠泊位置進行歸一化處理，保證獲得的作業(yè)調(diào)度方案滿足岸橋位置和岸橋作業(yè)安全距離的要求;Oc（t）表示在時刻t岸橋c的作業(yè)位置;qlv為0-1變量，為已知量，qlv=1表示任務(wù)l屬于船v，否則qlv=0;gcc′為0-1變量，為已知量，gcc′=1表示c′為c的緊右岸橋，否則gcc′=0;vll′為0-1變量，為已知量，vll′=1表示l′為l的緊前任務(wù)，即對任務(wù)l′作業(yè)完成后才能對任務(wù)l進行作業(yè)，否則vll′=0;uc（t）表示岸橋c在時刻t的最小絕對位置;nc（t）表示岸橋c在時刻t的最大絕對位置;τt表示截至?xí)r刻t的作業(yè)時間，τt0=0;Γ（t）表示在時刻t所有作業(yè)任務(wù)的完成時間集合，可觀測得到;flc（s）表示在狀態(tài)st下，由岸橋c完成任務(wù)l還需要的作業(yè)時間，該作業(yè)時間服從以岸橋、任務(wù)和當(dāng)前狀態(tài)為條件的經(jīng)驗分布，包含所需的岸橋移動時間;dc（t）表示在時刻t岸橋與其緊右岸橋的作業(yè)安全距離限制，當(dāng)岸橋c的緊右岸橋處于維修狀態(tài)時，該安全距離的確定要考慮維修中岸橋的當(dāng)前位置。

中間變量和中間觀測量：Wlc（t）為0-1變量，Wlc（t）=1表示在時刻t任務(wù)l正由岸橋c作業(yè)，否則Wlc（t）=0;Gc（t）為0-1變量，Gc（t）=1表示在時刻t岸橋c空閑，否則Gc（t）=0;Hv（t）為0-1變量，Hv（t）=1表示在時刻t完成了對船v的作業(yè)任務(wù)，否則Hv（t）=0，

式（3）表示該模型的優(yōu)化目標為最小化最大完成時間;式（4）為岸橋狀態(tài)約束，岸橋狀態(tài)只可能為空閑或作業(yè)中或故障維修中;式（5）表示在不同決策階段岸橋位置的狀態(tài)轉(zhuǎn)移過程約束，具體為當(dāng)被分配新作業(yè)任務(wù)時，岸橋移動至新任務(wù)位置，當(dāng)前作業(yè)中的岸橋位置保持不變，當(dāng)前空閑或故障維修中的岸橋隨其緊左岸橋移動，與作業(yè)安全距離約束一起共同保證當(dāng)前岸橋調(diào)度方案不會引起岸橋碰撞和相互穿越;式（6）為岸橋與任務(wù)的關(guān)系約束，即一個任務(wù)只能分配給一個岸橋（作業(yè)路），且不給不可用岸橋分配任務(wù);式（7）表示不能對已作業(yè)的任務(wù)進行重復(fù)作業(yè);式（8）為岸橋作業(yè)安全距離約束，當(dāng)岸橋處于維修狀態(tài)時，其兩側(cè)岸橋作業(yè)安全距離增加，同時由于dc（t）≥0，該約束通過岸橋之間的左右關(guān)系保證了岸橋不相互穿越;式（9）為任務(wù)緊前關(guān)系約束;式（10）和（11）為岸橋位置約束;式（12）為時間轉(zhuǎn)移約束，表示作業(yè)從當(dāng)前時間向下一時間的變化過程;式（13）為任務(wù)狀態(tài)轉(zhuǎn)移約束，其中作業(yè)時間服從經(jīng)驗分布;式（14）為完工狀態(tài)約束，即在作業(yè)終止時刻所有任務(wù)都處于完成狀態(tài);式（15）為單船完工時間約束。

1.5 MDP模型主體

MDP可由一個四

元組〈S，A，N，R〉表述，其中：S表示智能體的狀態(tài)集合;A表示智能體的動作集合;N（si，a，sj）=P（sj|si，a）表示狀態(tài)轉(zhuǎn)移函數(shù)，狀態(tài)轉(zhuǎn)移滿足馬爾科夫性;R表示回報。

狀態(tài)包含智能體中3個基礎(chǔ)對象的狀態(tài)，即任務(wù)、岸橋和船舶狀態(tài)，該狀態(tài)可由〈〈Bl（t），El（t）〉，〈Wic（t），Gc（t），Oc（t）〉，Hv（t）〉表示，其中：第一部分為任務(wù)狀態(tài)，由一個二元組構(gòu)成;第二部分為岸橋狀態(tài)，由一個三元組構(gòu)成;第三部分為船舶狀態(tài)。

在某狀態(tài)下智能體采取的動作為分配后續(xù)作業(yè)任務(wù)，即當(dāng)前狀態(tài)下任務(wù)的開始執(zhí)行情況，表示為〈Xlc（t）〉。

st+1表示在t+1時刻的狀態(tài)。st+1～P（st|at），由于過程的不確定，狀態(tài)轉(zhuǎn)移服從特定的分布。此狀態(tài)轉(zhuǎn)移符合馬爾科夫過程的無后效性，即下一狀態(tài)僅由當(dāng)前狀態(tài)和當(dāng)前采取的動作決定。

作業(yè)效率回報。當(dāng)完成單船作業(yè)任務(wù)時，以單船完工時間Zt作為整體回報。整體回報向與該船決策相關(guān)的前向步驟進行反向傳播，傳播衰減率為λ1。

特殊回報。當(dāng)重點路被拆解時，給予特殊回報。例如，某船的10、14和18貝位均有作業(yè)任務(wù)，且這3個貝位的總作業(yè)量占整船作業(yè)量比例較大，如果按照10—14—18的作業(yè)順序由單臺岸橋依次作業(yè)，則整船作業(yè)效率較低;此時應(yīng)先安排岸橋完成14貝位的作業(yè)，再由2臺岸橋同時完成10和18貝位的作業(yè)，這是因為優(yōu)先執(zhí)行重點路上中間貝位的作業(yè)在無其他限制的情況下不會造成作業(yè)效率下降。為重點路上中間貝位的作業(yè)增加特殊回報。該回報向與該船決策相關(guān)的前向步驟進行反向傳播，傳播衰減率為λ2。

2 算法設(shè)計

蒙特卡洛樹搜索（Monte Carlo tree search，MCTS）算法是一種通過在決策空間內(nèi)隨機抽取樣本并根據(jù)結(jié)果建立搜索樹來尋找給定領(lǐng)域內(nèi)最優(yōu)決策的算法[18]。MCTS算法最顯著的優(yōu)點就是它可以在沒有掌握太多相關(guān)領(lǐng)域知識的前提下，僅通過相關(guān)規(guī)則約束搜索范圍，利用目標函數(shù)指引搜索方向，并且基于合適的樣本量就可以求得一個比較好的結(jié)果，且采樣越多，結(jié)果越接近實際。因此，應(yīng)用MCTS算法解決本文問題。

MCTS算法迭代過程包含選擇、擴展、模擬、回溯4個基本步驟，如圖3所示。集裝箱碼頭裝卸船作業(yè)重調(diào)度MCTS算法流程見圖4。

選擇策略。本文采用上限置信區(qū)間（upper confidence bound apply to tree， UCT）算法作為裝卸船作業(yè)重調(diào)度的選擇策略。UCT算法為基礎(chǔ)MCTS算法的改進方法。UCT算法的公式如下：

式中，ri為UCT值;i為節(jié)點i的平均回報值，此處對應(yīng)裝卸船作業(yè)重調(diào)度的回報值，包括作業(yè)效率回報和特殊回報;ni為節(jié)點i被選擇的總次數(shù)，n為節(jié)點i的父節(jié)點被選擇的總次數(shù)，τ為搜索廣度（深度）參數(shù)，τ∈[0，1]。每次迭代都直接選擇ri最大的節(jié)點。由式（16）可知，MCTS算法在迭代初期傾向于選擇訪問次數(shù)少的節(jié)點，即傾向于搜索廣度;在迭代后期傾向于選擇目標估值更高的節(jié)點，即傾向于提升目標值。

擴展策略。為節(jié)約決策資源，MCTS算法的搜索樹是動態(tài)更新的，并非在決策開始時生成所有狀態(tài)節(jié)點;在選擇當(dāng)前節(jié)點后，對葉子節(jié)點進行擴展，獲得下一步所有可能的決策狀態(tài)節(jié)點。本問題中，通過擴展策略在狀態(tài)轉(zhuǎn)移約束下獲取當(dāng)前狀態(tài)下后續(xù)所有可能的調(diào)度方案。

模擬策略。本問題中，采用集裝箱碼頭層次仿真模型對集裝箱碼頭裝卸船作業(yè)（視為離散事件）進行模擬，把模擬得到的實際作業(yè)效果（最終作業(yè)完成時間、重點路作業(yè)情況）作為模擬過程的回報值。

回溯策略。在模擬完成后，采用UCT算法進行回溯，更新路徑各節(jié)點回報值和訪問次數(shù)。

剪枝策略。在算法中加入剪枝策略剪掉劣解，提升求解效率。采用剪枝策略剪掉任務(wù)量分配明顯不均衡的解所在分支。本問題中，超出重點路總作業(yè)量比例閾值的解一定為劣解，對其所在分支進行剪枝。

3 仿真驗證

3.1 多作業(yè)路計算仿真

選取實際生產(chǎn)中有5個作業(yè)路的裝卸船作業(yè)調(diào)度和故障發(fā)生后重調(diào)度案例，驗證重調(diào)度算法的有效性，其基本設(shè)置如表1所示，有30組任務(wù)，分布于19個貝位中，有5臺岸橋可使用。

分別進行岸橋無故障、突發(fā)故障后和故障排除后等3種情況下的裝卸船作業(yè)仿真。

無故障時的調(diào)度方案見圖5。按照圖5的調(diào)度方案，各岸橋的作業(yè)分配相對均衡，最晚完成作業(yè)的為QC4，各作業(yè)路作業(yè)均滿足作業(yè)安全距離約束，未出現(xiàn)作業(yè)交叉，滿足作業(yè)約束。

考慮在當(dāng)前作業(yè)狀態(tài)下，QC3突發(fā)故障，此時進行故障發(fā)生后重調(diào)度，重調(diào)度方案見圖6，該方案為QC3全程故障情況下的調(diào)度方案。由于QC3發(fā)生故障，安排QC2和QC4分擔(dān)原由QC3承擔(dān)的重點路30～46貝位的作業(yè)。部分任務(wù)要考慮QC3實際占用的空間，不能由QC2和QC4同時作業(yè)，因此先安排QC2作業(yè)30貝位的任務(wù)，后安排QC4接替作業(yè)38～42貝位的任務(wù)。原由QC2和QC4作業(yè)的部分任務(wù)分別分配給QC1和QC5執(zhí)行，具體地，原由QC2作業(yè)的18貝位的部分任務(wù)分配給QC1執(zhí)行，原由QC4作業(yè)的62貝位的任務(wù)分配給QC5執(zhí)行。在QC3全程故障調(diào)度方案下，需要移動一次發(fā)生故障的QC3，QC5最后完成作業(yè)，總體作業(yè)時間大于未發(fā)生岸橋故障時的作業(yè)時間，整體作業(yè)分配相對均衡。

假設(shè)QC3在380 min時故障排除，則故障排除后重調(diào)度方案見圖7。

由圖7可知：在QC3故障排除后，安排QC3繼續(xù)執(zhí)行38貝位的作業(yè)， 62貝位的作業(yè)調(diào)整為由QC4完成;總體作業(yè)時間小于QC3全程故障情況下的作業(yè)時間。

該算例中，3種情況下的調(diào)度方案均滿足任務(wù)分配約束、作業(yè)約束、作業(yè)安全距離約束和故障岸橋相關(guān)約束，且故障排除后重調(diào)度方案相對故障發(fā)生后重調(diào)度方案總體作業(yè)時間短，體現(xiàn)了本文方法的優(yōu)勢。

3.2 不同規(guī)模算例仿真分析

為驗證本文方法對不同規(guī)模問題的求解效果，選擇不同規(guī)模的實際案例進行仿真分析。案例中各作業(yè)任務(wù)的作業(yè)時間服從岸橋作業(yè)經(jīng)驗分布，該經(jīng)驗分布由實際岸橋作業(yè)時間數(shù)據(jù)擬合得到。不同規(guī)模算例的基本信息見表2，其中：同貝連續(xù)作業(yè)任務(wù)視為一個任務(wù)組;參考作業(yè)時間為基于重點路作業(yè)量計算得到的作業(yè)時間，作為總體作業(yè)時間的參考。

各規(guī)模算例在岸橋無故障時的仿真結(jié)果見表3。

表3結(jié)果表明：在小規(guī)模算例中，作業(yè)時間不確定性對調(diào)度方案影響較小，最差目標值與平均目標值差距不大;在大規(guī)模算例中，MCTS算法可在較短時間內(nèi)得到調(diào)度方案;由于作業(yè)過程不確定性的影響，大規(guī)模算例比小規(guī)模算例的調(diào)度方案的穩(wěn)定性弱，但未出現(xiàn)大波動，調(diào)度方案的魯棒性在可控范圍內(nèi)。

設(shè)置岸橋突發(fā)故障時間和故障排除后重新投入使用的時間，獲得多次故障和故障排除后重調(diào)度的仿真結(jié)果，見表4。

與無故障時的仿真結(jié)果相比，由于岸橋故障的系統(tǒng)性影響，突發(fā)故障情況下的總體作業(yè)時間均增加，其中在最大規(guī)模算例中，故障發(fā)生后重調(diào)度后的作業(yè)時間增加了19.69%。在穩(wěn)定性方面，因為多次調(diào)度消除了作業(yè)過程中部分不確定因素，所以相比無故障時的仿真結(jié)果，表現(xiàn)出更佳的效果以及更

合理的不確定性情況下的作業(yè)時間分布范圍。在小規(guī)模算例中算法可在1個作業(yè)循環(huán)時間內(nèi)完成重調(diào)度，在最大規(guī)模算例中算法平均能在2個作業(yè)循環(huán)時間內(nèi)完成重調(diào)度。該仿真結(jié)果表明，提出的方法可在岸橋突發(fā)故障時，在極短的時間內(nèi)更新調(diào)度方案，從而使岸橋作業(yè)分配恢復(fù)均衡，實現(xiàn)突發(fā)故障情況下的快速重調(diào)度。

4 結(jié)論與展望

本文提出一種集裝箱碼頭岸橋突發(fā)故障情況下的裝卸船作業(yè)快速重調(diào)度方法。該方法考慮了故障岸橋時空約束，建立裝卸船作業(yè)重調(diào)度馬爾科夫決策過程（MDP）模型。與描述此類問題常用的混合整數(shù)規(guī)劃模型相比，該模型考慮了故障岸橋?qū)ψ鳂I(yè)的時空約束，表述了正常作業(yè)、突發(fā)故障、重調(diào)度、基于重調(diào)度方案作業(yè)、故障排除后重調(diào)度到恢復(fù)正常作業(yè)的狀態(tài)變化過程。該模型描述的狀態(tài)鄰域更接近人類決策過程的策略搜索鄰域，有利于使用鄰域搜索算法進行高效求解。針對此問題設(shè)計了改進的蒙特卡洛樹搜索（MCTS）算法進行求解。仿真實驗表明，改進的MCTS算法適用于求解該快速重調(diào)度問題，尤其在大規(guī)模算例中能在2個作業(yè)循環(huán)時間內(nèi)更新調(diào)度方案，快速實現(xiàn)全岸線岸橋裝卸船作業(yè)分配均衡;所求得的重調(diào)度方案能夠優(yōu)化作業(yè)完工時間，削弱作業(yè)時間不確定性的影響。該決策框架為集裝箱碼頭岸橋突發(fā)故障后重調(diào)度問題提供了新的思路，可推廣于求解集裝箱碼頭類似序貫決策問題。

參考文獻：

[1]ZHAO N， LIU Y， MI W J， et al. Digital management of container terminal operations[M]. Springer， 2020： 233-237.

[2]KASM O A， DIABAT A. The quay crane scheduling problem with non-crossing and safety clearance constraints： an exact solution approach[J]. Computers & Operations Research， 2019， 107： 189-199. DOI： 10.1016/j.cor.2019.03.014.

[3]KASM O A， DIABAT A. Next-generation quay crane scheduling[J]. Transportation Research Part C， 2020， 114： 694-715. DOI： 10.1016/j.trc.2020.02.015.

[4]SUN D F， TANG L X， BALDACCI R. A Benders decomposition-based framework for solving quay crane scheduling problems[J]. European Journal of Operational Research， 2019， 273（2）： 504-515. DOI： 10.1016/j.ejor.2018.08.009.

[5]LIANG C J， FAN L B， XU D H， et al. Research on coupling scheduling of quay crane dispatch and configuration in the container terminal[J]. Computers & Industrial Engineering， 2018， 125： 649-657. DOI： 10.1016/j.cie.2018.05.004.

[6]MSAKNI M K， DIABAT A， RABADI G， et al. Exact methods for the quay crane scheduling problem when tasks are modeled at the single container level[J]. Computers & Operations Research， 2018， 99： 218-233. DOI： 10.1016/j.cor.2018.07.005.

[7]HUANG S Y， LI Y. A bounded two-level dynamic programming algorithm for quay crane scheduling in container terminals[J]. Computers & Industrial Engineering， 2018， 123： 303-313. DOI： 10.1016/j.cie.2018.06.010.

[8]AL-DHAHERI N， DIABAT A. A Lagrangian relaxation-based heuristic for the multi-ship quay crane scheduling problem with ship stability constraints[J]. Annals of Operations Research， 2017， 248： 1-24. DOI： 10.1007/s10479-016-2239-8.

[9]周鵬飛， 康海貴. 面向隨機環(huán)境的集裝箱碼頭泊位-岸橋分配方法[J]. 系統(tǒng)工程理論與實踐， 2008（1）： 161-169.

[10]侯艷芬. 服務(wù)臺可變的集裝箱岸橋調(diào)度建模與仿真[D]. 北京： 北京交通大學(xué)， 2016.

[11]張思， 呂夢晴， 代劍環(huán)， 等. 基于操作時間不確定性條件下的岸橋調(diào)度優(yōu)化研究[J]. 工業(yè)工程與管理， 2020， 25（5）： 50-58. DOI： 10.19495/j.cnki.1007-5429.2020.05.007.

[12]包博， 張琳， 張搏. 設(shè)備故障條件下柔性作業(yè)車間重調(diào)度方法[J]. 計算機工程與應(yīng)用， 2018， 54（19）： 248-253. DOI： 10.3778/j.issn.1002-8331.1706-0307.

[13]段俊華， 孫衛(wèi)青， 李俊青， 等. 一種基于遷徙鳥群優(yōu)化的流水車間重調(diào)度方法[J]. 控制工程， 2017， 24（8）： 1656-1661. DOI： 10.14107/j.cnki.kzgc.D4.0232.

[14]ZHANG J， QIN W， WU L H， et al. Fuzzy neural network-based rescheduling decision mechanism for semiconductor manufacturing[J]. Computers in Industry， 2014， 65（8）： 1115-1125. DOI： 10.1016/j.compind.2014.06.002.

[15]SHAPIRO A， DENTCHEVA D， RUSZCZYN′SKI A. Lectures on stochastic programming： modeling and theory[M]. 2nd ed. Philadelphia： Society for Industrial and Applied Mathematics， 2014： 1-25.

[16]BIRGE J R， LOUVEAUX F. Introduction to stochastic programming[M]. 2nd ed. Springer Science & Business Media， 2011： 84-87.

[17]PUTERMAN M L. Markov decision processes： discrete stochastic dynamic programming[M]. John Wiley & Sons， 2014： 5-14.

[18]BROWNE C B， POWLEY E， WHITEHOUSE D， et al. A survey of Monte Carlo tree search methods[J]. IEEE Transactions on Computational Intelligence and AI in Games， 2012， 4（1）： 1-43. DOI： 10.1109/TCIAIG.2012.2186810.

（編輯 趙勉）

收稿日期： 2021-02-25

修回日期： 2021-06-18

作者簡介：

夏孟玨（1992—），男，山東煙臺人，博士，研究方向為物流智能化，（E-mail）xiamengjue@qq.com;

史學(xué)鑫（1996—），男，安徽安慶人，碩士，研究方向為物流信息化、智能化，（E-mail）1109136218@qq.com;

李美貞（1971—），女，福建南安人，高級工程師，碩士，研究方向為港口設(shè)備管理，（E-mail）limeizhen@xctg.com.cn