貨箱到人模式下的AMR 揀選路徑規(guī)劃

俞明哲，董寶力，張書亭 YU Mingzhe, DONG Baoli, ZHANG Shuting

（浙江理工大學(xué) 機械與自動控制學(xué)院，浙江 杭州 310018）

0 引 言

隨著市場經(jīng)濟的迅速發(fā)展，客戶需求逐漸從大批量少批次向小批量個性化方向轉(zhuǎn)變，客戶對訂單的配送時限和服務(wù)質(zhì)量要求越來越高。傳統(tǒng)人到貨揀選方式逐漸向更有效率的貨到人揀選方式轉(zhuǎn)變。貨到人揀選方式避免了傳統(tǒng)揀選方式揀選時間長、效率低、容易出錯、需要大量人力等缺點，能更好適應(yīng)新市場環(huán)境對企業(yè)訂單的需求。貨箱到人揀選系統(tǒng)作為一種新興揀選方式，屬于貨到人揀選方式的一種。相比其他貨到人揀選方式，其具有倉庫改造成本低，揀選效率高，目標更精準，投入便能迅速應(yīng)用等優(yōu)點。貨箱到人揀選方式對揀選機器人的功能要求更高，傳統(tǒng)揀選用的自動導(dǎo)向車（Automated Guided Vehicle，AGV） 并不能滿足要求，于是更為智能和靈活的自主移動機器人（Autonomous Mobile Robot，AMR） 就成為該揀選系統(tǒng)最合適的揀選執(zhí)行者。

貨箱到人模式下AMR 的揀選過程與人到貨模式下人的揀選過程較為相似，目前人到貨模式下揀選系統(tǒng)的優(yōu)化研究主要集中在揀貨策略和揀選路徑優(yōu)化上。揀貨策略主要有訂單別揀貨策略和批量揀貨策略。隨著訂單數(shù)量的增長，訂單別揀選的效率逐漸滿足不了系統(tǒng)需求，學(xué)術(shù)界開始越來越重視批量揀貨策略的研究。批量揀貨時的首要問題是訂單分批，時窗分批是一種適用于密集訂單的分批策略。學(xué)者們在此基礎(chǔ)上設(shè)計了動態(tài)時窗分批，提升了揀貨系統(tǒng)的均衡性。針對貨到人揀選模式，現(xiàn)有研究主要構(gòu)建以設(shè)備搬運次數(shù)最小化為目標的數(shù)學(xué)模型，通過優(yōu)化訂單的分批方法來實現(xiàn)目標。何其超等建立并求解0～1整數(shù)線性規(guī)劃模型，使AGV 小車搬運次數(shù)顯著減少。楊鴻雪和徐冉分別通過聚類算法和啟發(fā)式算法對訂單進行分批，提升了貨到人揀選系統(tǒng)的運行效率。

揀選路徑優(yōu)化的研究主要構(gòu)建以揀選時間或路程最小化為目標的數(shù)學(xué)模型，并用算法求得最優(yōu)解?，F(xiàn)有研究主要采用啟發(fā)式算法對問題進行求解，找到最優(yōu)的揀選路徑。張娟等使用禁忌搜索算法對單區(qū)型物流配送中心揀選路徑進行優(yōu)化，證明其總體優(yōu)化效果比只使用聚類算法對訂單分批更好。在貨到人揀選模式下，張彩霞和寧新杰分別通過遺傳算法和改進的PRM算法優(yōu)化了AGV 的揀選路徑。閆妍等使用A*算法對菜鳥智能倉庫的搬運機器人路徑規(guī)劃，解決了機器人碰撞沖突和死鎖等問題。通過蟻群算法等啟發(fā)式算法，同樣可以對堆垛機等自動化分揀系統(tǒng)的揀選路徑進行優(yōu)化，提高系統(tǒng)效率。相較于人到貨模式揀選系統(tǒng)，貨箱到人模式下AMR 揀選系統(tǒng)具有揀選路徑更為復(fù)雜等特點，揀選過程中總作業(yè)效率受揀選路徑規(guī)劃影響更大，因此在對該系統(tǒng)的優(yōu)化研究中揀選路徑的優(yōu)化更為重要。以上研究尚未解決貨箱到人模式下AMR 的三維揀選路徑問題，同時也未能考慮到揀選貨箱數(shù)受到揀選設(shè)備存儲容量約束下的作業(yè)情況。

本文根據(jù)貨箱到人模式下AMR 揀選系統(tǒng)的具體特點，構(gòu)建以總作業(yè)時間最小化為目標的AMR 揀選作業(yè)優(yōu)化模型，并設(shè)計改進的粒子群算法進行求解，通過實例對模型和算法進行驗證。

1 問題描述與模型建立

1.1 問題描述

本文研究某倉庫分揀系統(tǒng)基于貨箱到人揀選模式下AMR 的揀選路徑規(guī)劃問題。倉庫主要由貨架和AMR 組成，AMR 揀選使用整箱揀貨方案。倉庫內(nèi)進行分區(qū)作業(yè)，AMR 與倉庫原理圖如圖1 所示。O 點為分揀臺位置，貨架縱向排列。設(shè)貨架上單元貨格的深度為l，寬度為w，層高為h，貨架列數(shù)為s, 巷道寬度為f。

圖1 AMR 與倉庫原理圖

系統(tǒng)中負責揀選作業(yè)的AMR 單一執(zhí)行出庫或入庫工作，本文僅研究出庫工作時的AMR 揀選作業(yè)，其具體樣式如圖2 所示，AMR 從揀選臺出發(fā)在倉庫巷道中移動，按照任務(wù)清單對貨箱進行揀選。假定某一時間段內(nèi)的任務(wù)清單上有n 個揀選任務(wù)，每個任務(wù)有且只有一個對應(yīng)貨箱，以揀選臺位置O 為坐標原點，橫向為X 軸，縱向為Y 軸建立坐標系，待揀貨箱i 的信息表示為(x, y,z)，x為貨箱i 橫坐標所在位置，y為貨箱i 縱坐標所在位置，z為貨箱i所在層。如： (6,2,3 )表示該貨箱存儲在第6 排貨架、第2 列的第3 層貨格。

圖2 AMR 立體圖

考慮到實際問題的復(fù)雜性和不確定性，在對AMR 揀選作業(yè)路徑規(guī)劃問題建立模型之前，需要對該問題進行必要的簡化并設(shè)定條件參數(shù)，本文對貨架和AMR 做以下假設(shè)和參數(shù)設(shè)定：（1） AMR 的最大存儲貨箱數(shù)量為M；（2） AMR 在進行揀選作業(yè)時由下至上將被揀貨箱放入自身的存儲貨格中；（3） AMR 在停止水平移動的情況下才可以升降貨叉；（4） AMR 需要經(jīng)過加速、勻速和減速才能完成一次水平運動，設(shè)其運動變化的加減速度為a, 最大速度為v；（5） 揀選作業(yè)中單個貨箱的存取時間固定，設(shè)為b；（6） 貨叉升降時的速度固定，設(shè)為v；（7） 不考慮缺貨和插單等意外情況。

1.2 模型建立

AMR 執(zhí)行揀選作業(yè)工作由移動、升降和存取3 個動作組成，設(shè)完成一次揀選任務(wù)需要的時間為T。

其中：T為AMR 水平移動所耗時間；T為AMR 垂直移動所耗時間；T為AMR 存取貨箱的時間。

圖3 AMR 行駛速度未達到v1 時的移動距離

圖4 AMR 行駛速度達到v1 時的移動距離

設(shè)T為各階段AMR 水平運動時間，其計算公式如式（3） 所示：其中：式（10） 至式（12） 保證貨物的先后揀選關(guān)系，且每個車次貨物會優(yōu)先被揀選至AMR 自身的最下方空閑貨格；式（13） 保證AMR 每次揀選車次的起始位置和終止位置都在分揀臺O 處。

2 算法設(shè)計

粒子群算法（Particle Swarm Optimization，PSO） 是解決路徑規(guī)劃問題常用的算法之一。它的實現(xiàn)簡單高效，搜索速度快。但在求解過程中，各粒子易受其自身的最佳過去位置p和整個群或近鄰最佳過去位置g的影響，陷入局部最優(yōu)解?；谏鲜鋈秉c，本文提出一種改進的PSO 進行模型求解。

2.1 改進的粒子群優(yōu)化算法

本文在標準PSO 的基礎(chǔ)上，設(shè)置二階震蕩環(huán)節(jié)和隨機慣性權(quán)重，通過前期全局搜索和后期局部搜索的方式來尋找最優(yōu)解，標準的PSO 算法公式為：

2.1.3 隨機權(quán)重

慣性權(quán)重ω 的取值對算法的搜索能力有著重要的影響作用，較大的ω 有利于跳出局部最小點，提高算法的全局搜索能力；而較小的ω 有利于提高當前搜索區(qū)域的搜索精度，增強算法的局部搜索能力。Eberhart 等人提出了線性遞減慣性權(quán)重，更好地平衡算法的全局搜索能力和局部搜索能力。但這種方法需要反復(fù)實驗確定參數(shù)最優(yōu)值，且易陷入局部最優(yōu)解。本文設(shè)置一種隨機分布慣性權(quán)重，當在算法前期找到最優(yōu)值，則易產(chǎn)生較小的ω 值，加快收斂速度；當在算法前期找不到最優(yōu)值，則易產(chǎn)生較大的ω 值，擴大搜索范圍。其計算公式如下：

Step4：根據(jù)式（18） 更新慣性權(quán)重ω。

Step5：對于每個粒子，將其適應(yīng)值與其經(jīng)歷過的最好位置作比較，如果較好，則將其作為當前的最好位置p。

Step6：比較當前所有p和g的值，更新g。

Step7： 若達到最大迭代次數(shù)，則結(jié)束搜索并輸出最優(yōu)個體作為結(jié)果。否則返回Step2 繼續(xù)搜索。

3 實例驗證

本文以某配送中心AMR 庫中的一個分區(qū)為例，對該AMR 庫分區(qū)一定時間內(nèi)的揀選訂單數(shù)據(jù)進行仿真實驗。已知該AMR庫分區(qū)共有10 排貨架，作業(yè)AMR 數(shù)量為1 臺。貨架有6 層，每排每層有15 個貨位。貨位尺寸為：深度l=0.6m，寬度w=0.6m，高度h=0.42m；巷道寬度f=1.2 米；AMR 的貨位M=6，行駛速度v=2.5m/s，加速度a=1m/s，貨叉垂直升降速度v=0.3m/s。

圖5 改進的PSO 流程圖

實驗所用數(shù)據(jù)選取該配送中心系統(tǒng)中某時間段內(nèi)的揀選作業(yè)任務(wù)單，其中含有30 個不同的待撿貨物，具體信息如表1 所示。

表1 揀選任務(wù)清單

利用改進的PSO 對數(shù)據(jù)進行仿真模擬，具體參數(shù)為：設(shè)PSO 的種群規(guī)模為100，學(xué)習(xí)因子為c=c=2.0，慣性權(quán)重為w=0.5，最大迭代次數(shù)為1 000，前500 次迭代漸進收斂，后500 次迭代振蕩收斂。并利用標準PSO 對數(shù)據(jù)進行仿真模擬，具體參數(shù)與改進的PSO 相同，但不設(shè)置二階振蕩環(huán)節(jié)和隨機慣性權(quán)重。

圖6 反映了在兩種算法的求解過程中最優(yōu)值隨迭代次數(shù)的演化，與標準PSO 相比，改進的PSO 前500 次迭代最小化目標函數(shù)值快速下降，后500 次迭代最小化目標函數(shù)值跳出局部最優(yōu)，進一步降低。最終優(yōu)化結(jié)果如表2 所示。

表2 基于兩種PSO 的揀選路徑優(yōu)化結(jié)果對比

圖6 改進的PSO 迭代曲線

AMR 完成任務(wù)清單上的揀貨任務(wù)共需要5 個車次，總的最優(yōu)作業(yè)順序為(23,26,4,7,1,19 )→(29,21,5,2,15,16 )→(8,24,17,28,30,11)→(22,10,6,9,14,13 )→(3,18,25,20,27,12 )，揀選作業(yè)共耗時1 378s。若按照標準PSO 算法進行求解，則得到的揀選作業(yè)優(yōu)化結(jié)果為 (28,18,21,2,3,24 )→ (6,17,9,10,14,8 )→ (30,25,5,15,12,23 )→ (26,27,20,11,29,16 )→ (7,4,1,19,13,22 )，其揀選作業(yè)共耗時1 633s。比較可發(fā)現(xiàn)利用改進的粒子群算法能夠獲得更優(yōu)的結(jié)果，可以有效降低貨箱到人模式下AMR 揀選作業(yè)的時間。

4 結(jié) 論

本文構(gòu)建了以總作業(yè)時間最小化為目標的AMR 揀選作業(yè)優(yōu)化模型，并設(shè)計一種改進的PSO 用于求解最優(yōu)AMR 揀選路徑，實例實證表明該方法是可行的。通過算法前期漸進收斂和后期振蕩收斂，提高了逼近最小化目標的速度并實現(xiàn)跳出局部最優(yōu)值，保證了算法精度的同時提高了迭代效率。改進的PSO 優(yōu)化后揀選時間比標準PSO 節(jié)約了15.6%，有效地降低了貨箱到人模式下AMR 揀選作業(yè)耗時。

在貨箱到人揀選模式下除了貨箱的出庫外，還包含回庫和AMR 調(diào)度等目標或條件，在此基礎(chǔ)上，多AMR 動態(tài)分區(qū)情況下的貨箱到人揀選路徑規(guī)劃研究是今后工作的方向。