郜振華，陳 卓 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ù)配送中心是勞動(dòng)力密集型的，配送中心中揀選作業(yè)勞動(dòng)量占據(jù)配送中心全部勞動(dòng)量的60%[1]，成本占40%[2]，時(shí)間占30～40%[3]?？梢?，揀選作業(yè)在配送中心的重要性不言而喻。

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

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

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

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

1.1 模型假設(shè)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（16）揀選過程中采用改進(jìn)的S型策略（穿越策略），改進(jìn)的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個(gè)揀選批次，k=1,2,…,K；Pnk：決策變量，取值為0或1，該決策變量決

圖1 倉庫布局

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

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

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

2.1 螢火蟲算法編碼

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

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

2.2 螢火蟲算法解碼

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

2.3 螢火蟲構(gòu)建

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

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

螢火蟲將會(huì)向熒光素濃度大的位置移動(dòng)，螢火蟲熒光素濃度大的位置對其他螢火蟲的吸引力：

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

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

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

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

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

2.4 行為實(shí)現(xiàn)

（1） 吸引行為

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

（2） 隨機(jī)行為

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

2.5 算法的終止條件

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

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

3.1 庫位編碼和距離計(jì)算

3.1.1 庫位編碼

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

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

3.1.2 距離計(jì)算

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

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

圖2 穿越庫位的兩種路線

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

3.2 螢火蟲算法分批

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

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

圖3 螢火蟲算法進(jìn)化圖

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

圖4 螢火蟲算法適應(yīng)度值圖

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

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

4 比較分析

4.1 按訂單分批

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

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

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

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

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

4.2 先到先分批

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

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

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

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

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

4.3 螢火蟲算法分批

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

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

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

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

4.4 比較分析

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

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

5 總結(jié)與展望

5.1 研究總結(jié)

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

5.2 研究展望

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

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

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