李 凡，杜玉越

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

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

李 凡，杜玉越

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

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

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

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

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

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

1 問題描述

集裝箱港口卸載作業(yè)流程可以簡單描述為：為進港船舶分配泊位，由岸橋將集裝箱從船舶卸到集卡，再由集卡將集裝箱運輸?shù)较鄳褕觯缓髨鰳驅⒓b箱卸下放置在堆場。集裝箱裝船作業(yè)流程恰好相反。集裝箱港口的在線調度策略指根據(jù)港口實時數(shù)據(jù)，對各設備及場區(qū)的狀態(tài)做出及時判斷，然后給出實時調度指令。

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

圖1 “作業(yè)路”模式調度路線

圖2 “大作業(yè)面”模式調度路線

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

2 集卡調度的數(shù)學模型

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

2.1 模型假設與參數(shù)定義

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

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

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

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

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

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

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

表1 參數(shù)定義

2.2 目標函數(shù)

基于2.1節(jié)的假設，考慮岸吊延遲時間、集卡行駛時間以及系統(tǒng)完成時間最短，建立多優(yōu)化目標函數(shù)[11-13]。

若同一岸吊當前執(zhí)行的任務已經(jīng)完成，可執(zhí)行下一任務，但集卡未到就造成了岸吊等待，影響作業(yè)效率及經(jīng)濟成本?？紤]岸吊的等待時間，得到目標函數(shù)：

(1)

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

(2)

在實際港口中，系統(tǒng)總作業(yè)完成時間直接反映港口的工作效率，考慮系統(tǒng)總作業(yè)完成時間，建立目標函數(shù)

f3=T=t-t0。

(3)

(4)

約束條件：

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

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

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

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

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

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

續(xù)表

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

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

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

4 仿真實驗及結果分析

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

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

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

表2 箱區(qū)與泊位間的行駛距離

表3 各箱區(qū)間的行駛距離

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

案例1：某時刻泊位1?？恳凰邑涊喰栊遁d進口集裝箱2 000個，2 h后泊位2?？恳凰邑涊喰柩b載出口集裝箱2 000個。

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

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

4.2 實驗結果與分析

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

圖3 軟件仿真截圖

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

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

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

表5 不同案例中算法優(yōu)化效果

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

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

5 總結

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

[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]田亮.基于同步裝卸的岸橋與集卡協(xié)同作業(yè)優(yōu)化研究[D].大連：大連海事大學,2013.

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

[9]馬慧娟,杜玉越.一種集裝箱港口集卡的動態(tài)調度方法[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]梁承姬,翟點點,王丹丹.港口集裝箱多場橋裝卸動態(tài)調度模型研究[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]黃發(fā)良,張師超,朱曉峰.基于多目標優(yōu)化的網(wǎng)絡社區(qū)發(fā)現(xiàn)方法[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]杜振,宮會麗,張蕾,等.港口物流集裝箱調度效率優(yōu)化仿真研究[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]徐亞,陳秋雙,龍磊等.基于多目標規(guī)劃的堆場空間分配問題研究[J].系統(tǒng)工程學報,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)；山東省優(yōu)秀中青年科學家科研獎勵基金項目(BS2015DX010)

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

U691.3

A

1672-3767(2017)02-0107-08