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

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

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

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

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

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

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

自動(dòng)導(dǎo)向車；自動(dòng)引導(dǎo)搬運(yùn)車；局部環(huán)路；智能倉(cāng)儲(chǔ)；運(yùn)行策略；運(yùn)行方向模式

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

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

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

1 智能倉(cāng)儲(chǔ)工作方式

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

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

1.1 AGV運(yùn)行方向的兩種模式

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

圖1 兩種AGV運(yùn)行方向模式Fig.1 Two AGV running patterns

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

1.2 模式比較

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

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

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

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

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

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

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

圖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正在運(yùn)行的柵格序列為 Path（Ai），有式（1）成立：

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

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

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

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

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

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

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

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

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

條件 1v（i，xk）（k＝1，2，3，4）是交叉點(diǎn)。

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

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

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

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

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

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

其中，v1=a，vn=b，元組中任意兩柵格對(duì)象是不同的，且對(duì)于任意整數(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交叉點(diǎn)存在意味著“幾”字形的第2，第3，第4交叉點(diǎn)也是存在的，也意味著“幾”字形路徑存在。若Path（Ai）中存在“幾”字形第1交叉點(diǎn) v（i，x1），則稱路徑 Path（Ai）在單 AGV 條件下對(duì)于柵格v（i，x1）是可優(yōu)化的。優(yōu)化的方式是將Path（Ai）中的 v（i，x1），…，v（i，x4）序列替換為ShortCut（v（i，x1），v（i，x4））中所含的對(duì)象序列。 當(dāng)“幾”字形路徑屬于Ⅰ型和Ⅱ型時(shí)，對(duì)應(yīng)的捷徑滿足條件4；當(dāng)“幾”字形路徑屬于Ⅲ型和Ⅳ型時(shí)，對(duì)應(yīng)的捷徑滿足條件5。

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

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

3 仿真

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

研究了局部地圖下單個(gè)AGV分別在2種不同的運(yùn)行方向模式下訪問貨架的運(yùn)行步數(shù)，得出了局部環(huán)路對(duì)單個(gè)AGV訪問更優(yōu)的結(jié)論。針對(duì)局部環(huán)路存在的“幾”字形路徑會(huì)導(dǎo)致AGV運(yùn)行效率低下的問題，提出了運(yùn)行時(shí)在不存在與其他AGV碰撞的情況下動(dòng)態(tài)更改當(dāng)前AGV路徑的運(yùn)行策略。仿真試驗(yàn)證明，優(yōu)化后的策略在多AGV倉(cāng)儲(chǔ)系統(tǒng)中對(duì)AGV運(yùn)行效率具有提高作用，且有提高作用隨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é)合重大項(xiàng)目（2012A090300013）；廣東省公益研究與能力建設(shè)專項(xiàng)（2016A010106005）

趙雨亭（1995—），男，碩士研究生，研究方向?yàn)橐苿?dòng)機(jī)器人；葉峰（1972—），男，博士，副教授，研究方向?yàn)榍度胧较到y(tǒng)設(shè)計(jì)與機(jī)器視覺。