丁榮寬，董寶力

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

0 引言

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

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

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

1 問題描述與模型建立

1.1 問題描述

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

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

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

1.2 基本假設(shè)

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

1.3 模型建立

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

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

O：訂單集合

S：貨架集合

P：SKU 商品種類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

約束條件為：

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

2 算法設(shè)計

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

2.1 SAPSMA

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

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

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

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

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

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

2.1.2 引入懲罰函數(shù)

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

2.2 SAPSMA基本步驟

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

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

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

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

（5）計算新舊位置的適應(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）更新個體最優(yōu)值和群體最優(yōu)值。

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

（8）退溫操作。

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

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

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

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

Fig.2 Flow of SAPSMA圖2 SAPSMA流程

3 實例驗證

以某揀選中心的智能倉庫為工況背景，該倉庫中某區(qū)型的固定貨架布局方式為12 列、15 排、5 層，共900 個貨格。其中，貨架的各參數(shù)分別為：單個貨架寬度L=1.2 m，長度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，垂直方向升降臺恒定上升下降速度v2=0.3 m/s，單次取貨卸貨時間為s=3 s。

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

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

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

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

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

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

圖3 為采用MATLAB 對3 種算法各運(yùn)行30 次的平均收斂曲線。其中橫坐標(biāo)為算法運(yùn)行的迭代次數(shù)，縱坐標(biāo)為AMR 揀選總耗時。由圖3可知：在相同參數(shù)的情況下，PSO在初期收斂較快，但容易陷入局部最優(yōu)，導(dǎo)致搜索范圍不夠，無法得到最優(yōu)解；SAA 雖然能夠有效跳出局部最優(yōu)位置，但是前期收斂震蕩時間過長。相較于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種算法收斂曲線對比

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

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

表3 為SAPSMA 和SAA 的路徑優(yōu)化結(jié)果，因為PSO 算法陷入局部最優(yōu)，無法得出最優(yōu)解，故只考慮SAPSMA 和SAA 的最優(yōu)解。其中SAPSMA 的揀選作業(yè)順序為：0-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 個SKU 分5 車次揀選完成，總耗557s；SAA 的揀選作業(yè)順序為：0-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 個SKU 分5 車次揀選完成，總耗時596s。通過與SAPSMA 對比，SAA 揀選總時間減少39s，總揀選時間節(jié)約7.01%。

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

4 結(jié)語

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

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