具有勞動異質性的訂單分批優化研究

徐兆峰，姜雪松，李春偉，王 婧

（東北林業大學機電工程學院，哈爾濱 150040）

0 引言

近年來，越來越多的實體超市，如永輝超市、盒馬生鮮、物美等，開始將傳統的實體銷售渠道與數字銷售渠道整合，這也被稱為O2O超市（online to offline）。O2O超市是利用現有的大型實體超市作為倉儲配送中心，為客戶提供準時、便捷的送貨上門服務。揀選商品作為倉儲配送中心出庫作業的終點、超市配送的起點，其作業效率是超市提高配送效率和顧客滿意度的關鍵［1］。在揀選作業中，通常會遇到大量相似度高的商品未能有效合并，實際揀選作業中大規模訂單未能合理安排，揀選員工實際效率不高的問題。對于近幾年文獻提出的訂單分批的解決方案，發現大多數相關研究都假設在配送中心的揀選員工都有著相同的揀選能力。對于超市倉儲配送中心，專業的揀選員工將創造更多利潤［2］。但是這種行業往往有著更多兼職，即臨時的工組人員，這種具有勞動異質性員工的出現使工作平衡就變得尤為重要，因此對倉儲配送中心的訂單分批、揀選員工之間平衡的研究具有重要的現實意義［3］。

對于商品揀選員工來說，揀選商品是一種特殊的旅行商問題，其中揀選員工從入口到出口形成一個閉環揀選路徑，并且目標為行走距離最短。Difrancesco等［4］發現，對于員工工作平衡問題的關注顯得更加突出。Koch等［5］發現忽略勞動力異質性可能會影響整體生產效率。朱友瓊等［6］根據訂單相似度建立訂單分批模型。在完全確定揀選系統中，旅行商也可以表現出混沌行為［7］。陳彥博等［8］在S型策略的基礎上，提出一種定價分支算法對問題進行求解，保證在既定規則下的最優揀貨路徑。還有很多學者從員工揀選平衡［9］、員工學習能力［10］、員工揀選方式等［11］方面對問題訂單分批進行研究。目前，超市常用的揀選路徑策略主要為S型策略［12］。劉晨旻等［13］采用螢火蟲算法求解最短揀貨路徑，結果表明其適合于大型倉儲揀貨路徑優化。劉晨旻等［13］的作業負載平衡問題與上述研究的不同之處是，它是按時間（即每天）來平衡工作負載，而不是在區域、拾取者或批次之間進行平衡的。因此，Zulj等［14］主要在揀選訂單的背景下研究工作負荷峰值。

綜上所述，目前對于訂單分批問題結合平衡工作負載已經有了相關的研究，但是沒有考慮揀選員工之間的差異性對于訂單揀選的影響。大部分超市配送中心在揀選商品時存在沒有合理的分批訂單和考慮揀選員工之間存在的差異性會影響工作平衡。在此背景下，綜合考慮具有勞動異質性的員工和訂單分批問題，提出揀選員工行走的最小距離、最大化揀選員工工作量平衡的雙目標混合整數非線性規劃模型，并通過改進螢火蟲算法進行求解，仿真驗證其結果的可行性。

1 問題描述及數學模型

1.1 問題描述

本文研究面向以超市為倉儲配送中心的訂單分批和具有勞動異質性的揀選員工揀選平衡問題，并通過對現有常用的訂單到交付通道的指派規則，即先到先服務（first come first served，FCFS）指派規則進行分析，來獲得使揀選員工行走距離最小、員工揀選最平衡的訂單分批策略。工作流程為揀選員工需要等待訂單信息的到來，然后根據分批后的訂單信息從入口進入商品區揀選對應的商品，等商品揀選完成后打包發送。配送流程如圖1所示。

圖1 配送流程圖

傳統的FCFS方法已經不能滿足超市揀選的需求，過多的揀選時間將導致訂單延誤風險的增加。在這種動態競爭中，隨著具有勞動異質性的揀選員工的出現，專業的揀選員工總是快速揀選完成后等待訂單的到來，而業余的揀選員工總在根據訂單揀選，所以揀選員工平衡問題已經成為超市倉儲配送中心揀選商品的重要問題。

1.2 模型構建

超市配送倉庫由12條通道和300個倉位組成，起點和終點都在左下角，所研究的倉庫布局圖如圖2所示，模型參數如表1所示。為了簡化描述，模型的假設條件如下。

表1 模型參數

圖2 倉庫布局圖

1）每個倉位的物品都不一樣，并且物料充足。商品質量：1—100號為1 kg，101—200號為2 kg，201—300為5 kg。每個小推車最大承載量為100 kg。

2）每個訂單都不許拆開，只能一起揀選并放到一個訂單批次內。

3）揀選員工必須按倉位順序揀選，不可跳著揀選商品。如果訂單只有一個商品，那么揀選員工需要在揀選商品完成后原路返回，返回入口0。

4）在貨架上尋找和揀選物品的時間與每個揀選員工對特定存儲位置的熟悉程度高度相關，并在數學模型中明確考慮這一因素。

構建訂單分批優化模型，第1個目標主要是高效及時地完成訂單揀選，第2個目標旨在使具有勞動異質性的揀選員工的工作更加平衡。雙目標混合整數規劃模型為：

式（1）和式（2）為所提數學模型的目標函數，即揀選員工行走的最小距離和揀選員工工作量最平衡；式（3）約束了每一批次訂單的總質量不得超出小推車的載重量；式（4）約束了每個訂單商品的質量不得大于小推車的載重量；式（5）和式（6）保證一個訂單只能出現在一個批次里；式（7）為每個員工的揀選能力。假設揀選時間遵循學習曲線，并且進一步假設學習發生在單個項目級別，因此越頻繁地揀選物品，揀選員工就越能記住該物品的位置，并且搜索時間越短。搜索時間為：

S形路線的批次的總行進距離為：

式（2）的模型系數允許揀選員工以以下方式表示：具有β1，w的揀選者，w表示能力強的人；具有β2，w的揀選者，w表示能力弱的人；揀選員工的平均批處理執行時間隨著訂單數、行進距離的增加而增加。這些都是合理的，隨著工作量的增加，時間自然也會增加。較高揀選水平的員工揀選更快，這表明根據揀選能力來進行訂單分批處理，使揀選商品的效率更高。

2 算法設計

2.1 螢火蟲算法

螢火蟲算法屬于種群智能優化算法，每只螢火蟲都可以看做一個問題的解。這種算法就是通過模擬螢火蟲的發光行為而提出的，所以實際上其原理很簡單。為了方便算法的描述，需要3個理想化的假設：

1）所有螢火蟲雌雄同體，都能被其他螢火蟲所吸引；

2）螢火蟲的亮度受目標函數影響或決定，對于最大化問題，亮度可以簡單地與目標函數值成正比；

3）對于任意2只閃爍的螢火蟲，較暗的那只會朝著較亮的那只移動；

需要滿足不得超過小推車載裝量的限制，因此訂單分批方案的總成本計算公式為：

式中：a為螢火蟲個體，代表訂單分批方案；f（a）為螢火蟲個體轉化成訂單分批方案的總成本；c（a）為揀選工作行走的距離；q（a）為各批次訂單違反小推車的裝載量之和；?為違反裝載量權重。

在使用螢火蟲算法解決連續優化問題時，第a只到第b只螢火蟲的距離為：

在牽引力作用下，螢火蟲在可見范圍內向比它們自己更亮的個體b移動。位置移動的公式如下：

式中：x（t）為個體a在t的位置；α為步長因子，恒定范圍為［0，1］。

2.2 動態自適應步長改進螢火蟲算法

雖然螢火蟲算法有明顯的優點并受到許多研究者的青睞，但與其他啟發算法一樣，它也存在一些不足。例如，在高維條件下，算法很容易陷入局部最小值，并且由于吸引力的減弱而降低了解的性能。為此提出了一種動態自適應的螢火蟲優化算法，加入動態步長調整因子，隨機改變算法的步長，防止算法陷入局部最優。該策略能有效平衡算法，提高算法的收斂速度。

標準FA是根據高亮度螢火蟲和低亮度螢火蟲之間的吸引力來更新位置的。由于螢火蟲的可視范圍有限，因此低亮度螢火蟲只能在其可視范圍內找到可移動的高亮度螢火蟲。對于標準螢火蟲算法，步長因子α是常數。這意味著在迭代中，步長因子α是一個固定值，沒有考慮后期個體之間的距離隨著迭代次數的增加而不斷減小，因此固定值α容易導致算法產生“振蕩”。步長因子α的取值對算法的搜索能力有很大的影響。通過分析和實驗發現，α值越大，全局最優性越好，但在算法后期不容易收斂。α值越小，收斂越好，但容易陷入局部最優。

為了使演化過程更有效，在優化過程中引入動態階躍因子機制，將α控制在一個區間［αmin，αmax］，并使該值與優化的距離偏差程度相適應，從而提高求解精度和收斂速度。同時，為了增強種群的靈活性，采用均勻分布隨機因子對α進行定向隨機化。新算法中α的取值公式為：

式中：αmax、αmin分別為最大步長和最小步長。經過大量的實驗測試，當αmin＝0.5，αmin＝0.1時，優化效果最好。螢火蟲個體分散在整個空間中，大多數螢火蟲個體與全局最優個體之間存在較大距離。為了防止算法因α值過小而陷入局部極值，加入了向最好螢火蟲移動的方法，即最好的螢火蟲在其搜索方向上采用大步長線性加速，剩下的螢火蟲采用線性減速移動，Δ＝（max－min）／最大迭代數＝1。

根據上述分析，步長因子α根據螢火蟲個體間的距離自適應動態變化，平衡了算法開發和搜索的能力。

本文采用動態自適應步長改進螢火蟲算法的終止條件為迭代出最優的目標函數值，如果滿足終止條件，那么輸出最短行走距離和訂單分批出的具體訂單。改進后的算法解決訂單分批流程如圖3所示。

圖3 動態自適應步長改進螢火蟲算法解決訂單分批流程圖

3 仿真實驗與結果分析

3.1 實驗參數

為了驗證改進的螢火蟲算法可以更好地解決訂單分批和揀選員工工作量不平衡的問題，采用模擬仿真方法進行了一系列數值實驗。超市布局和訂單特征等參照相關文獻和現實調研情況設定。以永輝超市（YH）配送中心實際訂單數據為例，假設在1個時間窗口內累積了20個在線訂單?？捎玫膾x訂單的工作人員的最大數量應大于在1個時間窗口中累積的訂單總數?？晒x訂單的工作人員為10人，因為員工具有勞動異質性，其中一些員工接受了揀選訂單的培訓，另一些為零時工。

式中：t2＝1表示初學者的初始搜索時間；LRp＝0.95表示搜索時間的個體差異；k為先前選擇的累積項。將k設為100、500和1 000，表示個人的技能熟練程度。設置了2個經驗豐富的揀選人選（k＝1 000）、4個新員工（k＝500）和4個臨時工（k＝100）。每名采摘者的行走速度為40 m／min。

本文采用隨機的方式構建初始種群，初始種群的任意1只螢火蟲個體都是（N＋K－1）的隨機排列。在使用改進螢火蟲算法解決連續優化問題時，第i只螢火蟲與第j只螢火蟲之間的距離為求出2只螢火蟲對應位置上不同元素之和，并且把2個目標函數看成2只螢火蟲之間的相互吸引。我們隨機揀選永輝超市（YH超市）配送中心的20個訂單數據，通過應用Matlab軟件進行多組仿真驗證。輸入基礎參數、初始化定義、訂單數據后，開始仿真驗證，求出最優訂單批次。訂單數據如表2所示，基礎參數如表3所示。

表2 訂單數據

表3 基礎參數

3.2 小規模實驗分析

訂單分批策略定義了如何將消費者訂單分批到單個揀選流程中。FCFS策略為與改進FA策略比較的基線，并且還與基本FA策略和種子策略進行比較。種子分批策略首先選擇順序最小種子通道的數量，然后添加客戶訂單，使需要通過額外倉庫通道數量最小，直到揀選的產品總數達到分批處理量。先前的研究已經證明了種子分批策略可以產生高效的訂單分批解決方案。FCFS和種子分批策略產生的訂單批次首先分配給專業的揀選者，然后給其他的員工。研究的目的是實現雙目標揀選訂單，使超市的利益最大化。盡管有各種復雜的啟發式方法來解決訂單批處理和分配問題，但增加的計算時間和復雜（或簡化）的假設可能會阻礙它們在實踐中的應用。

實驗的程序運行環境：處理器CPU為R7，主頻為3.40 GHz，操作系統為Windows10，開發環境為MatlabR 2022b。改進FA算法的步長因子在［0.5，0.1］區間，經過100次迭代結束。

在訂單分批問題中，超市倉儲配送中心采用的是先到先揀選的策略。在相同揀選S型路徑的策略下，分別對比FCFS策略、種子策略、FA策略和改進FA策略。在訂單數據表2的20個訂單數、85個商品的條件下，得出的訂單分批不同策略對比如表4所示，揀選距離對比迭代圖和員工揀選平衡圖如圖4、圖5所示。

表4 不同策略對比表

圖4 揀選距離對比迭代圖

可以看出，在4種分批策略下，揀選員工行走的距離分別為749、630、628、568 m，而揀選員工的平均工作平衡率為75.1%、77.1%、85.0%、88.3%。改進FA策略與其超市倉儲配送中心采用的FCFS策略（基準）、種子策略和FA策略相比都有所降低，揀選員工揀選距離分別降低了24.1%、9.8%、9.5%；而揀選員工的平均工作平衡率分別提高了17.6%、14.5%、3.9%。綜合來說，改進FA策略與現階段超市倉儲配送中心采取的FCFS策略、FA策略和種子策略相比，揀選效率有著明顯的提高。

3.3 大規模實驗分析

為了減少因訂單數據以及商品數據數量少的偶然性，將隨機選取的YH超市50個訂單進行訂單分批實驗。所有的參數變量都和以上分析一致，得到的不同策略對比如表5所示，揀選距離對比迭代圖和員工揀選平衡圖如圖6、圖7所示。

圖6 50組訂單揀選距離對比迭代圖

圖7 50組訂單員工揀選平衡圖

可以看出，隨著訂單數據的增加，改進FA策略改善訂單分批的效果更加明顯，比FCFS策略和種子策略分別降低了21.4%和21.9%。但是在工作平衡方面，隨著訂單的增加，揀選員工揀選單批訂單行走的路程增加，工作量平衡率大幅降低，尤其是種子策略，甚至分批訂單數已經超過了揀選員工數量，只能進行下一次揀選，這對于揀選效率無疑是大大降低的。簡單來說，改進FA策略并不能保證在工作平衡方面做到極致，在8批訂單中，80%都高于FCFS策略?？偟膩碚f在訂單窗口正常接單、無員工惡意曠工的情況下，改進FA策略是可以提高超市倉儲配送中心的揀選效率的，可以使揀選員工更有效率、更平衡地揀選商品，提高總體效率。

4 結論

本文對O2O超市倉儲配送中心的訂單分批和揀選員工工作不平衡問題進行了描述，結合現有的研究提出了雙目標混合整數型模型。由于超市線上訂單數量巨大，商品種類豐富，因此采用改進FA算法求解優化模型。

首先為解決雙目標混合整數模型，在算法設計中采用均勻隨機分布步長因子和最好的螢火蟲搜索方向上采用線性加速，剩下的螢火蟲采用線性減速移動的方式改進螢火蟲算法，并且利用螢火蟲相互吸引的特點；然后通過Matlab仿真驗證模型及算法，設計多組數值實驗，在20個訂單實驗中驗證了模型的可行性。為了避免數據過小存在隨機性，采用50組訂單實驗、200多個商品進行驗證；最后通過實驗表明改進FA策略可以較好地解決所提模型存在的求解問題，并且改進FA策略比FCFS策略、種子策略在求解上更具有優勢。

綜上所述，本文是對O2O超市倉儲配送中心訂單分批問題改進的初步嘗試，但關于此方面的研究并沒有考慮到揀選商品的一些復雜的操作特征，如商品位置的不準確性、后臺庫存數據更新不及時，以及不同區域揀選中存在的問題，所以希望未來的研究可以建立相對應的模型給予解決。