基于自動導引車輛的物流分揀系統交通控制策略

李蘇琪，朱孔金

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

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

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

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

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

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

1 系統描述

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

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

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

2 數學模型

為仿真分析大規模的物流分揀系統，本文基于有向網絡構建AGV運行網絡，中央控制器再基于運行網絡對所有AGV行駛路徑進行規劃，并在規定的時間間隔內根據系統狀態進行更新。為協調眾多AGV同時移動時的交通問題，本文采用交叉口不停留規則對分揀系統內的AGV進行交通控制。交叉口不停留規則要求AGV只能在決策元胞進行決策判斷，即停留還是繼續行駛，一旦進入交叉口，則AGV除轉彎外不允許停留。

2.1 符號和定義

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

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

2.2 運行網絡

本文不考慮AGV離開系統后的調度問題，因此需在系統中增加一個虛擬目的地元胞0+作為空載AGV離開系統時的目的地。為了描述AGV的行駛路徑，分揀平臺環境可由有向網絡G=(N,A)表示。其中，N=CR∪CD∪{0+}為網絡G的節點構成的集合，A為網絡G的弧構成的集合。網絡G中的弧分為三類：(1)運行弧。對于任意交叉口，供AGV駛入該交叉口的決策元胞與供AGV駛出該交叉口的決策元胞之間相連構成的弧。(2)卸貨弧。卸貨元胞與自己對應的儲貨元胞之間相連構成的弧。(3)駛出弧。任意出口元胞與虛擬元胞0+相連構成的弧。

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

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

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

中央控制器根據AGV運行網絡對AGV進行路徑規劃，得到的路徑信息為弧的有序集合，中央控制器將弧的集合轉換為元胞的有序集合，AGV根據元胞的有序排列在柵格地圖上移動。

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

(1)

2.3 交通控制

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

移動指令的確定是依據仿真系統當前狀態判斷的，容易出現判斷不充分的情況，因此本文引入最大循環判斷次數kmax來進行重復循環判斷，最大化調動系統內可移動的AGV。

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

3 結果與討論

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

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

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

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

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

3.1 路徑更新時間間隔對分揀系統性能影響

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

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

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

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

3.2 路徑更新間隔對分揀系統容量的影響

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

圖6 不同狀態AGV數量隨時間的變化Fig.6 Number of AGVs in different states changes over time

4 結論

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

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