自主移動機器人三維揀選路徑規劃研究

丁榮寬，董寶力

（浙江理工大學 機械工程學院，浙江 杭州 310018）

0 引言

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

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

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

1 問題描述與模型建立

1.1 問題描述

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

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

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

1.2 基本假設

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

1.3 模型建立

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

首先對優化模型中出現的符號進行說明：

O：訂單集合

S：貨架集合

P：SKU 商品種類

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

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

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

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

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

式中：xi，xj均表示揀選點所在的列位置。

（2）當前貨物揀選點i到待揀貨物揀選點j之間的水平距離。此時分為兩種情況：

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

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

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

②貨物揀選點i和j都在同一巷道內。

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

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

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

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

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

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

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

根據以上描述，AMR 揀選作業時間模型可以表示為：

約束條件為：

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

2 算法設計

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

2.1 SAPSMA

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

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

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

2.1.1 慣性權重取值

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

式中：wmin為慣性權重最小值，一般取0.4；wmax為慣性權重最大值，一般取0.9；通過查閱大量文獻，取上述慣性權重極值能使算法性能達到最優。T 為當前迭代次數，Tmax為算法最大迭代次數。

2.1.2 引入懲罰函數

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

2.2 SAPSMA基本步驟

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

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

（3）自適應改變w慣性權重取值。

（4）根據式（18）、（19）對粒子速度及位置進行更新，并計算新適應度值。

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

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

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

（6）更新個體最優值和群體最優值。

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

（8）退溫操作。

其中λ為退火系數。

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

（10）輸出當前最優粒子，算法結束。

總體算法運行流程如圖2所示。

Fig.2 Flow of SAPSMA圖2 SAPSMA流程

3 實例驗證

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

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

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

通過MATLAB R2022b 對SAPSMA 進行仿真實驗，將其結果與SAA 和PSO 進行對比。為增強3 種算法的可比性，均使用相同的初始參數，如下：

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

（2）PSO。種群規模80；最大迭代次數1 500；個體因子2，社會因子2；慣性權重0.75。

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

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

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

表2 為3 種算法獨立運行30 次后的運行結果，可以得出：SAPSMA 的收斂次數優于PSO 和SAA。雖然SAPSMA的運行時間略高于PSO 和SAA，但SAPSMA 解的上下波動性范圍更小，更加穩定，且SAPSMA 解的平均值更小，得到的解質量更高。

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

表3 為SAPSMA 和SAA 的路徑優化結果，因為PSO 算法陷入局部最優，無法得出最優解，故只考慮SAPSMA 和SAA 的最優解。其中SAPSMA 的揀選作業順序為：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 的揀選作業順序為：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，總揀選時間節約7.01%。

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

4 結語

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

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