自動(dòng)化集裝箱碼頭自動(dòng)導(dǎo)引小車(chē)與軌道式龍門(mén)起重機(jī)的協(xié)同調(diào)度

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

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

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

中圖分類(lèi)號(hào)： U656.135； U691.34

文獻(xiàn)標(biāo)志碼： 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 引 言

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

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

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

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

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

1 問(wèn)題描述

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

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

2 模型建立

2.1 模型假設(shè)

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

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

2.2 模型參數(shù)

稱(chēng)每卸載1個(gè)集裝箱為岸橋完成1個(gè)任務(wù).N為任務(wù)集合，N={1，2，…，n}，i，j∈N；K為所有岸橋的集合；B為所有可用箱區(qū)的集合，b∈B；S為虛擬開(kāi)始岸橋；F為虛擬結(jié)束岸橋；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的任務(wù)數(shù)；uik為岸橋k開(kāi)始執(zhí)行第i個(gè)任務(wù)的時(shí)刻；tik為海側(cè)小車(chē)將船上的集裝箱卸到中轉(zhuǎn)平臺(tái)上所需的時(shí)間；T1為岸側(cè)小車(chē)將中轉(zhuǎn)平臺(tái)上的集裝箱卸到AGV上花費(fèi)的時(shí)間；rik為AGV執(zhí)行岸橋k的第i個(gè)任務(wù)的時(shí)刻；tkb為AGV從岸橋k運(yùn)行到箱區(qū)b交接區(qū)所需要的時(shí)間；dik為AGV到達(dá)箱區(qū)交接區(qū)的時(shí)刻；T2為RMG1將集裝箱卸到暫存區(qū)所需時(shí)間；eik為RMG2開(kāi)始執(zhí)行岸橋k的第i個(gè)任務(wù)的時(shí)刻；hik為RMG2將岸橋k的第i個(gè)集裝箱運(yùn)到指定位置所需的時(shí)間；fik為完成岸橋k的第i個(gè)任務(wù)的時(shí)刻；M是一個(gè)較大的整數(shù).

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

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

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

3 GA求解

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

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

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

4 算例分析

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

4.1 參數(shù)設(shè)定

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

4.2 小規(guī)模算例

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

以算例5為例，共有8個(gè)集裝箱任務(wù)，3輛AGV，2臺(tái)岸橋和3個(gè)箱區(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.也就是說(shuō)，AGV1執(zhí)行岸橋1的第1個(gè)任務(wù)到達(dá)箱區(qū)1，執(zhí)行岸橋1的第3個(gè)任務(wù)到達(dá)箱區(qū)1，執(zhí)行岸橋2的第2個(gè)任務(wù)到達(dá)箱區(qū)2.同理可得AGV2和AGV3的具體調(diào)度方案.利用CPLEX求解該算例的運(yùn)行時(shí)間為3.32 s，精確解為568 s.

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

4.3 大規(guī)模算例

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

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

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

5 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)：

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

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

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

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

[9]柯冉絢， 任亞?wèn)|. 集裝箱碼頭AGV調(diào)度優(yōu)化[J]. 集美大學(xué)學(xué)報(bào)（自然科學(xué)版）， 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.

（編輯 趙勉）