楊勇生+馮有勇+梁承姬+許波桅+李軍軍

摘要：為解決自動導引小車（Automated Guided Vehicle，AGV）與軌道式龍門起重機（RailMounted Gantry Crane， RMG）的協(xié)同調(diào)度問題，考慮AGV和RMG的任務分配約束，以卸船作業(yè)最小完工時間為目標，建立混合整數(shù)規(guī)劃（Mixed Integer Programming， MIP）模型.改變AGV，岸橋和箱區(qū)數(shù)量的配置，得出不同條件下的完工時間.對該問題設計兩組算例：小規(guī)模算例采用CPLEX軟件和遺傳算法（Genetic Algorithm，GA）分別進行求解，通過結果對比驗證GA的有效性；大規(guī)模算例采用GA求解，給出自動化碼頭設備調(diào)度優(yōu)化方案.分析結果表明，卸船完工時間隨著卸船任務量的增加而增加，隨著AGV，岸橋和箱區(qū)數(shù)量的增加而減少，且AGV和岸橋數(shù)量的增加對完工時間的影響大于箱區(qū)數(shù)量的增加時完工數(shù)量的影響.

關鍵詞： 自動導引小車（AGV）； 堆場箱區(qū)； 協(xié)同調(diào)度； 混合整數(shù)規(guī)劃（MIP）； 遺傳算法（GA）

中圖分類號： U656.135； U691.34

文獻標志碼： A

Abstract： For the integrated scheduling issue of Automated Guided Vehicles （AGVs） and RailMounted Gantry Cranes （RMGs）， a Mixed Integer Programming （MIP） model is proposed so as to minimize the makespan of unloading operation with task allocation constraints of AGVs and RMGs. Changing the numbers of AGVs， quay cranes and blocks， the makespans under different conditions are obtained. Two groups of examples are performed. The smallsized examples are solved by CPLEX software and Genetic Algorithm （GA） respectively， and the validity of GA is verified by comparing the results. The largesized examples are solved only using GA， and the equipment scheduling scheme at an automated container terminal is given. The results show that the makespan increases with the increase of unloading task， and decreases with the increase of the numbers of AGVs， quay cranes and blocks， where the effects of the increase of the numbers of AGVs and quay cranes on the makespan are greater than that of the increase of the number of blocks.

Key words： Automated Guided Vehicle （AGV）； block； integrated scheduling； Mixed Integer Programming （MIP）； Genetic Algorithm （GA）

0 引 言

由于勞動力成本上升、船舶大型化和碼頭作業(yè)高效化等多重原因的影響，國內(nèi)外已經(jīng)掀起了自動化集裝箱碼頭（簡稱自動化碼頭）研究的熱潮.近年來，自動化碼頭成為中國各港口重點建設對象，如：廈門遠海自動化碼頭已建成，目前處于調(diào)試階段；上海洋山四期自動化碼頭正在建設中. 自動導引小車（Automated Guided Vehicle，AGV）是一種典型的水平運輸設備，裝備有電磁、激光等自動導引裝置，沿著規(guī)定的導引路徑在岸橋與堆場間來回作業(yè)，完成集裝箱裝卸任務.本文針對卸船作業(yè)過程，研究AGV與軌道式龍門起重機（RailMounted Gantry Crane，RMG）的協(xié)同調(diào)度問題.

目前，國內(nèi)外學者對自動化碼頭AGV調(diào)度已有一定的研究.單獨研究AGV調(diào)度的有：CHOE等[1]以AGV空駛距離最短和岸橋作業(yè)時間最短為優(yōu)化目標，提出一種基于人工神經(jīng)網(wǎng)絡的在線學習算法，實時選擇最優(yōu)的AGV調(diào)度方案；KIM等[2]以任務的總延遲時間和AGV 的總運輸成本最小為優(yōu)化目標，采用整數(shù)規(guī)劃模型對自動化碼頭AGV的靜態(tài)調(diào)度問題進行了研究；ANGELOUDIS等[3]對不確定環(huán)境下自動化碼頭AGV任務分配問題提出了一種滾動時域的策略，最大限度地減少船舶的在港時間，提高自動化碼頭的作業(yè)效率；MIYAMOTO等[4]主要考慮AGV在自由路徑上的調(diào)度，考慮緩沖區(qū)的容量限制，提出了本地搜索和隨機搜索的方法并進行評估；邱躍龍等[5]在分析自動化碼頭AGV工作的基礎上，建立了基于Petri網(wǎng)的AGV運輸路徑模型，并對其進行了系統(tǒng)性能分析；馬越匯等[6]為研究不確定環(huán)境下自動化碼頭AGV 調(diào)度與配置問題，建立了以最小化最末任務結束時間為目標的基本模型，并通過算例證明了模型的有效性和實用性；霍凱歌等[7]研究了自動化碼頭多載AGV調(diào)度問題，以最小化作業(yè)費用為目標，建立了混合整數(shù)規(guī)劃模型，通過Gurobi和遺傳算法（Genetic Algorithm， GA）求解；康志敏[8]提出在作業(yè)面調(diào)度模式下，考慮集裝箱裝卸并行的作業(yè)工藝，建立以等待時間最少為目標的AGV調(diào)度模型，并利用GA進行求解；柯冉絢等[9]為解決集裝箱碼頭AGV調(diào)度優(yōu)化問題，建立以無效時間最短為原則的數(shù)學模型，采用

NetLogo軟件進行仿真，比較了“作業(yè)線”與“作業(yè)面”兩種AGV調(diào)度模式.

相比單獨研究AGV調(diào)度，研究AGV與場橋或岸橋集成調(diào)度的很少，其中最具代表的有：MEERSMANS等[10]最早提出解決自動化碼頭AGV，岸橋和場橋集成調(diào)度問題，采用分支定界和定向搜索方法在合理的時間內(nèi)求出最小完工時間；WU等[11]和LUO等[12]采用GA研究岸橋與AGV的集成調(diào)度，考慮邊裝邊卸和只卸不裝兩種作業(yè)模式，有效減少了船舶在港時間；XIN等[13]提出一種方法論，在提高自動化碼頭作業(yè)效率的同時減少AGV，岸橋和自動堆垛機的能源消耗，通過仿真論證了該方法的有效性.

傳統(tǒng)碼頭與垂岸式自動化碼頭布局的不同使集卡與AGV的調(diào)度方式有著很大的差別：AGV行駛路徑比較固定，而集卡調(diào)度路徑相對比較靈活，可根據(jù)實時道路交通狀況改變路徑.隨著AGV數(shù)量的增加，AGV之間發(fā)生死鎖與沖突的概率變大，給AGV調(diào)度帶來很大的難度，并且隨著裝卸設備的改進，岸橋和場橋的結構發(fā)生了顯著變化.因此，研究新的裝卸設備具有重要的實用價值.本文主要考慮的是雙小車岸邊起重機、AGV和接力式雙軌道龍門起重機等3種自動化碼頭設備的調(diào)度問題.

1 問題描述

垂岸式自動化碼頭包含泊位區(qū)、岸橋作業(yè)區(qū)、堆場箱區(qū)、AGV水平運輸區(qū)等區(qū)域，其布局見圖1.

本文采用的岸橋是雙小車岸邊起重機.與傳統(tǒng)岸橋不同，雙小車岸邊起重機有2臺小車，一般將靠近海側的稱為海側小車，另一臺稱為岸側小車.岸橋采用接力式的作業(yè)方式，海側小車將集裝箱從船卸至中轉(zhuǎn)平臺，隨即岸側小車將中轉(zhuǎn)平臺上的集裝箱卸至AGV.由于海側小車不用等待AGV，可以連續(xù)進行卸船作業(yè)，因此這種卸箱工藝能最大程度地減少船舶在港時間.本文采用的場橋是接力式雙軌道龍門起重機，每個箱區(qū)配置2臺，分別記為RMG1和RMG2.兩臺RMG互相合作完成任務作業(yè)，具體流程為：首先AGV通過水平運輸將集裝箱運輸?shù)蕉褕鼋唤訁^(qū)，接著RMG1將集裝箱從AGV上卸下，放到箱區(qū)的暫存區(qū)；接著AGV回到岸橋的交接區(qū)運輸下一個集裝箱，與此同時，RMG2將暫存區(qū)的集裝箱卸到指定位置，直到完成所有的卸箱任務.本文主要針對進口箱作業(yè)，已知岸橋卸箱作業(yè)順序，結合岸橋、AGV和RMG等3種設備，建立以最小化最末卸箱任務結束時間為目標的混合整數(shù)規(guī)劃模型，采用CPLEX軟件和GA進行求解，并給出相應的調(diào)度方案.

2 模型建立

2.1 模型假設

根據(jù)自動化碼頭的實際情況，對問題進行合理的簡化.在實際卸船過程中，海側小車、AGV和RMG2的運行時間與集裝箱初始位置（船上位置）和最終位置（箱區(qū)位置）有關，因此可以假設其運行時間在一個范圍內(nèi).[14]

假設：（1）提前分配岸橋給集裝箱船，且已知岸橋卸箱作業(yè)順序；（2）海側小車取箱至中轉(zhuǎn)平臺的時間在一個范圍內(nèi)；（3）岸側小車取箱時間不計，且從中轉(zhuǎn)平臺取箱放到AGV上的時間已知；（4）AGV從岸橋交接區(qū)行駛至堆場交接區(qū)的時間在一個范圍內(nèi)；（5）RMG1取箱時間不計，且取箱至暫存區(qū)的時間已知；（6）RMG2取箱時間不計，且將集裝箱放至指定位置的時間在一個范圍內(nèi)；（7）當AGV開始下一個卸箱作業(yè)時，若沒有可用岸橋和RMG，則AGV需要等待，同理，若岸橋和RMG沒有可用的AGV，則岸橋和RMG也要等待；（8）AGV可以服務任何一個岸橋，集裝箱可以堆存到任何一個箱區(qū).

2.2 模型參數(shù)

稱每卸載1個集裝箱為岸橋完成1個任務.N為任務集合，N={1，2，…，n}，i，j∈N；K為所有岸橋的集合；B為所有可用箱區(qū)的集合，b∈B；S為虛擬開始岸橋；F為虛擬結束岸橋；V為所有可用AGV的集合， v∈V；OS=K∪{S}，OF=K∪{F}，O=K∪{S，F(xiàn)}；k，l∈O；φ為可用AGV的總數(shù)；γ為可用箱區(qū)的總數(shù)；λ為分配給箱區(qū)b的任務數(shù)；uik為岸橋k開始執(zhí)行第i個任務的時刻；tik為海側小車將船上的集裝箱卸到中轉(zhuǎn)平臺上所需的時間；T1為岸側小車將中轉(zhuǎn)平臺上的集裝箱卸到AGV上花費的時間；rik為AGV執(zhí)行岸橋k的第i個任務的時刻；tkb為AGV從岸橋k運行到箱區(qū)b交接區(qū)所需要的時間；dik為AGV到達箱區(qū)交接區(qū)的時刻；T2為RMG1將集裝箱卸到暫存區(qū)所需時間；eik為RMG2開始執(zhí)行岸橋k的第i個任務的時刻；hik為RMG2將岸橋k的第i個集裝箱運到指定位置所需的時間；fik為完成岸橋k的第i個任務的時刻；M是一個較大的整數(shù).

決策變量：xikjl∈{0，1}，xikjl=1表示AGV完成岸橋k的第i個任務后接著執(zhí)行岸橋l的第j個任務，否則xikjl=0；βikv∈{0，1}，βikv=1表示岸橋k的第i個任務分配給編號為v的AGV，否則βikv=0；zikmb∈{0，1}，zikmb=1表示岸橋k的第i個任務是箱區(qū)b的第m個任務，否則zikmb=0；yikb∈{0，1}，yikb=1表示岸橋k的第i個任務落在箱區(qū)b上，否則yikb=0；wikjl∈{0，1}，wikjl=1表示RMG完成岸橋k的第i個任務后再去執(zhí)行岸橋l的第j個任務，否則wikjl=0；σikb∈{0，1}，σikb=1表示岸橋k的第i個任務分配給編號為b的箱區(qū)，否則σikb=0.

基本模型是一個混合整數(shù)規(guī)劃模型[12].令岸橋卸第1個集裝箱的時刻為0，即u1k=0，k∈O.式（1）表示最小化卸船任務的完工時間；式（2）表示岸橋k完成所有任務的時刻（Fk）與完成每個任務的時刻的關系；式（3）表示岸橋k開始執(zhí)行任務的時刻（Sk）與每個任務開始的時刻的關系；式（4）表示AGV完成1個集裝箱運輸任務后還有1個集裝箱運輸任務；式（5）表示AGV開始集裝箱運輸任務之前有1個集裝箱運輸任務；式（6）表示每個集裝箱運輸任務只能由1輛AGV完成；式（7）表示每輛AGV每次只能完成1個集裝箱運輸任務；式（8）表示每個待卸集裝箱都會堆存在堆場箱區(qū)；式（9）表示每個箱區(qū)至少會有1個卸箱任務；式（10）構建了1個中間變量用來表示2個決策變量之間的關系；式（11）表示RMG完成1個卸箱任務后還有1個卸箱任務；式（12）表示RMG開始執(zhí)行卸箱任務前有1個卸箱任務；式（13）表示每個集裝箱只能堆存在1個箱區(qū)上；式（14）表示

RMG每次只能完成1個卸箱任務（RMG每次只能卸1個集裝箱）；式（15）表示在岸側將集裝箱放到AGV上后，AGV才能開始執(zhí)行任務；式（16）表示AGV到達堆場交接區(qū)的時刻與RMG1開始作業(yè)時刻的關系；式（17）表示RMG1將集裝箱運到暫存區(qū)的時刻與RMG2開始作業(yè)時刻的關系；式（18）表示當AGV完成上一個集裝箱運輸任務再回到下一個集裝箱運輸任務指定岸橋緩存區(qū)后，才能開始執(zhí)行下一個任務；式（19）表示RMG1的下一個卸箱任務開始時刻與上一個卸箱任務開始時刻的關系；式（20）表示完成任務的時刻；式（21）表示岸橋執(zhí)行兩個相鄰任務的開始時刻關系；式（22）表示時間參數(shù)的范圍.

3 GA求解

本文所提出的問題涉及岸橋、AGV和RMG，因此采用多層染色體及整數(shù)編碼的方式表示自動化碼頭調(diào)度問題.假設有2臺岸橋，每臺岸橋有9個卸箱任務，1～9為岸橋1的任務，10～18為岸橋2的任務，采用3輛AGV進行水平運輸，將集裝箱隨機卸到3個箱區(qū).第i個卸箱任務的編碼v，b表示第v輛AGV將1個集裝箱運送到箱區(qū)b.染色體示例如圖2所示.根據(jù)箱區(qū)對染色體進行解碼，即將分配給不同箱區(qū)的集裝箱進行適應度值的計算，然后對適應度值進行比較，最大的適應度值即為所求目標函數(shù).

由于每個卸箱任務可以被任何1輛AGV和任何1臺RMG服務，為提高計算最優(yōu)解的效率，交叉操作采用兩點交叉原則（即只需要對染色體的AGV編號和箱區(qū)編號進行交叉操作），變異操作是針對單條染色體進行的（即只要對染色體中AGV編號和箱區(qū)編號進行變異操作）.

交叉操作的具體做法為：選擇2條父代染色體，隨機產(chǎn)生2個切點位置，交換2個切點位置的AGV編號和箱區(qū)編號，得到子代染色體.變異操作的具體做法為：隨機選擇1條父代染色體，確定其中2個變異點，交換2個變異點相對應的子串，得到子代染色體.

4 算例分析

首先對參數(shù)進行初步設定.對小規(guī)模問題（卸箱任務較少），采用MATLAB中的YALMIP工具箱結合CPLEX 12.2求解器進行精確求解，同時采用GA進行近似求解，通過對兩種結果進行對比來驗證GA的有效性.隨著問題規(guī)模的擴大，即卸箱數(shù)量增加，很難采用精確求解方法解決問題，故采用GA獲得滿意解.

4.1 參數(shù)設定

卸箱數(shù)量為4～200個，4～20個集裝箱卸載任務視為小規(guī)模問題，21～200個集裝箱卸載任務視為大規(guī)模問題，AGV數(shù)量為3～10輛，箱區(qū)數(shù)量為2～7個，岸橋數(shù)量為2～5臺.海側小車處理集裝箱的時間服從均勻分布U（30 s，70 s）；RMG2處理集裝箱的時間服從均勻分布U（80 s，140 s）；AGV行駛時間（從岸橋交接區(qū)到堆場交接區(qū)的時間）服從均勻分布U（20 s，90 s）；岸側小車和RMG1處理集裝箱時間是確定的，分別為20 s和25 s.GA參數(shù)設置：交叉概率Pc=0.8，變異概率Pm=0.05，初始種群為50，最大迭代次數(shù)為200.

4.2 小規(guī)模算例

小規(guī)模問題集裝箱任務為4～20個，分別采用CPLEX和GA進行求解.由于GA求解結果存在隨機誤差，所以為減小這個隨機誤差，每個算例運行20次，記錄其平均運算時間和平均最優(yōu)適應度值.最優(yōu)適應度值差異表示采用GA求得的最優(yōu)適應度值與采用CPLEX得到的精確解之間的差異程度.詳細的計算結果見表1.

以算例5為例，共有8個集裝箱任務，3輛AGV，2臺岸橋和3個箱區(qū).利用CPLEX可得到AGV最優(yōu)調(diào)度方案：AGV1的調(diào)度方案為（1，1）→1，（1，3）→1，（2，2）→2；AGV2的調(diào)度方案為（2，1）→2，（2，3）→1，（1，4）→2；AGV3的調(diào)度方案為（1，2）→1，（2，4）→2.也就是說，AGV1執(zhí)行岸橋1的第1個任務到達箱區(qū)1，執(zhí)行岸橋1的第3個任務到達箱區(qū)1，執(zhí)行岸橋2的第2個任務到達箱區(qū)2.同理可得AGV2和AGV3的具體調(diào)度方案.利用CPLEX求解該算例的運行時間為3.32 s，精確解為568 s.

從算例1～3可知，當卸箱數(shù)量較小時，CPLEX能很快計算出結果.然而，隨著卸箱數(shù)量的增加（如算例9和10），CPLEX的求解時間越來越長，當卸箱數(shù)量達到30個時，CPLEX無法在可接受的時間內(nèi)得到精確解.從算例7和8可知，當卸箱數(shù)量相同時，箱區(qū)數(shù)量增加使CPLEX的求解時間變長.再觀察GA的性能：隨著卸箱數(shù)量的增加，GA的求解時間并沒有隨著卸箱數(shù)量的增加而劇烈變化，幾乎穩(wěn)定在2～7 s之間；利用GA求得的最優(yōu)適應度值與利用CPLEX求得的精確解差別不大，最大差別出現(xiàn)在算例7，也只有6.3%， 其他11個算例的平均最優(yōu)適應度值差異為3.26%.以上結果表明，GA對小規(guī)模算例是有效的.

4.3 大規(guī)模算例

采用CPLEX很難在可接受的時間內(nèi)求得大規(guī)模算例的精確解，因此在GA對小規(guī)模算例有效的基礎上，采用GA對大規(guī)模問題進行求解.與小規(guī)模算例一樣，每個算例運行20次，取其平均值來減小誤差.結果見表2.

通過表2可以看出，對大規(guī)模問題：GA能夠在較短的時間內(nèi)得到近似最優(yōu)解；最優(yōu)適應度值隨著卸箱數(shù)量的增加而增大；當卸箱數(shù)量相同時，隨著AGV，岸橋和箱區(qū)數(shù)量的增加，最優(yōu)適應度值變小.從算例13和14可知，當卸箱數(shù)量、AGV數(shù)量和岸橋數(shù)量不變時，箱區(qū)數(shù)量的增加使最優(yōu)適應度值減??；從算例17和18可知，當卸箱數(shù)量、AGV數(shù)量和箱區(qū)數(shù)量不變時，岸橋數(shù)量增加會減小最優(yōu)適應度值；從算例21和22可知，當卸箱數(shù)量、岸橋數(shù)量和箱區(qū)數(shù)量不變時，增加AGV數(shù)量會使最優(yōu)適應度值減小.綜合以上分析可以發(fā)現(xiàn)，岸橋和AGV數(shù)量變化對最優(yōu)適應度值的影響大于箱區(qū)數(shù)量變化的影響.因此，在實際的卸船作業(yè)中，岸橋和AGV的重要性略大于箱區(qū)裝卸設備（RMG）的重要性，但同時需要三者之間的協(xié)調(diào)作業(yè)以提高作業(yè)效率.

圖3為算例13利用GA進行一次求解得到的收斂圖.

5 結束語

自動化碼頭自動導引小車（AGV）調(diào)度方案受到岸橋和堆場的影響，提高AGV水平運輸效率是增強自動化碼頭連續(xù)作業(yè)能力的關鍵因素之一.鑒于此，本文研究了AGV與軌道式龍門起重機（RMG）的協(xié)同調(diào)度問題，以最小化卸船任務完工時間為目標，建立了混合整數(shù)規(guī)劃模型.對小規(guī)模卸箱作業(yè)和大規(guī)模卸箱作業(yè)進行了算例分析.利用CPLEX求得小規(guī)模卸箱作業(yè)的精確解，同時與利用遺傳算法（GA）求得的解進行比較，驗證了GA的有效性；對大規(guī)模卸箱作業(yè)問題，利用GA求得結果，并給出自動化碼頭任務調(diào)度的優(yōu)化方案.

本文只考慮了已知卸箱順序的AGV與RMG的協(xié)同調(diào)度問題，然而任務調(diào)度還受岸橋、AGV和RMG配置數(shù)量的影響，如何合理配置多種設施設備的數(shù)量成為提高碼頭作業(yè)效率的關鍵.此外，水平運輸是銜接岸橋作業(yè)與堆場作業(yè)的關鍵，因此解決AGV水平運輸?shù)膿矶?、死鎖等問題也將會是今后研究的重點.

參考文獻：

[1]CHOE R， KIM J， RYU K R. Online preference learning for adaptive dispatching of AGVs in an automated container terminal[J]. Applied Soft Computing， 2015， 38： 647660.

[2]KIM J， CHOE R， RYU K R. Multiobjective optimization of dispatching strategies for situationadaptive AGV operation in an automated container terminal[C]//Association for Computing Machinery （ACM）. Research in Adaptive and Convergent Systems. New York： ACM， 2013： 16.

[3]ANGELOUDIS P， BELL M G H. An uncertaintyaware AGV assignment algorithm for automated container terminals[J]. Transportation Research Part E， 2010， 46（3）： 354366.

[4]MIYAMOTO T， INOUE K. Local and random searches for dispatch and conflictfree routing problem of capacitated AGV systems[J]. Computers & Industrial Engineering， 2015， 91： 19.

[5]邱躍龍， 陶德馨. 基于時間Petri網(wǎng)的集裝箱碼頭AGV調(diào)度系統(tǒng)建模研究[J]. 武漢理工大學學報（交通科學與工程版）， 2006， 30（6）： 958960.

[6]馬越匯， 胡志華. 不確定環(huán)境下自動化集裝箱碼頭AGV調(diào)度與配置問題[J]. 廣西大學學報（自然科學版）， 2016， 41（2）： 589597.

[7]霍凱歌， 張亞琦， 胡志華. 自動化集裝箱碼頭多載AGV調(diào)度問題研究[J]. 大連理工大學學報， 2016， 56（3）： 244251.

[8]康志敏. 集裝箱自動化碼頭AGV路徑優(yōu)化和調(diào)度研究[D]. 武漢： 武漢理工大學， 2011.

[9]柯冉絢， 任亞東. 集裝箱碼頭AGV調(diào)度優(yōu)化[J]. 集美大學學報（自然科學版）， 2016， 21（1）： 3541.

[10]MEERSMANS P J M， WAGELMANS A P M. Effective algorithms for integrated scheduling of handling equipment at automated container terminals[C]// ERIM Report Series Research in Management. Rotterdam： Erasmus Research Institute of Management， 2001： 31.

[11]WU Yue， LUO Jianbin， ZHANG Dali， et al. An integrated programming model for storage management and vehicle scheduling at container terminals[J]. Research in Transportation Economics， 2013， 42（1）： 1327.

[12]LUO J， WU Y， MENDES A B. Modelling of integrated vehicle scheduling and container storage problems in unloading process at an automated container terminal[J]. Computers & Industrial Engineering， 2016， 94： 3244.

[13]XIN J， NEGENBORN R R， LODEWIJKS G. Energyaware control for automated container terminals using integrated flow shop scheduling and optimal control[J]. Transportation Research Part C， 2014， 44： 214230.

[14]HAN Y， LEE L H， CHEW E P， et al. A yard storage strategy for minimizing traffic congestion in a marine container transshipment hub[J]. OR Spektrum， 2008， 30： 697720.

（編輯 趙勉）