基于A*算法的配送中心“貨到人”揀選法AGV路徑規劃研究

張洪濤，蘇凱凱，何震，林雪成，郭曼曼

（1.大連海事大學，遼寧 大連 116026；2.天津科技大學 天津 300457；3.大禹節水（天津）有限公司，天津 301739）

傳統倉庫系統主要依靠人工進行存儲和揀選作業，需要員工手動查找物品，這種方式效率低下，很容易出現錯誤，導致服務水平低，且需要較多人力資源投入，增加了企業的人力成本。多臺自動導引車協同人工揀選能夠大幅提高作業效率，李騰[1]將AGV的運行階段根據路段特征和交通情況進行劃分，如直行、左轉和右轉等。在A* 算法中，引入一個轉彎懲罰值，減少轉彎的次數，從而達到更快的行駛速度和更高的效率。根據AGV 當前遇到的障礙物的等待時間，設置其避障的優先級，從而避免避障過程中的效率問題。在多AGV 路徑規劃中，A* 算法是一種重要的算法，多位學者對A* 算法進行了創新性研究，例如劉恒麟[2]改進后的A* 算法相較傳統A* 算法在同樣的路徑成本下，轉彎的次數減少了17%；并行化CBS 算法比傳統CBS 算法路徑規劃運算時間降低了33.9%。廖凱文[3]采用拓撲-柵格法來建立地圖模型，可以提高路徑規劃的效率和精度，即將拓撲圖柵格化，并根據機器人的占空比將柵格化后的地圖進行二值化處理。這一步操作可以將整個地圖進行分解，將其變成一個一個的柵格單元。當多臺AGV 從同一起始位置規劃路徑時，侯正[4]將OPEN 表分為公有OPEN 表和私有OPEN 表，其中公有OPEN 表存儲了所有AGV 擴展節點和路徑，提出了離線多AGV 路徑規劃算法即DC-CBS 算法。陳夢夏[5]發現DC-CBS 規劃出的路徑代價總和接近最優解，并且在較大或較小的規模中運行時間都比CBS 算法短。郭超[6]針對多AGV 協同作業場景中的無沖突路徑規劃問題，采用基于沖突搜索的兩層路徑規劃架構來解決。對AGV 與環境進行建模，確定AGV 的啟動和目標位置，并將地圖柵格化表示為矩陣。其次，利用搜索算法來規劃AGV 的路徑。即采用兩層搜索的方式，結合A* 算法和沖突搜索算法，可以有效規劃AGV 在倉庫內的路徑，避免沖突并實現高效的物品搬運。

一、問題描述

本文所研究的“貨到人”揀選系統主要流程如圖1 所示[7]。針對某時間段的用戶訂單，根據訂單需求、貨架庫存及補貨需求生成揀貨和上貨任務指令，然后將所對應貨架的搬運任務分配至AGV，由AGV沿算法規劃的路線完成搬運揀選任務。以AGV 完成所有訂單揀選任務的行駛路徑最短為目標，研究“貨到人”揀選系統下的AGV 路徑規劃。為簡化模型，本文不考慮系統如何分析訂單，通過設置貨架優先級代表貨架的重要程度，融合至AGV 的分配策略，從全局視角對AGV 進行路徑規劃。

圖2 為貨物存儲分揀中心平面規劃圖，最下側為AGV 充電區，AGV 無作業安排或者非工作時間可在此完成充電和停放。此模型安排3 輛AGV 小車完成各項作業，設定整個工作區域為64×64 個單位，AGV 每秒可以運行3 個單位。

規劃圖中間部分為存儲區，每個特制貨架有四層，貨物放置于四層貨位上，每個貨位僅存放一種商品，一個貨架可以放置四種貨物。

規劃圖最左側為上貨區，將補貨需求輸入控制系統中，對需要補貨的貨架賦予更高的優先級，派遣AGV 至優先級高的貨架下，AGV 將貨架頂起，利用A* 算法進行路徑規劃，使貨架到達上貨區指定位置，完成上貨作業。上貨工作平臺共三個，每個上貨平臺有操作員進行上貨作業，將貨物補貨到相應位置。規劃圖最右側為揀選區，有六個打包臺，并配備六名揀選員，完成訂單所需的揀選作業與打包作業，兩個打包臺為一組，共三組。

基于貨架優先級，設計AGV 貨架搬運任務分配方式，該方式考慮了訂單揀選需求和商品補貨需求，并根據貨架的重要程度設置了優先級。對于訂單揀選需求，將貨架上具有更多所需商品種類和數量的貨架賦予較高的優先級。通過優先搬運需求率更高的貨架，可以盡早滿足多訂單者的商品需求，減少貨架搬運次數，從而實現訂單更快出庫。對于商品補貨需求，貨架的優先級指的是貨架中空貨位的數量，可優先選取空貨位更多的貨架進行補貨，加快補貨速度。

二、地圖選擇以及沖突類型

（一）柵格地圖法

柵格地圖法將環境劃分為多個柵格單元，如一個正方形或一個六邊形。然后，使用傳感器例如激光雷達、攝像頭等，獲取環境中的障礙物和地形信息，并將其映射到相應的柵格單元中，形成一張柵格地圖。柵格地圖法保存環境的靜態信息，例如墻壁、障礙物等。由于柵格的尺寸可以調整，這種方法能夠在不同的場景中應用。柵格地圖法還可以使用快速的碰撞檢測算法，讓機器人在避免碰撞的同時進行導航，如圖3 所示。

柵格地圖法是一種簡單且高效的方法，常用于工業機器人、無人機和移動機器人的環境感知與導航任務。本文的研究場景為存儲揀選倉庫，每個貨架上都有上貨和取貨任務，需要準確地描述倉庫中的障礙物信息和實際距離成比例的關系，地圖構建的方法應具有普適性和擴展性。

（二）多AGV路徑規劃沖突類型

在多AGV 系統中，路徑規劃沖突通常是指兩個或多個AGV 嘗試占用相同的區域。相向沖突如圖4所示[8]，當兩個AGV 相向而行時，在狹窄的路徑或交叉路口相遇，就會發生相向沖突。這種情況下，需要在路徑規劃時合理安排AGV 的運動方向或在交叉路口設置信號燈等手段避免沖突。

當一個AGV 追趕另一個AGV 并試圖占用它正在占用的位置時，就會發生追及沖突。這種情況下，需要在路徑規劃中考慮AGV 速度、加速度等因素避免沖突，追及沖突示意圖，如圖5 所示[9]。

在多AGV 系統中，路口沖突是指在AGV 通過路口時，由于路口通道的容量限制或者不恰當的路徑規劃，導致多輛AGV 在同一路口等待進入通道或目標位置，甚至可能發生相撞的情況，路口沖突如圖6 所示[10]。

三、多AGV路徑規劃

（一）多AGV路徑規劃模型建立

多AGV 路徑規劃問題較為復雜，隨著作業場地的動態變化，路徑規劃也會隨之動態調整。本文所考慮的場景是貨物存儲分揀中心倉庫，利用AGV 配合人工完成對貨物的揀選工作。本倉庫內有3 臺AGV 運載車，每臺AGV 分別被派發了不同的運輸與搬運任務，系統程序為每臺AGV 各自規劃互不碰撞的最優路徑，但是由于作業場地的限制，搬運任務實施過程中必然有重合的路徑。多AGV 路線規劃可以建立數學模型來進行求解，其前提假設如下：

1.假設多臺AGV 在同一時間只能處理一項任務，同一任務只能由一臺AGV 執行；

2.每柵格點同一時刻只允許一臺AGV 占用，當某柵格在某一時刻有AGV 通過時，其他AGV 在該柵格的通行狀態為不可通過；

3.在規劃期間，系統的整體狀態不會發生改變，例如場地上的所有AGV 數量不會增加或減少，任務也不會跳出等；

4.AGV 運輸車在結束本次移動任務后，才可接受系統調度的下一個移動指令；

5.每個AGV 車輛都具有相同的速度、最大負載、最大行駛距離和最大運行時間；

6.每個任務都有一個起點和終點，AGV 可以在兩個節點之間完成任務。

（二）基于A*算法規劃多AGV無碰撞最優路徑

A* 算法通過評估從起點到目標點的代價函數，來引導搜索過程，以便盡可能快地找到從起點到目標點的最短路徑。A* 算法的輸入是在給定空間中的一個起始狀態和一個目標狀態，算法的輸出是一個狀態轉移序列，表示AGV 的移動路徑。當輸入一個起始狀態和終點狀態后，A* 算法從起點開始向四周擴張節點，如圖7 所示[11]，同時避開障礙物，每次擴張到列表中具有最小值的節點，直至擴張到目標節點為止，函數將記錄的擴張節點順序作為結果返回。

在計算代價時，A* 算法通常結合兩個指標：節點到起點的代價和節點到目標點的估計代價。對于估計代價，A* 算法使用啟發式函數，需要滿足兩個條件：一是啟發式函數的返回值不超過節點到目標點的實際代價；二是啟發式函數越小越好。一般來講，A* 算法利用估計代價一般通過下列評估函數計算：

其中，n 為當前節點，g（n）表示從起點到當前節點的實際代價，h（n）表示從當前節點到目標點的估計代價，f（n）表示從起點到當前節點再加上從當前節點到目標點的總代價，優先考慮估計代價更小的節點，能保證找到的路徑是最優解，如表1 所示[12]。

表1 符號定義表

將會用到的符號內涵為[13]：n 為柵格地圖中的一個節點，n.x 為節點n 的橫坐標，n.y 為節點n 的縱坐標，goal.x 表示目標節點的橫坐標，goal.y 表示目標節點的縱坐標。歐幾里得距離的算法是：

歐幾里得距離通常用來計算在平面直角坐標系中兩點間的距離，即兩點之間的直線距離。本文算法選用歐幾里得距離為h（n）的計算方式。A* 算法的具體流程，如圖8 所示[14]：

（三）MATLAB實驗仿真

1.入庫作業

AGV 在沒有作業任務時在充電區等候指令并完成充電。系統根據實時監測從而獲得貨架上的貨物量，將缺貨的貨架賦予更高的優先級，并基于A*算法，將AGV 分配至優先級較高的貨架處，利用AGV 自帶的頂升裝置把需要補貨的貨架頂起，搬運各個貨架區域的貨架至指定的上貨平臺，由上貨平臺的操作員完成上貨作業。之后將貨架再搬運至由來的位置，完成上貨的全過程。圖9 所示為路徑規劃仿真演示：用圓點代表AGV 小車，為簡化模型，不考慮AGV 小車轉彎減速等情況，假設AGV 小車勻速行駛，設置AGV 小車的平均時速為3 個單位每秒，并用不同線形不同顏色來表示不同的AGV 路徑。

2.出貨作業

布局圖中一共有三個揀選平臺，每個揀選平臺分別為兩個打包平臺服務，本物流配送中心可為六個打包臺服務。系統將三個分揀平臺匯集的36 個訂單進行分析，根據訂單需求，匹配盡可能滿足訂單需求的貨架。AGV 在充電區等候指令，系統將每個需要搬運的貨架分配至距離貨架最近的AGV。AGV 接到指令后，基于A* 算法進行尋路，將指定貨架搬運至相應的揀選工作臺。在路徑規劃中要實現避障并滿足配送時間最短的要求。

分揀時的作業方式為人工播種式揀選，每個揀選平臺都有兩位揀選員完成對12 個訂單的貨物進行揀貨。一個揀選平臺為兩個打包臺服務，共用一個AGV 配送貨架進行揀貨。播種式揀選提高了揀選的效率，減少了AGV 移動距離，達到了降本增效的目的。圖10 為出庫作業時AGV 路徑規劃模擬結果。

圖1 分揀系統的工作流程圖

圖2 貨物存儲分揀中心規劃圖

圖3 柵格地圖法圖

圖4 相向沖突示意圖

圖5 追及沖突示意圖

圖6 路口沖突示意圖

圖7 AGV八向移動圖

圖8 A*算法流程圖

圖9 入庫路徑規劃仿真模擬圖

圖10 出庫路徑規劃仿真模擬圖

四、結論

物流是支持電子商務發展的核心基礎行業，因此高速發展的電子商務也推動了物流行業進入新的階段。許多企業都在對物流分揀中心場地進行擴張和無人化、智能化升級，引進多AGV 系統是目前最普遍最有效的實現方式。本文分析了AGV 作為搬運貨物主要運輸工具的優勢以及AGV 配合人工揀選的優勢，考慮了多AGV 路徑規劃時的路徑沖突，使用A* 算法規劃路徑。采用柵格法建立地圖模型，建立以各AGV 路徑最短為目標的數學模型，提出了適用于自動化倉庫環境的AGV 路徑規劃算法。