基于自動(dòng)導(dǎo)引車輛的物流分揀系統(tǒng)交通控制策略

李蘇琪，朱孔金

(合肥工業(yè)大學(xué) 汽車與交通工程學(xué)院，安徽 合肥 230009)

電子商務(wù)的蓬勃發(fā)展帶動(dòng)了現(xiàn)代物流業(yè)的快速進(jìn)步，通常物流中心需要對快遞包裹按照目的地進(jìn)行分揀作業(yè)，分揀效率是整個(gè)物流系統(tǒng)效率的關(guān)鍵，而傳統(tǒng)的手工分揀已經(jīng)遠(yuǎn)遠(yuǎn)不能滿足日益增長的任務(wù)需求。近年來，基于自動(dòng)導(dǎo)引車輛(automatic guided vehicle， AGV)的自動(dòng)分揀受到越來越多的關(guān)注，這主要得益于AGV系統(tǒng)具有工作效率高、安全性強(qiáng)、人力投入少、出錯(cuò)率低等優(yōu)勢[1-2]。京東物流、阿里巴巴、順豐快遞等企業(yè)均在大力發(fā)展基于AGV的自動(dòng)分揀系統(tǒng)。

通常，基于AGV的分揀系統(tǒng)可以建立在離散網(wǎng)格環(huán)境下，網(wǎng)格大小與AGV大小和分揀包裹大小相適應(yīng)，AGV在系統(tǒng)內(nèi)的運(yùn)行可以看作是沿著規(guī)劃路線從一個(gè)網(wǎng)格向另一個(gè)網(wǎng)格的連續(xù)移動(dòng)過程。AGV的運(yùn)動(dòng)和作業(yè)，可以是基于中央控制器的集中控制，也可以是基于無線通信的分散控制[3]。對大規(guī)模的基于AGV的自動(dòng)分揀系統(tǒng)而言，系統(tǒng)內(nèi)AGV的行駛路徑規(guī)劃和交通控制是其核心問題。

路徑規(guī)劃是指在周圍環(huán)境存在障礙物的情況下，為AGV規(guī)劃一條安全的從起點(diǎn)到終點(diǎn)的最優(yōu)路徑[4]。Qiu等[5]對AGV系統(tǒng)的路徑規(guī)劃問題進(jìn)行了詳細(xì)的討論。根據(jù)路徑規(guī)劃算法的特點(diǎn)，可以大致分為靜態(tài)路徑規(guī)劃和動(dòng)態(tài)路徑規(guī)劃。靜態(tài)路徑規(guī)劃是在AGV運(yùn)動(dòng)之前規(guī)劃其行駛路徑，并在移動(dòng)過程中不隨系統(tǒng)交通狀況的變化而改變；而動(dòng)態(tài)路徑規(guī)劃是指AGV的路徑會(huì)隨著系統(tǒng)內(nèi)交通狀態(tài)的變化而更新[6]。動(dòng)態(tài)路徑規(guī)劃中涉及到對動(dòng)態(tài)信息的采集與處理，增加了問題的復(fù)雜性，但可為AGV規(guī)劃出符合真實(shí)交通狀況的最優(yōu)路徑。

交通控制主要解決系統(tǒng)內(nèi)AGV運(yùn)動(dòng)過程中因運(yùn)動(dòng)路線沖突引發(fā)的碰撞以及多輛AGV相互干擾而導(dǎo)致的死鎖。多AGV運(yùn)動(dòng)沖突是指當(dāng)多輛AGV同時(shí)對同一資源進(jìn)行競爭時(shí)，就可能造成潛在的碰撞問題。已有研究中主要采用路徑網(wǎng)絡(luò)設(shè)計(jì)法、區(qū)域控制法或路徑規(guī)劃法來避免碰撞[7]，相對于前兩種方法，路徑規(guī)劃方法的系統(tǒng)柔性好，得到了廣泛的應(yīng)用。現(xiàn)有文獻(xiàn)中處理死鎖問題主要有三種方法：死鎖避免、死鎖預(yù)防以及死鎖檢測與恢復(fù)[8]。其中，死鎖避免、死鎖預(yù)防兩種方法不允許出現(xiàn)死鎖，通常運(yùn)行效率較低。而死鎖檢測與恢復(fù)方法[9]允許死鎖的產(chǎn)生，一旦出現(xiàn)死鎖，系統(tǒng)可以自動(dòng)檢測出來，并通過重新分配資源將系統(tǒng)恢復(fù)到無死鎖狀態(tài)。死鎖檢測與恢復(fù)方法在掌握系統(tǒng)全局信息的前提下，簡單方便，很容易在集中控制策略下實(shí)現(xiàn)。

隨著分揀系統(tǒng)規(guī)模的增大，由于缺乏適當(dāng)?shù)慕煌刂坪吐窂揭?guī)劃方法，還不能很好地解決系統(tǒng)中AGV運(yùn)動(dòng)過程中的沖突和死鎖等交通問題，尤其是有上百輛AGV同時(shí)存在時(shí)，無法保證系統(tǒng)的分揀效率和系統(tǒng)穩(wěn)定性[10]。因此，本文針對大規(guī)模的基于AGV的自動(dòng)分揀系統(tǒng)，在離散網(wǎng)格環(huán)境下，借鑒道路交通網(wǎng)中的交叉口不停留規(guī)則，采用基于Label Correcting算法的動(dòng)態(tài)路徑規(guī)劃方法，提出了融合交叉口不停留策略和死鎖檢測與恢復(fù)方法的交通控制策略，旨在從系統(tǒng)運(yùn)行效率和系統(tǒng)性能兩方面設(shè)計(jì)基于AGV的自動(dòng)分揀系統(tǒng)。

1 系統(tǒng)描述

如圖1所示，分揀平臺建立在網(wǎng)格環(huán)境下，并采用基于中央控制器的集中控制策略。AGV在入口處加載包裹并將獲取到的包裹目的地信息上傳至中央控制器，中央控制器根據(jù)接收到的信息和系統(tǒng)當(dāng)前的狀態(tài)為其規(guī)劃移動(dòng)路徑，并對其發(fā)送操作指令，操作指令包括移動(dòng)、轉(zhuǎn)彎、靜止、卸載等。AGV根據(jù)接收到的指令在可行的元胞之間移動(dòng)，直至到達(dá)包裹目的地，并完成卸載包裹。系統(tǒng)中每個(gè)元胞最多可容納一輛AGV，網(wǎng)格的大小與AGV的大小相適應(yīng)。根據(jù)元胞功能的不同，系統(tǒng)中元胞可分為7種類型，其中揀貨元胞、卸貨元胞和出口元胞的類型并不唯一，其同時(shí)也屬于決策元胞。

注：箭頭表示處于該行(列)的元胞所允許的移動(dòng)方向；紅色AGV表示處于載貨狀態(tài)；藍(lán)色AGV表示處于空載狀態(tài)； 紅色虛線為載貨AGV可行的移動(dòng)路徑；藍(lán)色虛線為卸載后空AGV離開系統(tǒng)的路徑。圖1 分揀平臺示意圖Fig.1 Schematic of the sorting platform

圖1中，揀貨元胞(CP)為系統(tǒng)的入口，空AGV在該類元胞上加載待分揀包裹，如圖1中的元胞(4,13)和(5,13)。卸貨元胞(CU)是載貨AGV停車卸載包裹的地方，如圖1中的元胞(3,3)和(3,5)。儲貨元胞(CD)是包裹的目的地出口，其下方連接有攬貨箱，分揀的包裹從該類元胞掉落到相應(yīng)的攬貨箱內(nèi)，同一攬貨箱內(nèi)的包裹具有相同的目的地，AGV不允許進(jìn)入該類元胞，該類元胞相當(dāng)于障礙物，如圖1中的元胞(3,4)、(3,7)、(6,4)和(6,7)。空AGV通過出口元胞(CE)離開系統(tǒng),如圖1中的元胞(1,13)、(2,13)、(4,1)和(5,1)。AGV在交叉口元胞(CJ)上可以通過旋轉(zhuǎn)改變運(yùn)動(dòng)方向,如圖1中的元胞(1,2)、(1,3)和(1,5)。通常一個(gè)完整的交叉口由4個(gè)交叉口元胞組成，圖1中藍(lán)色實(shí)線框所圍成的區(qū)域即為一個(gè)交叉口。無用元胞(CL)為系統(tǒng)中當(dāng)前未被利用的空間，如圖1中的元胞(3,1)、(3,13)、(6,1)和(6,13)，該類元胞可預(yù)留用于AGV充電、維修等。決策元胞(CR)是AGV調(diào)整行駛狀態(tài)的地方，AGV只能在該類元胞上對行駛路徑進(jìn)行動(dòng)態(tài)調(diào)整，如圖1中的元胞(1,1)、(1,13)、(3,3)、(3,12)和(4,13)。

2 數(shù)學(xué)模型

為仿真分析大規(guī)模的物流分揀系統(tǒng)，本文基于有向網(wǎng)絡(luò)構(gòu)建AGV運(yùn)行網(wǎng)絡(luò)，中央控制器再基于運(yùn)行網(wǎng)絡(luò)對所有AGV行駛路徑進(jìn)行規(guī)劃，并在規(guī)定的時(shí)間間隔內(nèi)根據(jù)系統(tǒng)狀態(tài)進(jìn)行更新。為協(xié)調(diào)眾多AGV同時(shí)移動(dòng)時(shí)的交通問題，本文采用交叉口不停留規(guī)則對分揀系統(tǒng)內(nèi)的AGV進(jìn)行交通控制。交叉口不停留規(guī)則要求AGV只能在決策元胞進(jìn)行決策判斷，即停留還是繼續(xù)行駛，一旦進(jìn)入交叉口，則AGV除轉(zhuǎn)彎外不允許停留。

2.1 符號和定義

表1列出了本文所用到的符號及其定義。

表1 符號及其定義Table 1 Symbols and their definitions

2.2 運(yùn)行網(wǎng)絡(luò)

本文不考慮AGV離開系統(tǒng)后的調(diào)度問題，因此需在系統(tǒng)中增加一個(gè)虛擬目的地元胞0+作為空載AGV離開系統(tǒng)時(shí)的目的地。為了描述AGV的行駛路徑，分揀平臺環(huán)境可由有向網(wǎng)絡(luò)G=(N,A)表示。其中，N=CR∪CD∪{0+}為網(wǎng)絡(luò)G的節(jié)點(diǎn)構(gòu)成的集合，A為網(wǎng)絡(luò)G的弧構(gòu)成的集合。網(wǎng)絡(luò)G中的弧分為三類：(1)運(yùn)行弧。對于任意交叉口，供AGV駛?cè)朐摻徊婵诘臎Q策元胞與供AGV駛出該交叉口的決策元胞之間相連構(gòu)成的弧。(2)卸貨弧。卸貨元胞與自己對應(yīng)的儲貨元胞之間相連構(gòu)成的弧。(3)駛出弧。任意出口元胞與虛擬元胞0+相連構(gòu)成的弧。

每條運(yùn)行弧均是由其路徑上的交叉口元胞和決策元胞構(gòu)成。根據(jù)分揀系統(tǒng)中各元胞的可行方向，可以確定網(wǎng)絡(luò)G中所有可能出現(xiàn)的運(yùn)行弧和卸貨弧的軌跡，圖2(a)～(e)列舉了AGV在圖1中紅色實(shí)線所圍成的區(qū)域內(nèi)所有可能的運(yùn)行弧和卸貨弧的運(yùn)行軌跡。AGV在上行路線上的運(yùn)行弧和卸貨弧的運(yùn)行軌跡如圖2(f)～(j)所示。圖2(e)和(j)為AGV在卸貨弧上的運(yùn)行軌跡，其余圖為AGV在運(yùn)行弧上的運(yùn)行軌跡。

目前實(shí)用的子帶合成方案有3種：合成距離包絡(luò)法[14]、時(shí)域合成法和頻域合成法[15]。3種方法各有優(yōu)缺點(diǎn)，合成距離包絡(luò)法效率最高，但是存在能量溢出，導(dǎo)致距離向形成虛假峰，而且該方法對速度誤差敏感。時(shí)域合成包含了時(shí)移、誤差補(bǔ)償和頻譜疊加，效率最低。頻域合成在完成子帶內(nèi)和子帶間誤差補(bǔ)償以后，只需進(jìn)行頻譜的拼接，具有運(yùn)算量小、實(shí)現(xiàn)簡單、性能好等優(yōu)點(diǎn)[16]。通過以上比較，本文采用的是頻域合成法。頻域合成其實(shí)就是頻譜的合成，根據(jù)頻率步進(jìn)關(guān)系，將各子帶信號進(jìn)行頻移，然后進(jìn)行疊加即可。頻域子帶合成示意圖如圖1所示。

圖2 AGV在運(yùn)行弧和卸貨弧上的運(yùn)行軌跡Fig.2 Trajectories of AGV on running and unloading arcs

中央控制器根據(jù)AGV運(yùn)行網(wǎng)絡(luò)對AGV進(jìn)行路徑規(guī)劃，得到的路徑信息為弧的有序集合，中央控制器將弧的集合轉(zhuǎn)換為元胞的有序集合，AGV根據(jù)元胞的有序排列在柵格地圖上移動(dòng)。

網(wǎng)絡(luò)G中卸貨弧的權(quán)重和駛出弧的權(quán)重均設(shè)置為0。由于采用交叉口不停留規(guī)則，AGV相當(dāng)于以自由流速度通過交叉口，但AGV可能會(huì)在決策元胞上花費(fèi)額外的等待時(shí)間，基于以上考慮，我們采用公式(1)來確定網(wǎng)絡(luò)G中運(yùn)行弧a在時(shí)段t的權(quán)重：

(1)

2.3 交通控制

圖3 移動(dòng)指令判斷流程圖Fig.3 Flow chart of movement instruction assessment

移動(dòng)指令的確定是依據(jù)仿真系統(tǒng)當(dāng)前狀態(tài)判斷的，容易出現(xiàn)判斷不充分的情況，因此本文引入最大循環(huán)判斷次數(shù)kmax來進(jìn)行重復(fù)循環(huán)判斷，最大化調(diào)動(dòng)系統(tǒng)內(nèi)可移動(dòng)的AGV。

AGV移動(dòng)過程中若出現(xiàn)AGV首尾相連，則形成死鎖循環(huán)，如圖1中紅色實(shí)線所示,處于死鎖循環(huán)中的AGV相互阻止其他AGV的移動(dòng)。在交叉口不停留交通控制策略下，AGV死鎖只會(huì)阻塞處于決策元胞上的AGV。因此，使用死鎖檢測與恢復(fù)算法[12]檢測系統(tǒng)中是否出現(xiàn)死鎖時(shí)，只需檢測決策元胞上的AGV狀態(tài)。選擇死鎖循環(huán)中決策元胞上的某輛AGV，改變其運(yùn)動(dòng)方向并重新規(guī)劃行駛路徑。若此時(shí)仍未解開死鎖，則重新選擇死鎖循環(huán)中的其他AGV，直至解開死鎖。

3 結(jié)果與討論

本文仿真實(shí)驗(yàn)所采用的分揀平臺如圖4所示，平臺劃分為40×55個(gè)元胞。平臺中均勻設(shè)置有12個(gè)揀貨元胞，204個(gè)儲貨元胞。假設(shè)待分揀包裹數(shù)量無限大，且其目的地服務(wù)均勻分布。仿真實(shí)驗(yàn)中還做如下假設(shè)：

圖4 仿真分揀平臺示意圖Fig.4 Schematic of the simulation sorting platform

(1) 每輛AGV一次只能攜帶一個(gè)包裹；

(2) AGV的轉(zhuǎn)彎操作需消耗一定的時(shí)間，本文中假設(shè)為1個(gè)單位時(shí)間步；

(3) 每個(gè)儲貨元胞兩側(cè)各有一個(gè)卸貨元胞，AGV只能將包裹沿著行進(jìn)方向的右側(cè)投入儲貨元胞，且AGV在卸貨元胞需要消耗一定的時(shí)間進(jìn)行卸載操作。

3.1 路徑更新時(shí)間間隔對分揀系統(tǒng)性能影響

AGV從一個(gè)元胞運(yùn)行到相鄰元胞所花費(fèi)的時(shí)間稱為一個(gè)時(shí)間步,仿真實(shí)驗(yàn)進(jìn)行10 000個(gè)時(shí)間步，每種工況重復(fù)30次，結(jié)果取其平均值，kmax取值為6。圖5展示了路徑更新間隔時(shí)間f對分揀系統(tǒng)性能的影響。

在圖5(a)中，系統(tǒng)總投遞包裹數(shù)量隨著f的增大先快速下降而后緩慢下降，同時(shí)，相同工況下重復(fù)仿真結(jié)果的離散程度隨著f的增大也在增大。中心控制器根據(jù)運(yùn)行網(wǎng)絡(luò)當(dāng)前狀態(tài)對系統(tǒng)內(nèi)AGV進(jìn)行行駛路徑更新，f越小，運(yùn)行網(wǎng)絡(luò)的權(quán)重計(jì)算越接近真實(shí)的路段情況，相應(yīng)地，所得到的行駛路徑也更為有效。相反，f越大，中心控制器更新計(jì)算出的路徑，可能因?yàn)闄?quán)重計(jì)算的偏差不是系統(tǒng)內(nèi)的最優(yōu)路徑，這也是圖5(b)中系統(tǒng)死鎖發(fā)生次數(shù)隨f增大而逐漸增多的原因。此外，隨著f的增大，AGV的平均運(yùn)行速度總體上呈下降趨勢。

圖5(c)為隨著f增大AGV平均旅行時(shí)間的變化情況，可以看出，空載AGV的平均旅行時(shí)間基本不受f值的影響，載貨AGV的平均旅行時(shí)間明顯隨著f值的增大而增加。對于載貨AGV，分揀系統(tǒng)內(nèi)的儲貨元胞多，揀貨元胞少，載貨AGV在分揀平臺內(nèi)的旅行時(shí)間與揀貨元胞到目的儲貨元胞的距離、路徑狀態(tài)相關(guān)，因此受f值影響大。而空載AGV只有一個(gè)虛擬的目的元胞，出口元胞多，AGV從卸貨點(diǎn)到出口元胞的距離近，因此基本不受f值影響。圖5(d)展示了仿真程序運(yùn)行時(shí)間與f的關(guān)系。隨著f的增加，運(yùn)行時(shí)間先大幅降低，然后趨于穩(wěn)定。

圖5 路徑更新間隔對系統(tǒng)性能的影響Fig.5 Impact of the update interval of the path on the performance of the system

3.2 路徑更新間隔對分揀系統(tǒng)容量的影響

為深入分析路徑更新時(shí)間間隔f對分揀系統(tǒng)容納AGV能力的影響，我們對比分析了兩種更新時(shí)間間隔下分揀系統(tǒng)內(nèi)不同狀態(tài)的AGV數(shù)量隨時(shí)間步的演化情況，如圖6所示。圖6(a)展示的是分揀系統(tǒng)內(nèi)容納的AGV總數(shù)量隨時(shí)間步的變化情況，可以看出，系統(tǒng)很快達(dá)到穩(wěn)定狀態(tài)，相比較而言，f=300時(shí)系統(tǒng)內(nèi)容納的AGV數(shù)量波動(dòng)更為明顯，這主要是因?yàn)樗梨i出現(xiàn)次數(shù)增加。在圖6(b)中，載貨AGV和空載AGV的數(shù)量在f=20時(shí)始終高于f=300時(shí)，f=300時(shí)系統(tǒng)內(nèi)載貨AGV數(shù)量的波動(dòng)最為明顯。圖6(c)展示的是移動(dòng)AGV和停止AGV數(shù)量隨時(shí)間步的變化情況，可以發(fā)現(xiàn)，不同更新時(shí)間間隔下系統(tǒng)內(nèi)停止AGV的數(shù)量基本維持在相同的水平，但移動(dòng)AGV的數(shù)量在f=20時(shí)始終高于f=300時(shí)的數(shù)量。

圖6 不同狀態(tài)AGV數(shù)量隨時(shí)間的變化Fig.6 Number of AGVs in different states changes over time

4 結(jié)論

本文在離散網(wǎng)格環(huán)境下設(shè)計(jì)了基于AGV的大規(guī)模物流包裹分揀系統(tǒng)，系統(tǒng)采用基于中央控制器的集中控制策略，中央控制器根據(jù)運(yùn)行網(wǎng)絡(luò)和系統(tǒng)狀態(tài)，采用Label Correcting算法，對AGV進(jìn)行行駛路徑規(guī)劃，并定期進(jìn)行更新。采用交叉口不停留策略對系統(tǒng)內(nèi)AGV進(jìn)行交通控制，并實(shí)時(shí)進(jìn)行死鎖檢測與恢復(fù)，保證系統(tǒng)能夠持續(xù)高效運(yùn)行。

基于所建立的分揀系統(tǒng)，通過開展仿真實(shí)驗(yàn)對系統(tǒng)進(jìn)行了測試，重點(diǎn)分析了更新間隔時(shí)間對系統(tǒng)運(yùn)行性能的影響。結(jié)果表明，隨著更新間隔時(shí)間的增大，雖然仿真運(yùn)行效率有顯著提升，但系統(tǒng)的運(yùn)行性能呈現(xiàn)下降趨勢。更新間隔時(shí)間越大，系統(tǒng)規(guī)定時(shí)間內(nèi)完成的包裹分揀次數(shù)越小，而系統(tǒng)內(nèi)死鎖產(chǎn)生次數(shù)和AGV平均旅行時(shí)間均越大。因此，在實(shí)際應(yīng)用中，確定更新間隔時(shí)間時(shí)，需兼顧系統(tǒng)運(yùn)行時(shí)間和系統(tǒng)運(yùn)行性能兩方面的指標(biāo)。需要說明的是本文中假定包裹的服務(wù)目的地是均勻分布的，而實(shí)際中會(huì)出現(xiàn)不均勻分布的情況，這也是下一步工作中將要解決的問題。