陳彥如,單 翠,蔣陽升，魏朝恒，曾東紅

(1.西南交通大學(xué) 經(jīng)濟(jì)管理學(xué)院， 四川 成都 610031；2.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031)

多分揀區(qū)FRP的GA&SS算法設(shè)計(jì)

陳彥如1,單 翠1,蔣陽升2，魏朝恒1，曾東紅2

(1.西南交通大學(xué) 經(jīng)濟(jì)管理學(xué)院， 四川 成都 610031；2.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031)

考慮到遺傳算法(GA)和分散搜索算法(SS)在求解大規(guī)模組合優(yōu)化問題的優(yōu)勢(shì)，針對(duì)多分揀區(qū)的分揀存儲(chǔ)指派決策(FRP)設(shè)計(jì)了GA&SS算法，對(duì)該算法的參數(shù)進(jìn)行了敏感性分析。獲得滿意的參數(shù)組合后，將該算法與單純形法的運(yùn)行效果進(jìn)行對(duì)比。結(jié)果表明：隨著產(chǎn)品規(guī)模的增加，GA&SS算法較單純形法有明顯的時(shí)間優(yōu)勢(shì)。

管理工程；多分揀區(qū)；分揀存儲(chǔ)指派決策；遺傳算法；分散搜索

0 引 言

提高分揀效率、縮短分揀時(shí)間、降低分揀成本是提升配送中心競爭力的核心所在。眾所周知，貨物的儲(chǔ)位分配對(duì)分揀成本的降低、分揀時(shí)間的減少有直接影響。為了降低分揀成本，許多配送中心設(shè)置了分揀區(qū)(Forward Area)和存儲(chǔ)區(qū)(Reserve Area)。分揀區(qū)用于快速分揀，提高分揀效率。存儲(chǔ)區(qū)用于大量存儲(chǔ)、補(bǔ)貨及未分配至分揀區(qū)產(chǎn)品的分揀。如何解決在有限的分揀區(qū)存放多少數(shù)量的何種產(chǎn)品，便形成了分揀存儲(chǔ)指派決策(Forward-Reserve Problem，F(xiàn)RP)。

目前關(guān)于配送中心相關(guān)的研究成果已非常豐富。GU Jinxiang[1]較系統(tǒng)地分析了倉庫設(shè)計(jì)問題，以倉庫整個(gè)壽命周期內(nèi)倉庫總成本為優(yōu)化目標(biāo)。S.S.HERAGU等[2]綜合考慮了分揀區(qū)空間大小和產(chǎn)品分配問題，以年分揀和存儲(chǔ)成本最小為目標(biāo)，建立了數(shù)學(xué)模型并給出啟發(fā)式算法。J.C.H.PAN等[3]研究高層人至物分揀系統(tǒng)產(chǎn)品存儲(chǔ)策略和分揀路徑選擇對(duì)訂單分揀行程時(shí)間的影響。R.ACCORSI等[4]為提高倉儲(chǔ)系統(tǒng)的設(shè)計(jì)和管理效率，設(shè)計(jì)了決策支持系統(tǒng)。D.B.DURDEVIC等[5]研究了配送中心內(nèi)分揀區(qū)和存儲(chǔ)區(qū)之間相互作用的各種影響因素，考慮服務(wù)水平不變的情況下，如何設(shè)計(jì)存儲(chǔ)區(qū)與分揀區(qū)的位置來降低配送中心成本。HARWIN de Vries等[6]研究了基于3種不同補(bǔ)貨優(yōu)先級(jí)對(duì)分揀區(qū)補(bǔ)貨時(shí)間的影響(基于存儲(chǔ)需求、基于訂單量及基于訂單需求)。C.H.MOWREY等[7]分析了寬窄巷道的布置和分揀路徑對(duì)分揀效率及成本的影響。周弘等[8]考慮了3層配送網(wǎng)絡(luò)中產(chǎn)品分配和運(yùn)輸模式?jīng)Q策問題，以總費(fèi)用最小和分揀中心負(fù)載的平衡為目標(biāo)，建立了基于公共交貨期的多目標(biāo)物流配送優(yōu)化模型。王鳳珍[9]從訂單產(chǎn)品種類的數(shù)量和需求相關(guān)性兩個(gè)角度出發(fā)，考慮不同產(chǎn)品間的需求相關(guān)性，將多個(gè)成品倉庫的產(chǎn)品進(jìn)行重新分配。

上述文獻(xiàn)為筆者提供了重要的研究基礎(chǔ)，但這些研究大多集中在單一分揀區(qū)，對(duì)多分揀區(qū)的研究較少。而多分揀區(qū)由于靈活的配置及高效率的分揀，已經(jīng)成為很多配送中心的選擇。因此，多分揀區(qū)FRP的解決開始引起企業(yè)的關(guān)注。由于配送中心產(chǎn)品種類與數(shù)量眾多，F(xiàn)RP算法的設(shè)計(jì)直接影響FRP的決策效率。筆者針對(duì)多分揀區(qū)FRP模型設(shè)計(jì)了GA&SS算法，并用算例驗(yàn)證了算法的有效性。

1 模型描述

多分揀區(qū)FRP主要解決什么產(chǎn)品應(yīng)該以多少數(shù)量被分配至哪個(gè)分揀區(qū)的問題。由于分揀區(qū)的面積小于存儲(chǔ)區(qū)，因而分揀區(qū)的分揀成本小于存儲(chǔ)區(qū)的分揀成本。

決策變量：

則多分揀區(qū)模型描述如下：

(1)

(2)

(3)

式(1)是模型的目標(biāo)函數(shù)，以分揀區(qū)節(jié)省成本與建設(shè)成本及分揀區(qū)產(chǎn)品處理成本之差最大化為目標(biāo)。約束條件式(2)保證了指派到分揀區(qū)的產(chǎn)品以一種存儲(chǔ)方式存儲(chǔ)到一個(gè)分揀區(qū)內(nèi)。約束條件(3)表示指派到分揀區(qū)的產(chǎn)品存儲(chǔ)空間不能超過分揀區(qū)容量。

2 算法設(shè)計(jì)

分散搜索( Scatter Search，簡稱SS)是Glover在20世紀(jì)70年代提出的一種啟發(fā)式算法，它主要通過解的組合來進(jìn)行尋優(yōu)。由于SS算法的框架靈活，很容易和其他算法結(jié)合，更有效地完成解空間搜索。筆者嘗試將SS與遺傳算法(GA)相結(jié)合，用來解決多分揀區(qū)的產(chǎn)品存儲(chǔ)組合優(yōu)化問題。算法設(shè)計(jì)如下。

2.1 編 碼

本階段對(duì)可行解進(jìn)行編碼?？紤]到將I種產(chǎn)品以J種存儲(chǔ)方式放在K個(gè)分揀區(qū)，因此所設(shè)計(jì)的染色體總長度為I×J×K+I+K。染色體包括3個(gè)部分，第1部分長度為I×J×K，表示I種產(chǎn)品以J種方式在K個(gè)分揀區(qū)的存儲(chǔ)方案。第2部分長度為I，表示I種產(chǎn)品的存儲(chǔ)方式是否發(fā)生改變。第3部分長度為K，表示K個(gè)分揀區(qū)是否建立。

2.2 產(chǎn)生多樣性初始解集

首先隨機(jī)產(chǎn)生初始種群。由于某產(chǎn)品在某分揀區(qū)只能采取一種存儲(chǔ)方式，需要保證在染色體的第1部分的每段基因體內(nèi)代表某個(gè)分揀區(qū)的J個(gè)基因位中只能有1個(gè)基因位為“1”，該基因位隨機(jī)產(chǎn)生。染色體的第2部分的基因由隨機(jī)方式產(chǎn)生。染色體的第3部分的基因隨機(jī)產(chǎn)生后，需進(jìn)行判斷，當(dāng)?shù)?部分染色體中某產(chǎn)品被分配到某分揀區(qū)后，第3部分染色體中該分揀區(qū)對(duì)應(yīng)基因位才能為“1”。

在上述初始種群中采用Glover提出的多樣性產(chǎn)生器選取50個(gè)多樣性較好的解作為多樣性初始解集。

2.3 構(gòu)建初始參考集

參考集包含1組高質(zhì)量的解和多樣性的解。參考集在初始階段被構(gòu)建，包含從多樣性初始解集中選出的5個(gè)高質(zhì)量解和5個(gè)多樣性解。高質(zhì)量解通過以下適應(yīng)度函數(shù)進(jìn)行選取，即在初始解集中選擇5個(gè)適應(yīng)度最大的解作為參考集中的高質(zhì)量解。

產(chǎn)生多樣性解時(shí)，首先須評(píng)估解的多樣性程度?？梢钥紤]從當(dāng)前種群中選取與其它解距離之和最小的解作為1個(gè)多樣性的解，重復(fù)此過程直到產(chǎn)生5個(gè)多樣性解為止，從而完成初始參考集的構(gòu)建。

2.4 產(chǎn)生子集

子集產(chǎn)生方法是通過對(duì)參考集的操作產(chǎn)生一系列用于合并的解集。筆者采用了常用的子集產(chǎn)生方法，即生成參考集中所有的二元組，每個(gè)二元組作為一個(gè)子集，共(102-10)/2個(gè)子集。

2.5 交叉與變異合并子集產(chǎn)生新解

文中第1部分染色體采用兩點(diǎn)交叉的方式，以保證產(chǎn)生的新個(gè)體為可行解。第2部分與第3部分采用單點(diǎn)交叉的方式。

變異操作是3部分分別進(jìn)行變異，第1部分染色體在每個(gè)產(chǎn)品每個(gè)分揀區(qū)對(duì)應(yīng)的基因段中搜尋值為“1”的基因，將其變?yōu)椤?”，然后在其余的基因位中任選一位將其變成“1”，以保證變異后的個(gè)體為可行解。第2部分和第3部分染色體采取常規(guī)變異的模式，同時(shí)保證第1部分染色體與第3部分染色體的制約關(guān)系。

2.6 更新參考集

本算法采用靜態(tài)更新方法，即在當(dāng)前參考集和通過交叉變異產(chǎn)生的新解中選取5個(gè)目標(biāo)函數(shù)值最優(yōu)解和5個(gè)多樣性最好解作為新參考集，具體操作同步驟3)。如果滿足參考集未發(fā)生變化，則獲得最佳方案，否則重復(fù)步驟4)～步驟5)。算法設(shè)計(jì)流程見圖1。

圖1 算法設(shè)計(jì)流程Fig.1 Flow chart of proposed algorithm

3 算 例

某配送中心設(shè)有存儲(chǔ)區(qū)與3個(gè)分揀區(qū)，分揀區(qū)容量分別為1 000，500，1 000?，F(xiàn)有A，B，C，D4類產(chǎn)品，其需求分別為226，238，287，259。分揀區(qū)有兩種存儲(chǔ)方式。現(xiàn)假設(shè)3個(gè)分揀區(qū)單位空間的建設(shè)成本相同，均為10。產(chǎn)品成本如表1、表2。

表1 產(chǎn)品在存儲(chǔ)區(qū)的分揀成本

表2 產(chǎn)品在分揀區(qū)的分揀成本、處理成本及補(bǔ)貨成本

由于算法參數(shù)選擇對(duì)優(yōu)化結(jié)果有一定的影響，筆者首先對(duì)不同參數(shù)進(jìn)行測(cè)試，分別考慮種群規(guī)模為40，80；迭代次數(shù)為20，40；交叉率為0.5，0.6，0.8；變異率為0.1的參數(shù)組合進(jìn)行測(cè)試，結(jié)果如圖2。

圖2 不同參數(shù)組合下測(cè)試結(jié)果Fig.2 Test results with different parameter combinations

由圖2可知：①在種群規(guī)模、迭代次數(shù)、變異率一定的情況下，交叉率為0.8時(shí)所得的結(jié)果比交叉率為0.5及0.6時(shí)更加平穩(wěn)；②在迭代次數(shù)、交叉率、變異率一定的情況下，隨著種群規(guī)模的不斷擴(kuò)大，滿意解的質(zhì)量及獲得最優(yōu)解的可能性逐漸增大，當(dāng)種群規(guī)模為80時(shí)更容易達(dá)到最優(yōu)解；③迭代次數(shù)由20增大到40時(shí)，對(duì)于運(yùn)行結(jié)果(滿意解的質(zhì)量以及達(dá)到最優(yōu)解的可能性)的影響不明顯；④當(dāng)?shù)螖?shù)達(dá)到40時(shí)，隨著種群規(guī)模的擴(kuò)大，對(duì)于滿意解的改進(jìn)不理想，當(dāng)?shù)螖?shù)增大時(shí)，滿意解的質(zhì)量以及達(dá)到最優(yōu)解的可能性反而更低。

因此，該問題最優(yōu)的算法參數(shù)組合為種群規(guī)模80，迭代次數(shù)20，交叉率0.8，變異率0.1。在此參數(shù)組合下，將所設(shè)計(jì)的GA&SS與單純形法從計(jì)算時(shí)間進(jìn)行對(duì)比，如圖3。

圖3 4個(gè)產(chǎn)品兩種算法的計(jì)算時(shí)間對(duì)比Fig.3 Comparison between the computation time of two algorithms for four products

當(dāng)產(chǎn)品數(shù)增加到10時(shí)，兩種算法的適應(yīng)度與計(jì)算時(shí)間對(duì)比如圖4(模型參數(shù)略)。

圖4 10個(gè)產(chǎn)品的兩種算法的對(duì)比Fig.4 Comparison between two algorithms for ten products

從結(jié)果可以看出，使用單純形法可以找到最優(yōu)解，但只適合數(shù)量規(guī)模小的產(chǎn)品，隨著產(chǎn)品數(shù)目增加，該方法計(jì)算時(shí)間大幅上升，陷入“維度災(zāi)難”，而筆者所設(shè)計(jì)的算法，在產(chǎn)品規(guī)模增大后時(shí)間優(yōu)勢(shì)十分明顯，可以在合理時(shí)間內(nèi)得到較滿意的方案。

4 結(jié) 語

多分揀區(qū)FRP是一類典型的組合優(yōu)化問題，隨著問題規(guī)模的增加，求解會(huì)變得越來越困難。考慮到遺傳算法和分散搜索算法在求解大規(guī)模問題的優(yōu)勢(shì)，筆者針對(duì)多分揀區(qū)FRP設(shè)計(jì)了GA&SS算法。和單純形法相比較，當(dāng)產(chǎn)品規(guī)模較小時(shí)，該算法優(yōu)勢(shì)并不明顯，但隨著產(chǎn)品規(guī)模的增大，該算法時(shí)間優(yōu)勢(shì)越來越明顯。

研究結(jié)果對(duì)大型配送中心多分揀區(qū)的運(yùn)營方案的快速獲取有一定參考價(jià)值，但研究依然存在一定的局限性，如選用更大規(guī)模的產(chǎn)品數(shù)對(duì)算法進(jìn)行驗(yàn)證，以及考慮和多種算法進(jìn)行比較，這將是筆者進(jìn)一步研究的方向。

[1] GU Jinxiang.TheForwardReserveWarehouseSizingandDimensioningProblem[D].Georgia,USA:Georgia Institute of Technology,2005.

[2] HERAGU S S,DU L,MANTEL R J,et al.Mathematical model for warehouse design and product allocation [J].InternationalJournalofProductionResearch,2005,43(2):327-338.

[3] PAN J C H,WU M H,CHANG W L.A travel time estimation model for a high-level picker-to-part system with class-based storage policies [J].EuropeanJournalofOperationalResearch,2014,237(3):1054-1066.

[4] ACCORSI R,MANZINI R,MARANESI F.A decision-support system for the design and management of warehousing systems [J].ComputersinIndustry,2014,65(1):175-186.

[6] HARWIN de Vriesa,RUTH Carrasco-Gallegob,Taoying Farenhorst-Yuan,et al.Prioritizing replenishments of the piece picking area [J].EuropeanJournalofOperationalResearch,2014,236(1):126-134.

[7] MOWREY C H,PARIKH P J.Mixed-width aisle configurations for order picking in distribution centers [J].EuropeanJournalofOperationalResearch,2014,232(1):87-97.

[8] 周泓,孫江蘇,譚小衛(wèi).多目標(biāo)物流配送優(yōu)化問題建模及其遺傳算法設(shè)計(jì)[J].公路交通科技,2007,24(9):140-144. ZHOU Hong,SUN Jiangsu,TAN Xiaowei.Multi-objective optimization for logistic distribution and its genetic algorithm [J].JournalofHighwayandTransportationResearchandDevelopment,2007,24(9):140-144.

[9] 王鳳珍.基于需求相關(guān)性的A企業(yè)產(chǎn)品庫存分配策略[D].大連:大連海事大學(xué),2013. WANG Fengzhen.AllocationStrategyofInventoryforEnterpriseABasedonDemandRelevance[D].Dalian:Dalian Maritime University,2013.

Developing GA&SS Based on FRP of Multiple Forward Areas

CHEN Yanru1, SHAN Cui1, JIANG Yangsheng2, WEI Chaoheng1, ZENG Donghong2

(1. School of Economics & Management, Southwest Jiaotong University, Chengdu 610031, Sichuan, P.R.China; 2. School of Transportation & Logistics, Southwest Jiaotong University, Chengdu 610031, Sichuan, P.R.China)

Based on the advantage of genetic algorithm (GA) and scatter search (SS) in solving large-scaled combinatorial optimization problems, an algorithm which combined GA and SS (GA&SS) was developed. Sensitivity analysis about parameters of GA&SS was also made to obtain optimal parameter combination. And the operation effect of the proposed algorithm was compared with that of the simplex method. The results show that the proposed GA&SS performs obviously better than simplex method does in computational time, with the increase of numbers of products.

management engineering; multiple forward areas; forward-reserve problem (FRP); genetic algorithm; scatter search

2014-05-07；

2014-09-26

四川省科技支撐計(jì)劃項(xiàng)目(2012GZ0063)； 中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2682013CX074)

陳彥如(1974—),女,內(nèi)蒙古包頭人，副教授，主要從事物流與供應(yīng)鏈優(yōu)化方面的研究。E-mail: chenyanru@163.com。

10.3969/j.issn.1674-0696.2016.01.23

F253.4

A

1674-0696(2016)01-117-05