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

（東北林業(yè)大學(xué)機(jī)電工程學(xué)院，哈爾濱 150040）

0 引言

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

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

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

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

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

圖1 配送流程圖

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

1.2 模型構(gòu)建

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

表1 模型參數(shù)

圖2 倉庫布局圖

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

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

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

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

構(gòu)建訂單分批優(yōu)化模型，第1個目標(biāo)主要是高效及時地完成訂單揀選，第2個目標(biāo)旨在使具有勞動異質(zhì)性的揀選員工的工作更加平衡。雙目標(biāo)混合整數(shù)規(guī)劃模型為：

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

S形路線的批次的總行進(jìn)距離為：

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

2 算法設(shè)計

2.1 螢火蟲算法

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

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

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

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

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

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

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

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

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

2.2 動態(tài)自適應(yīng)步長改進(jìn)螢火蟲算法

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

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

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

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

根據(jù)上述分析，步長因子α根據(jù)螢火蟲個體間的距離自適應(yīng)動態(tài)變化，平衡了算法開發(fā)和搜索的能力。

本文采用動態(tài)自適應(yīng)步長改進(jìn)螢火蟲算法的終止條件為迭代出最優(yōu)的目標(biāo)函數(shù)值，如果滿足終止條件，那么輸出最短行走距離和訂單分批出的具體訂單。改進(jìn)后的算法解決訂單分批流程如圖3所示。

圖3 動態(tài)自適應(yīng)步長改進(jìn)螢火蟲算法解決訂單分批流程圖

3 仿真實驗與結(jié)果分析

3.1 實驗參數(shù)

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

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

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

表2 訂單數(shù)據(jù)

表3 基礎(chǔ)參數(shù)

3.2 小規(guī)模實驗分析

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

實驗的程序運行環(huán)境：處理器CPU為R7，主頻為3.40 GHz，操作系統(tǒng)為Windows10，開發(fā)環(huán)境為MatlabR 2022b。改進(jìn)FA算法的步長因子在［0.5，0.1］區(qū)間，經(jīng)過100次迭代結(jié)束。

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

表4 不同策略對比表

圖4 揀選距離對比迭代圖

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

3.3 大規(guī)模實驗分析

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

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

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

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

4 結(jié)論

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

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

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