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

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

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

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

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

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

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

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

0 引 言

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

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

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

1 模型描述

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

決策變量：

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

(1)

(2)

(3)

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

2 算法設(shè)計

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

2.1 編 碼

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

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

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

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

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

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

產(chǎn)生多樣性解時，首先須評估解的多樣性程度。可以考慮從當前種群中選取與其它解距離之和最小的解作為1個多樣性的解，重復此過程直到產(chǎn)生5個多樣性解為止，從而完成初始參考集的構(gòu)建。

2.4 產(chǎn)生子集

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

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

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

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

2.6 更新參考集

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

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

3 算 例

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

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

[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).多目標物流配送優(yōu)化問題建模及其遺傳算法設(shè)計[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].大連:大連海事大學,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

四川省科技支撐計劃項目(2012GZ0063)； 中央高校基本科研業(yè)務費專項資金資助項目(2682013CX074)

陳彥如(1974—),女,內(nèi)蒙古包頭人，副教授，主要從事物流與供應鏈優(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