文 / 李岱東 金桂根 余榮洋 王國莉 黎建強(qiáng) 王佳

一、序言

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

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

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

二、密集倉儲四向穿梭車結(jié)構(gòu)模型

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

圖1 密集倉存儲四向穿梭車結(jié)構(gòu)模型

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

1.信息層Agent

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

2.控制層Agent

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

3.通訊層Agent

交互和通訊Agent主要負(fù)責(zé)各Agent之間的信息交互，以達(dá)到減少各Agent之間耦合性。各Agent之間通訊是基于通信斷言機(jī)制來進(jìn)行交互和傳輸。

4.執(zhí)行層Agent

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

各Agent類型及功能見表1。

表1 Agent類型及功能

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

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

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

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

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

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

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

1.主要技術(shù)指標(biāo)

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

（2）設(shè)計最大儲量：80000-100000件；

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

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

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

（6）設(shè)備配置：4臺貨架穿梭車，2臺提升機(jī)。

2.建立多Agent模型

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

圖3 密集存儲四向穿梭車調(diào)度模型

圖4 多Agent之間協(xié)調(diào)調(diào)度機(jī)制

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

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

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

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

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

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

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

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

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

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

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

（1）單車任務(wù)出入庫調(diào)度

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

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

（2）多車任務(wù)出入庫調(diào)度

在進(jìn)行多任務(wù)出入庫任務(wù)時，采用集中控制方式，各子Agent將自己的能力轉(zhuǎn)化為參數(shù)遞交給調(diào)度系統(tǒng)中，隨后采用改進(jìn)的匈牙利算法，將所有完成任務(wù)的子Agent的能力指標(biāo)參數(shù)構(gòu)成一個代價矩陣，隨后通過匈牙利算法對矩陣進(jìn)行轉(zhuǎn)換，最終得到一個簡化矩陣，最終矩陣中為1的元素代表任務(wù)分配給這些子Agent。

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

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

STEP3每行中只有一個0，則對該0進(jìn)行標(biāo)記，對于標(biāo)記所在列進(jìn)行劃線，依次劃線；

STEP4每列中只有一個0，對該0進(jìn)行標(biāo)記，對于標(biāo)記所在行劃線，依次劃線；

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

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

STEP7順回路方向每一個間隔的0進(jìn)行標(biāo)記，對標(biāo)記所在行列劃線，隨后轉(zhuǎn)到STEP8；

STEP8是否每一行都有被標(biāo)記的0，都存在則轉(zhuǎn)到STEP10，否則STEP9；

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

STEP10對應(yīng)的1為最優(yōu)分配解。

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

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

表2 運(yùn)行基礎(chǔ)數(shù)據(jù)

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

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

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

案例項目中，為使四向穿梭車的利用率進(jìn)一步提高，達(dá)到預(yù)期的優(yōu)化目標(biāo)，結(jié)合以上優(yōu)化調(diào)度技術(shù)，優(yōu)化輔助措施如下：

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

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

2.來料均衡入庫

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

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

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

五、結(jié)論

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

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