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

郜振華，陳 卓 GAO Zhenhua,CHEN Zhuo

（安徽工業(yè)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 馬鞍山 243032）

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

0 引言

現(xiàn)階段大多數(shù)配送中心是勞動力密集型的，配送中心中揀選作業(yè)勞動量占據(jù)配送中心全部勞動量的60%[1]，成本占40%[2]，時間占30～40%[3]?？梢姡瑨x作業(yè)在配送中心的重要性不言而喻。

訂單分批作為揀選作業(yè)的重要環(huán)節(jié)，是指將一定數(shù)目的訂單根據(jù)一定的規(guī)則合并到一個批次進行集中揀選，以提高揀選作業(yè)效率的過程。

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

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

1 訂單分批數(shù)學(xué)模型建立

1.1 模型假設(shè)

建立訂單分批數(shù)學(xué)模型前，需要對數(shù)學(xué)模型進行適當(dāng)假設(shè)，以滿足研究需要。所以，本研究將對訂單分批問題模型的假設(shè)如下：

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

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

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

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

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

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

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

（9）不存在因突發(fā)情況而出現(xiàn)的訂單插隊狀況，訂單上的貨品倉庫都是有存貨的，并且訂單在揀選前一經(jīng)確認(rèn)，無法更改，不能再插入新的訂單；

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

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

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

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

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

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

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

1.2 數(shù)學(xué)模型

建立的數(shù)學(xué)模型如下所示，該數(shù)學(xué)模型以揀選距離最短為目標(biāo)：目標(biāo)函數(shù)：

約束條件：

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

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

圖1 倉庫布局

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

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

2 訂單分批問題螢火蟲算法設(shè)計

2.1 螢火蟲算法編碼

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

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

2.2 螢火蟲算法解碼

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

2.3 螢火蟲構(gòu)建

根據(jù)螢火蟲算法的基本原理，將問題的目標(biāo)函數(shù)與螢火蟲的熒光素聯(lián)系起來，熒光素濃度為：

式（8）中，ρ表示熒光素?fù)]發(fā)因子，γ表示熒光素增強因子，fi表示螢火蟲的目標(biāo)函數(shù)值。

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

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

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

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

（2）函數(shù)部分：主要是包括目標(biāo)函數(shù)以及螢火蟲的兩種行為函數(shù)以及行為評價函數(shù)。選擇更低的總路徑作為螢火蟲執(zhí)行行為的行為評價準(zhǔn)則。

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

2.4 行為實現(xiàn)

（1） 吸引行為

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

（2） 隨機行為

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

2.5 算法的終止條件

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

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

3.1 庫位編碼和距離計算

3.1.1 庫位編碼

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

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

3.1.2 距離計算

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

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

圖2 穿越庫位的兩種路線

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

3.2 螢火蟲算法分批

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

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

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

4 比較分析

4.1 按訂單分批

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

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

按訂單分批的設(shè)備1揀選距離：

按訂單分批的設(shè)備2揀選距離：

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

4.2 先到先分批

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

分別計算設(shè)備1和設(shè)備2的揀選距離?？倰x距離即為設(shè)備1和設(shè)備2的揀選距離之和。

先到先分批分批設(shè)備1揀選距離：

先到先分批分批設(shè)備2揀選距離：

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

4.3 螢火蟲算法分批

分別計算設(shè)備1和設(shè)備2的揀選距離?？倰x距離即為設(shè)備1和設(shè)備2的揀選距離之和。

螢火蟲算法分批設(shè)備1揀選距離：

螢火蟲算法分批設(shè)備2揀選距離：

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

4.4 比較分析

按訂單分批、先到先分批、螢火蟲算法分批三種分批方式，分批的批次數(shù)分別為100、23、25，總揀選距離分別為19 575m、8 413m、7 929m?？梢姡鹊较确峙臀灮鹣x算法分批比按訂單分批的分批次數(shù)分別減少77%、75%，先到先分批和螢火蟲算法分批比按訂單分批的總揀選距離分別減少了57.02%、59.49%。具體如表1所示。

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

5 總結(jié)與展望

5.1 研究總結(jié)

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

5.2 研究展望

（1）本文的倉庫模型是雙區(qū)型，揀選設(shè)備是2個?？梢钥紤]將倉庫模型改為多區(qū)型，揀選設(shè)備設(shè)定為多個，這樣會更加符合實際。

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

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