李蘇琪，朱孔金

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

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

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

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

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

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

1 系統(tǒng)描述

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

注：箭頭表示處于該行(列)的元胞所允許的移動方向；紅色AGV表示處于載貨狀態(tài)；藍色AGV表示處于空載狀態(tài)； 紅色虛線為載貨AGV可行的移動路徑；藍色虛線為卸載后空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不允許進入該類元胞，該類元胞相當于障礙物，如圖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)改變運動方向,如圖1中的元胞(1,2)、(1,3)和(1,5)。通常一個完整的交叉口由4個交叉口元胞組成，圖1中藍色實線框所圍成的區(qū)域即為一個交叉口。無用元胞(CL)為系統(tǒng)中當前未被利用的空間，如圖1中的元胞(3,1)、(3,13)、(6,1)和(6,13)，該類元胞可預(yù)留用于AGV充電、維修等。決策元胞(CR)是AGV調(diào)整行駛狀態(tài)的地方，AGV只能在該類元胞上對行駛路徑進行動態(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運行網(wǎng)絡(luò)，中央控制器再基于運行網(wǎng)絡(luò)對所有AGV行駛路徑進行規(guī)劃，并在規(guī)定的時間間隔內(nèi)根據(jù)系統(tǒng)狀態(tài)進行更新。為協(xié)調(diào)眾多AGV同時移動時的交通問題，本文采用交叉口不停留規(guī)則對分揀系統(tǒng)內(nèi)的AGV進行交通控制。交叉口不停留規(guī)則要求AGV只能在決策元胞進行決策判斷，即停留還是繼續(xù)行駛，一旦進入交叉口，則AGV除轉(zhuǎn)彎外不允許停留。

2.1 符號和定義

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

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

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

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

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

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

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

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

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

(1)

2.3 交通控制

圖3 移動指令判斷流程圖Fig.3 Flow chart of movement instruction assessment

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

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

3 結(jié)果與討論

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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