基于多Agent的四向穿梭車調度優化技術與應用

文 / 李岱東 金桂根 余榮洋 王國莉 黎建強 王佳

一、序言

電子商務和智能制造發展助推了智能倉儲技術的創新，針對生產物流品規少、批量大的特點，以及倉儲空間高效利用的因素，以貨架穿梭車為存取設備的智能密集倉儲技術近年來發展迅猛。貨架穿梭車是一種以貨架軌道導向的存取和搬運設備，通過傳感器、編碼器及伺服控制等技術，精確定位各個輸入、輸出及存儲工位，通過計算機調度管理系統，接收物料后進行自動往復穿梭搬運，并通過垂直提升機實現換層作業。托盤貨架穿梭車一般指四向穿梭車和子母穿梭車，其中四向穿梭車將子母穿梭車合二為一，可在主道、子道運行，實現多層多車協同并行作業模式，為智能物流存儲系統提供新的解決方案，是傳統巷道堆垛機立體存儲模式之外的重要智能倉儲創新模式。但智能密集倉儲系統的缺點是不能較好地實現物料的先進先出，出入庫效率相對較低，穿梭車調度系統的策略和算法顯得尤為重要，而多Agent系統的自治性、反應性和主動性特點能更好地適應密集倉儲的多車調度效率問題。

四向穿梭車系統是依靠系統內的穿梭車輛和提升機結構相互配合完成多車多層出入庫任務，利用提升機與穿梭車本身配置相互通信，在通過計算機軟件操作系統、倉庫管理系統完成換層及出入庫作業，相比堆垛機出入庫系統減少了巷道通道，很大程度提高了存儲空間的利用率。密集倉儲系統一般每層均放置一臺四向穿梭車，可最大限度提高系統響應時間，從而增加系統的吞吐量，減少平均出入庫時間；但實際運營中可能會出現多臺穿梭車利用率不均，進而導致巷道堵塞，出入庫效率大打折扣，因此多車協同調度優化技術顯得迫切和重要。

采用Agent人工智能理論的調度系統通過Agent智能行為和Agent個體之間的協商可以讓調度系統變得高速和高效。本文通過分析四向穿梭車密集存儲結構和特征，構建了基于多Agent技術的四向穿梭車密集倉儲調度優化模型，并將多Agent合作求解技術應用到調度策略中，取得了較好的優化效果。

二、密集倉儲四向穿梭車結構模型

多Agent系統結構通常包括以下三種類型：集中式、分布式和混合式。在分布式結構當中，每個Agent的狀態是相對相等的，充分發揮每個Agent的自治性和協商性。不同的任務調度環節對應不同的作業流程，根據系統這一特點，建立基于多Agent的密集倉儲四向穿梭車結構模型，如圖1所示，其中包含了各類別Agent之間的信息交互過程以及各Agent的主要功能，在訂單進入系統當中后，向出入庫系統發出訂單需求信息，再根據訂單貨品類型等信息分配給各個倉儲貨架Agent，再由倉儲系統調度穿梭車以及提升機，共同調度協作，完成最終的出入庫訂單任務。

圖1 密集倉存儲四向穿梭車結構模型

根據分析系統的運作機制，將整個結構模型MAS（Multi-Agent System）分解為信息層、控制層、通訊層以及執行層，各Agent功能如下：

1.信息層Agent

信息層Agent位于本系統中第一級別，負責整個系統中的信息采集、信息處理，同時主要負責協調規范下一級別控制層的各種Agent的行為，即訂單管理Agent、出入庫管理Agent和倉儲管理Agent。雖然每個控制層的Agent各自都具有自治性，但當這一級Agent之間產生競爭沖突時，由上級Agent來解決。

2.控制層Agent

控制層Agent主要負責系統中的各項任務的分配，例如訂單分配、穿梭車及提升機的調度和貨位分配等一系列具體任務，控制層Agent對于各自所管轄的范圍內的資源和任務，具有自主性和獨立性，同時也需要調節執行層各Agent之間的行為。

3.通訊層Agent

交互和通訊Agent主要負責各Agent之間的信息交互，以達到減少各Agent之間耦合性。各Agent之間通訊是基于通信斷言機制來進行交互和傳輸。

4.執行層Agent

執行層是具體執行任務的各種Agent，在接收到控制層Agent下達的任務時，各執行層Agent對于任務進行競爭，最終由獲得任務的Agent完成任務并反饋結果。

各Agent類型及功能見表1。

表1 Agent類型及功能

在多Agent密集倉儲穿梭車系統中，Agent之間的交互主要體現在訂單管理Agent與出入庫月臺Agent、出入庫月臺Agent與倉儲貨架Agent、倉儲貨架Agent與穿梭車提升機Agent以及多穿梭車Agent與提升機Agent之間。各類Agent之間以招投標方式實現任務分配和相互協作執行任務。因此在系統中各Agent之間的協調調度步驟主要有以下三步：

(1)任務派發環節：招標環節采用廣播招標，基于多Agent的密集倉儲四向穿梭車模型中執行功能相同的Agent，其數據庫、知識庫以及狀態都不同且在實時變化，為確保系統運行最優化，招標者Agent 將標書實時發送至每個投標者Agent，即每個投標者Agent都將接收到招標者Agent發出的招標信息，再根據自身情況判斷是否發起投標。

(2)任務請求環節：投標者在接到任務消息時，會檢查自身能力，首先檢查是任務緩沖池的剩余容量，是否可以接收新的作業任務，其次判斷是否符合完成任務的基本要求，最后判斷是否能在規定時間窗內完成任務所需要求。若滿足以上條件，多Agent系統將會制作標書送至投標Agent，投標Agent接受任務后將任務加入任務緩沖池，并按合同執行任務，最終對結果進行反饋。

(3)執行評價：針對招標投標環節所反饋的數據信息，對該任務完成程度進行評價。

三、項目案例及優化模型構建

JX物流中心是以智能密集倉儲為中心，集快速處理客戶訂單和配送功能為一體的現代化物流項目，完成物料準確快速的存儲、復核、集貨、發運等業務。智能密集倉儲系統包括四向穿梭車、提升機、貨架、出入庫站臺及計算機調度管理系統，平面布局如圖2所示。

圖2 密集倉儲系統平面布局圖

1.主要技術指標

（1）存儲貨位數：5000貨位（6層貨架）；

（2）設計最大儲量：80000-100000件；

（3）存儲物料規格（SKU）：30個；

（4）入庫流量：滿足生產線3000件/天的產能，滿足500件/小時的入庫流量；

（5）出庫流量：滿足每天發貨大箱10000件/天，有效工作時間按6小時計算；

（6）設備配置：4臺貨架穿梭車，2臺提升機。

2.建立多Agent模型

根據四向穿梭車MAS模型，建立基于多Agent的密集存儲四向穿梭車調度模型，如圖3所示，其協調調度管理策略及機制如圖4所示。

圖3 密集存儲四向穿梭車調度模型

圖4 多Agent之間協調調度機制

3.數據處理與設置

通過對計算機系統數據進行預處理及設置后，對連續時間、儲位進行數據分析，得到系統運行基礎數據。

（1）貨架梭車在進行出入庫作業時，一動作周期具體分解為：接貨（升降）-換軌-勻加速直線運動-勻速直線運動-勻減速直線運動-放貨（升降）；

（2）換軌時間5S、升降時間6S；

（3）在進行換軌時，只需要子道向主道詢問路徑（通訊時間4S）；

（4）T實際=T總=t升降+n*t換軌+t直線+t通訊；

（5）系統要求到達70PL/h（4臺車）的流量，按照均分原則，每層物料間隔時間為4PL/min；

（6）針對多車模型，在主道只能一輛小車通過，當前車離開主道后，后車可以即刻進行。

4.模型參數設置驗證

在實際任務主導下，因要達到T實際=T總，四向穿梭車在直線道上速度未知，進行多次數據校驗，對平均速度進行參數化設置，使單車單循環的作業時間近似等于實際時間，在允許誤差到達2%以下，得到可行性參數。

5.基于多Agent的單車與多車任務調度優化

（1）單車任務出入庫調度

在進行單任務出入庫任務時，存在多個穿梭車以及多臺提升機競爭同一任務的情況，這種情況下的入庫過程采用分布式控制的方式，控制決策由控制層的各Agent之間相互通訊協調來實現，對于單任務出入庫來說，存在于一個最優選的穿梭車以及提升機選擇，因此要對于各執行層Agent進行指標評價，主要指標有：穿梭車到出入庫站臺的時間，穿梭車預計完成任務的時間，穿梭車的排隊任務指標，穿梭車的健康指標，穿梭車的利用率等。各子Agent需要互相協商，根據指標公式計算出自身能力值，同時對該任務進行競標，隨后由控制層Agent進行決策并分配任務，能力計算如下。

式中：C(t)表示各子Agent的總能力值，ha(t)表示健康指標，T(Lxy，Le)、T(Le，Lij)采用時間計算各子Agent完成任務的能力，A表示當前子Agent是否空閑，空閑為1，否則為0。

（2）多車任務出入庫調度

在進行多任務出入庫任務時，采用集中控制方式，各子Agent將自己的能力轉化為參數遞交給調度系統中，隨后采用改進的匈牙利算法，將所有完成任務的子Agent的能力指標參數構成一個代價矩陣，隨后通過匈牙利算法對矩陣進行轉換，最終得到一個簡化矩陣，最終矩陣中為1的元素代表任務分配給這些子Agent。

STEP1輸入效率矩陣，并且每行中減去最小元素；

STEP2從每列中減去該列最小元素；

STEP3每行中只有一個0，則對該0進行標記，對于標記所在列進行劃線，依次劃線；

STEP4每列中只有一個0，對該0進行標記，對于標記所在行劃線，依次劃線；

STEP5矩陣中是否還存在未劃線的0，若存在則轉到STEP6，否則STEP8；

STEP6是否存在有0的閉回路，若不存在則轉到STEP3，否則STEP7；

STEP7順回路方向每一個間隔的0進行標記，對標記所在行列劃線，隨后轉到STEP8；

STEP8是否每一行都有被標記的0，都存在則轉到STEP10，否則STEP9；

STEP9找出未被直線覆蓋的最小元素k，做成新矩陣bij=aij-ui-vj，轉到STEP2；

STEP10對應的1為最優分配解。

四、基于多Agent的調度優化結果分析

四向穿梭車運行基礎數據如表2所示，基于多Agent的四向穿梭車調度優化模型及策略在JX物流中心的應用，優化前和優化后系統運行數據如表3、表4所示。

表2 運行基礎數據

表3 優化前系統運行數據

表4 優化后系統運行數據

從運行數據來看，雙車能力比單車能力提升了65%左右的效率，且對比系統優化前運行數據來看，出入庫可提高約30%的效率。

案例項目中，為使四向穿梭車的利用率進一步提高，達到預期的優化目標，結合以上優化調度技術，優化輔助措施如下：

1.增加空車返回路徑通道

增設空車返回路徑，使路徑長度縮短，減少所用時間，提升出入庫效率。

2.來料均衡入庫

若入庫來料不均衡，會導致某層小車一直處于停滯等待狀態，導致出入庫效率降低，應在入庫前端進行來料預處理，盡可能實現SKU混合入庫。

3.將2/3區進行區域模數劃分

根據對物料托盤批次數和系統數據進行分析，對占比較高的物料批次進行區域規劃存儲，如2/3區劃分為區域模數。

五、結論

將Agent技術與密集倉儲四向穿梭車系統相結合，將系統中的各項流程及設備映射成為相應的Agent模塊，并對這些Agent模塊設計相應的行為和功能，通過各Agent之間的協商機制，可以使智能Agent融入倉儲調度系統，可以提高系統的整體能力，同時可以使系統能夠靈活處理各種突發事件，減少異常事件對于系統整體效率的影響，使系統靈活魯棒性更強。

實現智能密集倉儲系統中多臺四向穿梭車運行調度的競合博弈，多臺穿梭車智能體學會彼此合作和相互競爭，相互協同完成存取貨、行走搬運的出入庫任務；使用多Agent的數學算法和邏輯找到多車物流調度、動態路徑規劃的最優解，實現系統運籌優化。