Dijkstra算法在AGV調(diào)度系統(tǒng)中的應(yīng)用

張 偉，張秋菊

(1. 江南大學(xué)機(jī)械工程學(xué)院，江蘇 無(wú)錫 214122)

(2.江蘇省食品先進(jìn)制造裝備技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫 214122)

Dijkstra算法在AGV調(diào)度系統(tǒng)中的應(yīng)用

張 偉1,2，張秋菊1,2

(1. 江南大學(xué)機(jī)械工程學(xué)院，江蘇 無(wú)錫 214122)

(2.江蘇省食品先進(jìn)制造裝備技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫 214122)

目前倉(cāng)儲(chǔ)物流配貨中，訂單的周期短、批量少、批次多，傳統(tǒng)的倉(cāng)儲(chǔ)物流模式已很難適應(yīng)新的需求。隨著自動(dòng)化倉(cāng)儲(chǔ)物流的不斷發(fā)展，基于AGV的倉(cāng)儲(chǔ)物流配貨技術(shù)得到推廣與使用。首先基于倉(cāng)儲(chǔ)物流形式，建立了一個(gè)有效倉(cāng)儲(chǔ)空間模型并制訂了適于AGV的運(yùn)行路網(wǎng)，然后根據(jù)配單任務(wù)需求，給出了AGV運(yùn)行總距離最短的數(shù)學(xué)模型，對(duì)單任務(wù)調(diào)用AGV及多任務(wù)調(diào)用AGV進(jìn)行分析，運(yùn)用Dijkstra算法解決了倉(cāng)儲(chǔ)配貨系統(tǒng)中AGV與任務(wù)的匹配問(wèn)題。

任務(wù)；匹配；自動(dòng)導(dǎo)引運(yùn)輸車(chē)/無(wú)人搬運(yùn)車(chē)；Dijkstra算法

目前自動(dòng)導(dǎo)引運(yùn)輸車(chē)/無(wú)人搬運(yùn)車(chē)(Automated Guided Vehicle,AGV)在各種應(yīng)用環(huán)境中發(fā)揮了越來(lái)越重要的作用，也逐漸顯示出它的優(yōu)越性，由于AGV具有可靠性好、對(duì)接方便等優(yōu)點(diǎn)，又能實(shí)現(xiàn)生產(chǎn)和搬運(yùn)功能，所以它在各行各業(yè)中得到廣泛的應(yīng)用。本文針對(duì)目前應(yīng)用最廣泛的單向固定導(dǎo)軌的潛伏式AGV運(yùn)用于倉(cāng)儲(chǔ)物流配貨系統(tǒng)中進(jìn)行研究，倉(cāng)儲(chǔ)物流配貨系統(tǒng)中AGV的主要作用是銜接配貨車(chē)在整個(gè)配貨階段的自動(dòng)運(yùn)輸。

倉(cāng)儲(chǔ)物流系統(tǒng)中AGV的調(diào)度問(wèn)題，主要是任務(wù)與AGV的匹配問(wèn)題以及無(wú)沖突的路徑規(guī)劃問(wèn)題，目前大多數(shù)研究主要集中在路徑規(guī)劃問(wèn)題上[1-6]，而對(duì)任務(wù)與AGV匹配問(wèn)題的研究比較少。王文蕊等[7]研究了在規(guī)定的時(shí)間窗內(nèi)滿(mǎn)足約束條件的前提下，調(diào)整任務(wù)的執(zhí)行順序來(lái)實(shí)現(xiàn)與AGV的匹配。李軍等[8]提出了通過(guò)將多任務(wù)相組合由同一輛AGV運(yùn)輸?shù)慕M合運(yùn)輸策略，并為求解問(wèn)題提出了3階段求解算法的設(shè)計(jì)，即：1)任務(wù)分組；2)組內(nèi)線路安排；3)組間線路連接。金芳、方凱等[9]研究了基于排隊(duì)論方法解決自動(dòng)化立體倉(cāng)庫(kù)中AGV的調(diào)度問(wèn)題。

上述任務(wù)與AGV匹配問(wèn)題的研究是通過(guò)將任務(wù)和AGV執(zhí)行方法進(jìn)行處理，包括任務(wù)組合、任務(wù)等待、AGV區(qū)域化、AGV綁定多任務(wù)等方法。由于上述處理方法會(huì)導(dǎo)致任務(wù)的累積，一些任務(wù)等待時(shí)間較長(zhǎng)。在倉(cāng)儲(chǔ)物流配貨系統(tǒng)中，每個(gè)配貨車(chē)綁定的訂單中有多個(gè)任務(wù)，需要系統(tǒng)及時(shí)對(duì)訂單中的任務(wù)進(jìn)行處理和釋放。因此，本文對(duì)倉(cāng)儲(chǔ)物流配貨系統(tǒng)中的任務(wù)與AGV匹配的有效性進(jìn)行研究，在基于對(duì)倉(cāng)儲(chǔ)區(qū)域進(jìn)行有效劃分的前提下，以總路程最短為原則建立數(shù)學(xué)模型，利用Dijkstra算法進(jìn)行求解，得到任務(wù)與AGV匹配的解，并結(jié)合實(shí)例進(jìn)行驗(yàn)證。

1 倉(cāng)儲(chǔ)區(qū)域的有效劃分

倉(cāng)儲(chǔ)區(qū)域整體結(jié)構(gòu)包括存儲(chǔ)區(qū)、緩沖區(qū)、搬運(yùn)區(qū)等。主要考慮的是配貨車(chē)的停放位置與搬運(yùn)目標(biāo)、AGV行走路徑與方向等。

倉(cāng)儲(chǔ)區(qū)域整體結(jié)構(gòu)中，存儲(chǔ)區(qū)用于存放貨物，其規(guī)模由貨物子類(lèi)、貨物量確定；緩沖區(qū)用于人工配貨，其規(guī)模大小由貨物的出貨量和進(jìn)貨量確定；搬運(yùn)區(qū)主要作用是通過(guò)AGV托運(yùn)配貨車(chē)到指定的目標(biāo)點(diǎn)，搬運(yùn)區(qū)中包括貨車(chē)的待配區(qū)與已配區(qū)、AGV運(yùn)行路徑區(qū)、充電區(qū)、停靠區(qū)等。

設(shè)某倉(cāng)儲(chǔ)區(qū)域中的搬運(yùn)區(qū)的數(shù)目為M，AGV數(shù)量為Q。規(guī)定搬運(yùn)區(qū)中的任務(wù)點(diǎn)編號(hào)為Mi(i=0,1,2,3,…)，AGV運(yùn)行的地標(biāo)點(diǎn)編號(hào)為Qj(j=1,2,3,…)。確定完成搬運(yùn)區(qū)域中的任務(wù)點(diǎn)與AGV運(yùn)行的地標(biāo)點(diǎn)后，需要考慮區(qū)域中無(wú)AGV和AGV過(guò)載的情況，相對(duì)應(yīng)的解決策略是通過(guò)調(diào)用鄰近區(qū)域中的空閑AGV或釋放當(dāng)前區(qū)域中的AGV。

2 AGV在倉(cāng)儲(chǔ)物流配貨系統(tǒng)中調(diào)度問(wèn)題的描述與建模

倉(cāng)儲(chǔ)物流系統(tǒng)中AGV調(diào)度策略是，當(dāng)任務(wù)到達(dá)時(shí)由調(diào)度系統(tǒng)尋找與其匹配的AGV執(zhí)行任務(wù)。調(diào)度策略不僅要考慮當(dāng)前AGV所在地標(biāo)點(diǎn)到任務(wù)點(diǎn)的路徑最短，也要考慮到系統(tǒng)中的總路徑最短。針對(duì)上述調(diào)度策略，本文采用了單任務(wù)與AGV和多任務(wù)與AGV匹配的方法進(jìn)行分析，通過(guò)分析單任務(wù)與AGV的匹配方法后，按照同樣的分析原理，對(duì)多任務(wù)與AGV的匹配進(jìn)行分析。建立數(shù)學(xué)模型前假設(shè)以下條件成立：

1)同一時(shí)間段任務(wù)的優(yōu)先級(jí)相同。

2)每臺(tái)AGV運(yùn)行時(shí)的速度相同且不考慮啟動(dòng)和制動(dòng)的過(guò)程。

3)AGV運(yùn)行時(shí)不發(fā)生碰撞和死鎖情況。

在上述約束條件成立的前提下，建立數(shù)學(xué)模型如下：

(1)

(2)

(3)

模型(1)表示單任務(wù)調(diào)度AGV到任務(wù)點(diǎn)的最小總路徑(mind)，其中D表示AGV在完成某單一任務(wù)時(shí)所行走的最小路徑值，x表示所調(diào)度的小車(chē)數(shù)，n表示總車(chē)數(shù)。模型(2)表示區(qū)域中多任務(wù)調(diào)度AGV小車(chē)到所有調(diào)度任務(wù)點(diǎn)的最小總路徑，其中y表示區(qū)域中調(diào)度任務(wù)點(diǎn)數(shù)，N表示總?cè)蝿?wù)點(diǎn)數(shù)。模型(3)表示所有搬運(yùn)區(qū)域中的多任務(wù)調(diào)度AGV小車(chē)到所有調(diào)度任務(wù)點(diǎn)的最小總路徑之和，其中h表示搬運(yùn)區(qū)域數(shù)，H表示搬運(yùn)區(qū)域總數(shù)。

3 任務(wù)與AGV的匹配問(wèn)題求解

模型建立完成后，求解任務(wù)與AGV的匹配問(wèn)題時(shí)需要將路徑網(wǎng)以結(jié)構(gòu)圖的形式進(jìn)行保存。在結(jié)構(gòu)圖中，任意兩個(gè)區(qū)域之間都可能存在相應(yīng)的關(guān)系，比線性表和樹(shù)表要復(fù)雜。由于不存在前后順序即相對(duì)應(yīng)的關(guān)系是獨(dú)立的，因而不能采用簡(jiǎn)單的數(shù)組來(lái)存儲(chǔ)圖。另一方面，如果采用鏈表，由于圖中各區(qū)域的任務(wù)數(shù)不盡相同，可能差別很大，如果按最大的區(qū)域任務(wù)數(shù)來(lái)設(shè)計(jì)鏈表的指針域，則會(huì)浪費(fèi)很多存儲(chǔ)單元；反之，如果按照各個(gè)區(qū)域的任務(wù)數(shù)來(lái)設(shè)計(jì)不同的鏈表結(jié)點(diǎn)，則會(huì)使程序更加復(fù)雜且給操作帶來(lái)更大的困難。

本文選用鄰接矩陣存儲(chǔ)路徑網(wǎng)結(jié)構(gòu)圖。采用鄰接矩陣存儲(chǔ)，很容易判斷圖中區(qū)域中的任務(wù)與所調(diào)用的AGV是否相連，也容易求出各個(gè)區(qū)域的任務(wù)數(shù)。但是任何事物都不是完美的，采用鄰接矩陣存儲(chǔ)圖時(shí)，測(cè)試其邊的數(shù)目，必須遍歷二維數(shù)組中的所有元素，時(shí)間復(fù)雜度為O(n2)，這對(duì)于區(qū)域很多而邊較少的圖(稀疏圖)是不合算的。由于本文中的區(qū)域和路徑相對(duì)比較多，所以并不受到上述問(wèn)題的影響。

3.1任務(wù)與AGV的匹配問(wèn)題

匹配問(wèn)題換而言之即是任務(wù)點(diǎn)與AGV之間路徑最短問(wèn)題，所以將求最匹配問(wèn)題轉(zhuǎn)化為求最短路徑。最短路徑是實(shí)際應(yīng)用中非常有用的方法，常見(jiàn)的2種最短路徑是：1)從某源點(diǎn)到其余各頂點(diǎn)之間的最短路徑。2)每一段頂點(diǎn)之間的最短路徑。

本文研究中所指的最短路徑為第1種，即從某一任務(wù)區(qū)域到各個(gè)AGV之間的最短路徑。

3.2Dijkstra算法求最短路徑

本文采用Dijkstra算法求解區(qū)域中任務(wù)點(diǎn)到各AGV的最短距離，通過(guò)總距離最短原則得到各相匹配的AGV,并將此AGV的編號(hào)反饋給調(diào)度系統(tǒng)。

Dijkstra算法是按路徑長(zhǎng)度遞增的次序逐步產(chǎn)生源點(diǎn)到其他頂點(diǎn)間的最短路徑。算法建立一個(gè)頂點(diǎn)集合S，初始時(shí)該集合只有V0(任務(wù)點(diǎn))，然后逐步將已求得最短路徑的頂點(diǎn)加入到集合中，直到全部頂點(diǎn)都在集合S中，算法結(jié)束。

Dijkstra算法尋求區(qū)域中任務(wù)點(diǎn)到AGV的最短路徑的基本過(guò)程如下：

設(shè)cost[i,j]=0 (cost[i,j]為鄰接矩陣用于存儲(chǔ)各條邊的路徑值)，S為已經(jīng)求得最短路徑的頂點(diǎn)集合，Vi表示AGV當(dāng)前所在的位置點(diǎn)(i=1,2,…,n)。distance[i]用于存儲(chǔ)當(dāng)前狀態(tài)下任務(wù)點(diǎn)V0到各AGV的最短路徑。算法過(guò)程如下：

1)初始化，區(qū)域中任務(wù)工位點(diǎn)V0已在最短路徑的頂點(diǎn)集合S中。

S={V0},distance[i]=cost[0,i]

2)選擇各AGV當(dāng)前所在的位置點(diǎn)Vj，滿(mǎn)足：

distance[j]=min{distance[i]|Vi∈V-S}

3)把AGV當(dāng)前所在的位置點(diǎn)Vj加入集合S中。

4)修改distance數(shù)組元素，修改方法為對(duì)于所有不在集合S中的頂點(diǎn)Vi,if(distance[j]+cost[i,j]

5)重復(fù)操作2)、3)、4)，直到全部的點(diǎn)加入到集合S中。

6)通過(guò)總距離最短原則得到相匹配的AGV，算法結(jié)束。算法的流程圖如圖1所示。

4 單任務(wù)與多任務(wù)調(diào)度模型的分析與驗(yàn)證

假設(shè)倉(cāng)儲(chǔ)區(qū)域中的AGV數(shù)量為Q(用實(shí)心圓形表示)、搬運(yùn)區(qū)域中的任務(wù)數(shù)為H(用實(shí)心矩形表示)。當(dāng)前搬運(yùn)區(qū)域中的任務(wù)點(diǎn)為V01，搬運(yùn)區(qū)域中的AGV所在的目標(biāo)位置點(diǎn)為Vi。

4.1單任務(wù)調(diào)用AGV

分析單任務(wù)調(diào)用AGV的情況，選取H=1、Q=5，路段信息如圖2(a)中的有向圖所示，得到相應(yīng)的鄰接矩陣如圖2(b)所示(當(dāng)任務(wù)與AGV之間和AGV與AGV之間若不存在路徑時(shí)取當(dāng)前路徑值為∞。)

由Dijkstra算法將區(qū)域中的任務(wù)點(diǎn)與各AGV的最短路徑求出后得到距離最短的AGV，最后由調(diào)度系統(tǒng)將AGV與任務(wù)進(jìn)行匹配，輸出結(jié)果見(jiàn)表1。

輸出結(jié)果為：任務(wù)區(qū)域V01選定的AGV編號(hào)為2，2號(hào)AGV距離任務(wù)區(qū)域V01的距離為300m。

4.2多任務(wù)調(diào)用AGV

由單任務(wù)調(diào)度模型的分析與驗(yàn)證可以得出多任務(wù)的調(diào)度模型。對(duì)多任務(wù)與AGV的情況進(jìn)行分析，選取區(qū)域中任務(wù)點(diǎn)H=3，AGV數(shù)量Q=6，路段信息與對(duì)應(yīng)有向圖的鄰接矩陣如圖3所示。

同樣由Dijkstra算法將區(qū)域中的多任務(wù)點(diǎn)與各AGV的最短路徑進(jìn)行分析比較，得到匹配結(jié)果，輸出結(jié)果見(jiàn)表2。

輸出結(jié)果為：任務(wù)區(qū)域V01選定的AGV編號(hào)為3，3號(hào)AGV距離任務(wù)區(qū)域V01的距離為300m。任務(wù)區(qū)域V02選定的AGV編號(hào)為4，4號(hào)AGV距離任務(wù)區(qū)域V02的距離為350m。任務(wù)區(qū)域V03選定的AGV編號(hào)為6，6號(hào)AGV距離任務(wù)區(qū)域V03的距離為300m。

結(jié)果表明,單任務(wù)、多任務(wù)匹配AGV時(shí)，Dijk-stra算法能夠快速準(zhǔn)確地搜索到與任務(wù)點(diǎn)最匹配的AGV完成任務(wù)，當(dāng)不斷有新的配貨任務(wù)發(fā)出請(qǐng)求時(shí)，Dijkstra算法能夠找到與任務(wù)相匹配的AGV，使得AGV運(yùn)行的總路程最短，滿(mǎn)足數(shù)學(xué)模型(2)。

驗(yàn)證結(jié)果說(shuō)明，任務(wù)和AGV的匹配不是簡(jiǎn)單的求取兩者之間的最短距離，而是在已知的最短距離中找到滿(mǎn)足總路程最短要求的路徑，從而得出相應(yīng)的匹配關(guān)系。當(dāng)多任務(wù)與同一AGV的距離相等且都為最短距離時(shí)，由Dijkstra算法先對(duì)其中一個(gè)任務(wù)點(diǎn)選取最近AGV，然后對(duì)另外的任務(wù)點(diǎn)依次選取距離次短的AGV，最終使得總距離最短?？梢?jiàn)區(qū)域中任務(wù)數(shù)為H、AGV數(shù)為Q時(shí)，算法能夠滿(mǎn)足數(shù)學(xué)模型(3)要求。當(dāng)系統(tǒng)中有多區(qū)域任務(wù)請(qǐng)求時(shí)，該算法同樣滿(mǎn)足數(shù)學(xué)模型(3)，使得總路程最短。

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

本文分析了倉(cāng)儲(chǔ)物流配貨系統(tǒng)中AGV的調(diào)度機(jī)制，在基于倉(cāng)儲(chǔ)區(qū)域的有效劃分和建立數(shù)學(xué)模型的基礎(chǔ)上，從單任務(wù)與多任務(wù)匹配AGV方法出發(fā)，運(yùn)用算法解決了調(diào)度系統(tǒng)中任務(wù)與AGV匹配的問(wèn)題，結(jié)果表明該方法能夠快速準(zhǔn)確地將任務(wù)與AGV相匹配，保證了整個(gè)系統(tǒng)中的路徑最短。因此該方法能夠?yàn)閷?shí)際的AGV調(diào)度系統(tǒng)提供參考。

[1] 李玉.自動(dòng)導(dǎo)航小車(chē)的路徑規(guī)劃與控制研究[D].西安：西安科技大學(xué),2008.

[2]LinLin，SeongWhanShinn，MitsuoGen，etal.NetworkmodelandeffectiveevolutionaryapproachforAGVdispatchinginmanufacturingsystem[J].JournalofIntelligentManufacturing, 2006, 17(4):465-477.

[3]ZengChengkuan，TangJiafu，YanChongjun.Schedulingofnobufferjobshopcellswithblockingconstraintsandautomatedguidedvehicles[J].AppliedSoftComputing,2014,24: 1033-1046.

[4]Smolic-RocakN,BogdanS,KovacicZ,etal.Timewindowsbaseddynamicroutinginmulti-AGVsystems.[J].IEEETransactionsonAutomationScienceandEngineering,2010, 7(1):151-155.

[5] 雷定猷, 張?zhí)m.AGV系統(tǒng)的調(diào)度優(yōu)化模型[J]. 科學(xué)技術(shù)與工程, 2008 (1):66-69，79.

[6] 柳賽男, 柯映林. 一種解決有AGV小車(chē)約束的車(chē)間智能調(diào)度問(wèn)題的算法[J].中國(guó)機(jī)械工程,2007(15):1810-1813.

[7] 王文蕊,吳耀華.自動(dòng)導(dǎo)引車(chē)系統(tǒng)資源分配問(wèn)題的建模及求解[J]. 計(jì)算機(jī)應(yīng)用,2014(3):767-770,805.

[8] 李軍, 郭強(qiáng), 劉建新. 組合運(yùn)輸?shù)膬?yōu)化調(diào)度[J]. 系統(tǒng)工程理論與實(shí)踐, 2001, 21(2):117-121.

[9] 金芳,方凱,王京林.基于排隊(duì)論的AGV調(diào)度研究[J].儀器儀表學(xué)報(bào), 2004(增刊1):844-846，874.

The application of Dijkstra algorithm in the AGV dispatching system

ZHANG Wei1,2, ZHANG Qiuju1,2

(1.School of Mechanical Engineering, Jiangnan University, Jiangsu Wuxi, 214122, China)

(2.The key laboratory for advanced food manufacturing equipment technology of Jiangsu province, Jiangsu Wuxi, 214122, China)

It is difficult for traditional logistics mode to meet the market demand. It analyzes the requirement such as the short order cyclet, small batch and much batch times. Automated warehousing logistics has constantly get new development and application. Based on the AGV (automatic guided vehicle/AGV), it introduces the warehousing logistics distribution technology, designs the warehousing logistics form, establishes an effective storage space model and obtains a suitable road network for AGV run. Based on the single mission requirements, it builds the mathematical model of AGV running at the shortest total distance, analyzes from the methods of single task transfers AGV to multitasking transfers to AGV, applies Dijkstra algorithm to solve the warehousing distribution matching problem of AGV with tasks in the system.

task; AGV; Dijkstra algorithm; matches

10.3969/j.issn.2095-509X.2015.05.014

2015-04-23

張偉(1990—)，男，江蘇海安人，江南大學(xué)碩士研究生 ，主要研究方向?yàn)闄C(jī)械電子工程。

TP391.9

A

2095-509X(2015)05-0061-04