基于多Agent的四向穿梭車調度優(yōu)化技術與應用

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

一、序言

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

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

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

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

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

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

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

1.信息層Agent

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

2.控制層Agent

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

3.通訊層Agent

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

4.執(zhí)行層Agent

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

各Agent類型及功能見表1。

表1 Agent類型及功能

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

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

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

(3)執(zhí)行評價：針對招標投標環(huán)節(jié)所反饋的數(shù)據信息，對該任務完成程度進行評價。

三、項目案例及優(yōu)化模型構建

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

圖2 密集倉儲系統(tǒng)平面布局圖

1.主要技術指標

（1）存儲貨位數(shù)：5000貨位（6層貨架）；

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

（3）存儲物料規(guī)格（SKU）：30個；

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

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

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

2.建立多Agent模型

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

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

圖4 多Agent之間協(xié)調調度機制

3.數(shù)據處理與設置

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

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

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

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

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

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

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

4.模型參數(shù)設置驗證

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

5.基于多Agent的單車與多車任務調度優(yōu)化

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

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

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

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

在進行多任務出入庫任務時，采用集中控制方式，各子Agent將自己的能力轉化為參數(shù)遞交給調度系統(tǒng)中，隨后采用改進的匈牙利算法，將所有完成任務的子Agent的能力指標參數(shù)構成一個代價矩陣，隨后通過匈牙利算法對矩陣進行轉換，最終得到一個簡化矩陣，最終矩陣中為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為最優(yōu)分配解。

四、基于多Agent的調度優(yōu)化結果分析

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

表2 運行基礎數(shù)據

表3 優(yōu)化前系統(tǒng)運行數(shù)據

表4 優(yōu)化后系統(tǒng)運行數(shù)據

從運行數(shù)據來看，雙車能力比單車能力提升了65%左右的效率，且對比系統(tǒng)優(yōu)化前運行數(shù)據來看，出入庫可提高約30%的效率。

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

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

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

2.來料均衡入庫

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

3.將2/3區(qū)進行區(qū)域模數(shù)劃分

根據對物料托盤批次數(shù)和系統(tǒng)數(shù)據進行分析，對占比較高的物料批次進行區(qū)域規(guī)劃存儲，如2/3區(qū)劃分為區(qū)域模數(shù)。

五、結論

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

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