多AGV物流分揀系統效率研究

李蘇琪 朱孔金

摘? 要：使用自動導引小車（Automatic Guided Vehicle，AGV）運輸包裹能夠提高物流分揀的效率，但當系統規模較大時，如何保證分揀系統仍然具有較高的分揀效率這一問題還沒有得到很好的解決。該文在離散網格環境下設計基于AGV的物流分揀系統，并構建了多AGV分揀系統仿真模型。模型中使用改進標號修正法結合路徑更新時間間隔對AGV進行動態路徑規劃，制定AGV移動規則并輔以死鎖檢測和恢復算法來解決系統死鎖問題。仿真結果表明，該模型能夠適用于大規模物流分揀。針對該文分揀場景，系統容納的AGV數量應控制在260輛以下。且當系統容量大于200時，較小的路徑更新時間間隔對分揀系統效率的作用明顯優于較大的路徑更新時間間隔。

關鍵詞：物流分揀? AGV? 路徑規劃? 分揀效率

中圖分類號：TP27? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A文章編號：1672-3791（2021）05（a）-0001-05

Abstract： Using AGV to transport parcels can improve the efficiency of logistics sorting， but when the system scale is large， how to ensure the sorting system still has a high sorting efficiency has not been solved. In this paper， the multi-AGV logistics sorting system is designed in the discrete grid environment， and the simulation model of multi-AGV sorting system is built. In the model， the dynamic path planning of AGV is carried out by using the improved label correcting method combined with the path update time interval. The AGV movement rule is formulated， and the deadlock detection and recovery algorithm is supplemented to solve the system deadlock problem. The simulation results show that the model can be applied to large-scale logistics sorting. In this paper， the number of AGV can be accommodated in the system is about 260. When the system capacity is more than 200， the smaller path update time interval has a better effect on the efficiency of sorting system than the larger path update time interval.

Key Words： Logistics sorting; AGV; Path planning; Sorting efficiency

隨著電商的蓬勃發展，人們的購物方式已經發生了很大的改變，隨之而來的是大量的物流包裹亟待運輸。物流分揀中心是整個物流過程的運輸瓶頸所在，其分揀效率對于物流行業的整體水平影響巨大。當傳統的分揀設備無法滿足快速增長的物流需求時，多AGV物流分揀系統成為物流產業需要研究的一個重要課題，且有著很大的應用潛力和應用前景。AGV小車是一種無人駕駛的、按照預先設定路線運輸貨物的車輛，使用AGV代替傳送帶和人工進行包裹的分揀和運輸，能夠在較小的面積內實現一系列分揀作業，可以提高物流分揀效率。

雖然多AGV物流分揀系統已經在實踐中得到了應用，但該領域的詳細文獻和指導理論還不是很豐富。因此，該文旨在使用建模仿真的方法設計一個多AGV物流分揀系統，提高物流分揀效率，保證系統的正常高效運行。

1? 環境描述

由于AGV分揀系統效率和成本效益的性質，建模已被確定為改善設計、操作和維護AGV系統的重要途徑之一。越來越多的學者使用建模仿真的方式來對AGV系統進行研究[1-3]。De Ryck等人[4]對AGV系統相關控制算法和技術進行了綜述。陳勝軍[5]使用改進的A*算法對基于AGV調度的物流分揀系統中AGV小車的路徑規劃問題進行了研究，通過仿真模擬實驗驗證提出方法的合理性。武星等人[6]研究了多載量AGV系統的交通管控問題，提出了AGV避碰和系統死鎖預測與避免方法，通過仿真驗證所提方法的有效性。陳香玲等人[7]提出了一種AGV充電需求和電量消耗優化模型，仿真結果表明該模型能夠有效提高AGV分揀效率。近幾十年來，學者們使用建模方法從不同的角度對AGV系統進行研究[8-10]。因此，該文采用建模仿真的方法研究多AGV分揀系統，基于離散網格對分揀平臺進行描述，構建多AGV分揀系統仿真模型。

該文研究的是一個具有雙層結構的分揀平臺，上層用于包裹分揀，下層用于包裹收集，并采用中心控制器集中控制[11]的方法來控制整個分揀系統的運行。整個上層分揀平臺由m×n個大小相同的元胞組成，如圖1所示。平臺左右兩側的黑色矩形代表柵欄等障礙物，平臺外圍的箭頭表示AGV在該行或該列的運動方向。依據元胞的功能，該文把分揀平臺的元胞劃分為5種類型：入口元胞、出口元胞、儲貨元胞、卸貨元胞和普通元胞。入口元胞是系統的入口，空AGV在該類元胞上裝載包裹;出口元胞是系統的出口，空AGV通過該類元胞離開分揀系統;儲貨元胞是儲存包裹的地方，是AGV的分揀目的地，其下方連接有攬貨箱，分揀包裹從該類元胞掉落到相應的攬貨箱內，同一攬貨箱內的包裹具有相同的目的地;卸貨元胞與儲貨元胞相鄰，裝載包裹的AGV在這類元胞上將包裹卸載入儲貨元胞中;不具備以上4種功能的元胞稱之為普通元胞，AGV可在該類元胞上進行移動、停止、轉彎等操作。一個AGV一次只能攜帶一個包裹，且同一時刻一個元胞只能容納一個AGV。

單AGV運行流程如圖1所示，其中標號為1的AGV表示處于載貨狀態的AGV，標號為2的AGV表示處于空載狀態的AGV。空AGV在入口元胞處裝載包裹并獲取其包裹目的地，AGV將此信息上傳至中心控制器，中心控制器接收信息并為該AGV規劃從入口元胞到儲貨元胞的可行路徑，AGV根據路徑信息進行移動，直至到達目的卸貨元胞執行卸貨任務。AGV完成卸貨任務后將此信息反饋給中心控制器，中心控制器為該AGV再次規劃一條從當前元胞到出口元胞的路徑，AGV沿此路徑離開分揀平臺。AGV在移動過程中將自身位置、速度等信息不斷反饋給中心控制器，中心控制器根據反饋信息對分揀平臺進行交通控制。

對于AGV的運行，該文做出如下假設：（1）不考慮AGV離開系統后重新進入系統的調度問題，且系統外有足夠多的空AGV可以進行調度;（2）系統承擔的是輕型包裹的分揀，忽略AGV的加減速時間;（3）AGV必須靜止通過旋轉調整運動方向;（4）AGV只能將包裹沿著行進方向的右側投入儲貨元胞，且AGV在卸貨元胞需要花費1個單位時間將包裹投遞到儲貨元胞。

2? 仿真模型構建

改進標號修正算法[12]是解決最短路徑問題的一種常用算法。使用改進標號修正法進行路徑規劃前，需要基于分揀平臺構建AGV運行網絡。以分揀平臺中的元胞作為網絡中的節點，添加虛擬節點0+作為空載AGV的虛擬目的地節點，將節點按照分揀平臺中元胞與元胞之間的可行方向進行連接得到弧。出口元胞到虛擬元胞0+連接得到的弧權重為0，卸貨元胞與儲貨元胞相連得到的弧權重也為0，因這兩種弧對路徑更新無影響。AGV路徑規劃的目標是最小化運送包裹的時間，因此，其余弧以AGV在弧上通行花費的時間作為網絡中弧的權重，即AGV通過元胞所花費的時間。為了達到動態更新最優路徑的目的，該文在計算AGV通過元胞花費時間時引入時間變量，稱為路徑更新時間間隔f。每隔f個時間步，中心控制器可根據t-f時刻到t時刻時間段內分揀平臺內AGV運行狀況，重新計算AGV通過每個元胞花費的時間，更新AGV運行網絡中弧的權重，從而為AGV重新規劃從當前元胞到目的元胞的時間最短路徑，使AGV按照新路徑繼續行駛。

分揀系統類似于一個簡化的城市交通網絡，在平臺中AGV按照中心控制器規劃的路徑移動。AGV沿著既定路徑在分揀平臺內的移動可以看作AGV從一個元胞向另一個元胞移動的過程。因此，該文采用元胞自動機模型中的Nagel-Schreckenberg（NS）規則作為AGV移動規則。AGV是一種完全可控的小車，因此忽略了NS規則中的隨機慢化條件，僅使用其余條件來指導AGV的運行。

AGV在運動的過程中，會不可避免地發生沖突和死鎖問題，需要額外的交通控制策略來加以管控。根據環境設置，平臺中可能出現的碰撞可以分為兩種類型：追擊碰撞和交叉碰撞，具體見圖2，圖中用實心圓表示AGV。當兩輛AGV在同一行（列）行駛，且后面AGV的速度大于兩AGV之間的距離時，追擊碰撞就會發生，具體見圖2（a）。因該文采用NS規則作為控制單AGV的移動規則，因此可避免追擊碰撞，也可通過安裝在AGV上的傳感器來避免這種類型的碰撞。若同一時刻兩輛AGV在交叉路口同時爭奪未被其他AGV占用的同一元胞時，交叉碰撞即會發生，具體見圖2（b）。該文采用的是集中控制的方式來控制系統的運轉，上位機系統可根據各個AGV的優先級順序來對交叉碰撞進行管理控制。規定速度高的AGV比速度低的AGV擁有優先通過權。若兩輛AGV的速度相同，則隨機選擇一輛AGV優先通行。

在物流分揀系統中，有大量的AGV同時移動。AGV在移動過程中可能出現首尾相連的情況，形成一個死鎖環路，導致局部癱瘓，具體見圖2（c），這種情況不利于AGV的正常運行。死鎖檢測與恢復策略允許死鎖的產生，且對AGV進入系統并無限制，是解決死鎖問題常用的方法。該文采用死鎖檢測與恢復方法來處理分揀系統中的死鎖問題，通過一種有效的識別死鎖算法發現死鎖，并實時選擇死鎖中的某輛AGV，改變其路徑來解決死鎖問題。

3? 結果與討論

該文建立了一個大規模的仿真環境來評價提出的模型。圖3展示了一個由55×40個元胞組成的分揀平臺，平臺中共設置了12個入口元胞作為分揀入口，204個儲貨元胞作為分揀出口。仿真實驗研究在固定的10 000個時間步內AGV在平臺內的運行情況。每次實驗重復100次，結果取平均值。

為了研究系統內AGV數量與系統仿真算法性能的關系，該文提出了系統容量（SC）的概念，系統容量是指分揀平臺內部最大可容納的AGV數量。在仿真系統中，若分揀平臺內部的AGV數量小于SC，則新AGV可通過入口元胞進入分揀平臺。一旦分揀平臺內部的AGV數量等于SC，則新的AGV不允許進入分揀平臺。

針對圖3中的仿真場景結構，該文對分揀平臺所能容納的AGV數量進行研究。圖4（a）展示了系統容量為200、250、300時，分揀平臺內AGV數量隨時間的變化關系，其中路徑更新時間間隔f均取10。當sc=200時，分揀平臺內AGV數量在增加到穩定值后幾乎保持不變，振幅很小。當sc=250時，平臺內AGV數量也接近系統容量，但與sc=200時相比，曲線的振幅相對更大。然而，這一現象在sc=300時并不成立，在此系統容量下，AGV數量隨時間的變化曲線明顯是動蕩的，振幅較大，AGV平均數量取值為256輛，遠小于系統設置的容量300輛，即系統內實際運行的AGV數量明顯小于系統容量。

因此，在圖3這種分揀平臺布局結構中，系統容量應設置小于260輛。即使AGV數量繼續增加，實際運行在分揀平臺中的AGV數量也無法達到系統容量。與此同時，隨AGV數量的增多，交通控制的復雜性、碰撞和死鎖的概率也越來越高。

規定時間內AGV包裹分揀的數量是衡量分揀系統效率的一個重要指標。圖4（b）展示了SC和f的變化對仿真系統總投遞包裹數量的影響。從圖中可以看出，隨SC的增加，仿真系統總投遞包裹數量總體上呈上升趨勢。當sc>200后，無論f取何值，總投遞包裹數曲線斜率明顯下降。sc=250和sc=300時，總投遞包裹數量差距非常小。甚至sc=300，f=90時，其總投遞包裹數量相較于sc=250，f=90時不增反降。且當sc>200，后，f對分揀系統效率的影響開始凸顯，擁有較小f值的系統其總投遞包裹數量總體上大于較大的f值。

造成這一現象的原因是，在sc<200時，系統容量約束是限制AGV進入分揀平臺的主要因素，這種情況下分揀平臺內部AGV占比少，f對仿真系統的影響可以忽略。當sc>200后，限制AGV進入分揀平臺的主要因素由系統容量約束轉變為分揀平臺中入口分布、路線設置等其他原因。此時，即使不斷提高系統容量的上限值，AGV也由于其他因素的影響導致無法進入到分揀平臺。當sc>250后，這種情況下分揀平臺內部基本已經達到了飽和的狀態。此時，f對仿真系統的調節作用也由此凸顯出來，較小的f值其對分揀系統效率的作用明顯優于較大的f值。較小的f值可以更真實地反映路徑信息的變化，使AGV盡可能走時間最短的路線。但是，f的調節作用是有限的，繼續增加系統容量，使更多的AGV進入分揀平臺不僅不能提高分揀系統的效率，反而會適得其反。這不僅浪費資源，提高成本，而且使得分揀平臺中的交通控制更加復雜。f值小也意味著算法計算效率低，在實際應用時，建議根據分揀系統內部運行AGV數量和實際需求選取合理的f值。

4? 結語

采用二維離散網格對物流分揀平臺的環境進行建模，使用改進標號修正法結合路徑更新時間間隔為AGV動態規劃路徑。將NS規則作為單AGV移動規則并輔以交通控制策略來管理分揀系統的長久運轉。使用該模型對分揀系統進行仿真，研究了系統容量和路徑更新時間間隔對系統分揀效率的影響。仿真結果表明，針對該文分揀場景，系統容納的AGV數量應控制在260輛以下。且路徑更新時間間隔在系統容量小時，對分揀系統效率幾乎無影響;而當系統容量大于200時，較小的路徑更新時間間隔對分揀系統效率的作用明顯優于較大的路徑更新時間間隔。

參考文獻

[1] zou w，pan q，meng t，et al.An Effective Discrete Artificial Bee Colony Algorithm for Multi-AGVs Dispatching Problem in a Matrix Manufacturing Workshop[J].Expert Systems with Applications，2020（161）：113675.

[2] 張闖，張國濤，趙龍葛，等.基于VR的物流分揀仿真系統設計[J].中小企業管理與科技，2020（9）：192-193.

[3] qi m，li x，yan x，et al.On the Evaluation of AGVS-based Warehouse Operation Performance[J].Simulation Modelling Practice and Theory，2018（87）：379-394.

[4] De Ryck，Versteyhe M，Debrouwere F.Automated Guided Vehicle Systems，State-of-the-art Control Algorithms and Techniques[J].Journal of Manufacturing Systems，2020，54（1）：152-173.

[5] 陳勝軍.基于多臺AGV調度的物流分揀系統[D].深圳大學，2017.

[6] 武星，翟晶晶，肖海寧，等.多載量AGV系統防死鎖路口通行順序優化及避碰[J/OL].[2021-05-12].http：//kns.cnki.net/kcms/detail/11.5946.TP.20201130.1726.002.html.

[7] 陳香玲，郭鵬，溫昆，等.考慮充電需求和時間窗的多AGV調度優化建模[J].河北科技大學學報，2021，42（2）：91-100.

[8] 韓瀟，張煒昊，劉暢，等.一種基于AGV小車的智能物流分揀系統[J].山東工業技術，2018（16）：115.

[9] 梁彧.基于改進Dijkstra算法的AGV智能車路徑規劃[J].科技與創新，2020，168（24）：165-167.

[10] 龍永紅，向昭宇.基于顏色Petri net的多AGV防死鎖系統綜述[J].電子世界，2019（2）：64-66.

[11] 周忠太.多AGV物流分揀系統的設計與關鍵技術研究[D].華南理工大學，2018.

[12] Guerriero F， Musmanno R. Label correcting methods to solve multicriteria shortest path problems[J].Journal of Optimization Theory & Applications，2001，111（3）：589-613.