自動(dòng)化碼頭ALV實(shí)時(shí)任務(wù)分配

宓為建　梁梟　張曉華　夏孟玨　王郡嫻　孫思韻

摘要：

為彌補(bǔ)自動(dòng)化集裝箱碼頭自動(dòng)裝載車(chē)（Automated Lifting Vehicle， ALV）先到先服務(wù)（First Come First Service， FCFS）分配方式的缺陷，提出基于觸發(fā)事件的ALV作業(yè)任務(wù)實(shí)時(shí)分配方式.設(shè)置一組觸發(fā)事件觸發(fā)ALV實(shí)時(shí)分配，以ALV到達(dá)任務(wù)作業(yè)點(diǎn)估計(jì)時(shí)間最短為目標(biāo)，建立ALV實(shí)時(shí)分配模型，選用A*算法對(duì)該模型進(jìn)行求解.通過(guò)與貪婪算法的對(duì)比，驗(yàn)證A*算法的優(yōu)越性.對(duì)用A*算法求解大型集裝箱碼頭ALV實(shí)時(shí)分配問(wèn)題的求解速度和穩(wěn)定性進(jìn)行實(shí)驗(yàn)測(cè)試，結(jié)果驗(yàn)證了選用A*算法的可行性.

關(guān)鍵詞：

自動(dòng)化集裝箱碼頭； ALV實(shí)時(shí)分配； A*算法； 觸發(fā)事件

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

0 引 言

隨著集裝箱碼頭整體效率的不斷提高，碼頭水平運(yùn)輸車(chē)輛的任務(wù)分配問(wèn)題也成為一個(gè)非常重要的問(wèn)題.解決好車(chē)輛任務(wù)分配問(wèn)題，可以使車(chē)輛更好地服務(wù)于其他設(shè)備，提高其他設(shè)備的作業(yè)效率.然而，隨著碼頭向大型化和自動(dòng)化方向發(fā)展，現(xiàn)有的先到先服務(wù)（First Come First Service， FCFS）車(chē)輛任務(wù)分配方式已經(jīng)很難滿(mǎn)足碼頭的作業(yè)需求，急需提出一種更加高效合理的分配方式來(lái)解決水平運(yùn)輸車(chē)輛的任務(wù)分配問(wèn)題.[1]

國(guó)內(nèi)外學(xué)者對(duì)集裝箱碼頭的水平運(yùn)輸車(chē)輛任務(wù)分配問(wèn)題已經(jīng)進(jìn)行了許多研究.NGUYEN等[2]為自動(dòng)化集裝箱碼頭的自動(dòng)裝載車(chē)（Automated Lifting Vehicle， ALV）分配問(wèn)題建立混合整數(shù)規(guī)劃模型.ANGELOUDIS等[3]根據(jù)不準(zhǔn)確的碼頭作業(yè)信息，提出在成本/收益下的車(chē)輛分配模型和求解的算法.LEE等[4]考慮起重機(jī)的作業(yè)時(shí)間，建立根據(jù)多臺(tái)岸橋的作業(yè)任務(wù)順序分配車(chē)輛的混合整數(shù)規(guī)劃模型，應(yīng)用啟發(fā)式算法進(jìn)行求解.RASHIDI等[5]將自動(dòng)導(dǎo)引車(chē)（Automated Guided Vehicle， AGV）的分配問(wèn)題轉(zhuǎn)化為一個(gè)最小成本流問(wèn)題模型，應(yīng)用改進(jìn)的網(wǎng)絡(luò)單純形法求解.CAI等[6]研究跨運(yùn)車(chē)的作業(yè)時(shí)序安排問(wèn)題，利用裝卸和搬運(yùn)的時(shí)間窗解決這個(gè)問(wèn)題，并用分支定界法求解.軒華[7]利用FCFS規(guī)則進(jìn)行水平運(yùn)輸車(chē)輛和任務(wù)的分配，建立數(shù)學(xué)模型并用啟發(fā)式算法進(jìn)行求解.SONG等[8]針對(duì)AGV分配問(wèn)題提出混合元啟發(fā)式方法，并與貪婪算法進(jìn)行仿真實(shí)驗(yàn)對(duì)比.ICHOUA等[9]針對(duì)車(chē)輛分配問(wèn)題提出基于先進(jìn)先出的按時(shí)間的行駛速度模型，通過(guò)與固定行駛時(shí)間的實(shí)驗(yàn)結(jié)果的對(duì)比，發(fā)現(xiàn)按時(shí)間的車(chē)輛分配方式明顯優(yōu)于固定行駛時(shí)間的車(chē)輛分配方式.GUJJULA等[10]總結(jié)幾個(gè)AGV分配問(wèn)題常用的目標(biāo)，包括岸橋等待時(shí)間最短、AGV行駛時(shí)間最短、完成作業(yè)的時(shí)間最短等，也總結(jié)了幾種常用的AGV分配方式，包括最短的行駛時(shí)間、使用車(chē)輛的數(shù)量最少、先到先服務(wù)方式等.LIU等[11]總結(jié)了3種AGV分配規(guī)則，即最大行駛距離、最小行駛距離和隨機(jī)規(guī)則，并分別對(duì)其進(jìn)行仿真.

然而，上述研究都很難解決大型自動(dòng)化碼頭中難以估計(jì)車(chē)輛的實(shí)際行駛時(shí)間的問(wèn)題.在交通布局呈現(xiàn)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的碼頭，由于運(yùn)輸車(chē)輛數(shù)量多，交通堵塞經(jīng)常發(fā)生，對(duì)車(chē)輛的實(shí)際行駛時(shí)間估計(jì)的不準(zhǔn)確會(huì)嚴(yán)重影響車(chē)輛任務(wù)分配方案的選擇.

1 問(wèn)題描述

1.1 目前ALV任務(wù)分配方式

ALV可以在沒(méi)有其他設(shè)備輔助的情況下，自己提起和放下集裝箱.ALV任務(wù)分配問(wèn)題就是在碼頭作業(yè)時(shí)為需要作業(yè)的任務(wù)分配可用的ALV.

目前，碼頭ALV任務(wù)分配主要采用FCFS分配方式，每一個(gè)新產(chǎn)生的集裝箱運(yùn)輸任務(wù)都會(huì)被分配一輛空閑的ALV，這輛ALV是在分配時(shí)最適合去執(zhí)行這個(gè)運(yùn)輸任務(wù)的車(chē).應(yīng)用FCFS分配方式，在為任務(wù)分配了ALV后，即使有更合適的ALV可以選擇，也不能作出改變.因此，這樣的分配方式雖然操作簡(jiǎn)單，但不能實(shí)時(shí)保證水平運(yùn)輸車(chē)輛的任務(wù)分配方案處于最優(yōu)狀態(tài).在ALV運(yùn)輸時(shí)間不確定的大型自動(dòng)化碼頭，F(xiàn)CFS分配方式會(huì)導(dǎo)致ALV的作業(yè)效率大大降低，影響其他設(shè)備的作業(yè)，因此需要設(shè)計(jì)一個(gè)更加高效的水平運(yùn)輸車(chē)輛分配方式.

1.2 ALV實(shí)時(shí)分配方式

ALV實(shí)時(shí)分配是在作業(yè)過(guò)程中的某些條件下進(jìn)行一次ALV的任務(wù)分配，當(dāng)作業(yè)的條件發(fā)生變化時(shí)對(duì)ALV的作業(yè)任務(wù)進(jìn)行重新分配.把這些條件作為一組觸發(fā)事件，每次分配看作一次實(shí)時(shí)分配，建立一個(gè)實(shí)時(shí)分配模型.一組觸發(fā)事件和一個(gè)實(shí)時(shí)分配模型組成一個(gè)完整的ALV實(shí)時(shí)分配方式.

由于大型集裝箱碼頭ALV的作業(yè)過(guò)程中會(huì)經(jīng)常出現(xiàn)過(guò)去的最佳ALV分配方案后來(lái)不再是最佳分配方案的情況，所以要考慮在某些情況

（岸橋（Quay Crane，QC）或者場(chǎng)橋（Yard Crane，YC）準(zhǔn)備吊起下一個(gè)集裝箱；ALV完成上一個(gè)運(yùn)輸任務(wù)；已經(jīng)分配任務(wù)的ALV遇到交通擁堵等）下對(duì)ALV的任務(wù)重新進(jìn)行分配，盡量使ALV的任務(wù)分配方案保持最優(yōu).

對(duì)上述各種作業(yè)條件進(jìn)行歸納總結(jié)，設(shè)置一組觸發(fā)事件.每次觸發(fā)事件發(fā)生時(shí)，都需要進(jìn)行一次實(shí)時(shí)分配.實(shí)時(shí)分配是對(duì)當(dāng)時(shí)所有的任務(wù)和空閑ALV進(jìn)行分配，分配的目標(biāo)是使總的ALV到達(dá)作業(yè)地點(diǎn)的估計(jì)時(shí)間最短.

2 模型建立

2.1 ALV實(shí)時(shí)分配模型

由于集裝箱碼頭其他作業(yè)的ALV實(shí)時(shí)分配方式與裝卸船作業(yè)基本相同，所以本文構(gòu)建模型時(shí)，只以裝船和卸船作業(yè)為例.根據(jù)船的作業(yè)量給船配備適當(dāng)數(shù)量的QC和ALV，分配給同一艘船的所有QC共享分配給這艘船的ALV，分配給這艘船的ALV也只服務(wù)于為這艘船作業(yè)的QC.

2.1.1 模型假設(shè)

一輛ALV最多只能運(yùn)輸一個(gè)集裝箱；

分配給QC的ALV數(shù)量足夠，不會(huì)出現(xiàn)等待運(yùn)輸?shù)募b箱數(shù)量大于閑置ALV數(shù)量的情況；只預(yù)先分配一輛ALV給正在作業(yè)的QC.

2.1.2 參數(shù)定義

C為起重機(jī)即將進(jìn)行作業(yè)的集裝箱集合，如裝船時(shí)YC即將進(jìn)行作業(yè)的集裝箱和卸船時(shí)QC即將進(jìn)行作業(yè)的集裝箱的集合；

c為集合C的元素總數(shù)量；Q為正在對(duì)同一艘船進(jìn)行作業(yè)的QC的集合.在分配ALV時(shí)會(huì)考慮將部分空閑的ALV分配給正在作業(yè)的QC，這些空閑ALV任務(wù)的優(yōu)先級(jí)低于C中任務(wù)的優(yōu)先級(jí).q為集合Q的元素總數(shù)量；d為在實(shí)時(shí)分配時(shí)需要考慮的ALV任務(wù)數(shù)量，包括集裝箱運(yùn)輸任務(wù)數(shù)量和正在作業(yè)的QC的數(shù)量，d=c+q.將任務(wù)d分成兩部分是因?yàn)閮刹糠值姆峙鋬?yōu)先級(jí)不同.A為沒(méi)有開(kāi)始作業(yè)的ALV的集合；a為集合A的元素總數(shù)量；i為任務(wù)的標(biāo)識(shí)，i=1，2，…，c，c+1，…，c+q，其中，i=1，2，…，c表示需要運(yùn)輸?shù)募b箱，i=c+1，c+2，…，c+q表示正在對(duì)同一艘船進(jìn)行作業(yè)的QC；j為ALV的標(biāo)識(shí)，j=1，2，…，a；vj 為ALVj某一時(shí)刻的瞬時(shí)速度，ALVj停在停車(chē)場(chǎng)時(shí)vj=V，V為ALV正常行駛時(shí)的平均速度；dij為ALVj到任務(wù)i的作業(yè)地點(diǎn)的距離；

[WTHX]T[WTBX]為從ALVj到達(dá)任務(wù)作業(yè)地點(diǎn)的估計(jì)時(shí)間矩陣，由ALVj到任務(wù)i的作業(yè)地點(diǎn)的距離和ALVj的瞬時(shí)速度得出；tij為矩陣

[WTHX]T[WTBX]的元素；M為一個(gè)很大的數(shù)，作為預(yù)計(jì)行駛時(shí)間的上限；D為一個(gè)較小的距離常數(shù)，dij

2.1.3 模型構(gòu)建

式（1）表示xij是01變量，當(dāng)ALVj分配給任務(wù)i時(shí)xij=1，否則xij=0.式（2）表示模型的目標(biāo)為ALV到達(dá)作業(yè)地點(diǎn)的估計(jì)時(shí)間最短.由于αβ，會(huì)給到達(dá)任務(wù)地點(diǎn)時(shí)間短的ALV分配集裝箱運(yùn)輸任務(wù)，達(dá)到先考慮將空閑ALV分配給急需ALV的集裝箱運(yùn)輸任務(wù)，再考慮將空閑ALV分配給正在作業(yè)的QC的目的.式（3）表示每個(gè)集裝箱運(yùn)輸任務(wù)和每一臺(tái)正在作業(yè)的QC最多只能有一輛ALV為其服務(wù)；式（4）表示每輛ALV最多只能分配給一個(gè)集裝箱運(yùn)輸任務(wù)或一臺(tái)正在作業(yè)的QC；式（5）表示盡可能多地為需要考慮的作業(yè)任務(wù)分配ALV；式（6）表示根據(jù)距離和速度得出ALV到達(dá)作業(yè)地點(diǎn)的估計(jì)時(shí)間.優(yōu)先考慮分配與任務(wù)地點(diǎn)的距離很近的ALV.

2.2 ALV實(shí)時(shí)分配觸發(fā)事件

在ALV作業(yè)時(shí)，設(shè)置一個(gè)時(shí)間段Δt，在每個(gè)時(shí)間段末檢測(cè)ALV的行駛速度.記錄在第m次分配時(shí)ALV的速度vm，設(shè)置速度變化量為正值Δv.第m次分配后，當(dāng)空閑ALV的速度在某個(gè)檢測(cè)時(shí)間段末超出vm±Δv的范圍（說(shuō)明ALV的行駛速度相對(duì)于第m次分配時(shí)有了巨大變化，可能是因?yàn)锳LV遇到交通擁堵，也可能是因?yàn)锳LV的交通擁堵得到緩解，ALV的行駛速度恢復(fù)正常）時(shí)，需要考慮對(duì)ALV進(jìn)行第m+1次分配.根據(jù)大型集裝箱碼頭的特點(diǎn)，列舉出一組觸發(fā)事件：（1）新的集裝箱運(yùn)輸任務(wù)的產(chǎn)生，即起重機(jī)準(zhǔn)備對(duì)某個(gè)集裝箱進(jìn)行作業(yè)，需要進(jìn)行重新分配；（2）ALV完成上一個(gè)任務(wù)，空閑ALV數(shù)量增加，需要進(jìn)行重新分配；（3）第m次分配后，當(dāng)已經(jīng)分配任務(wù)的ALV的速度在某個(gè)檢測(cè)時(shí)間段末的速度超出vm±Δv且dij>D時(shí)，需要對(duì)ALV進(jìn)行第m+1次分配.

3 算法設(shè)計(jì)

大型高效的集裝箱碼頭ALV實(shí)時(shí)分配觸發(fā)事件發(fā)生的頻率很高，每次觸發(fā)事件的發(fā)生都會(huì)觸發(fā)一次ALV實(shí)時(shí)分配，進(jìn)行ALV實(shí)時(shí)分配的頻率也會(huì)很高，因此對(duì)處理ALV實(shí)時(shí)分配的時(shí)間要求也很高.每次觸發(fā)ALV實(shí)時(shí)分配后，ALV的任務(wù)分配必須在短時(shí)間內(nèi)完成并向ALV發(fā)送作業(yè)指令，這樣才能使ALV實(shí)時(shí)分配方式的優(yōu)勢(shì)得到發(fā)揮.因此，需要一種對(duì)ALV進(jìn)行任務(wù)分配的算法，以快速地對(duì)規(guī)模較大的ALV實(shí)時(shí)分配模型進(jìn)行求解.

3.1 算法簡(jiǎn)介

3.1.1 A*搜索算法

A*搜索算法是靜態(tài)路網(wǎng)中求解最短路最有效的方法.A*搜索算法通過(guò)最佳優(yōu)先搜索來(lái)尋找一條從起始節(jié)點(diǎn)到一個(gè)目標(biāo)節(jié)點(diǎn)或者多個(gè)可能的目標(biāo)節(jié)點(diǎn)的代價(jià)最短的路徑.作為啟發(fā)式搜索的一種，A*搜索算法同樣需要選取估價(jià)函數(shù)，以省略大量的無(wú)意義搜索，提高搜索效率.n是搜索圖中的一個(gè)節(jié)點(diǎn)，A*搜索算法通過(guò)一個(gè)啟發(fā)式代價(jià)函數(shù)

f（n）對(duì)節(jié)點(diǎn)n進(jìn)行評(píng)價(jià)，由f（n）決定在搜索圖中的搜索順序.f（n）是從初始點(diǎn)經(jīng)由節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估價(jià)函數(shù).

式中：g（n）是在狀態(tài)空間中從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)；h（n）是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià).h（n）是f（n）函數(shù)的一部分，是一個(gè)可采納的啟發(fā)式函數(shù).對(duì)h（n）的估計(jì)不能超過(guò)節(jié)點(diǎn)n與目標(biāo)節(jié)點(diǎn)之間的距離.如果應(yīng)用在路徑問(wèn)題中，h（n）可以表示節(jié)點(diǎn)n與目標(biāo)節(jié)點(diǎn)的距離，是兩個(gè)節(jié)點(diǎn)之間可能的最短實(shí)際距離.h（n）是f（n）函數(shù)中最重要的一部分，h（n）設(shè)計(jì)的好壞，決定該算法是否能被稱(chēng)為A*搜索算法，也會(huì)影響搜索的效率[13].

3.1.2 A*搜索算法搜索過(guò)程

在A*算法執(zhí)行的過(guò)程中用到OPEN表（用于存放搜索到的點(diǎn)但非最小代價(jià)節(jié)點(diǎn)的集合）和CLOSE表（用于存放已經(jīng)搜索過(guò)的最小代價(jià)節(jié)點(diǎn)的集合），假設(shè)起點(diǎn)和終點(diǎn)分別用

S和V表示，Vi表示節(jié)點(diǎn)S與V間的任意一點(diǎn)，fi表示該節(jié)點(diǎn)的估價(jià)值.A*搜索算法搜索基本步驟如下.

在搜索過(guò)程中可以根據(jù)需要記錄取得最短路徑的行走軌跡.行走軌跡就是從起始點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的路徑最短的行走方案，也是大多數(shù)問(wèn)題的解.

3.2 算法設(shè)計(jì)

應(yīng)用A*搜索算法對(duì)大型集裝箱碼頭ALV實(shí)時(shí)分配模型進(jìn)行求解時(shí)，可以很容易將碼頭獲取的ALV到達(dá)作業(yè)地點(diǎn)的距離dij按照第2節(jié)的模型規(guī)則轉(zhuǎn)換成ALV到達(dá)作業(yè)地點(diǎn)的估計(jì)時(shí)間tij，以時(shí)間tij作為任務(wù)分配的代價(jià)值進(jìn)行分配.用A*算法求解ALV實(shí)時(shí)分配問(wèn)題，需要先將ALV分配問(wèn)題轉(zhuǎn)換成靜態(tài)路網(wǎng)中的求解最短路問(wèn)題，舉例說(shuō)明如下.

將ALV的任務(wù)分配問(wèn)題轉(zhuǎn)換成一個(gè)路網(wǎng)圖（見(jiàn)圖1），圓圈表示節(jié)點(diǎn)，其中節(jié)點(diǎn)S是起始點(diǎn).根據(jù)ALV的數(shù)量或者任務(wù)的數(shù)量進(jìn)行分層，本文是根據(jù)ALV的數(shù)量進(jìn)行分層的.每一層為一輛ALV分配任務(wù)，下一層是在上一層的基礎(chǔ)上進(jìn)行的，根據(jù)第2節(jié)的模型，按照一輛

ALV最多只能被分配一個(gè)任務(wù)，一個(gè)任務(wù)最多只能分配一輛ALV的原則進(jìn)行分配.例如第一層為ALV1分配任務(wù)，此時(shí)ALV1可以選擇任務(wù)1，2，3三個(gè)任務(wù)，所以節(jié)點(diǎn)S下面有1，2，3三個(gè)節(jié)點(diǎn).節(jié)點(diǎn)1，2，3分別表示將任務(wù)1，2，3分配給ALV1.第二層分配是在第一層分配的基礎(chǔ)上進(jìn)行的.第一層中節(jié)點(diǎn)1表示任務(wù)1分配給ALV1后，第二層ALV2只能分配任務(wù)2或3.因此，節(jié)點(diǎn)1下面有兩個(gè)節(jié)點(diǎn)4，5，節(jié)點(diǎn)4表示將任務(wù)1分配給ALV1后，任務(wù)2分配給ALV2，節(jié)點(diǎn)5表示將任務(wù)1分配給ALV1后，將任務(wù)3分配給ALV2.同樣，節(jié)點(diǎn)2和3下面也分別有兩個(gè)節(jié)點(diǎn).到第三層為ALV3分配任務(wù)時(shí)，ALV3只能選擇上面兩層沒(méi)有選擇的任務(wù)，因此節(jié)點(diǎn)4下面只有一個(gè)節(jié)點(diǎn)10，表示任務(wù)1分配給ALV1，任務(wù)2分配給ALV2后，任務(wù)3分配給ALV3.節(jié)點(diǎn)5下面只有一個(gè)節(jié)點(diǎn)11，表示任務(wù)1分配給ALV1，任務(wù)3分配給ALV2后，任務(wù)2分配給ALV3.其他節(jié)點(diǎn)也按照同樣的規(guī)則進(jìn)行分配，直到所有的ALV分配任務(wù)完成，得到圖1所示的樹(shù)狀圖.

根據(jù)圖1所示的樹(shù)狀圖進(jìn)行搜索，對(duì)于搜索到的節(jié)點(diǎn)，需要求出它的h（n），g（n）和f（n）值.

g（n）是從起始節(jié)點(diǎn)S到達(dá)節(jié)點(diǎn)n所走的總路程，也就是搜索到達(dá)節(jié)點(diǎn)n時(shí)已經(jīng)進(jìn)行任務(wù)分配的總的

ALV到達(dá)作業(yè)地點(diǎn)的估計(jì)時(shí)間.h（n）是未分配的ALV到達(dá)每個(gè)作業(yè)地點(diǎn)的估計(jì)時(shí)間里最小的m個(gè)的總

如圖2所示，在搜索到節(jié)點(diǎn)11時(shí)，f（n）小于OPEN表中所有點(diǎn)的f（n）值，結(jié)束搜索.根據(jù)推理可得， S1511路徑為最優(yōu)路徑，總的ALV到達(dá)作業(yè)地點(diǎn)的估計(jì)時(shí)間為110 s，節(jié)點(diǎn)11代表的意義就是ALV的作業(yè)任務(wù)分配方案，也是問(wèn)題的解，即任務(wù)1分給ALV1，任務(wù)3分給ALV2，任務(wù)2分給ALV3.

在上述案例中，若不考慮從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)h（n），只考慮目前從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)g（n），也可以看作h（n）=0，此時(shí)f（n）=g（n），即貪婪算法.其搜索過(guò)程見(jiàn)圖3.從圖中可以看出，到達(dá)目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑為S1511，最短路程與用A*搜索算法得到的相同，都為110 s，但貪婪算法的搜索點(diǎn)數(shù)多于A*算法.從這個(gè)例子可以看出，A*算法中h（n）的作用是巨大的.

4 算例分析

4.1 A*搜索算法與貪婪算法對(duì)比實(shí)驗(yàn)設(shè)計(jì)

為驗(yàn)證A*搜索算法適用于大型集裝箱碼頭ALV實(shí)時(shí)分配問(wèn)題，設(shè)計(jì)幾組實(shí)驗(yàn).實(shí)驗(yàn)中使用幾組實(shí)驗(yàn)數(shù)據(jù)（ALV任務(wù)分配的到達(dá)作業(yè)地點(diǎn)的估計(jì)時(shí)間），用貪婪算法和A*搜索算法對(duì)ALV實(shí)時(shí)分配問(wèn)題進(jìn)行求解，對(duì)比兩種算法的求解結(jié)果，分析A*算法解決大型集裝箱碼頭ALV實(shí)時(shí)分配問(wèn)題的可行性，同時(shí)也驗(yàn)證A*算法的優(yōu)越性.

對(duì)a輛ALV和q個(gè)任務(wù)進(jìn)行任務(wù)實(shí)時(shí)分配，ALV到達(dá)作業(yè)地點(diǎn)的估計(jì)時(shí)間為a×q的矩陣.本文設(shè)計(jì)8組實(shí)驗(yàn)，分別是a輛ALV和q個(gè)任務(wù)（a=q=6，7，…，13）.實(shí)驗(yàn)數(shù)據(jù)是幾組實(shí)驗(yàn)的ALV到達(dá)作業(yè)地點(diǎn)的估計(jì)時(shí)間矩陣，分別為a×q的時(shí)間矩陣，代表實(shí)驗(yàn)問(wèn)題的規(guī)模，相應(yīng)的實(shí)驗(yàn)組為a×q組，每組進(jìn)行5次實(shí)驗(yàn)，分別對(duì)每組實(shí)驗(yàn)的5次實(shí)驗(yàn)結(jié)果取平均值.

用相同的軟件分別編寫(xiě)利用A*搜索算法和貪婪算法求解ALV實(shí)時(shí)分配問(wèn)題的程序，并在同一臺(tái)筆記本電腦上運(yùn)行.兩種算法使用的實(shí)驗(yàn)數(shù)據(jù)相同，求解出來(lái)的最短路徑的最優(yōu)值也相同.在此問(wèn)題中，這些分配方案是最優(yōu)的，在第3節(jié)中已經(jīng)證明.表3所示是兩種算法每組實(shí)驗(yàn)在求解過(guò)程中的運(yùn)行時(shí)間和總搜索點(diǎn)數(shù)的對(duì)比.通過(guò)對(duì)比可以看出，A*搜索算法的求解時(shí)間和總搜索點(diǎn)數(shù)明顯少于貪婪算法.

如圖4和5所示是求解運(yùn)行時(shí)間和總搜索點(diǎn)數(shù)

的平均值變化趨勢(shì).從圖4和5中可以看出，貪婪算法的運(yùn)行時(shí)間和總搜索點(diǎn)數(shù)隨求解問(wèn)題規(guī)模的變大迅速增加，而A*搜索算法變化得比較慢.這說(shuō)明，在遇到大規(guī)模的求解問(wèn)題時(shí)，A*搜索算法運(yùn)行時(shí)間和總搜索點(diǎn)數(shù)不會(huì)突然變大，求解速度所受的影響不大.

4.2 A*搜索算法性能測(cè)試

為進(jìn)一步驗(yàn)證A*搜索算法的求解速度，在上述實(shí)驗(yàn)的基礎(chǔ)上用A*搜索算法對(duì)14×14至17×17規(guī)模的ALV實(shí)時(shí)分配問(wèn)題進(jìn)行求解，實(shí)驗(yàn)運(yùn)行時(shí)間和總的搜索點(diǎn)數(shù)的平均值見(jiàn)表4.

大型集裝箱碼頭為一艘船最多配備6臺(tái)QC，每臺(tái)QC分配2輛ALV，即為同一艘船服務(wù)的ALV的最大數(shù)量為12臺(tái)，因此ALV實(shí)時(shí)分配問(wèn)題的最大規(guī)模為12×12，去掉部分正在運(yùn)輸集裝箱的ALV，大多數(shù)情況實(shí)時(shí)分配的規(guī)模在10×10以?xún)?nèi).從表3可以看出，10×10規(guī)模的問(wèn)題用A*搜索算法求解的時(shí)間在0.3 s左右.從表3和4可以看出，如果問(wèn)題的規(guī)模加大，A*搜索算法的計(jì)算時(shí)間不會(huì)出現(xiàn)急劇的增長(zhǎng).因此，在計(jì)算時(shí)間上，A*搜索算法完全可以滿(mǎn)足解決大型集裝箱碼頭ALV實(shí)時(shí)任務(wù)分配問(wèn)題的需求.

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

本文在大型自動(dòng)化集裝箱碼頭的背景下，根據(jù)碼頭的新特點(diǎn)和FCFS分配的缺陷，設(shè)計(jì)了基于觸發(fā)事件的ALV作業(yè)任務(wù)實(shí)時(shí)分配方式.設(shè)置了一組觸發(fā)事件觸發(fā)ALV實(shí)時(shí)分配，并以總的ALV到達(dá)任務(wù)作業(yè)地點(diǎn)估計(jì)時(shí)間最短為目標(biāo)，建立了一個(gè)ALV實(shí)時(shí)分配模型.選用A*搜索算法對(duì)分配模型進(jìn)行求解，通過(guò)與貪婪算法的對(duì)比驗(yàn)證A*搜索算法的優(yōu)越性.對(duì)A*搜索算法求解大型集裝箱碼頭的ALV實(shí)時(shí)分配問(wèn)題的求解速度和穩(wěn)定性進(jìn)行實(shí)驗(yàn)測(cè)試，驗(yàn)證了選用A*搜索算法是可行的.

參考文獻(xiàn)：

[1]

趙寧. 集裝箱碼頭發(fā)箱任務(wù)的集卡指派模型[J]. 上海海事大學(xué)學(xué)報(bào)， 2011， 32（1）： 910.

[2]NGUYEN V D， KIM K H. A dispatching method for automated lifting vehicles in automated port container terminals[J]. Computers & Industrial Engineering， 2009， 56（3）： 10021020.

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

[4]LEE L H， CHEW E P， TAN K C， et al. Vehicle dispatching algorithms for container transshipment hubs[J]. OR Spectrum， 2010， 32（3）： 663685.

[5]RASHIDI H， TSANG E P K. A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals[J]. Computers & Mathematics with Applications， 2011， 61（3）： 630641.

[6]CAI Binghuang， HUANG Shoudong， LIU Dikai， et al. Optimisation model and exact algorithm for autonomous straddle carrier scheduling at automated container terminals[J]. Intelligent Robots and Systems （IROS）， 2011 IEEE/RSJ International Conference on. IEEE， 2011（4）： 36863693.

[7]軒華. 基于FCFS策略的帶時(shí)間窗車(chē)隊(duì)調(diào)度問(wèn)題研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息， 2013， 13（6）： 140157.

[8]SONG L Q， HUAGN S Y. A hybrid metaheuristic method for dispatching automated guided vehicles in container terminals[J]. Computational Intelligence in Scheduling （SCIS）， 2013（8）： 5259.

[9]ICHOUA S， GENDREAU M， POTVIN J. Vehicle dispatching with timedependent travel times[J]. European Journal of Operational Research， 2003， 144（2）： 379396.

[10]GUJJULA R， GUNTHER HO. The impact of storage block assignment for import containers on AGV dispatching in highly automated seaport container terminals[J]. Industrial Engineering and Engineering Management， 2008（8）： 17391743.

[11]LIU ChinI， LOANNOU P. A comparison of different AGV dispatching rules in an automated container terminal[J]. Intelligent Transportation Systems， 2002（6）：880885.

[12]張海濤， 程蔭杭. 基于A*算法的全局路徑搜索[J]. 微計(jì)算機(jī)信息， 2007（23）： 238240.

[13]李淑霞. 基于A*的路徑規(guī)劃算法研究[J]. 福建電腦， 2013（3）： 99100.

（編輯 賈裙平）