基于多Agent的四向穿梭車調(diào)度優(yōu)化技術(shù)與應(yīng)用

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

一、序言

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

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

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

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

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

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

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

1.信息層Agent

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

2.控制層Agent

控制層Agent主要負(fù)責(zé)系統(tǒng)中的各項(xiàng)任務(wù)的分配，例如訂單分配、穿梭車及提升機(jī)的調(diào)度和貨位分配等一系列具體任務(wù)，控制層Agent對(duì)于各自所管轄的范圍內(nèi)的資源和任務(wù)，具有自主性和獨(dú)立性，同時(shí)也需要調(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ù)時(shí)，各執(zhí)行層Agent對(duì)于任務(wù)進(jìn)行競(jìng)爭(zhēng)，最終由獲得任務(wù)的Agent完成任務(wù)并反饋結(jié)果。

各Agent類型及功能見表1。

表1 Agent類型及功能

在多Agent密集倉(cāng)儲(chǔ)穿梭車系統(tǒng)中，Agent之間的交互主要體現(xiàn)在訂單管理Agent與出入庫(kù)月臺(tái)Agent、出入庫(kù)月臺(tái)Agent與倉(cāng)儲(chǔ)貨架Agent、倉(cāng)儲(chǔ)貨架Agent與穿梭車提升機(jī)Agent以及多穿梭車Agent與提升機(jī)Agent之間。各類Agent之間以招投標(biāo)方式實(shí)現(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的密集倉(cāng)儲(chǔ)四向穿梭車模型中執(zhí)行功能相同的Agent，其數(shù)據(jù)庫(kù)、知識(shí)庫(kù)以及狀態(tài)都不同且在實(shí)時(shí)變化，為確保系統(tǒng)運(yùn)行最優(yōu)化，招標(biāo)者Agent 將標(biāo)書實(shí)時(shí)發(fā)送至每個(gè)投標(biāo)者Agent，即每個(gè)投標(biāo)者Agent都將接收到招標(biāo)者Agent發(fā)出的招標(biāo)信息，再根據(jù)自身情況判斷是否發(fā)起投標(biāo)。

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

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

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

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

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

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

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

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

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

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

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

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

2.建立多Agent模型

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

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

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

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

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

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

（2）換軌時(shí)間5S、升降時(shí)間6S；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

STEP10對(duì)應(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%左右的效率，且對(duì)比系統(tǒng)優(yōu)化前運(yùn)行數(shù)據(jù)來看，出入庫(kù)可提高約30%的效率。

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

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

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

2.來料均衡入庫(kù)

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

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

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

五、結(jié)論

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

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