自主移動(dòng)機(jī)器人三維揀選路徑規(guī)劃研究

丁榮寬，董寶力

（浙江理工大學(xué) 機(jī)械工程學(xué)院，浙江 杭州 310018）

0 引言

自主移動(dòng)機(jī)器人（Autonomous Mobile Robots，AMR）揀選［1］是“貨到人”模式［2-3］下的一種方式，該方式通過(guò)系統(tǒng)規(guī)劃AMR 行駛路線，將訂單中的商品從貨架揀選至固定揀貨臺(tái)前。揀選貨物的時(shí)間是倉(cāng)庫(kù)提升效率的關(guān)鍵，因此，在AMR 執(zhí)行揀選作業(yè)時(shí)，如何規(guī)劃其移動(dòng)路徑、縮短揀選時(shí)間、提高揀選效率是亟待解決的問(wèn)題［4-5］。

近年來(lái)，不少學(xué)者對(duì)倉(cāng)庫(kù)智能揀選進(jìn)行了探究，路徑規(guī)劃更是成為倉(cāng)庫(kù)智能揀選的研究重點(diǎn)。如于浩洋［6］以雙區(qū)型倉(cāng)庫(kù)為例，基于先到先服務(wù)和固定訂單分批原則建立穿越策略路徑進(jìn)行揀選路徑優(yōu)化；潘魯寧［7］建立多目標(biāo)優(yōu)化模型，從配送中心儲(chǔ)位合理布局和揀選系統(tǒng)兩個(gè)角度對(duì)揀選路徑進(jìn)行優(yōu)化設(shè)計(jì)；胡小建等［8］針對(duì)魚骨型倉(cāng)庫(kù)揀貨路徑規(guī)劃問(wèn)題，以載重和容積為約束，以多車揀貨距離最短為總目標(biāo)進(jìn)行求解；秦德金［9］為提升多機(jī)器人協(xié)作分揀效率，構(gòu)建仿真模型并提出對(duì)應(yīng)路徑規(guī)劃算法與碰撞交通管理算法；辜勇等［10］對(duì)機(jī)器人路徑柵格化，并設(shè)計(jì)一種優(yōu)化轉(zhuǎn)移規(guī)則和信息素更新條件的新蟻群算法進(jìn)行求解；劉建勝等［11］針對(duì)Flying-V 型倉(cāng)庫(kù)的揀貨路徑優(yōu)化，提出一種接收正反饋的改進(jìn)蟻群算法。

此外，針對(duì)路徑規(guī)劃模型算法的研究也不在少數(shù)，常用于求解路徑規(guī)劃模型的算法包括：遺傳算法、粒子群算法、人工勢(shì)場(chǎng)法、A*算法等。張丹露等［12］針對(duì)智能倉(cāng)庫(kù)多機(jī)器人協(xié)同路徑規(guī)劃模型提出一種交通規(guī)則，并利用預(yù)約表生成基于改進(jìn)A*算法的動(dòng)態(tài)加權(quán)地圖；胡治鋒等［13］為優(yōu)化多層貨架人工揀選路徑模型，提出一種模擬退火蟻群算法，有效提升了倉(cāng)儲(chǔ)運(yùn)行效率；李艷生等［14］以路徑長(zhǎng)度、轉(zhuǎn)彎次數(shù)和機(jī)器人能耗為評(píng)價(jià)指標(biāo)構(gòu)建節(jié)能揀選路徑規(guī)劃模型，設(shè)計(jì)適用于倉(cāng)儲(chǔ)機(jī)器人路徑規(guī)劃的人工蜂群-自適應(yīng)遺傳算法；李騰等［15］針對(duì)大規(guī)模多AGV 多階段路徑揀選問(wèn)題，建立以任務(wù)完成時(shí)間最短為目標(biāo)的路徑規(guī)劃模型，并通過(guò)改進(jìn)A*算法解決模型中轉(zhuǎn)彎避障等問(wèn)題。然而，解決此類路徑問(wèn)題的常用智能算法只針對(duì)兩點(diǎn)間的直線距離，并不適用于三維空間內(nèi)橫梁式貨架［16］的路徑規(guī)劃問(wèn)題。因此，本文針對(duì)多區(qū)型倉(cāng)庫(kù)［17-18］中AMR 在三維空間下的路徑規(guī)劃問(wèn)題，考慮AMR 在揀選過(guò)程中載重以及速度變化等因素，構(gòu)建以AMR 分批次揀選總時(shí)間最小化為目標(biāo)的模型，并引入水平垂直疊加的折線路徑［19］。算法優(yōu)化方面，為避免傳統(tǒng)粒子群算法易陷入局部最優(yōu)的缺點(diǎn)，引入模擬退火算法（Simulated Annealing Algorithm，SAA）中 的Metropolis 準(zhǔn)則［20-21］，設(shè)計(jì)模擬退火粒子群混合算法（Simulate Annealed Particle Swarm Mixing Algorithm，SAPSMA）對(duì)目標(biāo)模型進(jìn)行求解。

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述

在多區(qū)型倉(cāng)庫(kù)中，每一區(qū)型配置有一臺(tái)AMR 負(fù)責(zé)該區(qū)型揀選作業(yè)。本文針對(duì)某一區(qū)型的AMR 揀選進(jìn)行研究，布局如圖1所示。該區(qū)型主要由橫梁式貨架、AMR 和I/O 起點(diǎn)構(gòu)成，其中貨架為普通、常規(guī)的多層貨架，I/O 起點(diǎn)為AMR 的開始和結(jié)束位置。貨架擺放方式：除最左最右兩列貨架貼墻放置外，中間貨架均兩列為一組，兩組之間由巷道間隔，縱向平行布置。假設(shè)貨架上單個(gè)貨格在X方向的長(zhǎng)度為l，Y方向的寬度為w，高度為h，巷道寬度為c，I/O 起點(diǎn)正對(duì)于第一條巷道。為方便觀察和計(jì)算，把該區(qū)型每個(gè)貨格按照網(wǎng)格狀排列分布。

Fig.1 Three-dimensional diagram of a certain area of the warehouse圖1 倉(cāng)庫(kù)某區(qū)型三維圖

假設(shè)系統(tǒng)累計(jì)接收n個(gè)訂單，且已知各訂單中貨物的存儲(chǔ)信息。AMR 最大承載重量為M，自身貨格數(shù)為Q，即AMR 單趟最多搬運(yùn)Q件貨物。在AMR 同時(shí)滿足載貨重量和貨格數(shù)雙約束的前提下，將訂單中所有待揀貨物分批次揀選完成，并將每一批次的揀選時(shí)間相加，優(yōu)化目標(biāo)為獲得一條相加后總時(shí)間最少的揀選路徑。

1.2 基本假設(shè)

建立揀選路徑規(guī)劃的數(shù)學(xué)模型前，對(duì)AMR 及貨架作以下假設(shè)和參數(shù)設(shè)定：①訂單中每一種庫(kù)存量單位（Stock Keeping Uint，SKU）對(duì)應(yīng)貨架中的一個(gè)貨格；②倉(cāng)庫(kù)中每一個(gè)貨格規(guī)格均一致，AMR 的大小參數(shù)與貨格大小相同；③每個(gè)貨格中SKU 的存儲(chǔ)數(shù)量都滿足訂單揀選數(shù)量；④AMR 在執(zhí)行某一種動(dòng)作時(shí)不能同時(shí)進(jìn)行其他動(dòng)作，也不會(huì)因其他因素中斷當(dāng)前動(dòng)作，以保證揀選作業(yè)的連續(xù)性；⑤AMR 開始執(zhí)行揀選任務(wù)時(shí)從I/O 起點(diǎn)出發(fā)，完成揀選任務(wù)或達(dá)到約束條件后均需返回I/O 點(diǎn)；⑥AMR 從一個(gè)揀選點(diǎn)移動(dòng)到另一個(gè)揀選點(diǎn)需要經(jīng)歷加速、（勻速）、減速階段，假設(shè)其空載和負(fù)載下水平方向運(yùn)動(dòng)的加減速度相同均為a，垂直方向升降臺(tái)提升和下落速度變化相同，設(shè)為v2。

1.3 模型建立

AMR 分批次揀選貨物的路徑規(guī)劃模型建立步驟如下。

首先對(duì)優(yōu)化模型中出現(xiàn)的符號(hào)進(jìn)行說(shuō)明：

O：訂單集合

S：貨架集合

P：SKU 商品種類

B=｛0，1，2，……，n｝：貨物揀選點(diǎn)集合，其中0 代表起點(diǎn)（揀選臺(tái)）；

（xi，yi，zi，mi）為訂單O上待揀SKU 的信息，例如（5，6，7，15）表示某SKU 位于倉(cāng)庫(kù)第5 列、第6 行、第7 層，重量為15KG。

AMR 一次完整的訂單揀選時(shí)間由3 個(gè)時(shí)間段組成：①揀選點(diǎn)間水平移動(dòng)時(shí)間，即在xoy面上移動(dòng)所需時(shí)間為T1；②在z軸方向，升降臺(tái)上升和下降的時(shí)間合為T2；③AMR 對(duì)SKU 取貨和卸貨的時(shí)間固定，合記為T3。AMR訂單揀選時(shí)間表示為：

假設(shè)AMR 在水平方面的移動(dòng)距離為rijs，為便于對(duì)小車路徑進(jìn)行規(guī)劃，將小車水平方向軌跡rijs分為3 個(gè)階段：

（1）I/O 起點(diǎn)到第一個(gè)貨物揀選點(diǎn)j間的水平距離。

式中：xi，xj均表示揀選點(diǎn)所在的列位置。

（2）當(dāng)前貨物揀選點(diǎn)i到待揀貨物揀選點(diǎn)j之間的水平距離。此時(shí)分為兩種情況：

①貨物揀選點(diǎn)i和j不在同一巷道時(shí)，即xi≠xj。

若i和j的行數(shù)相加小于f，則選擇下巷道出。其中，f為單列貨架在y軸方向上的行數(shù)。

若i和j的行數(shù)相加大于f，則選擇上巷道出。

②貨物揀選點(diǎn)i和j都在同一巷道內(nèi)。

（3）AMR 單趟揀選的最后一個(gè)貨架揀選點(diǎn)與I/O 點(diǎn)間的水平距離。

假設(shè)AMR 運(yùn)動(dòng)到待揀貨物下方，升降臺(tái)垂直方向移動(dòng)距離為d1，公式如下：

式中：zi為貨物i所在位置；zj為貨物j所在位置。

AMR 在水平方向的時(shí)間T1取決于移動(dòng)時(shí)的最大速度和加速度。假設(shè)AMR 水平移動(dòng)時(shí)能達(dá)到的最大速度為v1，由此分為兩種運(yùn)動(dòng)狀態(tài)：①AMR 在xoy面移動(dòng)過(guò)程中速度未達(dá)到最大速度v1，勻加速后做勻減速運(yùn)動(dòng)，即AMR 行駛的移動(dòng)距離；②AMR 在xoy面移動(dòng)過(guò)程中速度達(dá)到最大值v1，然后勻速運(yùn)動(dòng)，后再進(jìn)行勻減速運(yùn)動(dòng)，即移動(dòng)距離。

AMR 根據(jù)水平移動(dòng)距離rijs以及上述是否達(dá)到最大速度的兩種情況推算出第n次行駛時(shí)間。表示為：

第n次AMR 機(jī)械臂在垂直方向上升與下降的時(shí)間T2n。表示為：

假設(shè)AMR 在揀選單個(gè)貨物時(shí)的取貨和卸貨時(shí)間相同，為s，則AMR 完成一批待揀貨物所花費(fèi)的取貨卸貨作業(yè)時(shí)間為：

根據(jù)以上描述，AMR 揀選作業(yè)時(shí)間模型可以表示為：

約束條件為：

其中：式（11）為揀選時(shí)間優(yōu)化指標(biāo)；式（12）表示AMR單趟揀選的貨物重量不能超過(guò)M，否則需要先回起點(diǎn)卸貨后再進(jìn)行下一次揀貨作業(yè)；式（13）表示AMR 的最大貨格數(shù)量，即單趟最多只能容納Q個(gè)SKU；式（14）表示訂單中顯示的貨物都會(huì)被揀選；式（15）和（16）表示SKU 揀選的先后順序，且保證AMR 在揀選某SKU 時(shí)的連續(xù)性；式（17）中表示AMR 在第m車次滿載SKU 或重量達(dá)到上限后回到起點(diǎn)，表示AMR 在m+1 車次空車從起點(diǎn)出發(fā)揀貨，即第m車次滿載最終位置等于m+1車次開始位置。

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

標(biāo)準(zhǔn)的粒子群算法（Particle Swarm Optimization，PSO）屬于群智能算法，利用個(gè)體分享機(jī)制使整個(gè)群體的搜索方向從無(wú)序到有序漸變，最終產(chǎn)生最優(yōu)解，具有操作簡(jiǎn)、收斂速度快等優(yōu)點(diǎn)，但容易提前收斂于局部最優(yōu)，影響解的精度。SAA 具有較強(qiáng)的全局搜索能力，前期因溫度高使得算法對(duì)較差解的接受度較高，從而易于跳出局部最優(yōu)，但該算法具有漸進(jìn)收斂性，當(dāng)搜索空間大時(shí)，SAA 需要更長(zhǎng)的收斂時(shí)間才能得出最優(yōu)解。因此，本文結(jié)合兩種算法來(lái)求解AMR 分批次揀選路徑規(guī)劃問(wèn)題，利用PSO 快速生成一定種群規(guī)模的近似解，然后得到個(gè)體最優(yōu)和群體最優(yōu)，最后通過(guò)SAA 的馬爾科夫鏈和Metropolis 準(zhǔn)則得到最優(yōu)解［22］。

2.1 SAPSMA

由于PSO 收斂速度快，因而在求解過(guò)程中容易提前收斂于局部最優(yōu)，影響最優(yōu)解的精度。為了使PSO 能夠有效跳出局部最優(yōu)，增強(qiáng)全局搜索能力，將其與SAA 相結(jié)合，形成新的SAPSMA。

PSO 的速度和位移更新公式為：

式中：(t)表示粒子i第t次迭代后的速度；xid(t)表示粒子i第t次迭代后的位置；w為慣性權(quán)重取值；c1為個(gè)體因子；c2為社會(huì)因子；r1和r2為兩個(gè)隨機(jī)取值0～1 之間的數(shù)；pid和gi分別表示個(gè)體極值和群體最優(yōu)值。

2.1.1 慣性權(quán)重取值

以往經(jīng)典粒子群算法采用的值大多是通過(guò)實(shí)驗(yàn)或主觀判斷出來(lái)的固定值［23-25］，但是研究發(fā)現(xiàn)動(dòng)態(tài)慣性權(quán)重取值會(huì)影響PSO 的搜索能力：當(dāng)取值較大時(shí)，有助于提高算法的全局搜索能力；取值較小時(shí)，則有助于提高算法的局部搜索能力。因此，為了平衡算法的全局和局部搜索能力，設(shè)計(jì)一種非線性遞減的慣性權(quán)重，選取定義域在［-3，3］之間的雙曲正切函數(shù)值來(lái)控制算法搜索過(guò)程中的慣性權(quán)重取值。在初期階段，慣性權(quán)重取值較大，然后緩慢減小，使得算法前期有充分的時(shí)間搜索全局；在中期階段，慣性權(quán)重取值呈線性遞減，在減弱全局搜索能力的同時(shí)增強(qiáng)局部搜索能力；到后期階段，曲線斜率再次減小，慣性權(quán)重取值慢慢趨近于最小，局部搜索能力達(dá)到最強(qiáng)，進(jìn)而能夠進(jìn)一步確定最優(yōu)解。取值公式如下：

式中：wmin為慣性權(quán)重最小值，一般取0.4；wmax為慣性權(quán)重最大值，一般取0.9；通過(guò)查閱大量文獻(xiàn)，取上述慣性權(quán)重極值能使算法性能達(dá)到最優(yōu)。T 為當(dāng)前迭代次數(shù)，Tmax為算法最大迭代次數(shù)。

2.1.2 引入懲罰函數(shù)

由于模型存在AMR 載重及自身貨格數(shù)雙約束，為了使求解過(guò)程簡(jiǎn)潔化，決定引入懲罰函數(shù)。在處理雙約束問(wèn)題時(shí)，將懲罰函數(shù)添加到揀選總時(shí)間最小化的目標(biāo)函數(shù)中，將雙約束問(wèn)題轉(zhuǎn)變?yōu)闊o(wú)約束問(wèn)題來(lái)求解。其作用機(jī)理為：當(dāng)滿足約束條件時(shí)，求解過(guò)程將不會(huì)受到懲罰；若不滿足約束條件，將會(huì)在求解過(guò)程中加入懲罰函數(shù)，使其適應(yīng)度值增大，從而因不滿足精度要求而被淘汰。

2.2 SAPSMA基本步驟

（1）初始化PSO，設(shè)置種群規(guī)模大小、粒子維度、速度和位置。

（2）設(shè)定初始溫度t以及某一溫度下馬爾科夫鏈長(zhǎng)度，計(jì)算每個(gè)粒子的適應(yīng)度值，并將個(gè)體最優(yōu)存儲(chǔ)在pi中，種群最優(yōu)存儲(chǔ)在pg中。

（3）自適應(yīng)改變w慣性權(quán)重取值。

（4）根據(jù)式（18）、（19）對(duì)粒子速度及位置進(jìn)行更新，并計(jì)算新適應(yīng)度值。

（5）計(jì)算新舊位置的適應(yīng)度值之差△f=fitness(x') -fitness(x)，利用SAA 中的Metropolis 準(zhǔn)則，按式（22）、（23）更新新解：

式中：fitness（x’）為新適應(yīng)度值，fitness（x）為舊適應(yīng)度值，T為模擬退火初始溫度。

若新解適應(yīng)度值優(yōu)于舊解適應(yīng)度值，即fitness（x’）＜fitness（x），則以概率1 接受新解；若新解適應(yīng)度值差于舊解適應(yīng)度值，即fitness（x’）＞fitness（x），且式（23）成立，則粒子同樣接受新解。

（6）更新個(gè)體最優(yōu)值和群體最優(yōu)值。

（7）判斷是否達(dá)到馬爾科夫鏈長(zhǎng)度，否則返回步驟（3）。

（8）退溫操作。

其中λ為退火系數(shù)。

（9）判斷是否達(dá)到終止溫度，若未達(dá)到，則返回步驟（2）。

（10）輸出當(dāng)前最優(yōu)粒子，算法結(jié)束。

總體算法運(yùn)行流程如圖2所示。

Fig.2 Flow of SAPSMA圖2 SAPSMA流程

3 實(shí)例驗(yàn)證

以某揀選中心的智能倉(cāng)庫(kù)為工況背景，該倉(cāng)庫(kù)中某區(qū)型的固定貨架布局方式為12 列、15 排、5 層，共900 個(gè)貨格。其中，貨架的各參數(shù)分別為：?jiǎn)蝹€(gè)貨架寬度L=1.2 m，長(zhǎng)度w=1.2 m，高度h=1.0 m，單條巷道寬度c=1.5 m。揀選AMR 的各參數(shù)：貨格總數(shù)Q=8，最大承載總重量M=200 kg，水平方向最大速度v1=1.5 m/s，加速度a=1 m/s2，垂直方向升降臺(tái)恒定上升下降速度v2=0.3 m/s，單次取貨卸貨時(shí)間為s=3 s。

本次驗(yàn)證所用數(shù)據(jù)均來(lái)自于某揀選中心的訂單清單，其中包含30個(gè)待揀貨物，貨物信息見表1。

Table 1 Cargo information repository bit settings表1 貨物信息存儲(chǔ)庫(kù)位設(shè)置

通過(guò)MATLAB R2022b 對(duì)SAPSMA 進(jìn)行仿真實(shí)驗(yàn)，將其結(jié)果與SAA 和PSO 進(jìn)行對(duì)比。為增強(qiáng)3 種算法的可比性，均使用相同的初始參數(shù)，如下：

（1）SAPSMA。種群規(guī)模80；最大迭代次數(shù)1 500；個(gè)體因子2，社會(huì)因子2；慣性權(quán)重最大值0.9，最小值0.4；初始溫度2 000 ℃；馬爾科夫鏈長(zhǎng)度100；終止溫度0.01；溫度衰減系數(shù)0.99。

（2）PSO。種群規(guī)模80；最大迭代次數(shù)1 500；個(gè)體因子2，社會(huì)因子2；慣性權(quán)重0.75。

（3）SAA。初始溫度2 000 ℃；馬爾科夫鏈長(zhǎng)度100；終止溫度0.01；溫度衰減系數(shù)0.99。

圖3 為采用MATLAB 對(duì)3 種算法各運(yùn)行30 次的平均收斂曲線。其中橫坐標(biāo)為算法運(yùn)行的迭代次數(shù)，縱坐標(biāo)為AMR 揀選總耗時(shí)。由圖3可知：在相同參數(shù)的情況下，PSO在初期收斂較快，但容易陷入局部最優(yōu)，導(dǎo)致搜索范圍不夠，無(wú)法得到最優(yōu)解；SAA 雖然能夠有效跳出局部最優(yōu)位置，但是前期收斂震蕩時(shí)間過(guò)長(zhǎng)。相較于SAA 和PSO，SAPSMA 在PSO 算法的框架中引入SAA 的Metropolis 準(zhǔn)則和溫度衰減系數(shù)，使SAPSMA 可以快速跳出局部最優(yōu)處，從而搜索到更高質(zhì)量的解。

Fig.3 Comparison of convergence curves of the three algorithms圖3 3種算法收斂曲線對(duì)比

表2 為3 種算法獨(dú)立運(yùn)行30 次后的運(yùn)行結(jié)果，可以得出：SAPSMA 的收斂次數(shù)優(yōu)于PSO 和SAA。雖然SAPSMA的運(yùn)行時(shí)間略高于PSO 和SAA，但SAPSMA 解的上下波動(dòng)性范圍更小，更加穩(wěn)定，且SAPSMA 解的平均值更小，得到的解質(zhì)量更高。

Table 2 Experimental results of three algorithms表2 3種算法實(shí)驗(yàn)結(jié)果

表3 為SAPSMA 和SAA 的路徑優(yōu)化結(jié)果，因?yàn)镻SO 算法陷入局部最優(yōu)，無(wú)法得出最優(yōu)解，故只考慮SAPSMA 和SAA 的最優(yōu)解。其中SAPSMA 的揀選作業(yè)順序?yàn)椋?-12-3-18-19-8-30-11-0-23-16-20-5-0-27-13-15-9-14-0-26-22-21-7-17-4-25-2-0-6-10-1-29-24-28-0，將30 個(gè)SKU 分5 車次揀選完成，總耗557s；SAA 的揀選作業(yè)順序?yàn)椋?-2-24-10-6-3-18-0-25-16-21-7-22-20-5-0-19-11-8-13-27-30-28-12-0-23-4-17-26-14-9-15-1-29-0，將30 個(gè)SKU 分5 車次揀選完成，總耗時(shí)596s。通過(guò)與SAPSMA 對(duì)比，SAA 揀選總時(shí)間減少39s，總揀選時(shí)間節(jié)約7.01%。

由此可知，SAPSMA 在AMR 分批次揀選多目標(biāo)分批次SKU 的路徑規(guī)劃中有較好的應(yīng)用效果，該算法在迭代收斂上速度更快，解的精確度更高。

4 結(jié)語(yǔ)

本文針對(duì)多區(qū)型倉(cāng)庫(kù)中AMR 揀選多目標(biāo)分批次的揀選路徑規(guī)劃問(wèn)題，通過(guò)構(gòu)建三維空間坐標(biāo)，建立能夠依次揀選訂單中SKU 的三維路徑規(guī)劃模型，設(shè)計(jì)SAPSMA 對(duì)模型進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明，與其他啟發(fā)式算法相比，SAPSMA 算法在相同參數(shù)下收斂速度更快，能有效避免算法陷入局部最優(yōu)，得到具有更高精度的解。綜上，本文構(gòu)建的AMR 揀選模型及SAPSMA 在智能揀選倉(cāng)庫(kù)中具有較好的擬合效果，能有效提高倉(cāng)庫(kù)整體揀選效率。

然而本文僅研究了多區(qū)型倉(cāng)庫(kù)下某區(qū)型AMR 單指令出庫(kù)為背景的訂單揀選路徑規(guī)劃，即AMR 從起點(diǎn)出發(fā)，沿規(guī)劃的路線移動(dòng)到待揀貨物所在行和列，分批次裝載貨物后返回起點(diǎn)。未來(lái)將對(duì)多指令作業(yè)及多AMR 在同一區(qū)型下共同作業(yè)的揀選路徑規(guī)劃問(wèn)題進(jìn)行深入研究。