基于啟發(fā)式算法的自動化跨運車作業(yè)調(diào)度

堯雨琴,胡志華

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

基于啟發(fā)式算法的自動化跨運車作業(yè)調(diào)度

堯雨琴,胡志華

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

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

自動化集裝箱碼頭;自動化跨運車;先完成先執(zhí)行啟發(fā)式算法;同時取貨送貨;調(diào)度

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

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

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

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

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

1 問題描述

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

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

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

2 模型

2.1 符號

2.2 模型

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

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

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

3 FFFI算法

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

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

步驟4如果未完成任務(wù)集非空,轉(zhuǎn)到步驟2.

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

4 算例

4.1 實驗設(shè)計

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

表1 實驗場景Table 1 Experimental scenario

表2 任務(wù)數(shù)據(jù)集Table 2 Tasks’data set

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

圖3 結(jié)果數(shù)據(jù)集Fig.3 Results’set

圖4 ASC的作業(yè)序列Fig.4 ASC’s sequence

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

表3 結(jié)果數(shù)據(jù)Table 3 Results’data

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

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

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

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

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

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

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

5 結(jié)束語

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

[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]梁承姬,張松波.集裝箱港口裝卸作業(yè)設(shè)備集成調(diào)度[J].遼寧工程技術(shù)大學(xué)學(xué)報(自然科學(xué)版),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ìn)的蟻群算法[J].技術(shù)與方法,2010(S1)： 76-78.

[14]賈方方,孔德成.同時取送貨車輛路徑問題的改進(jìn)粒子群優(yōu)化算法[J].技術(shù)與方法,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.

本文彩色版可登陸本刊網(wǎng)站查詢：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

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

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