基于動態(tài)訂單約束的倉庫揀貨作業(yè)雙層優(yōu)化算法

王 磊，徐躍明，安裕強，葉 曉，潘 楠

（1.紅云紅河集團有限責(zé)任公司 物流中心，云南 昆明 650202；2.昆明理工大學(xué) 民航與航空學(xué)院，云南 昆明 650500）

0 引言

隨著物聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，物流行業(yè)步入智能化時代。倉儲作業(yè)作為物流行業(yè)的重要環(huán)節(jié)，其作業(yè)效率直接決定了物流行業(yè)的運轉(zhuǎn)速度。倉儲作業(yè)主要由訂單分配及揀貨兩大部分構(gòu)成，因此如何實現(xiàn)高效合理的訂單分配和揀貨路徑優(yōu)化成為行業(yè)關(guān)注的重點。

在倉儲作業(yè)問題中，已有不少學(xué)者對訂單分配和揀貨路徑優(yōu)化進行了協(xié)同研究，其中孫軍艷，等建立了基于嵌套遺傳算法的聯(lián)合優(yōu)化模型，通過外層不斷優(yōu)化訂單分批結(jié)果，內(nèi)層不斷優(yōu)化揀貨路徑，有效地提高了揀貨效率，為解決倉儲作業(yè)中的難題提供了有效依據(jù)。Cheng Chen-Yang ，等針對聯(lián)合批次揀選和揀選路線問題，設(shè)計了混合算法對其進行求解。此外，有部分學(xué)者研究了倉庫布局對揀貨時間的影響，其中劉建勝，等研究了Flying-V型倉庫布局下的揀貨問題，并針對倉庫布局特點設(shè)計了訂單分配及路徑優(yōu)化模型，進一步采用蟻群算法對模型進行了求解，仿真對比結(jié)果表明該模型有較強的實用性。文獻[8]則針對雙區(qū)型倉庫的布局特點，建立了以最短揀貨時間為目標(biāo)的優(yōu)化模型，并設(shè)計了動態(tài)貨物調(diào)整和人工揀貨協(xié)同作業(yè)的動態(tài)揀貨策略，采用混合遺傳算法對模型進行了求解，仿真實驗結(jié)果表明該策略在大規(guī)模訂單時能夠顯著地提高揀貨效率，但并沒有考慮揀貨輔助工具物理限制對揀貨作業(yè)的影響。孫慧，等在揀貨優(yōu)化模型中引入了揀貨車容量約束等實際約束，并通過仿真結(jié)果驗證了所設(shè)計的模型有較強的實際應(yīng)用價值。上述研究均取得了一定的成果，但沒有涉及多服務(wù)臺等倉庫模式。為此，本文基于某企業(yè)的倉庫布局，構(gòu)建了涉及多服務(wù)臺的訂單分配及揀貨路線優(yōu)化模型，嘗試解決相應(yīng)問題。

基于上述分析，本文針對某物流企業(yè)的倉庫布局特點，綜合考慮倉庫物理限制、揀貨人員及輔助工具能力約束等實際約束，構(gòu)建了涉及多貨物種類、多訂單、多服務(wù)臺的包含訂單分配和揀貨路徑優(yōu)化在內(nèi)的雙層優(yōu)化模型，并通過比較WOA（Whale Optimization Algorithm）、MVO（Multi- Verse Optimizer）和CSV（Crow Search Algorithm）以及改進CSV 的優(yōu)化結(jié)果，選擇改進群體智能算法進行訂單分批優(yōu)化和揀選作業(yè)路徑優(yōu)化。仿真實驗結(jié)果表明，所設(shè)計的算法能夠有效地求解人員揀貨問題，相較于傳統(tǒng)的遺傳算法，能夠進一步提高揀貨效率，為加快傳統(tǒng)物流企業(yè)智能化提供有效借鑒。

1 問題描述

某集團倉庫作業(yè)主要包含訂單分配和人員揀貨路徑規(guī)劃兩部分，其中訂單分配除訂單分批外還包含服務(wù)臺分配，而人員揀貨作業(yè)采用“人到貨”的揀貨模式，即貨物位置固定不動，由揀貨人員結(jié)合輔助揀貨作業(yè)工具完成貨物的揀選。訂單分配的結(jié)果直接決定了揀貨路徑的生成，因此，本文通過構(gòu)建雙層優(yōu)化模型對兩部分進行綜合優(yōu)化，針對上述對問題的分析及企業(yè)的倉庫管理策略，得到了以下假設(shè)：

（1）同一儲位貨物具有同質(zhì)性；

（2）儲位中心位置為該儲位的坐標(biāo)；

（3）員工的行走速度相同；

（4）每個儲位的尺寸相同；

（5）每個巷道入口處左側(cè)都有服務(wù)臺；

（6）倉庫處于動態(tài)補貨的過程中，即貨架的貨物剩余量無限；

（7）升降機等輔助工具數(shù)量充足，即不考慮其行駛時間；

（8）貨物在最大容量時未超過輔助工具的載重限制，因此忽略揀貨容積限制。

表1 符號說明

2 模型建立

2.1 倉庫布局介紹

倉庫布局如圖1所示，每個貨位的位置由巷道數(shù)、所處巷道貨位數(shù)、巷道左右側(cè)及貨位深度所決定(r,s,p,l,d)，其中，r為貨位所處巷道數(shù)；s為貨位所處巷道距入口序號；p為貨位位于巷道左或右側(cè)；l為貨位層數(shù)；d為貨位所處深度。

圖1 倉庫布局

在倉庫矩形布局中，得到任意兩個貨位之間的距離，表示如下：

從任意服務(wù)臺到任意一個貨位的距離為：

2.2 雙層優(yōu)化模型構(gòu)建

某集團的倉庫揀貨作業(yè)基于服務(wù)臺開展，其整體作業(yè)效率的高低取決于服務(wù)臺的合理利用與人員的任務(wù)安排，由于揀貨訂單采用批次處理，因此訂單的分批及分配結(jié)果直接決定了服務(wù)臺內(nèi)員工揀貨任務(wù)安排的合理性。綜上，考慮到揀貨訂單存在同質(zhì)性，因此基于相似度進行訂單分批，在此基礎(chǔ)上圍繞倉庫服務(wù)臺作業(yè)公平性進行訂單分配，并綜合考慮倉庫物理限制，最終建立以經(jīng)過最少揀貨通道、最高服務(wù)臺公平性為上層優(yōu)化目標(biāo)的訂單批次優(yōu)化模型。

式（11）表示每個批次由一個服務(wù)臺負責(zé)；式（12）表示每個訂單只能分配給一個批次；式（13）表示貨架能夠滿足該批次訂單的品項需求；式（14）表示不超過倉庫最大供應(yīng)能力。

基于上層訂單分批與服務(wù)臺分配結(jié)果，以及每個服務(wù)臺的作業(yè)情況，安排空閑員工進行揀貨作業(yè)，綜合考慮揀貨作業(yè)人員的作業(yè)素質(zhì)，揀貨輔助工具的物理限制，以及貨架的實際情況等真實約束，建立了以最短總揀貨時間為下層優(yōu)化目標(biāo)的員工揀貨作業(yè)模型。揀貨總作業(yè)時間由員工行走時間和作業(yè)輔助工具升降機工作時間以及貨物清點結(jié)算時間三部分構(gòu)成，揀貨作業(yè)人員作業(yè)過程中行走時間計算公式見式（15），揀貨作業(yè)過程中升降機工作時間計算公式見式（16）。

式（21）表示揀貨作業(yè)不超過最大人數(shù)限制；式（22）表示每個人負責(zé)一個批次；式（23）和式（24）表示在一個批次中貨架只能被揀貨一次；式（25）表示訂單容量不超過揀貨工具限制；式（26）表示單個訂單的工作時間不超過揀貨人員的最大持續(xù)作業(yè)時間；式（27）表示揀貨人員完成揀貨后返回出發(fā)時的服務(wù)臺。

3 算法設(shè)計

3.1 設(shè)計思路

訂單分批和揀貨路徑優(yōu)化是揀貨作業(yè)優(yōu)化的重要組成部分。訂單分批以所需貨架總數(shù)最少為目標(biāo)函數(shù)，每批次訂單中貨物的質(zhì)量和體積不可超過揀貨車的最大容積和最大載荷量。訂單分批結(jié)束后，根據(jù)訂單分批結(jié)果規(guī)劃揀貨路徑，得到每批次的最優(yōu)揀貨路徑。在實際生產(chǎn)活動中，大多數(shù)的倉庫揀貨人員大于1，因此得到各批次的最優(yōu)揀貨路徑后，需要檢查揀貨過程中是否存在沖突點，總體框架如圖2所示。

圖2 算法設(shè)計思路

3.2 優(yōu)化過程

3.2.1 訂單分批。為了更好地使用智能優(yōu)化算法求解上述模型，用矩陣索引號表示訂單編號，矩陣中的數(shù)值表示分批批次。如，假設(shè)對10張訂單進行分批，用“[1,1,2,3,4,4,2,3,5,2]”表示分批結(jié)果，其中第1、2張訂單為第1批次，第3、7,、10張訂單為第2批次，第4、8張訂單為第3批次，第5、6張訂單為第4批次，第9張訂單為第5批次。確定揀貨設(shè)備容量和體積限制，以及烏鴉數(shù)量、最大迭代次數(shù)（maxGen1）、矩陣維度（dim）、感知概率（AP）和飛行距離，具體優(yōu)化過程見表2。

表2 訂單分批問題偽代碼

3.2.2 揀貨路徑優(yōu)化。在揀貨路徑優(yōu)化問題方面，采用矩陣索引號表示揀貨員先后經(jīng)過對應(yīng)揀貨位的順序，矩陣中的數(shù)字表示某批次需要經(jīng)過的揀貨位信息。如“[1,2,3,8,23,45,32,34,12]”，表示依次經(jīng)過揀貨位1,2,3,8,23,45,32,34,12。確定自變量編碼后，初始化鯨魚種群數(shù)（SearchAgent）、變量維度（dim）、最大迭代次數(shù)（maxGen2）、系數(shù)向量A和c等，同時變量維度等于需要經(jīng)過的揀貨位數(shù)量。編碼過程見表3。

表3 揀選路徑優(yōu)化問題偽代碼

3.2.3 動態(tài)路徑調(diào)整。當(dāng)揀貨人員數(shù)大于1時，由于揀貨通道的寬度限制，極有可能發(fā)生堵塞現(xiàn)象，將文獻[11]與企業(yè)的實際情況相結(jié)合，可將堵塞種類分為以下三種，如圖3所示。

（1）一個揀貨員需要經(jīng)過該揀貨通道前往目的揀貨位進行揀貨，另一揀貨員在該揀貨通道有揀貨任務(wù)，如圖3中的a所示。

（2）兩揀貨員在該揀貨通道均有任務(wù)時，分為三種情況。兩揀貨員的目標(biāo)揀貨位位于揀貨通道兩側(cè)，且都需要經(jīng)過對方的目標(biāo)揀貨位，如圖3中的b(1)所示。兩揀貨員的目標(biāo)揀貨位位于同一通道兩側(cè)的相鄰位置，如圖3中的b(2)所示；兩揀貨員到同一通道揀選貨物，如圖3中的b(3)所示。

（3）兩揀貨人員在該揀貨通道均無揀貨任務(wù)，但需要經(jīng)過同一揀貨通道到達目的揀貨位，如圖3中的c所示。

圖3 路徑?jīng)_突類型

當(dāng)遇到以上列舉的情況時，為避免造成擁堵，需要進行路徑調(diào)整，本文基于動態(tài)規(guī)劃思想，以揀貨人員到達相鄰兩貨位的時間為單位，檢查是否存在沖突點。根據(jù)文獻[12]，當(dāng)員工揀選速度為1.39m/s 時，物流揀選勞動者平均每工作48min 后，需要休息6min，由此每當(dāng)有揀選員完成任務(wù)時，需要檢查員工的累計工作時間是否達到48min，若達到48min 則需安排該員工休息，具體過程如圖4所示。

圖4 路徑調(diào)整流程圖

4 實例分析

4.1 倉庫模型

倉庫布局如圖5所示，該揀貨區(qū)由5條揀貨通道、4 條巷道、160 個揀貨位組成。為每個揀貨位進行編號，圖中D表示揀貨通道寬度，D表示揀貨位寬度，D表示揀貨位長度，D表示巷道寬度。出入口位于揀貨位1、40、41、80、81、120、121附近。

圖5 揀貨區(qū)平面布局圖

4.2 訂單分批

對隨機產(chǎn)生的10張訂單，分別采取鯨魚優(yōu)化算法（WOA）、烏鴉搜索算法（CSV）、多元宇宙算法（MVO）以及改進烏鴉搜索算法對模型進行求解，對比結(jié)果如圖6所示。

圖6 收斂迭代曲線圖

由圖6可知，MVO收斂最快，改進算法收斂速度最慢，但是優(yōu)化效果最優(yōu)，同時由表4可知，盡管WOA和MVO 的優(yōu)化效果較好，但是二者在進行仿真時CPU響應(yīng)時間遠長于改進算法，當(dāng)訂單規(guī)模較大時，無法及時滿足生產(chǎn)要求。

表4 CPU響應(yīng)時間

4.3 揀貨路徑優(yōu)化

隨機生成10 張訂單，其中每張訂單中都包含10個貨物品項（即10個不同的揀貨位），分別采用遺傳算法（GA）、鯨魚優(yōu)化算法（WOA）、烏鴉搜索算法（CSV）和多元宇宙算法（MVO）計算10 張訂單的揀選距離，對比結(jié)果如圖7所示。

圖7 收斂迭代曲線圖

以第一張訂單為例研究各個算法的收斂性，收斂結(jié)果如圖7所示，由圖7可知烏鴉搜索算法收斂性最好，遺傳算法的優(yōu)化結(jié)果最優(yōu)。圖8為在使用各個算法對10 張訂單進行路徑優(yōu)化時，計算機CPU 響應(yīng)時間。由圖8可知，遺傳算法的計算時間最長，鯨魚優(yōu)化算法（WOA）、烏鴉搜索算法（CSV）和多元宇宙算法（MVO）的計算時間相近，且遠少于GA。盡管利用GA可得到最優(yōu)結(jié)果，但是CPU 響應(yīng)時間遠多于其他算法，無法滿足實際生產(chǎn)要求，因此選擇優(yōu)化結(jié)果次優(yōu)的WOA。

圖8 CPU響應(yīng)時間

4.4 路徑調(diào)整

隨機產(chǎn)生20張訂單，共有4名揀選人員。20張訂單進行分批后，對分批結(jié)果進行路徑規(guī)劃，最終各批次優(yōu)化后的揀選距離及揀選時間見表5。

對表5中的優(yōu)化路徑進行預(yù)研究，將揀選任務(wù)分配給4名揀選人員，以經(jīng)過一個揀貨位的時間為單位，檢查揀貨過程中是否存在揀貨沖突，若存在沖突點，則按照優(yōu)先級調(diào)整路徑，調(diào)整結(jié)果見表6。

表5 路徑優(yōu)化結(jié)果

表6 路徑調(diào)整結(jié)果

由表5和表6可知，單人完成揀選貨物所用總時間為18.29min，多人揀貨時間為24.57min，完成揀選任務(wù)需要6.69min。盡管單獨完成部分批次訂單揀選時間相較于調(diào)整前較長，但多人揀貨完成任務(wù)的總揀選時間明顯更短，效率更高。同時多人揀貨時基于人因工程考慮了每個人的最佳工作時間，并且達到一定的工作時間后，為工作人員設(shè)定合理的休息時間。

5 結(jié)語

本文針對某物流企業(yè)的作業(yè)要求，對訂單分配和揀貨路徑問題展開研究，構(gòu)建了以最少總貨架數(shù)、最大服務(wù)臺公平性為上層優(yōu)化目標(biāo)，以最短總揀貨時間為下層優(yōu)化目標(biāo)的雙層優(yōu)化模型，并綜合考慮了倉庫物理布局、人員及輔助工具能力約束等實際作業(yè)約束，相較于傳統(tǒng)的模型，本文所構(gòu)建的模型有更強的實用性，并通過比較MVO、WOA、CSV和基于WOA氣泡網(wǎng)圍捕機制改進的烏鴉搜索算法在解決訂單分批時的優(yōu)化效果，最終選擇改進算法求解上層優(yōu)化模型，選擇WOA求解下層優(yōu)化模型。同時針對揀貨過程中可能出現(xiàn)的路徑?jīng)_突，提出相應(yīng)的調(diào)整策略，避免員工在揀貨過程中出現(xiàn)阻塞，影響通行。仿真實驗結(jié)果表明，在訂單分批問題方面，本文所設(shè)計的算法相較于WOV、MVO和CSV等算法，在收斂速度和計算時間方面都有較為理想的效果，因此更能有效地求解物流企業(yè)的倉儲作業(yè)問題，為推動行業(yè)智能化發(fā)展提供有效借鑒。