李蘇琪 朱孔金

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

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

中圖分類(lèi)號(hào)：TP27? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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ā)展，人們的購(gòu)物方式已經(jīng)發(fā)生了很大的改變，隨之而來(lái)的是大量的物流包裹亟待運(yùn)輸。物流分揀中心是整個(gè)物流過(guò)程的運(yùn)輸瓶頸所在，其分揀效率對(duì)于物流行業(yè)的整體水平影響巨大。當(dāng)傳統(tǒng)的分揀設(shè)備無(wú)法滿足快速增長(zhǎng)的物流需求時(shí)，多AGV物流分揀系統(tǒng)成為物流產(chǎn)業(yè)需要研究的一個(gè)重要課題，且有著很大的應(yīng)用潛力和應(yīng)用前景。AGV小車(chē)是一種無(wú)人駕駛的、按照預(yù)先設(shè)定路線運(yùn)輸貨物的車(chē)輛，使用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)的重要途徑之一。越來(lái)越多的學(xué)者使用建模仿真的方式來(lái)對(duì)AGV系統(tǒng)進(jìn)行研究[1-3]。De Ryck等人[4]對(duì)AGV系統(tǒng)相關(guān)控制算法和技術(shù)進(jìn)行了綜述。陳勝軍[5]使用改進(jìn)的A*算法對(duì)基于AGV調(diào)度的物流分揀系統(tǒng)中AGV小車(chē)的路徑規(guī)劃問(wèn)題進(jìn)行了研究，通過(guò)仿真模擬實(shí)驗(yàn)驗(yàn)證提出方法的合理性。武星等人[6]研究了多載量AGV系統(tǒng)的交通管控問(wèn)題，提出了AGV避碰和系統(tǒng)死鎖預(yù)測(cè)與避免方法，通過(guò)仿真驗(yàn)證所提方法的有效性。陳香玲等人[7]提出了一種AGV充電需求和電量消耗優(yōu)化模型，仿真結(jié)果表明該模型能夠有效提高AGV分揀效率。近幾十年來(lái)，學(xué)者們使用建模方法從不同的角度對(duì)AGV系統(tǒng)進(jìn)行研究[8-10]。因此，該文采用建模仿真的方法研究多AGV分揀系統(tǒng)，基于離散網(wǎng)格對(duì)分揀平臺(tái)進(jìn)行描述，構(gòu)建多AGV分揀系統(tǒng)仿真模型。

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

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

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

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

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

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

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

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

3? 結(jié)果與討論

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

針對(duì)圖3中的仿真場(chǎng)景結(jié)構(gòu)，該文對(duì)分揀平臺(tái)所能容納的AGV數(shù)量進(jìn)行研究。圖4（a）展示了系統(tǒng)容量為200、250、300時(shí)，分揀平臺(tái)內(nèi)AGV數(shù)量隨時(shí)間的變化關(guān)系，其中路徑更新時(shí)間間隔f均取10。當(dāng)sc=200時(shí)，分揀平臺(tái)內(nèi)AGV數(shù)量在增加到穩(wěn)定值后幾乎保持不變，振幅很小。當(dāng)sc=250時(shí)，平臺(tái)內(nèi)AGV數(shù)量也接近系統(tǒng)容量，但與sc=200時(shí)相比，曲線的振幅相對(duì)更大。然而，這一現(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這種分揀平臺(tái)布局結(jié)構(gòu)中，系統(tǒng)容量應(yīng)設(shè)置小于260輛。即使AGV數(shù)量繼續(xù)增加，實(shí)際運(yùn)行在分揀平臺(tái)中的AGV數(shù)量也無(wú)法達(dá)到系統(tǒng)容量。與此同時(shí)，隨AGV數(shù)量的增多，交通控制的復(fù)雜性、碰撞和死鎖的概率也越來(lái)越高。

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

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

4? 結(jié)語(yǔ)

采用二維離散網(wǎng)格對(duì)物流分揀平臺(tái)的環(huán)境進(jìn)行建模，使用改進(jìn)標(biāo)號(hào)修正法結(jié)合路徑更新時(shí)間間隔為AGV動(dòng)態(tài)規(guī)劃路徑。將NS規(guī)則作為單AGV移動(dòng)規(guī)則并輔以交通控制策略來(lái)管理分揀系統(tǒng)的長(zhǎng)久運(yùn)轉(zhuǎn)。使用該模型對(duì)分揀系統(tǒng)進(jìn)行仿真，研究了系統(tǒng)容量和路徑更新時(shí)間間隔對(duì)系統(tǒng)分揀效率的影響。仿真結(jié)果表明，針對(duì)該文分揀場(chǎng)景，系統(tǒng)容納的AGV數(shù)量應(yīng)控制在260輛以下。且路徑更新時(shí)間間隔在系統(tǒng)容量小時(shí)，對(duì)分揀系統(tǒng)效率幾乎無(wú)影響;而當(dāng)系統(tǒng)容量大于200時(shí)，較小的路徑更新時(shí)間間隔對(duì)分揀系統(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] 張闖，張國(guó)濤，趙龍葛，等.基于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] 陳勝軍.基于多臺(tái)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小車(chē)的智能物流分揀系統(tǒng)[J].山東工業(yè)技術(shù)，2018（16）：115.

[9] 梁彧.基于改進(jìn)Dijkstra算法的AGV智能車(chē)路徑規(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.