趙雨亭，葉 峰，賴乙宗，謝先治，洪 崢

（華南理工大學(xué) 機(jī)械與汽車工程學(xué)院，廣州 510640）

面向智能倉儲系統(tǒng)的多AGV運行策略優(yōu)化

趙雨亭，葉 峰，賴乙宗，謝先治，洪 崢

（華南理工大學(xué) 機(jī)械與汽車工程學(xué)院，廣州 510640）

該文研究了智能倉儲中自動導(dǎo)向車AGV 2種運行方向模式的效率。對于局部回環(huán)運行模式，為提高AGV的運行效率，提出了基于道路復(fù)用的AGV運行策略優(yōu)化方案；對于單個AGV存在潛在捷徑的特定轉(zhuǎn)向序列的路徑，在與其他AGV無碰撞和沖突的條件下進(jìn)行優(yōu)化。給出了優(yōu)化適用的條件和實現(xiàn)方法。仿真試驗證明了優(yōu)化的AGV運行策略的有效性和可用性。

自動導(dǎo)向車；自動引導(dǎo)搬運車；局部環(huán)路；智能倉儲；運行策略；運行方向模式

智能倉儲，摒棄了傳統(tǒng)倉儲系統(tǒng)以人力進(jìn)行分揀，效率低下的缺點，轉(zhuǎn)而以自動導(dǎo)向車AGV（automate guided vehicle）作為運載工具，輔以智能調(diào)度系統(tǒng)，實現(xiàn)了物流倉庫“由人取貨物”至“從貨物到人”的轉(zhuǎn)變，大大提高了物流分揀的速度。AGV的運行方式與智能倉儲的運行效率密切相關(guān)，因此對AGV運行策略進(jìn)行研究具有重要意義。

國內(nèi)外已有對倉儲AGV的實踐和報道。國外的Kiva System在2006年實現(xiàn)了基于AGV的倉儲系統(tǒng)[1]，并于2012年被Amazon收購。國內(nèi)有?？低暀C(jī)器人、深圳歐鎧機(jī)器人等。在AGV研究方面，文獻(xiàn)[2-3]總結(jié)了通用的AGV調(diào)度和路徑規(guī)劃問題及解決方案。文獻(xiàn)[4]給出了空間運動的一般規(guī)劃方法。文獻(xiàn)[5]給出了自主運輸車的現(xiàn)狀和研究思路。截至目前，國內(nèi)外對AGV的調(diào)度策略研究多集中于柔性制造系統(tǒng)（FMS）領(lǐng)域[6-7]，對智能倉儲領(lǐng)域AGV應(yīng)用和研究則寥寥可數(shù)。

在此，針對智能倉儲貨架區(qū)AGV運行方向的2種規(guī)定模式進(jìn)行了研究，分析了這2種模式下單臺AGV訪問貨架的距離結(jié)果。對于局部回環(huán)地圖中規(guī)劃出的“幾”字形路徑，在避免碰撞和死鎖的基礎(chǔ)上，提出了運行策略上的優(yōu)化方法，通過計算機(jī)仿真，驗證了所提優(yōu)化后運行策略的有效性。

1 智能倉儲工作方式

智能倉儲系統(tǒng)的主要功能是貨物入庫和出庫。無論是入庫操作還是出庫操作，都需要AGV從貨架區(qū)將貨架取出，送至入（出）庫區(qū)。待工人將貨物從貨架上取出，AGV再將貨架送回至貨架區(qū)，送回的位置隨AGV調(diào)度系統(tǒng)的制定而給定。

智能倉儲的實際區(qū)域一般劃分為入庫區(qū)、出庫區(qū)、貨架區(qū)和中間區(qū)域。多以柵格法構(gòu)建地圖模型。以下重點研究貨架區(qū)AGV的運行策略。

1.1 AGV運行方向的兩種模式

為了簡化AGV路徑規(guī)劃，AGV在路段中的運行方向一般都在設(shè)計時期給定，給定的模式通常有2種，即交叉模式（模式1）和局部環(huán)路模式（模式2），如圖 1 所示。

圖1 兩種AGV運行方向模式Fig.1 Two AGV running patterns

在圖1中，帶陰影的柵格為貨架，無陰影的柵格為通道；通道上標(biāo)示有圓點的柵格稱為交叉點；2個交叉點之間（不包含交叉點）的白色柵格連接成的區(qū)域稱為路段；通道上的箭頭表示該路段的方向。AGV僅能從縱向通道中訪問貨架，而橫向通道僅供AGV通行使用。

1.2 模式比較

為了評估單個AGV在2種規(guī)定運行模式下的效率，假設(shè)1輛AGV存在于圖2所示的中心位置（標(biāo)有數(shù)字0），計算其訪問周圍4×4組貨架時運行的步數(shù)。AGV只能向南向北向東或向西移動1格（稱作1步），且AGV只能從縱向路段訪問至相鄰貨架，不考慮轉(zhuǎn)彎所消耗的步數(shù)。計算的結(jié)果如2所示，貨架處標(biāo)明的數(shù)字為AGV移動到該貨架最近的步數(shù)。

圖2 兩種模式下AGV訪問貨架所需步數(shù)Fig.2 AGV steps needed in two patterns

以AGV起始位置為原點，建立笛卡爾坐標(biāo)系。以象限為單元，計算AGV訪問單元內(nèi)貨架移動步數(shù)的均值，可得表1。分析數(shù)據(jù)可知，單個AGV在訪問第Ⅰ象限的貨架時，模式1優(yōu)于模式2；在訪問第Ⅱ象限貨架時，模式1與模式2持平；在訪問第Ⅲ象限和第Ⅳ象限貨架時，模式1劣于模式2。觀察發(fā)現(xiàn)，模式2下規(guī)定的路段方向是關(guān)于x，y軸對稱的，故單個AGV在模式2條件下訪問4個象限貨架的平均值是相同的。

表1 2種模式下AGV運行步數(shù)的均值Tab.1 Average of AGV steps needed in two patterns

綜合考慮，模式2對于單個AGV路徑規(guī)劃而言更優(yōu)。即使如此，模式2在多AGV路徑規(guī)劃下仍具有優(yōu)化的空間，在此給出模式2下優(yōu)化的運行策略。

2 局部回環(huán)模式下AGV運行策略優(yōu)化

在模式2條件下，考慮圖3所示情形，AGV在經(jīng)過S訪問T處貨架時，根據(jù)最短路徑規(guī)劃的算法（如經(jīng)典的Dijkstra算法或A-Star算法），可能有2種規(guī)劃的結(jié)果，分別標(biāo)注了數(shù)字1和2，這2種AGV移動的步數(shù)相同。由其形狀，可稱這種路徑為“幾”字形路徑。當(dāng)1臺AGV沿此“幾”字形運行而附近區(qū)域無其他AGV影響時無疑是低效的，故針對這種已經(jīng)規(guī)劃好的路徑的情形，在多AGV運行時，考慮到AGV之間可能存在的碰撞沖突問題，通過動態(tài)調(diào)整AGV運行策略，提高運行效率。

圖3 目標(biāo)為T且經(jīng)過S的2種“幾”字形路徑Fig.3 Two kinds of special path when target is T passed by S

定義函數(shù) P（v）＝（Row（v），Col（v）），式中：v 為任一柵格；Row（v）為柵格 v 所在位置的行數(shù)；Col（v）為柵格v所在位置的列數(shù)。

設(shè)Ai為標(biāo)作i的AGV。Ai正在運行的柵格序列為 Path（Ai），有式（1）成立：

對于柵格 vij和柵格 vi（j+1），有式（2）或式（3）成立，且對于任意整數(shù)不同于。Abs（）為取絕對值的函數(shù)：

式（4）中，dij（ j∈［1，n-1］∩Z）為 vij到 vi（j+1）的方向。dij有4種取值情況：

特別地，定義di0為一個數(shù)值，其與Ai在柵格vi1處的東西北朝向的關(guān)系為

式（7）給出了自變量為Ai的轉(zhuǎn)向函數(shù)，Ai在vij處應(yīng)進(jìn)行的轉(zhuǎn)向動作取值為 zij（ j∈［1，n-1］∩Z），滿足

當(dāng) zij＝-1 時，Ai在 vij處左轉(zhuǎn) 90°；

當(dāng) zij＝0 時，Ai在 vij處不必轉(zhuǎn)向；

當(dāng) zij＝1 時，Ai在 vij處右轉(zhuǎn) 90°；

當(dāng) zij＝2時，Ai在 vij處順時針或逆時針旋轉(zhuǎn)180°，且可以推斷此時 j＝1。

使用記號 v（i，j）表示 vij，使用記號 z（i，j）表示zij。 可以推知，v（i，x1）（x1∈［1，n-1］∩Z）是“幾”字形第 1 交叉點的充要條件，即存在整數(shù) x1＜x2＜x3＜x4≤n-1，滿足以下條件1、條件2和條件3：

條件 1v（i，xk）（k＝1，2，3，4）是交叉點。

條件 2?x∈（x1，x2）∪（x2，x3）∪（x3，x4）∪Z，Z（i，x）＝0。

條件3“幾”字形轉(zhuǎn)向條件，即式（9）為恒真式，

在條件 1、條件 2、條件 3 成立時，稱 v（i，xk），其中 k＝1，2，3，4 為“幾”字形第 k 交叉點。

根據(jù)“幾”字形道路經(jīng)過的交叉點情況，將“幾”字形道路分為4類，Ⅰ型，Ⅱ型，Ⅲ型和Ⅳ型，其性質(zhì)如表2所示。

表2 “幾”字形路徑類型的交叉點轉(zhuǎn)向及捷徑路段方向Tab.2 Turns on crossroads and direction of shortcuts in special path

定義兩柵格 a與 b的捷徑 ShortCut（a，b）為 n-元組，其形式為

其中，v1=a，vn=b，元組中任意兩柵格對象是不同的，且對于任意整數(shù)j∈［1，n-1］，僅滿足條件4或條件5二者之一：

條件 4Abs（Col（vj）-Col（v（j+1）））＝1

且 Row（vj）＝Row（v（j+1））

條件 5Abs（Row（vj）-Row（v（j+1）））＝1

且 Col（vj）＝Col（v（j+1））

“幾”字形第1交叉點存在意味著“幾”字形的第2，第3，第4交叉點也是存在的，也意味著“幾”字形路徑存在。若Path（Ai）中存在“幾”字形第1交叉點 v（i，x1），則稱路徑 Path（Ai）在單 AGV 條件下對于柵格v（i，x1）是可優(yōu)化的。優(yōu)化的方式是將Path（Ai）中的 v（i，x1），…，v（i，x4）序列替換為ShortCut（v（i，x1），v（i，x4））中所含的對象序列。 當(dāng)“幾”字形路徑屬于Ⅰ型和Ⅱ型時，對應(yīng)的捷徑滿足條件4；當(dāng)“幾”字形路徑屬于Ⅲ型和Ⅳ型時，對應(yīng)的捷徑滿足條件5。

假設(shè)Path（Ai）在單AGV條件下是可優(yōu)化的，此時并不能稱其在多AGV情況下也是可優(yōu)化的。因為在優(yōu)化使用的捷徑方向是與規(guī)定方向相悖的，可能導(dǎo)致已優(yōu)化AGV與其他AGV在捷徑（如圖3中雙箭頭捷徑）發(fā)生沖突。在此，給出不發(fā)生沖突，即路徑在單AGV條件下可優(yōu)化同時在多AGV情況下也可優(yōu)化的充分條件：捷徑不含Ai除之外的其他AGV（路徑屬于Ⅰ型、Ⅱ型），或捷徑和與其相鄰的貨架不含除Ai之外的其他AGV（路徑屬于Ⅲ型、Ⅳ型）。

在集中式管理的AGV系統(tǒng)中，優(yōu)化條件的判定是通過中心控制系統(tǒng)進(jìn)行的。當(dāng)AGV經(jīng)過每一個交叉點時，判斷AGV所執(zhí)行的路徑是否是關(guān)于交叉點可優(yōu)化的且滿足多AGV可優(yōu)化充分條件，如果不滿足，則路徑不變，否則執(zhí)行優(yōu)化。

3 仿真

為測試所提方法的優(yōu)化效果，根據(jù)圖4所示地圖，在PC上使用Matlab進(jìn)行多AGV的計算機(jī)仿真試驗，PC的硬件信息為CPU Core I7-4790K@4.0 GHz，RAM 16 GB。仿真所用的貨架區(qū)域大小為25×25。

圖4 測試使用的貨架區(qū)示意Fig.4 Illustration of shelf area for testing

AGV在貨架區(qū)進(jìn)行的任務(wù)有3種：①從某個外圍交叉點出發(fā)取貨架；②從某個貨架出發(fā)至某個外圍交叉點以離開貨架區(qū)；③從一個貨架上卸載，準(zhǔn)備去另一個貨架位置取貨架。

在所述的每次仿真中，AGV的任務(wù)隨機(jī)產(chǎn)生，即AGV任務(wù)的起始位置和終止位置在不同任務(wù)下從外圍交叉點或貨架上隨機(jī)選取，并且不重復(fù)。為考慮不同的AGV數(shù)量對調(diào)度策略優(yōu)化結(jié)果的影響，仿真試驗?zāi)M了在2～10臺不同數(shù)量AGV下調(diào)度策略優(yōu)化的結(jié)果。每種不同AGV數(shù)量下試驗1000次。當(dāng)某AGV運行到的下一個柵格存在其他AGV時，此AGV暫停運動。當(dāng)多臺AGV同時進(jìn)入某一空交叉點時，根據(jù)AGV優(yōu)先級判定進(jìn)入交叉點的AGV?？紤]到AGV在轉(zhuǎn)彎時的時間損耗，設(shè)AGV旋轉(zhuǎn)90°消耗時間與AGV在2個柵格之間移動消耗時間相同，即在時間上，AGV左轉(zhuǎn)90°或右轉(zhuǎn)90°相當(dāng)于額外移動一步。不同數(shù)量的AGV在優(yōu)化前和優(yōu)化后的運行步數(shù)見表3。

表3 不同數(shù)量AGV在優(yōu)化前和優(yōu)化后的運行步數(shù)Tab.3 Running steps in different count of AGV before and after optimization

此外，還計算了單AGV可優(yōu)化“幾”字形路線在多AGV同時運行條件下的優(yōu)化比例，如圖5所示。

圖5 路徑得到優(yōu)化的比例曲線Fig.5 Optimized path percentage curve

分析表3可知，所提方法對AGV運行效率具有提高作用，且提高的效果隨AGV數(shù)量的增加而逐步減小。圖5顯示，同時運行的AGV數(shù)量越多，“幾”字形路徑得到優(yōu)化的比例越少。這是由于隨著AGV數(shù)量的增多，AGV占用待優(yōu)化“幾”字形路徑的捷徑路段和“幾”字形路徑的第4交叉點的比率會提高，致使優(yōu)化比例下降。

4 結(jié)語

研究了局部地圖下單個AGV分別在2種不同的運行方向模式下訪問貨架的運行步數(shù)，得出了局部環(huán)路對單個AGV訪問更優(yōu)的結(jié)論。針對局部環(huán)路存在的“幾”字形路徑會導(dǎo)致AGV運行效率低下的問題，提出了運行時在不存在與其他AGV碰撞的情況下動態(tài)更改當(dāng)前AGV路徑的運行策略。仿真試驗證明，優(yōu)化后的策略在多AGV倉儲系統(tǒng)中對AGV運行效率具有提高作用，且有提高作用隨AGV的增加而下降的規(guī)律。

[1] Wurman P R，D'Andrea R，Mountz M.Coordinating hundreds of cooperative，autonomous vehicles in warehouses[J].AI magazine，2008，29（1）：9.

[2] Qiu L，Hsu W J，Huang S Y，et al.Scheduling and routing algorithms for AGVs：a survey[J].International Journal of Production Research，2002，40（3）：745-760.

[3] Fazlollahtabar H，Saidi-Mehrabad M.Methodologies to optimize automated guided vehicle scheduling and routing problems：a review study[J].Journal of Intelligent&Robotic Systems，2015，77（3-4）：525.

[4] La Valle S M.Motion planning[J].IEEE Robotics&Automation Magazine，2011，18（2）：108-118.

[5] Andreasson H，Bouguerra A，Cirillo M，et al.Autonomous transportvehicles：where we are and whatismissing[J].IEEE Robotics&Automation Magazine，2015，22（1）：64-75.

[6] Zheng Y，Xiao Y，Seo Y.A tabu search algorithm for simultaneous machine/AGV scheduling problem[J].International Journal of Production Research，2014，52（19）：5748-5763.

[7]Wang C，Wang L，Qin J，et al.Path planning of automated guided vehicles based on improved A-Star algorithm[C]//IEEE International Conference on Information and Automation.IEEE，2015：2071-2076.

Multi-AGV Running Strategy Optimization for Intelligent Warehouse Systems

ZHAO Yu-ting，YE Feng，LAI Yi-zong，XIE Xian-zhi，HONG Zheng
（School of Mechanical and Automotive Engineering，South China University of Technology，Guangzhou 510640，China）

The operational efficiency of two common AGV running patterns in intelligent warehouse is studied.In order to improve the operational efficiency of AGV，AGV operation strategy optimization scheme based on road reuse is proposed for local cyclic operation mode.The path is optimized under conditions of non-collision and conflict-free with other AGV，which has a specific steering sequence with a potential shortcut for a single AGV.Applicable conditions and implementation method of the optimization are provided.Simulation results show that the optimization method is effective and feasible.

automate guided vehicle（AGV）；automate guided van；local cyclic；intelligent warehouse；running strategy；run direction mode

TP24；TH242

A

1001-9944（2017）11-0067-05

10.19557/j.cnki.1001-9944.2017.11.016

2017-04-24；

2017-08-02

廣東省教育部產(chǎn)學(xué)研結(jié)合重大項目（2012A090300013）；廣東省公益研究與能力建設(shè)專項（2016A010106005）

趙雨亭（1995—），男，碩士研究生，研究方向為移動機(jī)器人；葉峰（1972—），男，博士，副教授，研究方向為嵌入式系統(tǒng)設(shè)計與機(jī)器視覺。