李蘇琪 朱孔金

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

關(guān)鍵詞：物流分揀? AGV? 路徑規(guī)劃? 分揀效率

中圖分類號：TP27? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標(biāo)識碼：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

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

雖然多AGV物流分揀系統(tǒng)已經(jīng)在實踐中得到了應(yīng)用，但該領(lǐng)域的詳細(xì)文獻和指導(dǎo)理論還不是很豐富。因此，該文旨在使用建模仿真的方法設(shè)計一個多AGV物流分揀系統(tǒng)，提高物流分揀效率，保證系統(tǒng)的正常高效運行。

1? 環(huán)境描述

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

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

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

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

2? 仿真模型構(gòu)建

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

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

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

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

3? 結(jié)果與討論

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

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

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

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

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

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

4? 結(jié)語

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

參考文獻

[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的物流分揀仿真系統(tǒng)設(shè)計[J].中小企業(yè)管理與科技，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調(diào)度的物流分揀系統(tǒng)[D].深圳大學(xué)，2017.

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

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

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

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

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

[11] 周忠太.多AGV物流分揀系統(tǒng)的設(shè)計與關(guān)鍵技術(shù)研究[D].華南理工大學(xué)，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.