一種基于多目標優化的混合在線集卡調度方法

李 凡，杜玉越

(山東科技大學 計算機科學與工程學院，山東 青島266590)

一種基于多目標優化的混合在線集卡調度方法

李 凡，杜玉越

(山東科技大學 計算機科學與工程學院，山東 青島266590)

為了提高集裝箱港口工作效率，在“大作業面”前提下，結合任務觸發型和集卡觸發型兩種集卡在線調度方法，綜合考慮系統總作業時間、岸吊等待時間以及集卡空載率問題，建立多目標優化模型，并運用啟發式方法提出一種混合在線集卡調度算法。最后，以港口實際數據為例，通過實驗仿真例證了模型優化效果和算法工作效率。

在線集卡調度；集裝箱港口；多目標優化；混合；仿真

集裝箱港口(Container Terminal)是用來停靠運輸集裝箱的船舶、集裝箱裝卸作業的場所，是在集裝箱運輸過程中水路和陸路運輸的連接點，也是集裝箱多式聯運的樞紐。隨著世界經濟的飛速發展，全球化趨勢日益加快，遠洋運輸已在各國貿易中起到舉足輕重的作用，集裝箱港口的建設與發展也成為競爭的焦點。港口在線調度策略的研究對自動化港口建設具有重要意義。為了提高集裝箱港口的工作效率，國內外學者針對集裝箱調度優化做了大量研究。在時間優化方面，謝晨等[1]使用基于改進的johnson法則的啟發式算法研究了集卡調度問題，但只考慮了最小完成時間這一個因素，缺乏對其他影響港口運營成本因素的考慮；CAO等[2]運用混合整數規劃模型對岸吊與堆場運輸問題進行研究，并用遺傳算法和johnson法則對模型進行求解，但是優化目標考慮的因素不夠全面。在路徑優化方面，蔡寒[3]改進了拖車調度模型，運用在線模式對集卡調度問題進行研究，為自動化碼頭研究提供了思路，但是僅僅在“作業路”的基礎上進行研究，優化效果不夠理想；Kim等[4]討論在裝船時集卡和場橋的取箱路徑優化問題，并采用了整數規劃方法進行建模和求解，但沒有考慮卸船時的情況，優化不夠全面，效果不夠理想。

目前國內集裝箱港口大多采用人工駕駛機械，港口工作效率較低，系統的穩定性較差，建設自動化港口，研究在線集卡調度策略勢在必行。清華大學蔡寒等[3]提出了一種混合在線調度方法的框架，是基于“作業路”模式的調度，集卡的利用率較低，作業成本較高。很多研究以岸吊對集卡的總等待時間為主要優化目標[5-7]，而沒有考慮集卡的空載率以及集卡與任務地點的距離問題。

本研究將以集卡為中心，在“大作業面”前提下，綜合考慮集卡執行完當前任務所需的時間和岸橋延遲時間，以及執行完當前任務后集卡前往下一個任務地點的行駛時間，建立多目標優化模型，并提出一種混合在線集卡調度算法。最后，通過仿真實驗驗證提出的模型和算法的有效性。

1 問題描述

集裝箱港口卸載作業流程可以簡單描述為：為進港船舶分配泊位，由岸橋將集裝箱從船舶卸到集卡，再由集卡將集裝箱運輸到相應堆場，然后場橋將集裝箱卸下放置在堆場。集裝箱裝船作業流程恰好相反。集裝箱港口的在線調度策略指根據港口實時數據，對各設備及場區的狀態做出及時判斷，然后給出實時調度指令。

在港口裝卸作業過程中，集卡的調度策略主要有兩種[8]：“作業路”模式和“大作業面”模式。兩種模式集卡調度路線分別如圖1和圖2所示。

圖1 “作業路”模式調度路線

圖2 “大作業面”模式調度路線

在“作業路”模式中，集卡隊列1在出口箱區裝載集裝箱，運輸到岸吊A1處，由岸吊A1卸載集裝箱到船舶A，然后集卡空載回到出口箱區，循環此過程；集卡隊列2在岸吊A2處裝載集裝箱，運輸到進口箱區，由對應的場橋將集裝箱卸載，然后集卡回到岸吊A2處，循環此過程。此模式下每輛集卡固定為某一岸吊服務，行駛路線也相對固定，在集卡循環行駛過程中，一半的路程為空載，造成了集卡資源的浪費。在圖2“大作業面”模式中，集卡靈活地服務于所有岸吊，集卡可以在岸吊B1或B2處裝載集裝箱，運輸到進口箱區，卸載集裝箱后，行駛到出口箱區裝載集裝箱，然后運輸到岸吊A1或A2處，由岸吊卸載集裝箱到船舶A。此模式集卡行駛路線相對靈活，集卡的空載率相對較低。

2 集卡調度的數學模型

綜合考慮系統總作業時間、岸吊的操作及等待時間、集卡空載時間問題以及任務地點與集卡的距離問題，建立混合在線集卡調度的多目標優化的數學模型。

2.1 模型假設與參數定義

根據港口集裝箱調度的實際情況，結合有關文獻中的場景設計[2，3,9-10]及模型設計實際，給出下面的模型假設：

1) 所有船計劃和堆場計劃已知；

2) 所有岸吊和場橋的裝(卸)載操作時間及設備調整時間已知；

3) 各任務地點之間的行駛時間已知；

4) 所有岸吊和場橋的裝卸箱任務序列已知；

5) 集裝箱為單一箱型，一輛集卡一次運輸1 TEU(Twenty-foot Equivalent Unit, 20英尺標準箱)。

所涉及的模型與算法的參數定義如表1所示。

表1 參數定義

2.2 目標函數

基于2.1節的假設，考慮岸吊延遲時間、集卡行駛時間以及系統完成時間最短，建立多優化目標函數[11-13]。

若同一岸吊當前執行的任務已經完成，可執行下一任務，但集卡未到就造成了岸吊等待，影響作業效率及經濟成本。考慮岸吊的等待時間，得到目標函數：

(1)

減少集卡行駛路程可以降低集卡空駛率，考慮集卡位置與任務地點之間的空載行駛時間，得到目標函數

(2)

在實際港口中，系統總作業完成時間直接反映港口的工作效率，考慮系統總作業完成時間，建立目標函數

f3=T=t-t0。

(3)

(4)

約束條件：

其中：式(5)表明系統總完成時間大于等于最后一個任務執行完畢的時間減去系統開始時間；式(6)表明同一任務的執行集卡離開時間與抵達時間至少間隔一個設備操作時間；式(7)表明同一工作點的相鄰任務的執行集卡抵達時間至少間隔一個設備操作時間；式(8)表明集卡在所有工作點的任務都被其他集卡認領完畢后才可以休眠；式(9)表明集卡只有完成所有其響應的任務后才可以休眠。

本節建立的混合在線集卡調度多目標優化模型，考慮了多個影響與評價集裝箱港口作業效率和作業成本的因素，可用來評價港口的作業能力、港口調度算法的優劣。

3 混合在線集卡調度算法設計

集卡在線調度方法根據觸發事件的不同，一般分為任務觸發型和集卡觸發型[3]兩種。任務觸發型是指當有新任務產生而未被指派出去時，調用算法尋找合適集卡去完成。集卡觸發型是指在集卡空閑時，調用算法尋找合適任務去執行。任務觸發型能使每個任務都能選用最合適的集卡來執行，但是容易造成遠處作業的集卡利用率低。集卡觸發型能使每輛集卡均衡使用，提高集卡利用率，但容易造成岸吊或場橋等待時間過長。

在實際港口中希望集卡等待任務，而不是任務等待集卡，所以本研究以集卡觸發型為基礎，結合任務觸發型策略的優點，運用啟發式方法，建立基于“大作業面”的混合在線集卡調度算法。該算法每次執行都會遍歷所有工作點，選取工作點的當前第一個未被集卡認領的任務，然后計算目標評價函數(函數所用某些變量定義已在第2節給出)，選取合適的任務。考慮到設備的操作時間遠大于算法的執行時間，為了最大限度減少任務等待時間和集卡等待時間，降低集卡空駛率，算法的主體Select()函數是在集卡的當前任務結束前執行(即集卡卸載當前任務集裝箱的同時，為其選好下一任務地點)。算法1描述了基于“大作業面”的混合在線集卡調度算法的基本步驟。

算法1 基于“大作業面”的混合在線集卡調度算法Input:任務地點初始任務列表Li,初始化集卡編號k。Output:目標函數f1、f2、f3的值,總目標函數值F。Step1:集卡k開始工作Ck=0,r=0,Bk,r,i,j=1;/*初始化,集卡k第0個任務執行完畢*/Step2:Foreachrdo/*對每一任務r執行以下操作*/Step2.1:調用Select()函數;/*Select函數在下文定義*/Step2.2:IfBk,(r-1),i,j=0thenWait(Bk,(r-1),i,j);/*集卡k的第r-1個任務未完成,則等待*/Step2.3:集卡k前往任務地點i;Step2.4:記錄當前時刻tarri,j,執行任務j,記錄當前時刻tdepi,j;/*約束條件(5)(6)*/

續表

算法1的核心是計算目標函數尋找集卡下一個任務地點，將其單獨編寫為描述計算目標函數基本步驟的Select()函數

函數Select()Input:各任務點的當前任務列表Li,各地點之間的行駛時間d(s1,s2)。Output:下一任務地點i。Step1:Foreachi({1,2,…,n}do/*對每一地點i執行以下操作*/Step1.1:If任務列表Li為空then循環i++,直到任務列表Li不為空;EndifStep1.2:取當前任務j;Step1.3:IfAi,j=0then /*當前任務j已被其他集卡認領*/Step1.3.2:For(j;Ai,j=0;j++)do /*對每一個已認領的任務j執行以下操作*/Step1.3.2.1:Ifj>mitheni++,gotoStep1;Endif/*地點i的所有任務都已被認領*/Step1.3:EndifStep1.4:根據目標函數f1,計算岸吊等待時間 f1i,j=[tchi-(t-tarri,j-1)]·Bk,r,i,j-1+(t-tdepi,j-1)(1-Bk,r,i,j-1);Step1.5:根據目標函數f2,計算集卡行駛時間 f2k.r=d(s(1)k,r,s(2)k,r-1)·Bk,r,i,j+d(s(0)k,0,s(1)k,r)·Ck;Step1.6:計算評價函數f1,2k,r,i=0.35f1i,j+0.15f2k,r;/*通過優化岸吊等待時間和集卡行駛時間,來減少系統總作業時間,先對目標函數f1和f2整合*/Step1:Endfor/*遍歷完所有任務地點*/Step2:選擇評價函數f1,2k,r,i的值最小的任務地點;Step3:記錄下一任務地點Sk,r=i,記錄下一任務地點的此刻岸吊等待時間為f1i,j,記錄下一任務地點的集卡行駛時間為f2k,r;/*為計算目標函數f1、f2做準備*/Step4:Ai,j=0,Bk,r,i,j=0;/*標記地點i的任務j被認領,設置集卡k的任務r未完成*/END /*函數Select()結束*/

算法1中設計的任務以集裝箱為中心，指卸船集裝箱從離船到被運至堆場箱區安放(或裝船集裝箱從離開箱區到安放至貨船)的全過程。算法核心是判斷任務執行狀態，并準確計算目標評價函數值，選擇集卡的下一任務地點。與基于“作業路”的在線集卡調度算法[3](以下簡稱“算法2”)相比，算法1以“大作業面”為基礎，擴大了集卡的服務范圍，綜合考慮了系統作業時間、岸吊等待時間以及集卡空載行駛時間。

4 仿真實驗及結果分析

為了更好地驗證算法1的有效性，通過FlexTerm軟件進行仿真，運用第2節的目標函數，對算法1和算法2分別進行比較分析。

4.1 港口基本情況及案例設計

以青島某集裝箱港口為例，每個泊位有2臺岸吊為其服務(1～2號岸吊服務泊位1，3～4號岸吊服務泊位2)，泊位后方有4個堆場共16個箱區(1～4號箱區為出口堆場1，5～8號箱區為進口堆場1，9～12號箱區為出口堆場2，13～16號箱區為進口堆場2)，每個箱區有1臺場橋。岸吊操作一個集裝箱所需時間為1.5 min，場橋操作一個集裝箱所需時間為2 min，集卡平均行駛速度為18 km/h。兩泊位與箱區的行駛距離如表2所示，各箱區間的行駛距離如表3所示(只列出本實驗用到的數據)。

表2 箱區與泊位間的行駛距離

表3 各箱區間的行駛距離

為驗證本文模型和算法的有效性，結合港口實際，取3個不同規模的案例進行模擬仿真。

案例1：某時刻泊位1停靠一艘貨輪需卸載進口集裝箱2 000個，2 h后泊位2停靠一艘貨輪需裝載出口集裝箱2 000個。

案例2：某時刻泊位1停靠一艘貨輪需卸載進口集裝箱1 000個，同時泊位2停靠一艘貨輪需裝載出口集裝箱800個。

案例3：某時刻泊位1停靠一艘貨輪需卸載出口集裝箱5 000個，2 h后泊位1停靠一艘貨輪需裝載進口集裝箱3 000個。

4.2 實驗結果與分析

根據以上數據，用FlexTerm仿真軟件，分別嵌入算法1和算法2對模型進行求解，軟件仿真截圖如圖3所示。

圖3 軟件仿真截圖

根據該港口基本情況，設定岸吊的數量nA為4。根據相關專家經驗及相關文獻[8-9,14]，得出在系統配置9輛集卡時效率較高。因此，取系統集卡的數量nK為9。

通過仿真，得到不同案例中基于算法1和算法2的各目標函數值(如表4)。

表4 不同案例中兩種算法運行結果

表5 不同案例中算法優化效果

表5給出了算法1與算法2在各目標函數指標上的比較，其中，f1、f2、f3、F表示算法1得出的各指標值，f1*、f2*、f3*、F*表示算法2得出的各指標值。(f1*-f1)/f1*、(f2*-f2)/f2*、(f3*-f3)/f3*、(F*-F)/F*表示算法1得出的各指標相對算法2的優化程度[15]。由表5可以看出，所提出的算法1在岸吊等待時間和系統總作業時間方面，優化效果較好，對集卡空載行駛時間的優化次之，其中，岸吊的等待時間平均減少22.5%，系統總作業時間平均減少了22.4%，集卡的空載行駛時間平均減少12.5%。綜合以上各指標，總目標函數F優化效果也較好，綜合指標平均降低了17.6%。

由以上結果分析可知，算法1與基于“作業路”的在線集卡調度算法(算法2)相比優化效果較好，具有良好的實用性。

5 總結

綜合考慮系統作業完成時間、岸吊等待時間(即利用率問題)、集卡空載行駛時間(即空載率問題)等因素，建立了多目標優化模型，并結合傳統的任務觸發型集卡調度算法和集卡觸發型集卡調度算法，對基于“作業路”的在線集卡調度算法進行改進，提出一種基于“大作業面”的混合在線集卡調度算法，且通過實驗仿真驗證了算法的有效性。除了本研究所考慮的上述3個因素外，實際港口運作中，岸橋分配、船舶的在港時間、港口前后方作業的銜接等，也是影響港口成本的重要因素，將作為下一步的研究內容。

[1]謝晨,梁承姬,徐德洪.基于HFSS的集裝箱碼頭集成調度模型的建立與求解[J].華中師范大學學報(自然科學版),2016，50(3):369-375. XIE Chen,LIANG Chengji,XU Dehong.A integrated scheduling model based on the HFSS for container terminal[J].Journal of Central China Normal University (Natural Science),2016，50(3):369-375.

[2]CAO J X,SHI Q X,LEE D H.Integrated quay crane and yard truck schedule problem in container terminals[J].Tsinghua Science and Technology,2010,15(4):467-474.

[3]蔡寒.基于仿真的集裝箱碼頭拖車調度研究[D].北京：清華大學,2007.

[4]KIM K H,KIM K Y.An optimal routing algorithm for a transfer crane in port container terminals[J].Transportation Science,1999,33(1):17-33.

[5]CHENG Y L,SEN H C,NATARAJAN K,et al.Dispatching automated guided vehicles in a mega container terminal[M].Springer US,2005,98:355-389.

[6]MEISEL F,BIERWIRTH C.A unified approach for the evaluation of quay crane scheduling models and algorithms[J].Computers & Operations Research,2011,38(3):683-693．

[7]田亮.基于同步裝卸的岸橋與集卡協同作業優化研究[D].大連：大連海事大學,2013.

[8]吳名建.港口集裝箱拖車調度優化研究[D].南京：南京航空航天大學,2010.

[9]馬慧娟,杜玉越.一種集裝箱港口集卡的動態調度方法[J].山東科技大學學報(自然科學版),2016，35(4):99-105. MA Huijuan,DU Yuyue.A Dynamic scheduling method of truck in container terminal[J].Journal of Shandong University of Science and Technology (Natural Science),2016，35(4):99-105.

[10]梁承姬,翟點點,王丹丹.港口集裝箱多場橋裝卸動態調度模型研究[J].計算機仿真,2016(3):363-366. LIANG Chengji,ZHAI Diandian,WANG Dandan.Dynamic scheduling model research for multiple yard crane in container terminal[J].Computer Simulation,2016(3):363-366.

[11]黃發良,張師超,朱曉峰.基于多目標優化的網絡社區發現方法[J].軟件學報,2013,24(9):2062-2077. HUANG Faliang,ZHANG Shicao,ZHU Xiaofeng.Discovering network community based on multi-objective optimization[J].Journal of Software,2013,24(9):2062-2077.

[12]CAI B,HUANG S,LIU D,et al.Multiobjective optimization for autonomous straddle carrier scheduling at automated container teminals[J].IEEE Transaction on Automation Science and Engineering,2013,10(3):711-725.

[13]CARLO H J,VIS I F A,ROODBERGEN K J.Storage yard operations in container terminals:Literature overview,trends,and research directions[J].Flexible Services and Manufacturing Journal,2015,27(2):224-262.

[14]杜振,宮會麗,張蕾,等.港口物流集裝箱調度效率優化仿真研究[J].計算機仿真,2016,33(1):340-343. DU Zhen,GONG Huili,ZHANG Lei,et al.Simulation study on container scheduling optimization in port logistics efficiency[J].Computer Simulation,2016,33(1):340-343.

[15]徐亞,陳秋雙,龍磊等.基于多目標規劃的堆場空間分配問題研究[J].系統工程學報,2009,24(3):365-369. XU Ya,CHEN Qiushaung,LONG Lei,et al.Yard space allocation based on multi-objective programming[J].Journal of Systems Engineering,2009,24(3):365-369.

(責任編輯：傅 游)

A Hybrid Online Scheduling Method of Truck Based on Multi-objective Optimization

LI Fan, DU Yuyue

(College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao, Shandong 266590, China)

In order to improve the efficiency of container ports, a multi-objective optimization model was constructed under the premise of the “full working-area” by combining the task trigger online scheduling and truck trigger online scheduling and by comprehensively considering the total operating time of system, the waiting time of quay cranes, and the no-load rate of trucks. Then a hybrid online scheduling algorithm of trucks was proposed by using a heuristic method. Finally, the optimization effect of the proposed model and the efficiency of the proposed algorithm were verified by simulation experiment based on the actual data of a port.

truck online scheduling; container terminal; multi-objective optimization; hybrid; simulation

2016-07-31

國家自然科學基金項目(61170078，61472228)；泰山學者建設工程項目；山東省自然科學基金項目(ZR2014FM009)；山東省優秀中青年科學家科研獎勵基金項目(BS2015DX010)

李 凡(1992—)，女，山東淄博人，碩士研究生，主要從事港口調度與仿真研究. E-mail:1321136177 @qq.com 杜玉越(1960—)，男，山東聊城人，教授，博士生導師，主要從事Petri網、工作流、過程挖掘等方面的研究，本文通信作者.E-mail:yydu001@163.com

U691.3

A

1672-3767(2017)02-0107-08