李蘇琪 朱孔金

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

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

中圖分類號：TP27? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(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ùn)輸。物流分揀中心是整個(gè)物流過程的運(yùn)輸瓶頸所在，其分揀效率對于物流行業(yè)的整體水平影響巨大。當(dāng)傳統(tǒng)的分揀設(shè)備無法滿足快速增長的物流需求時(shí)，多AGV物流分揀系統(tǒng)成為物流產(chǎn)業(yè)需要研究的一個(gè)重要課題，且有著很大的應(yīng)用潛力和應(yīng)用前景。AGV小車是一種無人駕駛的、按照預(yù)先設(shè)定路線運(yùn)輸貨物的車輛，使用AGV代替?zhèn)魉蛶Ш腿斯みM(jìn)行包裹的分揀和運(yùn)輸，能夠在較小的面積內(nèi)實(shí)現(xiàn)一系列分揀作業(yè)，可以提高物流分揀效率。

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

1? 環(huán)境描述

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

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

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

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

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

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

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

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

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

3? 結(jié)果與討論

該文建立了一個(gè)大規(guī)模的仿真環(huán)境來評價(jià)提出的模型。圖3展示了一個(gè)由55×40個(gè)元胞組成的分揀平臺，平臺中共設(shè)置了12個(gè)入口元胞作為分揀入口，204個(gè)儲貨元胞作為分揀出口。仿真實(shí)驗(yàn)研究在固定的10 000個(gè)時(shí)間步內(nèi)AGV在平臺內(nèi)的運(yùn)行情況。每次實(shí)驗(yàn)重復(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可通過入口元胞進(jìn)入分揀平臺。一旦分揀平臺內(nèi)部的AGV數(shù)量等于SC，則新的AGV不允許進(jìn)入分揀平臺。

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

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

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

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

4? 結(jié)語

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

參考文獻(xiàn)

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

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

[9] 梁彧.基于改進(jìn)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è)計(jì)與關(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.