帶時(shí)間窗的車間搬運(yùn)機(jī)器人路徑優(yōu)化建模及算法研究

任劍鋒, 葉春明, 楊 楓

(1.上海理工大學(xué) 管理學(xué)院,上海 200083; 2.河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,河南 鄭州 450018)

0 引言

“中國(guó)制造2025”戰(zhàn)略指出我國(guó)要大力推進(jìn)信息化和工業(yè)化深度融合，加速推進(jìn)生產(chǎn)過(guò)程智能化進(jìn)程[1]；眾所周知，車間是生產(chǎn)制造的關(guān)鍵環(huán)節(jié)，提高車間智能化管理水平，挖掘潛能、節(jié)約成本、降低能耗是學(xué)術(shù)界和工業(yè)界共同關(guān)心的課題。

以客戶為中心，小規(guī)模、高靈敏度的個(gè)性化生產(chǎn)模式成為當(dāng)前搶占市場(chǎng)、贏得客戶的有力工具，車間搬運(yùn)機(jī)器人的大量引進(jìn)改變了以傳送帶進(jìn)行物料配送的大規(guī)模生產(chǎn)模式，可在車間中準(zhǔn)確高效地完成配送任務(wù)；多臺(tái)搬運(yùn)機(jī)器人則可組成柔性配送系統(tǒng)，并可以隨著生產(chǎn)工藝流程的調(diào)整及時(shí)變更配送路徑，使同一條生產(chǎn)線上能夠同時(shí)加工多種產(chǎn)品，極大地提高了生產(chǎn)的柔性程度，生產(chǎn)效率得到很大提高，但同時(shí)人們也發(fā)現(xiàn)機(jī)器人的高額投資卻與收益不成比例，如何充分挖掘機(jī)器人的生產(chǎn)潛能成為新的研究熱點(diǎn)。合理分配機(jī)器人數(shù)量，改變機(jī)器人單一配送或回收任務(wù)為同時(shí)執(zhí)行配送和回收任務(wù)，將機(jī)器人單獨(dú)作業(yè)升級(jí)為多機(jī)器人同時(shí)作業(yè)模式；如此以來(lái)，我們就要考慮車間生產(chǎn)過(guò)程中存在的需求、供應(yīng)、設(shè)備故障和其他類型的各種不確定干擾因素；另外，多機(jī)器人作業(yè)模式下，還要考慮機(jī)器人與障礙物或其他機(jī)器人之間可能存在的碰撞問(wèn)題，合理設(shè)置避障機(jī)制。本文正是以車間場(chǎng)景下搬運(yùn)機(jī)器人面對(duì)同時(shí)配送和回收任務(wù)為背景，以機(jī)器人數(shù)量、運(yùn)輸成本和時(shí)間懲罰成本的加權(quán)和為目標(biāo)，解決機(jī)器人路徑優(yōu)化問(wèn)題建模及算法研究。

遺傳算法較早被用來(lái)求解機(jī)器人路徑優(yōu)化問(wèn)題，Panchu等用遺傳算法求解機(jī)器人的作業(yè)完成時(shí)間最小問(wèn)題[2]；李妍峰等根據(jù)接收到的動(dòng)態(tài)信息來(lái)進(jìn)行機(jī)器人路徑優(yōu)化[3]；也有學(xué)者提出基于遺傳算法來(lái)優(yōu)化任務(wù)點(diǎn)的順序[4]，通過(guò)優(yōu)化和模擬完成任務(wù)的時(shí)間來(lái)確定機(jī)器人在連續(xù)點(diǎn)之間的最短路徑[5]；雙種群遺傳蟻群算法也被用來(lái)求解該問(wèn)題[6]，也有學(xué)者使用改進(jìn)遺傳算法求解類似問(wèn)題[7～9]；通過(guò)對(duì)遺傳算法在求解機(jī)器人路徑優(yōu)化問(wèn)題分析發(fā)現(xiàn)，該算法在可以求解得到小規(guī)模機(jī)器人路徑優(yōu)化問(wèn)題的最優(yōu)值，但收斂速度較慢，難以很好滿足車間生產(chǎn)模式下的敏捷需求。蟻群算法也被成功應(yīng)用于機(jī)器人路徑優(yōu)化問(wèn)題，裴振兵等提出用改進(jìn)蟻群算法求解機(jī)器人避障問(wèn)題[10]；趙宏才等提出建立α和β的互鎖關(guān)系來(lái)定義信息素更新規(guī)則[11]，也有學(xué)者提出基于蟻群算法求解高質(zhì)量的配送路線問(wèn)題[12]；王輝等提出用改進(jìn)蟻群算法求解泊車系統(tǒng)路徑優(yōu)化問(wèn)題[13]；張建同等提出用混合蟻群算法求解卡車路徑規(guī)劃問(wèn)題[14]；也有學(xué)者提出一種求解路徑優(yōu)化問(wèn)題的混合蟻群算法[15]；分析發(fā)現(xiàn)，蟻群算法在求解機(jī)器人路徑優(yōu)化問(wèn)題時(shí)具有魯棒性較強(qiáng)、分布式特征明顯、可靠性高等優(yōu)點(diǎn)，缺點(diǎn)則是會(huì)以一定概率陷入局部最優(yōu)解。強(qiáng)化學(xué)習(xí)[16]算法近年來(lái)也被應(yīng)用于路徑優(yōu)化問(wèn)題，于乃功等采用改進(jìn)后的Q學(xué)習(xí)算法求解并取得了很好的效果[17]；高樂(lè)等提出一種改進(jìn)的Q學(xué)習(xí)算法應(yīng)用在多障礙環(huán)境下機(jī)器人的路徑規(guī)劃問(wèn)題[18]；還有學(xué)者設(shè)計(jì)了一種改進(jìn)的模糊Q學(xué)習(xí)算法求解路徑規(guī)劃策略問(wèn)題[19]。還有學(xué)者用螢火蟲優(yōu)化算法進(jìn)行車輛路徑優(yōu)化問(wèn)題求解[20]；以及采用禁忌搜索算法求解車輛路徑優(yōu)化問(wèn)題[21,22]，對(duì)本文問(wèn)題研究也提供了一定的啟發(fā)。

綜上，國(guó)內(nèi)外學(xué)者對(duì)機(jī)器人或類似研究對(duì)象的路徑優(yōu)化問(wèn)題有較為深入的研究，在理論、模型和算法方面也取得了豐碩的成果，但在車間特定場(chǎng)景下同時(shí)進(jìn)行配送和回收任務(wù)的多機(jī)器人作業(yè)路徑優(yōu)化問(wèn)題研究成果并不多見；同時(shí)，相關(guān)研究多采用遺傳算法、蟻群算法等智能仿生算法，用強(qiáng)化學(xué)習(xí)算法解決車間場(chǎng)景的機(jī)器人路徑優(yōu)化問(wèn)題更是少見；同時(shí)，已有成果考慮的多為靜態(tài)環(huán)境下的路徑優(yōu)化問(wèn)題，并不符合車間場(chǎng)景下不確定因素眾多的實(shí)際情形。比如車間生產(chǎn)環(huán)境下存在的動(dòng)態(tài)障礙物出現(xiàn)、機(jī)器人自身性能波動(dòng)、緊急訂單插入、加工設(shè)備故障等動(dòng)態(tài)因素；因此，本文提出一種強(qiáng)化學(xué)習(xí)遺傳蟻群算法進(jìn)行問(wèn)題求解，結(jié)合蟻群算法的魯棒性強(qiáng)、高可靠性等優(yōu)點(diǎn)，同時(shí)引入遺傳算子的交叉、變異機(jī)制跳出局部最優(yōu)解，同時(shí)將強(qiáng)化學(xué)習(xí)算法對(duì)環(huán)境變化的感知能力有機(jī)結(jié)合起來(lái)，有效彌補(bǔ)單一算法的缺點(diǎn)和不足；全局路徑通過(guò)嵌入遺傳算子的蟻群算法求解，局部子路徑通過(guò)強(qiáng)化學(xué)習(xí)算法求解，同時(shí)在子路經(jīng)上捕捉車間動(dòng)態(tài)出現(xiàn)的碰撞信息，并實(shí)現(xiàn)動(dòng)態(tài)避障，最終求出以總成本最低為目標(biāo)的路徑優(yōu)化問(wèn)題。

1 問(wèn)題描述

車間生產(chǎn)中每種產(chǎn)品所需的配件不同，每臺(tái)加工設(shè)備均要及時(shí)供給物料，同時(shí)要及時(shí)取走該加工設(shè)備上已加工的產(chǎn)品，否則就會(huì)造成庫(kù)存增加甚至導(dǎo)致設(shè)備暫停，對(duì)于高精尖且需要較長(zhǎng)預(yù)熱時(shí)間的設(shè)備，頻繁關(guān)?；蚩辙D(zhuǎn)均會(huì)造成成本增加，甚至對(duì)設(shè)備造成損害。

在車間場(chǎng)景下，本文構(gòu)建了多機(jī)器人的柔性搬運(yùn)系統(tǒng)，根據(jù)生產(chǎn)車間存在眾多不確定因素的實(shí)際情形，本文考慮在時(shí)間窗內(nèi)為加工設(shè)備提供配送和回收服務(wù)，以確保加工設(shè)備及時(shí)得到物料供應(yīng)，同時(shí)取走工位上的加工成品，通過(guò)時(shí)間窗口來(lái)降低車間不確定因素帶來(lái)負(fù)面影響；故將搬運(yùn)機(jī)器人對(duì)每臺(tái)加工設(shè)備的到達(dá)時(shí)間設(shè)置為時(shí)間窗[Eti,Lti]，同時(shí)明確搬運(yùn)機(jī)器人對(duì)每臺(tái)設(shè)備的服務(wù)時(shí)長(zhǎng)。

車間內(nèi)部每臺(tái)設(shè)備之間有一定的物理距離，可以確保搬運(yùn)機(jī)器人能夠穿梭行駛，且假定每臺(tái)設(shè)備的位置和配送中心的位置、每臺(tái)搬運(yùn)機(jī)器人的最大運(yùn)載能力已知，并且機(jī)器人的最大運(yùn)載能力大于每臺(tái)加工設(shè)備的單次配送或回收量。每臺(tái)設(shè)備只能由一臺(tái)機(jī)器人服務(wù)。為使問(wèn)題簡(jiǎn)化，搬運(yùn)機(jī)器人的電力續(xù)航能力較強(qiáng)，不再考慮機(jī)器人的最大運(yùn)行距離問(wèn)題。根據(jù)物料配送和產(chǎn)品回收的任務(wù)情況，合理安排搬運(yùn)機(jī)器人的數(shù)量，要求完成物料配送和產(chǎn)品回收任務(wù)的同時(shí)，還要使每臺(tái)加工設(shè)備在時(shí)間窗內(nèi)得到服務(wù)，實(shí)現(xiàn)機(jī)器人數(shù)量即基本成本、運(yùn)輸成本和時(shí)間懲罰成本加權(quán)總成本最小。車間只設(shè)置一個(gè)配送-回收中心，機(jī)器人在完成配送-回收任務(wù)之后均返回中心，形成閉合的運(yùn)行軌跡，如圖1所示。

圖1 配送路徑示意圖

車間環(huán)境下機(jī)器人的配送問(wèn)題路徑優(yōu)化與一般的pickup-delivery問(wèn)題相比，因?yàn)檐囬g環(huán)境狹小、設(shè)備價(jià)值較高因素，要考慮機(jī)器人與其他機(jī)器人或障礙物之間可能發(fā)生的碰撞問(wèn)題，避免因碰撞而導(dǎo)致末端執(zhí)行工具的損壞，可能發(fā)生碰撞時(shí)，機(jī)器人傳感器及時(shí)發(fā)送信號(hào)給控制系統(tǒng)，進(jìn)而緊急調(diào)整配送路徑；因此，結(jié)合車間環(huán)境下的配送回收問(wèn)題特殊性，動(dòng)態(tài)避障問(wèn)題是本文在設(shè)計(jì)算法時(shí)加入強(qiáng)化學(xué)習(xí)部分的主要原因。

2 模型構(gòu)建

車間有R臺(tái)最大運(yùn)載能力均為Q的搬運(yùn)機(jī)器人在時(shí)間窗[Eti,Lti]為M臺(tái)加工設(shè)備提供配送-回收服務(wù)。

Eti表示機(jī)器人對(duì)設(shè)備i的最早開始服務(wù)時(shí)間，Lti表示最遲服務(wù)時(shí)間。

ti表示機(jī)器人到達(dá)設(shè)備i的時(shí)間，并在完成對(duì)設(shè)備i的服務(wù)后經(jīng)時(shí)間tij運(yùn)行至下一個(gè)服務(wù)對(duì)象j，到達(dá)時(shí)間為tj，wi表示機(jī)器人對(duì)設(shè)備i的服務(wù)時(shí)長(zhǎng)。

Qrij表示機(jī)器人r從設(shè)備i到j(luò)的過(guò)程中是否產(chǎn)生碰撞。

di表示該設(shè)備需要的配送量，pi表示該設(shè)備需要的回收量，eij表示機(jī)器人在經(jīng)過(guò)設(shè)備i之后的配送總量，之后前往j設(shè)備；fij表示機(jī)器人在經(jīng)過(guò)設(shè)備i后的回收總量，之后前往j設(shè)備；且任何時(shí)候機(jī)器人的配送量與回收量之和不能超過(guò)機(jī)器人的最大運(yùn)載能力；配送-回收中心和各加工設(shè)備的空間位置已知，并用相應(yīng)的坐標(biāo)表示，用dij表示從加工設(shè)備i到設(shè)備j的距離，決策變量xijr和yir定義如下。

問(wèn)題的數(shù)學(xué)模型如下:

(1)

(13)

該模型中式(1)表示目標(biāo)函數(shù)，即車間總的配送-回收成本最低；式(2)表示所有機(jī)器人均從配送-回收中心出發(fā)；式(3)表示機(jī)器人完成任務(wù)之后返回配送-回收中心；式(4)、(5)和(6)表示有且僅有一臺(tái)機(jī)器人到達(dá)某一設(shè)備，并提供服務(wù)；式(7)、(8)和(9)表示服務(wù)時(shí)間約束；式(10)表示設(shè)備所需的物料配送量約束；(11)表示設(shè)備所需產(chǎn)品回收量約束；(12)表示機(jī)器人的運(yùn)載能力限制，(13)中Qij值為1表示從機(jī)器人r從設(shè)備i到j(luò)的過(guò)程中是否產(chǎn)生碰撞，0表示未產(chǎn)生碰撞。

3 算法設(shè)計(jì)

3.1 位置掃描

采用掃描法來(lái)獲取加工設(shè)備的位置，即用極坐標(biāo)來(lái)表示加工設(shè)備的位置，隨機(jī)選取某一設(shè)備位置為起始點(diǎn)，將其角度設(shè)為零度，以機(jī)器人的最大運(yùn)載能力為限制條件進(jìn)行設(shè)備節(jié)點(diǎn)分割，得到若干符合運(yùn)載量限制的子區(qū)域，取子區(qū)域的幾何中心并設(shè)置為虛擬節(jié)點(diǎn)。

3.2 節(jié)點(diǎn)選擇策略

(14)

3.3 信息素更新策略

信息素的更新方式至關(guān)重要，信息素更新過(guò)快，會(huì)導(dǎo)致“早熟”而陷入局部最優(yōu)，更新過(guò)慢則會(huì)降低收斂速度。因此，本算法中的信息素更新方式根據(jù)路徑的適應(yīng)度值來(lái)動(dòng)態(tài)更新信息素的方式，如式(15)。

(15)

其中Q′為常數(shù)，適應(yīng)度值較小的路徑上信息素增加量大，反之，信息素增加量?。淮罅繉?shí)驗(yàn)證明，式(15)的信息素更新方式可以有效提高收斂速度。

3.4 編碼

本算法中采用路徑表示法編碼，每個(gè)可行解編碼即表示經(jīng)過(guò)的節(jié)點(diǎn)序列，對(duì)于有n臺(tái)加工設(shè)備的車間，m臺(tái)機(jī)器人來(lái)執(zhí)行配送-回收任務(wù)的問(wèn)題，用0到n+m-1共n+m個(gè)數(shù)字編碼為(0-x1-x2-…-xn+m-1)，0表示配送-回收中心，在編碼中第一臺(tái)機(jī)器人用0表示，其余機(jī)器人則用n+1,n+2,…,n+m-1表示。之所以第一臺(tái)機(jī)器人也用編碼中的0表示，是為了減少編碼長(zhǎng)度，同時(shí)不影響編碼的結(jié)構(gòu)特征和信息表達(dá)。

如車間有10臺(tái)加工設(shè)備，4臺(tái)機(jī)器人參與服務(wù)，則編碼0-3-5-11-2-7-8-12-4-6-1-13-9-10表示一個(gè)可行序列，編碼序列表達(dá)的配送-回收子序列為:

機(jī)器人1服務(wù)路線：O-3-5-0

機(jī)器人2服務(wù)路線：O-2-7-8-0

機(jī)器人3服務(wù)路線：O-4-6-1-0

機(jī)器人4服務(wù)路線：O-9-10-0

根據(jù)機(jī)器人路徑優(yōu)化的特點(diǎn)，為保留染色體的優(yōu)秀基因，可行解的較優(yōu)染色體采用如下的交叉策略，設(shè)兩組染色體分別為A1和A2。

(1)隨機(jī)生成染色體交叉的起始位置和交叉段長(zhǎng)度如下：

本文中交叉策略保留染色體中的優(yōu)秀基因片段，并且可以加快收斂到最優(yōu)解，缺點(diǎn)是容易陷入局部最優(yōu)；實(shí)驗(yàn)證明，遺傳算子在變異過(guò)程中可以對(duì)信息素產(chǎn)生明顯的擾動(dòng)作用，跳出局部最優(yōu)解。

3.5 動(dòng)態(tài)避障策略

本算法中采用強(qiáng)化學(xué)習(xí)算法來(lái)求解子路徑的優(yōu)化及動(dòng)態(tài)避障問(wèn)題。

(1)狀態(tài)迭代

本算法中構(gòu)造的狀態(tài)值函數(shù)迭代方程為：

V(sk)←V(sk)+α[rk+1+γV(sk+1)-V(sk)]

(16)

即:V(sk)←αrk+1+γV(sk+1)+(1-α)V(sk)

(17)

其中α為學(xué)習(xí)率，γ為折扣因子，V(sk)為當(dāng)前狀態(tài)值，V(sk+1)為下一狀態(tài)值，通過(guò)式(16)的反復(fù)迭代，最終使方程收斂到最大狀態(tài)值，進(jìn)而得到最優(yōu)路徑[23]。

將配送-回收中心抽象為節(jié)點(diǎn)0，在服務(wù)子路徑中的加工設(shè)備抽象為中間節(jié)點(diǎn)①→，將終點(diǎn)也抽象為節(jié)點(diǎn)0(即只有一個(gè)配送-回收中心)，如圖2所示。

圖2 強(qiáng)化學(xué)習(xí)路徑尋優(yōu)示意圖

從出發(fā)節(jié)點(diǎn)0開始前往子路徑上的任意其他節(jié)點(diǎn)，例如路線0→①→③表示從配送中心出發(fā)首先前往節(jié)點(diǎn)1服務(wù)，然后再前往節(jié)點(diǎn)3服務(wù)，以此類推，節(jié)點(diǎn)①與節(jié)點(diǎn)①之間沒(méi)有連線，表示不允許從該節(jié)點(diǎn)仍回到該節(jié)點(diǎn)。

本問(wèn)題中動(dòng)態(tài)選擇路徑的過(guò)程中不存在狀態(tài)轉(zhuǎn)移的概率模型，因此選用Q-learning算法，將路徑長(zhǎng)度作為強(qiáng)化學(xué)習(xí)迭代過(guò)程中的獎(jiǎng)勵(lì)值；同時(shí)，因?yàn)楸疚囊鉀Q有時(shí)間窗和服務(wù)時(shí)間的機(jī)器人配送-回收問(wèn)題，因此，將每個(gè)加工設(shè)備上的服務(wù)時(shí)間作為該節(jié)點(diǎn)的狀態(tài)值，并采用貪婪策略選擇路徑，如式(18)所示。

(18)

算法流程如圖3所示。

圖3 強(qiáng)化學(xué)習(xí)遺傳蟻群算法流程

(2)動(dòng)態(tài)避障

車間環(huán)境下的障礙物一般可分為長(zhǎng)期靜態(tài)障礙物、臨時(shí)靜態(tài)障礙物和臨時(shí)動(dòng)態(tài)障礙物共三類；因前兩類的研究已較為成熟，本文主要以臨時(shí)動(dòng)態(tài)障礙物為研究對(duì)象，通過(guò)強(qiáng)化學(xué)習(xí)算法感知超聲波、紅外等傳感器數(shù)據(jù)來(lái)實(shí)現(xiàn)動(dòng)態(tài)避障[24]。

如圖4所示的問(wèn)題，在常規(guī)情況下算法按照約束條件可以快速搜尋到最短路徑1-3-7-11-16-19-20，如果最優(yōu)路徑上第11個(gè)節(jié)點(diǎn)動(dòng)態(tài)出現(xiàn)障礙物，根據(jù)傳感器反饋的障礙物信息，將該節(jié)點(diǎn)的狀態(tài)值設(shè)為無(wú)限大，從而快速避開障礙物并搜尋到其他可行路徑1-3-7-12-16-19-20。

圖4 動(dòng)態(tài)避障示意圖

圖5 避障迭代曲線

圖5表示了常規(guī)約束條件下和動(dòng)態(tài)避障后的迭代曲線。通過(guò)對(duì)比可以發(fā)現(xiàn)，在常規(guī)情況下，強(qiáng)化學(xué)習(xí)算法可以快速收斂到最優(yōu)值28；在障礙物出現(xiàn)后，強(qiáng)化學(xué)習(xí)算法可以迅速捕捉到節(jié)點(diǎn)狀態(tài)值的突然變化，在計(jì)算開銷很小的情況下實(shí)現(xiàn)緊急避障，并重新搜尋到最優(yōu)路徑值32。

從實(shí)驗(yàn)中還可以發(fā)現(xiàn)，假如機(jī)器人行駛在節(jié)點(diǎn)3與節(jié)點(diǎn)7之間的路徑上，此時(shí)節(jié)點(diǎn)11產(chǎn)生臨時(shí)動(dòng)態(tài)障礙物，在重新規(guī)劃路徑時(shí)，不需要重新設(shè)置起始點(diǎn)，即障礙物出現(xiàn)之前的已規(guī)劃路徑不會(huì)改變，為機(jī)器人執(zhí)行配送任務(wù)的連續(xù)性提供了支持。

4 模擬仿真

4.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

本文在Intel i7處理器使用Matlab2017a進(jìn)行實(shí)驗(yàn)，其中蟻群算法的信息素重要程度因子取值為1，啟發(fā)函數(shù)重要程度因子取值為5，信息揮發(fā)因子為0.1，常系數(shù)Q為1；遺傳算法的交叉概率為0.85,變異概率為0.1,遺傳代溝為0.8；強(qiáng)化學(xué)習(xí)算法的學(xué)習(xí)率取值為0.1，折扣因子為0.9，三種成本參數(shù)如表1所示。

表1 成本參數(shù)表

本文將車間生產(chǎn)的配送-回收中心作為節(jié)點(diǎn)0，取其坐標(biāo)值為(30，60)，車間內(nèi)共有加工設(shè)備45臺(tái)，分別以相應(yīng)的坐標(biāo)X值和Y值表示其位置，每臺(tái)加工設(shè)備的配送量和需回收量已知，以及接受服務(wù)的最早時(shí)間和最遲時(shí)間，每臺(tái)加工設(shè)備有明確的配送和回收的服務(wù)時(shí)長(zhǎng)，如表2所示。

表2 加工設(shè)備信息表

4.2 實(shí)驗(yàn)及對(duì)比分析

用本文算法對(duì)問(wèn)題進(jìn)行求解，設(shè)每臺(tái)機(jī)器人的基本成本為300，每次實(shí)驗(yàn)的最大迭代次數(shù)為500次，可以發(fā)現(xiàn)在200次迭代以后基本可以得到較滿意解，并可以得到機(jī)器人基本成本為2100，即需移動(dòng)機(jī)器人7臺(tái)來(lái)完成物料配送和產(chǎn)品回收任務(wù)，結(jié)果如表3所示。

表3 最優(yōu)配送路徑

表中SP(Service path)表示服務(wù)路徑，AC(Actual capacity)表示機(jī)器人的實(shí)際運(yùn)載量，DW(Dead weight)表示最大載重量，F(xiàn)R(full-load ratio)表示滿載率。

同時(shí)，可求得運(yùn)輸成本為1970.13；時(shí)間懲罰成本為0，即所有加工設(shè)備均可在時(shí)間窗內(nèi)得到服務(wù)，總成本代價(jià)為4070.13。對(duì)每臺(tái)機(jī)器人的滿載率計(jì)算可以發(fā)現(xiàn)運(yùn)載能力得到了充分利用。

為了進(jìn)一步驗(yàn)證本文算法的有效性，與Wang等[25]公開的用遺傳算法(GA)求解的20個(gè)基本算例結(jié)果進(jìn)行對(duì)比，其中小規(guī)模算例(10個(gè)配送節(jié)點(diǎn)算例3個(gè)，20個(gè)配送節(jié)點(diǎn)算例2個(gè))共5個(gè)，中等規(guī)模算例(50個(gè)配送節(jié)點(diǎn))3個(gè)，大規(guī)模算例(100個(gè)配送節(jié)點(diǎn))12個(gè)?；谝陨匣鶞?zhǔn)算例，同時(shí)用Chao Wang等[26]公開的模擬退火算法(PSA)進(jìn)行求解并對(duì)比。

表4和表5中的NR(Number of Robot)表示分配的機(jī)器人數(shù)量，TD(Travel Distance)表示完成配送任務(wù)的行駛距離，NO(Number of obstacles)表示在算例中隨機(jī)出現(xiàn)的區(qū)間[0,5]之間的動(dòng)態(tài)障礙物個(gè)數(shù)。

小規(guī)模算例計(jì)算結(jié)果可以發(fā)現(xiàn)，使用RLGA算法對(duì)5個(gè)算例進(jìn)行求解，RCdp1004算例的計(jì)算結(jié)果達(dá)到理論最優(yōu)值，其余四個(gè)算例的計(jì)算結(jié)果與理論最優(yōu)值相比，與理論最優(yōu)值差距的平均值是0.26%，可見本算法在小規(guī)模算例中的計(jì)算結(jié)果可以很好的逼近理論最優(yōu)值，如表4所示。

小規(guī)模算例RCdp1001的求解路徑如圖6所示，該算例加入動(dòng)態(tài)障礙物之后的求解路徑如圖7所示。

對(duì)中等規(guī)模和大規(guī)模的15個(gè)基準(zhǔn)算例分別采用GA、PSA和RLGA進(jìn)行求解，將實(shí)驗(yàn)結(jié)果分為兩種情形，第一種情形是在算例中加入了障礙物的7個(gè)算例；由表5可知，7個(gè)算例添加的障礙物平均個(gè)數(shù)是3，其TD值均較基準(zhǔn)結(jié)果有所增加，其中GA計(jì)算結(jié)果平均增大0.33%，PSA計(jì)算結(jié)果平均增大0.27%,RLGA計(jì)算結(jié)果平均增大0.17%，在三種算法計(jì)算結(jié)果中，RLGA算法表現(xiàn)最好，可見RLGA算法對(duì)動(dòng)態(tài)避障問(wèn)題有較好的解決機(jī)制，可以將障礙物對(duì)路徑優(yōu)化的帶來(lái)的干擾降到合理范圍，得到比GA和PSA優(yōu)秀的結(jié)果；第二種情形是未出現(xiàn)障礙物的算例共8個(gè)，其中有2個(gè)算例節(jié)約了1臺(tái)機(jī)器人，同時(shí)伴隨TD值略有增加，其余6個(gè)算例中的3個(gè)算例TD值與GA算法和PSA算法計(jì)算結(jié)果相同，剩余3個(gè)算例的TD值有不同程度降低，平均降低0.34%；可見，RLGA算法可以得到更優(yōu)的結(jié)果。

在算法的計(jì)算速度方面，選取小規(guī)模算例(10個(gè)配送節(jié)點(diǎn))、中等規(guī)模算例(50個(gè)配送節(jié)點(diǎn))、大規(guī)模算例(100個(gè)配送節(jié)點(diǎn))問(wèn)題的GA、PSA和RLGA算法的收斂曲線對(duì)比如圖8(a)、(b)、(c)所示。

比較發(fā)現(xiàn)，在求解小規(guī)模問(wèn)題時(shí)，RLGA算法在收斂速度和解質(zhì)量上略優(yōu)于其他兩種算法；在求解中等規(guī)模和大規(guī)模問(wèn)題時(shí)，RLGA算法的求解質(zhì)量和速度上要明顯優(yōu)于GA算法和PSA算法計(jì)算結(jié)果。

算法在解決大規(guī)模配送問(wèn)題時(shí)優(yōu)勢(shì)更加明顯，在考慮動(dòng)態(tài)障礙物和無(wú)障礙物兩種情況下，求解質(zhì)量和速度均優(yōu)于其他兩種算法，表明RLGA算法的優(yōu)越性。

表4 RLGA算法與理論最優(yōu)值對(duì)比結(jié)果

表5 GA、PSA、RLGA算法結(jié)果

圖6 RCdp1001算例路徑

圖7 RCdp1001算例加入障礙物后路徑

圖8 GA、PSA、RLGA算法收斂曲線對(duì)比

5 結(jié)論

本文提出強(qiáng)化學(xué)習(xí)遺傳蟻群算法來(lái)求解車間場(chǎng)景下的搬運(yùn)機(jī)器人路徑優(yōu)化問(wèn)題，引入掃描法對(duì)設(shè)備節(jié)點(diǎn)進(jìn)行聚類劃分，將復(fù)雜問(wèn)題簡(jiǎn)化；借助強(qiáng)化學(xué)習(xí)的序貫決策和環(huán)境感知能力，結(jié)合蟻群算法的信息素更新策略和遺傳算法的交叉、變異機(jī)制實(shí)現(xiàn)車間搬運(yùn)機(jī)器人同時(shí)執(zhí)行配送和回收問(wèn)題的路徑優(yōu)化，通過(guò)與基準(zhǔn)算例的結(jié)果比較表明算法在解質(zhì)量和求解速度上的優(yōu)越性。

本算法中強(qiáng)化學(xué)習(xí)的狀態(tài)值和獎(jiǎng)勵(lì)值分別由加工設(shè)備所需的服務(wù)時(shí)長(zhǎng)和路徑長(zhǎng)度決定；實(shí)驗(yàn)發(fā)現(xiàn)，如果設(shè)置動(dòng)態(tài)的狀態(tài)值和獎(jiǎng)勵(lì)值可以更好地體現(xiàn)車間實(shí)際情形，同時(shí)加入機(jī)器人行為要素，同時(shí)考慮更復(fù)雜的避障要素會(huì)進(jìn)一步提升算法在理論和應(yīng)用上的價(jià)值。