基于啟發式算法的自動化跨運車作業調度

堯雨琴,胡志華

(上海海事大學物流研究中心,上海 201306)

基于啟發式算法的自動化跨運車作業調度

堯雨琴,胡志華

(上海海事大學物流研究中心,上海 201306)

針對自動化集裝箱碼頭自動化跨運車(automated straddle carrier,ASC)的調度問題,首先建立混合整數規劃模型,基于ASC可以獨立完成集裝箱在岸邊和堆場之間的運輸作業這一特性,將自動化集裝箱碼頭ASC的作業調度問題轉化為同時取貨送貨問題,并提出一種先完成先執行(first finished first insert,FFFI)啟發式算法進行求解,實現集裝箱任務分配,確定ASC的作業序列,計算每輛ASC的使用率.最后,通過改變集裝箱任務數和ASC數量驗證該算法的有效性和可行性.

自動化集裝箱碼頭;自動化跨運車;先完成先執行啟發式算法;同時取貨送貨;調度

隨著世界經濟的快速發展,集裝箱運輸方式得到廣泛使用,推動了國際貿易量的上升,促進了集裝箱港口吞吐量的高速增長.為了提高集裝箱碼頭的運作效率,各大集裝箱碼頭都在建設實施自動化集裝箱碼頭.在卸船作業中,船舶首先停靠在碼頭為其分配的泊位處,需要卸載的集裝箱由岸吊從船舶上拾取至岸橋下岸邊的臨時堆存區;自動化跨運車(automated straddle carrier,ASC)從岸邊堆存區拾取集裝箱后運輸到堆場,并卸載至堆場特定箱區的特定存放位置.集裝箱裝船作業的順序與卸船作業相反.集裝箱碼頭的導航系統要求ASC沿著指定的電磁軌道行進,在碰撞檢測等安全和可靠性保證的技術下進行作業.ASC和自動導引車的調度問題類似,二者都是在自動化碼頭進行作業的無人操作的運輸工具.但是ASC運輸集裝箱時不需要其他設備的輔助,可以獨立完成集裝箱的運輸,具有控制簡單的靈活性.本工作針對ASC作業工藝下的作業調度問題,基于ASC可以獨立完成集裝箱在岸邊和堆場之間運輸作業的獨立性,將ASC的作業調度問題轉化為同時取貨送貨路徑問題.

在作業過程中,岸橋和場吊等垂直作業設備、ASC和自動導向車(automated guided vehicle,AGV)等水平作業設備通過調度優化減少設備等待時間,提高碼頭作業效率.就調度優化問題,Cao等[1]針對集裝箱碼頭堆場卡車和堆場橋吊裝載作業的調度問題,建立混合整數規劃模型.Homayouni等[2]對自動化集裝箱碼頭的運輸設備和存儲設備建立整數規劃模型,使用遺傳算法求解.Gelareh等[3]考慮調度模型的復雜性,基于拉格朗日松弛方法,設計啟發式算法求解.梁承姬等[4]將集裝箱任務的裝卸過程看作岸橋裝卸、集卡運輸和場橋裝卸的三階段混合Flow Shop調度問題,建立以裝卸任務完工時間最小化為目標的混合整數規劃模型.

目前常見的水平作業設備有集裝箱拖掛車、AGV、ASC等,其中集裝箱拖掛車和AGV一般只能完成水平作業,無法直接從地面取走集裝箱或將集裝箱放置于地面;然而ASC可以直接取走集裝箱或將集裝箱放置于地面.針對ASC的調度問題,Yuan等[5-6]研究了當ASC在堆場進行運輸作業時,綜合ASC的路徑和任務分配問題建立數學模型.Skinner等[7]用遺傳算法求解模型,更加有效地提高了集裝箱的裝卸效率和ASC使用率.Cai等[8-10]利用基于精確算法的分支定界法和列代法求解自動跨運車的調度問題,建立了不確定條件下ASC調度的多目標規劃模型.

基于ASC獨立作業的特性,可將ASC的調度問題轉化為同時取貨送貨問題.針對同時取貨送貨問題,Montan′e等[11]使用禁忌搜索算法對同時取貨送貨車輛路徑問題進行求解.Zhao等[12]考慮有取送貨的旅行商問題,并且用混合遺傳算法進行求解.姚錦寶等[13]用改進的蟻群算法對同時取貨送貨車輛路徑問題進行求解.賈方方等[14]利用改進的粒子群優化算法對同時取貨送貨車輛路徑問題進行求解.Zachariadis等[15-16]提出一個基于禁忌搜索和導引式局部搜索的混合式啟發式算法求解同時取貨送貨問題.

本工作研究了自動化集裝箱碼頭自動化跨運車的作業調度問題,基于ASC獨立作業這一特性,將ASC的作業調度問題轉化為同時取貨送貨問題,提出先完成先執行(first finished first insert,FFFI)啟發式算法進行求解,對任務進行分配并確定每輛ASC的作業序列.最后通過改變ASC數量、任務數論證所提出算法的有效性.

1 問題描述

隨著科學技術的快速發展和勞動力成本的提高,自動化碼頭得到重視.目前,中國各大港口已開展自動化集裝箱碼頭的建設,已經建有數十個不同規模的自動化集裝箱碼頭.由于ASC的作業工藝和作業系統具有易于實施和控制的特點,已在澳大利亞布里斯班等多個集裝箱碼頭得到推廣應用.本工作考慮基于ASC的自動化集裝箱碼頭的作業工藝,將ASC的作業調度問題轉化為同時取貨送貨問題.

圖1是基于自動化跨運車的自動化集裝箱碼頭平面圖.在集裝箱運輸過程中,ASC可以直接取走集裝箱或將集裝箱放置于地面,不需要其他設備輔助,可以獨立完成集裝箱在岸邊和堆場之間的裝卸搬運作業.基于ASC作業工藝的特點,集裝箱卸船作業可以看作是一個送貨過程,集裝箱裝船作業是一個取貨過程,從而可將ASC的集裝箱運輸過程轉化為同時取貨送貨問題.在使一定數量的ASC完成現有任務的前提下,本工作以最小化完工時間為目標建立混合整數規劃模型,提出FFFI啟發式算法求解并確定ASC的作業序列,記錄每輛ASC的完工時間,計算ASC的使用率,最后論證所提出算法的有效性.

圖1 基于ASC的垂岸式自動化集裝箱碼頭Fig.1 A shore-based ASC vertical container terminal automation

2 模型

2.1 符號

2.2 模型

針對自動化集裝箱碼頭ASC的調度問題,以最小化完工時間為目標建立混合整數規劃模型,模型的目標函數與約束條件如下.

目標函數式(1)是最小化完工時間fM.fM是由每個任務的開始工作時間和完成時間決定的(見式(2)).在分配每輛ASC的作業序列時,需要考慮每個任務的開始時間,以免發生時間重疊.對任意跨運車v安排的作業任務序列,如果在完成對任務i的作業后緊接著對任務j作業,即xijv=1,那么要求滿足zj>zi+Tij+T,即zj>xijv(zi+Tij+T).線性化后得到式(3).式(4)和(5)約束任務i∈I的開始時間,任務i∈I的開始時間在其預定的最早開始時間后進行(見式(4)).分配給車輛v∈V的任務i∈I在ASC的有效工作時間內進行(見式(5)).對任意ASC和任意非虛擬任務,滿足該任務在任務網絡中的流約束(見式(6)).通過式(7)約束每個任務只可以由一輛ASC完成,對于任意ASC,從虛擬任務出發到虛擬任務后完成運輸,僅負責一個作業序列,約束如式(8)所示.對于每輛車都是從虛擬任務出發到虛擬任務后完成運輸,約束如式(9)和(10)所示.

混合整數規劃模型中的各種約束條件會導致時間復雜度成立方級數增長,限制了問題的求解規模.混合整數規劃模型可以求出最優解,但是在實際運用中并不適宜.基于ASC獨立運作的特性,本工作提出FFFI啟發式算法對ASC裝卸作業任務進行求解.

3 FFFI算法

FFFI算法是一種啟發式算法,ASC首先選取最近的集裝箱任務來執行,執行完任務的ASC從剩下的任務中選取最近的一個任務,直到完成所有的任務.

N為節點總數,即岸吊的位置以及堆場中的各個存放點和放置點;Q為任務集合, Q={(i,j)|i,j∈N,i≠j};V為ASC的集合;Pv表示ASC的初始位置;Cij表示任意兩點之間的距離,并且用直角距離進行計算;Cij=|Xi?Xi|+|Yi?Yi|,?i,j∈N,i≠j;Sv為每輛ASC的作業序列;Ev為ASC當前的位置;Op是任務p的集裝箱存放點;Cp是任務p的執行時間;Dv為車子v的完工時間;CSO(v,p)為車子v完成任務p后的時間.

步驟4如果未完成任務集非空,轉到步驟2.

FFFI算法的時間復雜度為O(n2),空間復雜度為O(n);混合整數線性規劃(mixed-integer linear programming,MILP)的約束條件較多,其時間復雜度為O(6n3),空間復雜度為O(2n).時間復雜度、空間復雜度會限制問題的求解規模.對比MILP和FFFI算法可知,FFFI算法的求解規模更大,執行時間更短,有效性更好.

4 算例

4.1 實驗設計

表1是所設計的同時取貨送貨問題實驗場景.有8個集裝箱運輸任務,任務的具體信息如表2所示.圖2是取貨送貨布局,其中編號1～10是堆場中的10個存放集裝箱的位置,編號11～20是岸吊下的集裝箱存放區.將自動化集裝箱碼頭的裝船任務看作送貨,卸船看作取貨,則自動化集裝箱碼頭的ASC作業調度問題轉化為同時取貨送貨問題.

表1 實驗場景Table 1 Experimental scenario

表2 任務數據集Table 2 Tasks’data set

圖2 取貨送貨布局Fig.2 Pickup and delivery layout

圖3 結果數據集Fig.3 Results’set

圖4 ASC的作業序列Fig.4 ASC’s sequence

圖5 ASC的使用率Fig.5 ASC’s usage

表3 結果數據Table 3 Results’data

圖6 實驗3求解的ASC使用率Fig.6 ASC’s usage of Experiment 3

(1)在實驗1中,對如圖2所示的8個任務集用一輛集卡進行運輸的同時取貨送貨的問題,用任意方法對同時取貨送貨問題進行求解,得到的結果如圖3所示.用FFFI算法進行求解得到的集卡的作業序列為1—2—5—3—6—4—8—7,距離為71 m;由圖3得出的結論是完成所有任務后集卡行駛的距離最小值為71 m,最大值為110 m.該結果與通過FFFI算法得到的結果一致,二者結果對比可以充分說明FFFI算法的有效性.

圖7 實驗4求解的ASC使用率Fig.7 ASC’s usage of Experiment 4

(2)實驗2將自動化集裝箱碼頭的ASC作業調度問題轉化為同時取貨送貨問題,用啟發式算法對自動化集裝箱碼頭的自動化跨運車作業調度問題進行求解,得到的ASC的作業序列如圖4所示,每輛ASC的使用率如圖5所示.表3是對ASC的完工時間、作業序列、使用率的統計數據.由圖5可得出結論,ASC的使用率較高,都在80%以上,論證了所提出算法在實際問題中應用的有效性.

(3)通過改變任務總數得到不同ASC的使用率如圖6所示.從圖6中可以看出,不同任務數下ASC的使用率在85%～100%之間,大部分在90%以上,可見ASC的使用率是比較高的,說明所提出算法非常適用于實際問題,對大規模的任務進行分配時也是有效的.

(4)改變ASC的數量,在任務總數為200的情況下,各個ASC的使用率如圖7所示.從圖7可以清楚地看出,ASC使用率基本都在90%以上,這些數據充分說明了所提出算法在實際問題中具有效性.

根據以上4種實驗可以得到結論,在不同情景、不同規模下應用FFFI算法求解得到的ASC的使用率均較高,充分論證了FFFI算法在自動化集裝箱碼頭ASC調度問題應用中的有效性.

5 結束語

本工作針對自動化集裝箱碼頭的自動化跨運車的作業調度問題,建立了混合整數規劃模型,將作業調度問題轉化為同時取貨送貨問題,并提出FFFI算法進行求解.首先,對同時取貨送貨問題進行求解,并且對FFFI算法進行論證,對實驗數據進行統計分析所得到的結論,證明了FFFI算法的高效性;然后,將自動化集裝箱碼頭的自動化跨運車作業調度問題轉化為同時取貨送貨問題進行求解;最后,對不同規模下的作業調度問題進行求解,證實了FFFI算法在實際問題中應用的有效性和可行性.但是,在求解過程中沒有考慮到各個作業任務的時間限制,未來可以在算法中考慮這方面因素進行更深入的研究.

[1]Cao J X,Lee D H,Chen J H,et al.The integrated yard truck and yard crane scheduling problem：Benders’decomposition-based methods[J].Transportation Research Part E：Logistics and Transportation Review,2010,46(3)：344-353.

[2]Homayouni S M,Tang S H,Motlagh O.A genetic algorithm for optimization of integrated scheduling of cranes,vehicles,and storage platforms at automated container terminals[J].Journal of Computational and Applied Mathematics,2014,270：545-556.

[3]Gelareh S,Merzouki R,McGinley K,et al.Scheduling of intelligent and autonomous vehicles under pairing/unpairing collaboration strategy in container terminals[J].Transportation Research Part C：Emerging Technologies,2013,33：1-21.

[4]梁承姬,張松波.集裝箱港口裝卸作業設備集成調度[J].遼寧工程技術大學學報(自然科學版),2015, 34(2)：262-266.

[5]Yuan S,Skinner B T,Huang S D,et al.Mathematical modelling of container transfers for a fleet of autonomous straddle carriers[C]//IEEE International Conference on Robotics and Automation.2010：1261-1266.

[6]Yuan S,Skinner B T,Huang S D,et al.A job grouping approach for planning container transfers at automated seaport container terminals[J].Advanced Engineering Informatics,2011, 25(3)：413-426.

[7]Skinner B T,Yuan S,Huang S D,et al.Optimisation for job scheduling at automated container terminals using genetic algorithm[J].Computers&Industrial Engineering,2013, 64(1)：511-523.

[8]Cai B,Huang S D,Liu D,et al.Optimisation model and exact algorithm for autonomous straddle carrier scheduling at automated container terminals[C]//2011 IEEE/RSJ International Conference on Intelligent Robots and Systems.2011.

[9]Cai B,Huang S D,Liu D,et al.Multiobjective optimization for autonomous straddle carrier scheduling at automated container terminals[J].Transactions on Automation Science and Engineering,2013,10(3)：711-724.

[10]Cai B,Huang S D,Liu D,et al.Rescheduling policies for large-scale task allocation of autonomous straddle carriers under uncertainty at automated container terminals[J].Robotics and Autonomous Systems,2014,62(4)：506-514.

[11]Montan′e F A T,Galv?ao R D.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J].Computers&Operations Research,2006,33(3)： 595-619.

[12]Zhao F G,Sun J S,Li S J,et al.A hybrid genetic algorithm for the traveling salesman problem with pickup and delivery[J].International Journal of Automation and Computing,2009,6(1)： 97-102.

[13]姚錦寶,夏禾,賀興東,等.同時取貨送貨車輛路徑問題的改進的蟻群算法[J].技術與方法,2010(S1)： 76-78.

[14]賈方方,孔德成.同時取送貨車輛路徑問題的改進粒子群優化算法[J].技術與方法,2012,19： 108-111.

[15]Zachariadis E E,Tarantilis C D,Kiranoudis C T.A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service[J].Expert Systems with Applications,2009,36(2)：1070-1081.

[16]Zachariadis E E,Kiranoudis C T.A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries[J].Expert Systems with Applications,2011,38(3)：2717-2726.

本文彩色版可登陸本刊網站查詢：http：//www.journal.shu.edu.cn

Scheduling of automated straddle carrier based on heuristic algorithm

YAO Yuqin,HU Zhihua
(Logistics Research Center,Shanghai Maritime University,Shanghai 201306,China)

For automatic scheduling of automated straddle carrier(ASC)of a container terminal,a mixed integer programming model is established.Considering that ASC can be done in a separate container transport between the shore and yard work independently, this paper turns the ASC container terminal scheduling into a simultaneous pickup and delivery problem,and proposes a first finished first insert(FFFI)heuristic algorithm to solve it.Thus the sequence of ASC is assured.Utilization per ASC is calculated.With the numbers of tasks and ASCs changed,utilization of ASC is calculated to verify effectiveness of the algorithm.

automated container terminal;automated straddle carrier(ASC);first finished first insert(FFFI)heuristic algorithm;simultaneous pickup and delivery;scheduling

U 695. 2;F 252

A

1007-2861(2017)03-0443-09

10.12066/j.issn.1007-2861.1688

2015-06-12

國家自然科學基金青年基金資助項目(71101088);國家自然科學基金面上資助項目(71471109)

胡志華(1977—),男,教授,博士生導師,博士,研究方向為港航與物流運作優化. E-mail：zhhu@shmtu.edu.cn