張 偉，張秋菊

(1. 江南大學機械工程學院，江蘇 無錫 214122)

(2.江蘇省食品先進制造裝備技術重點實驗室，江蘇 無錫 214122)

Dijkstra算法在AGV調度系統(tǒng)中的應用

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

(1. 江南大學機械工程學院，江蘇 無錫 214122)

(2.江蘇省食品先進制造裝備技術重點實驗室，江蘇 無錫 214122)

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

任務；匹配；自動導引運輸車/無人搬運車；Dijkstra算法

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

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

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

1 倉儲區(qū)域的有效劃分

倉儲區(qū)域整體結構包括存儲區(qū)、緩沖區(qū)、搬運區(qū)等。主要考慮的是配貨車的停放位置與搬運目標、AGV行走路徑與方向等。

倉儲區(qū)域整體結構中，存儲區(qū)用于存放貨物，其規(guī)模由貨物子類、貨物量確定；緩沖區(qū)用于人工配貨，其規(guī)模大小由貨物的出貨量和進貨量確定；搬運區(qū)主要作用是通過AGV托運配貨車到指定的目標點，搬運區(qū)中包括貨車的待配區(qū)與已配區(qū)、AGV運行路徑區(qū)、充電區(qū)、?？繀^(qū)等。

設某倉儲區(qū)域中的搬運區(qū)的數目為M，AGV數量為Q。規(guī)定搬運區(qū)中的任務點編號為Mi(i=0,1,2,3,…)，AGV運行的地標點編號為Qj(j=1,2,3,…)。確定完成搬運區(qū)域中的任務點與AGV運行的地標點后，需要考慮區(qū)域中無AGV和AGV過載的情況，相對應的解決策略是通過調用鄰近區(qū)域中的空閑AGV或釋放當前區(qū)域中的AGV。

2 AGV在倉儲物流配貨系統(tǒng)中調度問題的描述與建模

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

1)同一時間段任務的優(yōu)先級相同。

2)每臺AGV運行時的速度相同且不考慮啟動和制動的過程。

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

在上述約束條件成立的前提下，建立數學模型如下：

(1)

(2)

(3)

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

3 任務與AGV的匹配問題求解

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

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

3.1任務與AGV的匹配問題

匹配問題換而言之即是任務點與AGV之間路徑最短問題，所以將求最匹配問題轉化為求最短路徑。最短路徑是實際應用中非常有用的方法，常見的2種最短路徑是：1)從某源點到其余各頂點之間的最短路徑。2)每一段頂點之間的最短路徑。

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

3.2Dijkstra算法求最短路徑

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

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

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

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

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

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

2)選擇各AGV當前所在的位置點Vj，滿足：

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

3)把AGV當前所在的位置點Vj加入集合S中。

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

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

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

4 單任務與多任務調度模型的分析與驗證

假設倉儲區(qū)域中的AGV數量為Q(用實心圓形表示)、搬運區(qū)域中的任務數為H(用實心矩形表示)。當前搬運區(qū)域中的任務點為V01，搬運區(qū)域中的AGV所在的目標位置點為Vi。

4.1單任務調用AGV

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

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

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

4.2多任務調用AGV

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

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

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

結果表明,單任務、多任務匹配AGV時，Dijk-stra算法能夠快速準確地搜索到與任務點最匹配的AGV完成任務，當不斷有新的配貨任務發(fā)出請求時，Dijkstra算法能夠找到與任務相匹配的AGV，使得AGV運行的總路程最短，滿足數學模型(2)。

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

5 結束語

本文分析了倉儲物流配貨系統(tǒng)中AGV的調度機制，在基于倉儲區(qū)域的有效劃分和建立數學模型的基礎上，從單任務與多任務匹配AGV方法出發(fā)，運用算法解決了調度系統(tǒng)中任務與AGV匹配的問題，結果表明該方法能夠快速準確地將任務與AGV相匹配，保證了整個系統(tǒng)中的路徑最短。因此該方法能夠為實際的AGV調度系統(tǒng)提供參考。

[1] 李玉.自動導航小車的路徑規(guī)劃與控制研究[D].西安：西安科技大學,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)的調度優(yōu)化模型[J]. 科學技術與工程, 2008 (1):66-69，79.

[6] 柳賽男, 柯映林. 一種解決有AGV小車約束的車間智能調度問題的算法[J].中國機械工程,2007(15):1810-1813.

[7] 王文蕊,吳耀華.自動導引車系統(tǒng)資源分配問題的建模及求解[J]. 計算機應用,2014(3):767-770,805.

[8] 李軍, 郭強, 劉建新. 組合運輸的優(yōu)化調度[J]. 系統(tǒng)工程理論與實踐, 2001, 21(2):117-121.

[9] 金芳,方凱,王京林.基于排隊論的AGV調度研究[J].儀器儀表學報, 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—)，男，江蘇海安人，江南大學碩士研究生 ，主要研究方向為機械電子工程。

TP391.9

A

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