基于螢火蟲算法的訂單分批問題研究

郜振華，陳 卓 GAO Zhenhua,CHEN Zhuo

（安徽工業大學 管理科學與工程學院，安徽 馬鞍山 243032）

(School of Management Science and Engineering,Anhui University of Technology,Maanshan 243032,China)

0 引言

現階段大多數配送中心是勞動力密集型的，配送中心中揀選作業勞動量占據配送中心全部勞動量的60%[1]，成本占40%[2]，時間占30～40%[3]。可見，揀選作業在配送中心的重要性不言而喻。

訂單分批作為揀選作業的重要環節，是指將一定數目的訂單根據一定的規則合并到一個批次進行集中揀選，以提高揀選作業效率的過程。

訂單分批主要是為了縮短揀選訂單時所用的時間和走過的距離。揀選人員在對訂單進行分批作業時，可以將好幾個訂單合并在一起然后用一套揀選設備一次性揀完，這顯然會極大地提高了揀選作業的效率，大中型配送中心應用十分廣泛。訂單分批比較適合于訂單量龐大，但是單個訂單下面的商品的種類數又不多的情況。而這與當今消費者的需求又是一致的，所以訂單分批有極大的存在價值。

對于配送中心的揀選作業，一般來說最簡單最常用的方式是先到先分批（FCFS）。這種分批方式雖然簡單易行，但是當今社會對高效率的追求，使得這種分批方式已經不能夠滿足消費者的要求。這就需要一種新的分批方式，能夠提高揀選作業的效率。本文就運用螢火蟲算法來進行訂單分批，并將螢火蟲算法分批和按訂單分批、先到先分批進行對比分析，驗證其優越性。

1 訂單分批數學模型建立

1.1 模型假設

建立訂單分批數學模型前，需要對數學模型進行適當假設，以滿足研究需要。所以，本研究將對訂單分批問題模型的假設如下：

（1）配送中心的揀選區域是8排平行貨架，倉庫有2個區，倉庫的布局如圖1所示；

（2）揀選設備（或者揀選人員）數量為2個，以前的學者往往是針對單個揀選設備進行的揀選作業，然而實際生產生活中，多人多設備同時揀選的情況普遍存在，更符合實際；

（3）每一張訂單至少包含一種貨品；

（4）每個批次訂單有多個揀選人員或（或揀選設備）進行揀選，該批次全部揀選完畢后下一個批次才開始揀選；（5）所有揀選設備的容量限制和重量限制是一致的；

（6）每一個批次進行揀選作業時，該批次所有貨品總體積和總重量不大于所有揀選設備的總體積和總重量限制；

（7）一個訂單是不能分割到兩個或兩個以上的揀選批次中；

（8）一個批次的訂單必須一次揀選完，忽略揀選庫位上貨物庫存不足情況導致的額外作業；

（9）不存在因突發情況而出現的訂單插隊狀況，訂單上的貨品倉庫都是有存貨的，并且訂單在揀選前一經確認，無法更改，不能再插入新的訂單；

（10）揀選人員或者揀選設備的速度是一個恒定值，在揀選時保持不變；

（11）揀選人員對配送中心的平面布局非常熟悉，不考慮因失誤導致的往返情況；

（12）所有訂單中各個貨品的數據以及存儲位置是已知的；

（13）貨物之間是緊密排列的，不考慮不同貨物放在揀選設備產生空隙，存在容積浪費的情況；

（14）每一種貨品對應倉庫里的一個庫位，即不存在一種貨品擺放在不同庫位或者相同庫位存在多種貨品的情況；

（15）忽略貨品在貨架上的垂直位移。倉庫中的貨架一般都是多層的，貨品在貨架上的垂直位移不計入到揀選距離的計算，垂直位移的多少不影響揀選人員的揀選距離；

（16）揀選過程中采用改進的S型策略（穿越策略），改進的S型策略指的是設備在第一區的巷道揀選完之后回到的是過道1，而設備在第二區的巷道揀選完之后回到的是過道2，這與單區型的S型策略（穿越策略）有所不同。

1.2 數學模型

建立的數學模型如下所示，該數學模型以揀選距離最短為目標：目標函數：

約束條件：

其中，各字母代表的含義如下：

k：訂單的批次；K：所有訂單分批的總批數；m：揀選人員或者揀選設備；M：揀選人員或者揀選設備的總數；x：貨品x；y：貨品y；Z：所有訂單中貨品的種類數；n：訂單；N：需要揀選的訂單總數；qnk：批次k中，訂單n的貨品重量，k=1,2,…,K；capmq：揀選設備最大能承載的貨物的重量限制；vnk：揀選批次k中，訂單n的貨品總體積 ，k=1,2,…,K；capmv：揀選設備最大能承載的貨物的體積限制；no_batchk：第k個揀選批次，k=1,2,…,K；Pnk：決策變量，取值為0或1，該決策變量決

圖1 倉庫布局

定該訂單n是否存在揀選批次k中；j：路徑；Tjk：揀選批次k中的揀選路徑j，j=1,2,…,L；在第k個揀選批次中，揀選設備m在揀選完貨物x后再接著揀選貨物y所經過的距離決策變量，取值為0或1，該決策變量決定在第k批次里，是否在揀選完貨物x后就馬上揀選貨物y。

式（1）為訂單分批數學模型的目標函數，目標函數是求最小值，在揀選完所有批次的貨物后，使得總揀選距離最小。式（2）表示，在任意一個揀選批次，該批次所有貨品的總重量不超過所有揀選設備所能承受的總重量。式（3）表示，在任意一個揀選批次，該批次所有貨品的總體積不超過所有揀選設備所能承受的總容積。式（2）和式（3）對應模型準備中的第（6）條規則。式（4）表示一個訂單是不能分割到兩個或兩個以上的揀選批次中的。式（4）對應模型準備中的第（7）條規則。式（5）表示在一個批次中，揀選路徑的總數等于揀選設備的數量，表示該批次貨品要做到一次揀選完畢。式（6）為決策變量，決定訂單n是否在揀選批次k中，若在則取值為1，不在則取值為0。式（7）為決策變量，決定在第k個揀選批次中，揀選設備m揀選完貨品x后是否立即揀選貨品y，也就是說如果貨品x、y是連續揀選的就取值為1，不是連續揀選的就取值為0。

2 訂單分批問題螢火蟲算法設計

2.1 螢火蟲算法編碼

由于本文配送中心訂單分批和揀選路徑優化問題求解的是配送路徑最小時訂單的分批組合，解空間對應的是離散的整數域空間，因此需要在螢火蟲位置狀態與本文研究問題的解通過編碼的方式建立一種映射關系，通過對螢火蟲位置狀態的解碼計算目標函數值。螢火蟲編碼是將所研究問題的可行解從解空間轉換到螢火蟲算法所能處理的搜索空間中。基于實數進行編碼，隨機產生分批批次的螢火蟲，增加初始螢火蟲狀態的隨機性，盡量使得螢火蟲分布到整個解空間=1,2,…,D，其中D代表每條編碼長度，同時代表訂單號，每個實數xj的取值范圍是 1,[ ]m ，m代表最大分批批次。

下面以一個簡單例子對本文編碼方式進行說明。假設有6個訂單，分3個批次完成。隨機產生一只螢火蟲的編碼Xi代表訂單1、2、6為第一批次，3、5為第二批次，4為第三批次。

2.2 螢火蟲算法解碼

螢火蟲解碼是由算法解空間向實際模型解空間的轉換，根據上述的編碼方式，本文在解碼過程中根據重量、體積約束將不合法螢火蟲位置進行調整，依次將每一批次訂單的待揀選貨物聚成兩類，兩個揀選設備以改進S型方式分別揀選這兩類，計算其路程。

2.3 螢火蟲構建

根據螢火蟲算法的基本原理，將問題的目標函數與螢火蟲的熒光素聯系起來，熒光素濃度為：

式（8）中，ρ表示熒光素揮發因子，γ表示熒光素增強因子，fi表示螢火蟲的目標函數值。

螢火蟲將會向熒光素濃度大的位置移動，螢火蟲熒光素濃度大的位置對其他螢火蟲的吸引力：

式（9）中，ε表示光照吸收率，dij表示螢火蟲與熒光素濃度大的位置的距離。螢火蟲將向吸引力最大的位置移動，如果沒有比自身位置熒光素更濃的位置，螢火蟲則隨機移動一步。發揮群體智能作用，螢火蟲從局部尋優實現最終全局尋優。

螢火蟲攜帶信息包括變量與函數兩部分信息。

（1）變量部分：包括螢火蟲總數N、熒光素揮發因子ρ、熒光素增強因子γ、光照吸收率ε、移動的步長Step等基本參數部分，另外還包括螢火蟲位置狀態編碼為訂單號。螢火蟲個體之間的距離計算采用同一位置上不同數字的總個數。舉例子來說明螢火蟲個體間的距離相同位置上只有第5、6位相同，那么兩只螢火蟲之間的距離為4。

（2）函數部分：主要是包括目標函數以及螢火蟲的兩種行為函數以及行為評價函數。選擇更低的總路徑作為螢火蟲執行行為的行為評價準則。

（3）解空間：螢火蟲算法中螢火蟲所在的位置對應著數學問題中的解空間，根據本文研究的模型，解空間是非常龐大的。用公式表示如下：SP=mn，其中SP代表解空間。n表示訂單數量，m代表訂單所在的批次。

2.4 行為實現

（1） 吸引行為

假設某螢火蟲當前的位置信息是Xi，搜索當前鄰域內的其它螢火蟲，記錄亮度最強的螢火蟲位置Xj，如果該螢火蟲的亮度強于自身的亮度，則向Xj的方向移動一步，否則，執行隨機行為，如式（10）：

（2） 隨機行為

如果當前螢火蟲位置為視野范圍內亮度最強的位置，則螢火蟲執行隨機行為，本文的螢火蟲編碼為離散的整數，因此本文的隨機行為采用單點變換的方式進行，如隨機取一個位置2，則隨機行為后的位置就變成了

2.5 算法的終止條件

本文終止條件的依據是是否存在更高的適應度值。根據這一準則可以以最大迭代次數Maxgen作為算法的終止條件，如果滿足終止條件，則輸出最優路徑值以及對應的訂單分批批次，否則，繼續迭代。

3 訂單分批問題螢火蟲算法分批

3.1 庫位編碼和距離計算

3.1.1 庫位編碼

為方便進行計算，需要對倉庫模型的各個參數進行說明，該倉庫分為第一區和第二區兩個區域，一共有8排貨架，3個過道，7個巷道，1排貨架一共有24個庫位（一區二區各12個），入口處和離入口最遠處的通道是沒有揀選庫位的。圖1中，過道寬度a=2m，存儲貨品庫位的長度和寬度是一致的b=c=1m，巷道寬度d=1.5m。

為了計算兩個待揀選點之間的距離，可以首先對一個待揀選點進行編碼操作，具體的編碼方式是：[區域編號，巷道編號，巷道左右側編號，庫位編號 ]，這樣就可以清晰明確地知道待揀選點的具體位置，各個編號都是自然數編碼。區域編號指的是，將倉庫分為兩個區，靠近出入口的是第一區，編號為1，遠離出入口的是第二區，編號為2。區域編號只能是1或者2中的一個。巷道從出入口的第一個巷道開始編號，越遠離出入口，巷道編號越大，因為巷道一共是7條，所以巷道編號為1到7的自然數。巷道左右側編號指的是，背向過道1，面向過道2時，位于巷道左側的待揀選點，編號為1，位于巷道右側的待揀選點，編號為2。庫位編號指的是庫位點的編號，以過道為分界線，從左到右依次從小到大編號，庫位點一共是14個，所以庫位編號為1到14的自然數。出入口的編號是[0,0,0,]0。例如，圖1中標號為2的待揀選點的編號是標號為7的待揀選點的編號是[1,1,2,]3。這種標號方式清晰自然，而且可以很便捷地進行擴展。考慮到每個待揀選點都有貨品需要揀取，可以將每個待揀選點的貨品重量和體積信息編碼進去，這樣每個待揀選點的信息將會更加全面。例如編號指的是在第二區，第4個巷道，該待揀選點位于巷道右側，從左到右第8個貨架的位置上，該待揀選點上的貨品重量為2KG，體積為1dm3。

3.1.2 距離計算

庫位編碼是為了更好地計算兩個庫位之間的距離。對于任意兩個庫位，兩個庫位的編碼分別是]和采用如下步驟進行求解：

（3）計算穿越庫位的距離，分為以下幾種情況：

圖2 穿越庫位的兩種路線

總距離為穿越過道的距離、穿越巷道的距離、穿越庫位的距離之和。

3.2 螢火蟲算法分批

設置揀選貨品的重量限制為1～5KG，揀選貨品的體積限制為1～10dm3，揀選設備的數量為2，揀選設備的重量限制為1～50KG，揀選貨品的體積限制為1～100dm3。隨機100個訂單數據，預設訂單批次數50，訂單批次數訂單中貨品的待揀選庫位的數量為1～10。螢火蟲算法的代碼限于篇幅不做附錄。運用螢火蟲算法對100個訂單數據進行訂單分批。每次迭代的結果如圖3所示。在螢火蟲算法進化的過程中，適應度值是目標函數值的倒數，隨著迭代次數的增加，其值是不斷上升的，表明個體的適應度是在不斷增加的，具體如圖4所示。

螢火蟲算法進行分批，一共分為了25個批次。限于篇幅，不做一一展示。其中第1、第2批次的揀選路徑圖如圖5、圖6所示。

圖3 螢火蟲算法進化圖

第1批次29個揀選點，為訂單28,32,37,63,96。第2批次7個揀選點，為訂單13,100。第3批次22個揀選點，為訂單21,34,47。第4批次35個揀選點，為訂單17,25,61,81,99。第5批次27個揀選點，為訂單27,40,41,48,69。第6批次25個揀選點，為訂單45,56,65。第7批次32個揀選點，為訂單9,11,29,33,54。第8批次26個揀選點，為訂單26,91,93。第9批次9個揀選點，為訂單59,84。第10批次28個揀選點，為訂單8,22,35,55,76。第11批次30個揀選點，為訂單2,44,52,83,92。第12批次27個揀選點，為訂單18,36,58,82。第13批次29個揀選點，為訂單30,68,71,73。第14批次27個揀選點，為訂單5,38,70,85。第15批次33個揀選點，為訂單6,39,60,67,86,98。第16批次33個揀選點，為訂單43,51,77,79,95。第17批次30個揀選點，為訂單19,31,49,50,80。第 18批次26個揀選點，為訂單 57,62,87,89。第19批次30個揀選點，為訂單7,16,53,64,74,90。第20批次23個揀選點，為訂單42,72,94,97。第21批次18個揀選點，為訂單20,23,46。第22批次23個揀選點，為訂單4,10,66。第23批次25個揀選點，為訂單1,3,14,15。第24批次15個揀選點，為訂單24,88。第25批次7個揀選點，為訂單12,75,78。

圖4 螢火蟲算法適應度值圖

圖5 螢火蟲算法分批第1批次揀選路徑圖

圖6 螢火蟲算法分批第2批次揀選路徑圖

4 比較分析

4.1 按訂單分批

按訂單分批十分簡單易行，也是最原始的訂單分批方式，按照訂單到達的前后次序，對訂單進行順序的揀選，每次揀選作業只處理一個訂單，即從1～100個訂單一一揀選。按照改進的S型策略進行揀選，運用MATLAB編程，具體編程限于篇幅，不做詳述。

分別計算設備1和設備2的揀選距離。總揀選距離即為設備1和設備2的揀選距離之和。

按訂單分批的設備1揀選距離：

按訂單分批的設備2揀選距離：

按訂單揀選的揀選路徑總距離為9 235+10 340=19 575m。

4.2 先到先分批

先到先分批分批指的是，訂單按照訂單到達先后順序從1～100個訂單依次進行分批，但是要滿足分批原則，即滿足揀選車輛的載重量和容量限制。一個批次可以處理多個訂單。按照改進的S型策略進行揀選，運用MATLAB編程，具體編程限于篇幅，不做詳述。按照先到先服務分批策略進行分批，一共分為了23個批次，各批次情況如下（數字代表訂單號，括號內訂單表示同一個批次）：

分別計算設備1和設備2的揀選距離。總揀選距離即為設備1和設備2的揀選距離之和。

先到先分批分批設備1揀選距離：

先到先分批分批設備2揀選距離：

先到先分批的揀選路徑總距離為4 108+4 305=8 413m。

4.3 螢火蟲算法分批

分別計算設備1和設備2的揀選距離。總揀選距離即為設備1和設備2的揀選距離之和。

螢火蟲算法分批設備1揀選距離：

螢火蟲算法分批設備2揀選距離：

螢火蟲算法進行分批的總揀選距離即為3 801+4 128=7 929m。

4.4 比較分析

按訂單分批、先到先分批、螢火蟲算法分批三種分批方式，分批的批次數分別為100、23、25，總揀選距離分別為19 575m、8 413m、7 929m。可見，先到先分批和螢火蟲算法分批比按訂單分批的分批次數分別減少77%、75%，先到先分批和螢火蟲算法分批比按訂單分批的總揀選距離分別減少了57.02%、59.49%。具體如表1所示。

表1 三種分批方式揀選距離對比

5 總結與展望

5.1 研究總結

本文針對配送中心揀選作業的訂單分批問題，建立了訂單分批問題的數學模型，設計了螢火蟲算法，并運用MATLAB編程對其進行求解，將求解的結果與傳統的按訂單分批和先到先分批進行了對比分析，驗證了螢火蟲算法分批在訂單分批問題上的優越性。

5.2 研究展望

（1）本文的倉庫模型是雙區型，揀選設備是2個。可以考慮將倉庫模型改為多區型，揀選設備設定為多個，這樣會更加符合實際。

（2）本文揀選的時候采用的是改進的S型策略。還可以考慮更多策略的結合與運用。

（3）本文只是以揀選距離最短為單一的目標函數。實際上訂單分批還受到擁堵狀況、消費者需求等的影響，可以考慮建立訂單分批的多目標數學模型。