李曉春，鐘雪靈，王雄志，王國慶

1.華南師范大學南海校區(qū)信息工程與技術(shù)系，廣東南海 528225

2.廣東金融學院計算機系，廣州 510520

3.華南農(nóng)業(yè)大學經(jīng)濟管理學院，廣州 510642

4.暨南大學管理學院，廣州 510632

并行分區(qū)揀貨系統(tǒng)儲位優(yōu)化設計

李曉春1，鐘雪靈2，王雄志3，王國慶4

1.華南師范大學南海校區(qū)信息工程與技術(shù)系，廣東南海 528225

2.廣東金融學院計算機系，廣州 510520

3.華南農(nóng)業(yè)大學經(jīng)濟管理學院，廣州 510642

4.暨南大學管理學院，廣州 510632

1 引言

零售型配送中心由于訂單多為多貨品小批量型，大約80%的訂單貨品都少于一個整貨箱，需要進行拆箱揀貨。這類配送中心經(jīng)常通過分區(qū)揀貨方式跨越好幾個倉儲區(qū)完成訂單揀貨任務。所謂并行分區(qū)（如圖1所示）就是將揀貨員分配到各個揀貨區(qū)，即將整個揀貨區(qū)分成幾塊，由一個或一組固定的揀貨員負責揀選某區(qū)域內(nèi)的貨品，在有訂單需求時，結(jié)合批量揀貨方式及訂單分割策略進行揀貨。其中，批量揀貨是指揀貨員以批量作業(yè)的形式同時揀取一組訂單品項的作業(yè)方式，該系統(tǒng)中，將一組訂單首先按區(qū)域進行訂單的分割，各個揀貨區(qū)根據(jù)分割后的子訂單同時進行揀貨作業(yè)，直到所有分區(qū)揀貨作業(yè)完成品項匯總為止。系統(tǒng)中，由于各分區(qū)揀貨員揀貨速度不同，工作負載若不均衡，經(jīng)常造成部分分區(qū)揀貨員忙碌和部分分區(qū)揀貨員空閑的情況，導致瓶頸現(xiàn)象、阻塞現(xiàn)象及員工效率降低等。

目前，對并行分區(qū)揀貨作業(yè)的研究大都首先通過歷史訂單數(shù)據(jù)計算品項需求之間的相似關系（即，某兩種品項的需求經(jīng)常發(fā)生在同一張訂單的概率，下文統(tǒng)一稱為“相似性系數(shù)”）[1-2]，然后基于同類族模型思想[3]建立自然族（Natural Cluster）模型，并提出啟發(fā)式算法求解使訂單需求的所有品項均衡存儲在不同的分區(qū)中，但忽略品項在各分區(qū)的貨位分布，在各分區(qū)內(nèi)品項采用隨機存儲策略。文獻[4]對常見的揀貨策略做了綜述；文獻[5-9]則通過模擬實驗，從不同角度模擬測試了巷道布局、存儲策略及分區(qū)規(guī)則不同時的揀貨效率及巷道的最優(yōu)布局；文獻[10]主要考慮了動態(tài)分區(qū)揀貨策略，提出“排序-動態(tài)-平衡”思想，提高揀貨效率；文獻[11-14]則重點考慮了分區(qū)揀選策略在自動分揀機上的應用及優(yōu)化；文獻[15]考慮被揀貨物具有一定質(zhì)量和體積的實際，提出了當量訂購次數(shù)的概念及系統(tǒng)利用率評價函數(shù)。但多數(shù)算法在設計中未考慮各分區(qū)中揀貨員揀貨速度之間的差異，實際揀貨中不僅因各分區(qū)中待揀選品項間的差異，而且因揀貨員揀貨速度的不同，導致各分區(qū)工作時間不均衡。

鑒于此，本文考慮各分區(qū)揀貨員揀貨速度不同的情況下，對并行分區(qū)揀貨系統(tǒng)優(yōu)化的目的為：（1）同一訂單中經(jīng)常出現(xiàn)的品項盡可能分布在不同的分區(qū)中，避免部分分區(qū)出現(xiàn)無任務作業(yè)的情況；（2）分區(qū)中根據(jù)揀貨員的速度，安排較多品項給揀貨快的分區(qū)，較少品項給揀貨慢的分區(qū)，從而均衡各分區(qū)的作業(yè)時間。其作業(yè)流程如圖1[16]所示。

圖1 并行分區(qū)揀貨系統(tǒng)示意圖

2 儲位策略優(yōu)化模型

設揀貨系統(tǒng)中，揀貨員分布于Z個獨立的分區(qū)，同樣，品項也被分到該Z個獨立的分區(qū)中，各分區(qū)間無緩沖區(qū)（或緩沖設備）。

假設1揀貨區(qū)按照從左到右的方向依次排列，分別設為z=1，2，…，Z，對于該定一組訂單，各分區(qū)揀貨員同時從領單點處領取其負責的分區(qū)內(nèi)的任務，同時開始揀貨。即將訂單進行分割，使所有揀貨員同時作業(yè)。

該假設主要是基于揀貨區(qū)一般是根據(jù)品項在配送中心的流向（如集貨點的位置）布置。

假設2每一訂單需要不同種類的品項，且每種品項需求數(shù)量較小，均為小型品項，各種品項都可在一個揀取動作中完成，即每種品項需求數(shù)大于1時，視為一個品項，可一次揀選完成。

假設3整個揀貨線上揀貨員的速度恒定且不同，揀貨員的行走速度與揀取速度一起并入揀貨速度中，其速度為νz，表示單位時間內(nèi)揀貨員z可揀選品項的數(shù)量，1≤z≤Z。用tz表示揀貨員z揀選每一品項所需要的時間，即tz=1/νz。

假設4一個揀貨動作只揀取一種品項，每次揀貨清單不會超過揀貨車載容積限制。

假設5品項是由訂單中挑選出來進行聚類群擺放到各個分區(qū)中，各分區(qū)的儲位不一定能擺滿品項。品項儲存位置唯一，品項儲位一經(jīng)擺放，在相對長一段揀貨周期內(nèi)都不會改變；且不允許缺貨發(fā)生。

根據(jù)假設，每一品項不論其出現(xiàn)在一張訂單還是多張訂單中，其均為獨立揀選，且每種品項的揀選次數(shù)等于該品項在不同訂單中出現(xiàn)的總次數(shù)。揀貨員在某訂單上花費的揀貨時間與該訂單在揀貨員所負責分區(qū)的品項種類有關。顯然，如果訂單需求的所有品項在不同分區(qū)中的分布可使得各分區(qū)揀貨作業(yè)時間趨于相同，則揀貨員的空閑時間將減少。但是訂單需求品項種類一般不同，各訂單在各分區(qū)的品項需求不同，數(shù)量也存在差異，且揀貨員的揀貨速度不同，從而導致品項均衡儲存的復雜性。因此，目標函數(shù)用數(shù)學模型表示為：

其中，式（1）為目標函數(shù)，式（2）表示揀貨員z的揀貨工作任務量，式（3）保證每一品項只能存放于一個分區(qū)中，式（4）為0-1決策變量。

模型中涉及的參數(shù)如下所示。

Z：揀貨區(qū)分區(qū)總數(shù)；n：揀貨區(qū)總品項數(shù)量；P：品項集，P={1，2，…，n}；O：訂單集；Qi：品項i在歷史訂單數(shù)據(jù)庫中的總需求次數(shù)；Q：配送中心揀貨員在歷史訂單數(shù)據(jù)庫中總揀貨次數(shù)；Nz：分區(qū)z中的所有品項集，Nz={n1，n2，…，nPz}；tz：揀貨員z揀選每一品項平均所需時間；：揀貨員z所用的總揀貨時間；：各分區(qū)平均揀貨時間；ρz：揀貨員z的總揀貨時間占各分區(qū)平均揀貨時間的比例；ρ：誤工率，即每個揀貨員完成其分區(qū)揀貨任務的時間的差異率之和；xiz：為儲位均衡指派方案的0-1變量，品項i被分配到第z個分區(qū)中，則xiz=1，否則xiz=0。

當揀貨員揀貨速度相同時，均衡分配各分區(qū)的作業(yè)量已為NP-難問題，無法獲得時間復雜度為問題規(guī)模的多項式時間精確算法，故只有尋找時間復雜度較小的近似算法或啟發(fā)式算法。下面通過分析訂單品項間的關系，設計結(jié)合品項關聯(lián)規(guī)則的儲位指派算法。

3 儲位指派算法

設P={1，2，…，n}為所有品項的集合，D為歷史訂單數(shù)據(jù)庫，O為訂單品項子集，O?P，每個訂單具有唯一的標志Oi，設A是由部分品項構(gòu)成的集合，稱為品項集，簡稱項集。訂單O中包含項集A，當且僅當A?O，如果項集A包含了k個品項，則稱其為k項集，或稱A的長度為k。

定義1品項集A的支持度。歷史訂單數(shù)據(jù)庫D中，支持品項集A的訂單數(shù)O稱為品項集A的支持數(shù)，記為Count(A)。設歷史訂單數(shù)據(jù)庫D中，總的訂單數(shù)為|D|，則品項集A的支持度為：Count(A)/|D|，記為S(A)。

在設計品項儲位指派算法時，同時希望經(jīng)常出現(xiàn)在同一張訂單中的品項分布在各個分區(qū)中，避免部分分區(qū)經(jīng)常出現(xiàn)無作業(yè)任務的情況。例如，品項集A中包含品項i和j，其支持度為S(A)，即品項i和j在同一種訂單中出現(xiàn)的概率Sij，Sij=S(A)，這里需要把支持度越大的品項儲存在不同的分揀區(qū)，以使訂單中的品項均衡分布在各分區(qū)中，從而每個揀貨員均有揀選任務，即

下面將根據(jù)歷史訂單庫D中的數(shù)據(jù)，尋找D中所有的頻繁關聯(lián)規(guī)則，找出所有頻繁項集。所謂頻繁關聯(lián)規(guī)則是指這些規(guī)則的支持度不低于預先給定的最小支持度，從而得到相應的頻繁項集。根據(jù)頻繁關聯(lián)規(guī)則及揀貨員的揀貨速度，設計結(jié)合品項關聯(lián)規(guī)則的儲位指派算法，均衡分派品項在各分區(qū)的存放，使訂單在各分區(qū)的揀貨時間均衡。

尋找關聯(lián)規(guī)則，首先根據(jù)配送中心揀貨系統(tǒng)品項及訂單特征，利用Excel試算表產(chǎn)生品項及歷史訂單數(shù)據(jù)。然后用基于頻繁模式樹FP-Tree的關聯(lián)分類規(guī)則挖掘算法FP-growth[17]對品項之間的關系進行挖掘，根據(jù)頻繁關聯(lián)規(guī)則及揀貨員的揀貨速度設計儲位分配算法。基于FP-tree的關聯(lián)規(guī)則挖掘算法FP-growth是將發(fā)現(xiàn)頻繁模式的問題轉(zhuǎn)換成遞歸地發(fā)現(xiàn)一些短模式，然后鏈接后綴。它使用最不頻繁的項目做后綴，提供了較好的選擇性，可顯著降低搜索開銷。

頻繁模式樹FP-tree的構(gòu)造涉及的參數(shù)主要有：FP-tree樹中，每個節(jié)點由4個域組成，是節(jié)點名稱node-name、節(jié)點計數(shù)node-count、節(jié)點鏈指針node-link和父節(jié)點指針node-parent。其中，node-name記錄節(jié)點所表示的品項名，node-count記錄該節(jié)點所表示品項被揀選的次數(shù)，node-link為指向FP-tree中具有相同的node-name值的下一節(jié)點，即通過node-link將FP-tree中具有相同node-name值的節(jié)點連接起來，node-parent為指向父節(jié)點的指針。另外，為了方便樹遍歷，創(chuàng)建一個頻繁項目頭表，它由兩個域組成：品項名稱node-name以及節(jié)點鏈頭node-head。其中，node-head為指向FP-tree中具有相同node-name值的首節(jié)點的指針。算法具體步驟描述如下：

4 算法性能測試

運用VB語言分別對AHACAR算法及隨機存儲策略算法編程。設計的大量算例在CPU為Intel Pentium Processor1.70 GHz的PC機上進行模擬運算，測試算法性能。揀貨區(qū)共有60種品項（SKU），每個訂單中的品項種類為5～12種，每種品項的需求量為1～5個。有5個揀貨區(qū)，由5個揀貨員負責，1個揀貨員負責1個揀貨區(qū)。揀貨員的揀貨速度同上，分別是0.22 min/品項，0.30 min/品項，0.35 min/品項，0.4 min/品項，0.48 min/品項。歷史訂單數(shù)據(jù)庫由Excel試算表產(chǎn)生每行不重復的介于1～60隨機數(shù)2 000行，列數(shù)介于5～12列，數(shù)字1～60分別代表品項P1～P60，從而產(chǎn)生歷史訂單數(shù)據(jù)庫結(jié)果。本算例產(chǎn)生的歷史訂單數(shù)據(jù)庫中，品項集合為：I={P1，P2，…，P60}，在此分別用數(shù)字代替各品項，如用“1”代替“P1”，品項集合可簡寫為I={1，2，…，60}，其中，任一品項集（itemset）為品項集I的子集合；該數(shù)據(jù)庫由2 000筆訂單交易D={O1，O2，…，O2000}所構(gòu)成，其中，Oi也是由I中任意品項的子集合所形成的交易資料。對數(shù)據(jù)庫資料統(tǒng)計分析后，其最大訂單項為12項，最小訂單項為7項，總揀貨次數(shù)為23 016次，由品項出現(xiàn)次數(shù)統(tǒng)計可以發(fā)現(xiàn)品項出現(xiàn)次數(shù)最高為705次，最低的品項113次。各品項的揀選率見表1；訂單與訂單品項關系圖及品項出現(xiàn)次數(shù)分別如圖2、圖3所示。

比較按單揀貨和批量揀貨兩種方式，每次批量作業(yè)為5個訂單進行合并，并與隨機存儲策略進行比較。為了評價優(yōu)化算法的優(yōu)化程度，定義績效改進為：

表1 品項在歷史數(shù)據(jù)庫中出現(xiàn)次數(shù)及揀選率（依次數(shù)遞減統(tǒng)計）

圖2 訂單與訂單品項關系圖

圖3 訂單品項出現(xiàn)次數(shù)統(tǒng)計圖

由于揀貨員每次揀取能力的限制，設每一品項不論其出現(xiàn)在一張訂單還是多張訂單中，其均為獨立揀選。即每種品項的揀選次數(shù)等于該品項在不同訂單中一共出現(xiàn)的次數(shù)，根據(jù)AHACAR算法對60中品項進行儲位安排，其揀貨效率模擬分析結(jié)果如表2所示，其中SD為訂單執(zhí)行率標準差。

表2 并行分區(qū)揀貨系統(tǒng)模擬測試結(jié)果

分析表2中的數(shù)據(jù)，不論按單揀選還是批量揀選，根據(jù)AHACAR算法安排的貨位，可明顯改善揀貨績效，如每批次揀選5個訂單，績效改進值從平均16.72%增加到平均31.99%。此外，對于并行分區(qū)揀貨系統(tǒng)，當結(jié)合分批策略后，即一次揀取多個訂單，AHACAR算法能顯著提高生產(chǎn)率。因為通過批量作業(yè)，可以對各分區(qū)的作業(yè)量均衡加以改善，如每批次8個訂單時比每批次5個訂單時，績效提高約1.04%，這主要是由于揀貨員一次處理的訂單越多，可以明顯減少各分區(qū)間的差異，減少等待時間使得揀貨效率越高；當然，超過一定限度適得其反，這主要是訂單批量的增加會導致分類時間的增加。

5 結(jié)論

本文考慮各分區(qū)揀貨員揀貨速度不等的情況，在分析該問題的基礎上建立目標規(guī)劃模型，結(jié)合品項揀選率及品項之間的關聯(lián)規(guī)則，設計啟發(fā)式算法，通過存儲策略的改進，使揀貨作業(yè)時間降低，提高了揀貨效率。與傳統(tǒng)的隨機存儲策略做對比，進行模擬測試，結(jié)果顯示結(jié)合品項關聯(lián)規(guī)則設計的AHACAR算法效果最好；研究各分區(qū)同時進行訂單揀貨作業(yè)的并行分區(qū)揀貨系統(tǒng)，應用AHACAR算法進行了模擬測試，分析顯示，將AHACAR算法與分批揀貨策略相結(jié)合，可顯著提高揀貨效率。

[1]Jane C C，Laih Y W.A clustering algorithm for item assignment in a synchronized zone order picking system[J].European Journal of Operational Research，2005，166（2）：489-496.

[2]王雄志.配送中心配貨作業(yè)計劃方法研究[D].廣州：暨南大學，2007.

[3]Rosenwein M B.An application of cluster analysis to the problem of locating items within a warehouse[J].IIE Transactions，1994，26（1）：101-103.

[4]De Koster R，Le-Duc T，Roodbergen K J.Design and control of warehouse order picking：a literature review[J].European Journal of Operational Research，2007，182（2）：481-501.

[5]Petersen C G.Considerations in order picking zone configuration[J].InternationalJournalofOperations&Production Management，2002，22（7/8）：793-805.

[6]Ho Y C，Wee H M，Chen H C.A geometric design of zonepicking in a distribution warehouse[C]//Proceedings of the International Conference on Computational Science and its Applications（ICCSA 2007），2007：625-636.

[7]Le-Duc T，De Koster R B M.Travel distance estimation and storage zone optimization in a 2-block class-based storage strategywarehouse[J].InternationalJournalofProduction Research，2005，43（17）：3561-3581.

[8]Parikh P J，Meller R D.Selecting between batch and zone order picking strategies in a distribution center[J].Transportation Research：Part E Logistics and Transportation Review，2008，44（5）：696-719.

[9]Brynzer H，Johansson M I.Design and performance of kitting and order picking systems[J].International Journal of Production Economics，1995，41（1/3）：115-125.

[10]李曉春，鐘雪靈，王雄志，等.配送中心動態(tài)分區(qū)揀貨系統(tǒng)優(yōu)化設計[J].華南師范大學學報：自然科學版，2011（3）：54-60.

[11]張貽弓.基于分區(qū)揀選策略的分揀機系統(tǒng)綜合優(yōu)化研究[D].濟南：山東大學，2011.

[12]王艷艷.并行自動分揀系統(tǒng)任務及補貨緩存優(yōu)化研究[D].濟南：山東大學，2012.

[13]盧少平，張貽弓，吳耀華，等.自動分揀系統(tǒng)并行分區(qū)揀選優(yōu)化策略[J].深圳大學學報：理工版，2010（1）：120-125.

[14]盧少平，張貽弓，吳耀華，等.自動揀選系統(tǒng)揀貨區(qū)數(shù)量與品項分配綜合優(yōu)化[C]//Proceedings of the International Conference on Computational Intelligence and Industrial Application（PACIIA），2010：461-467.

[15]李詩珍.基于工作量均衡的分區(qū)同步揀貨系統(tǒng)儲位分配與評價[J].包裝工程，2010（11）：114-118.

[16]李曉春.配送中心揀貨作業(yè)設計與優(yōu)化管理[D].廣州：暨南大學，2009.

[17]Han Jiawei，Pei Jian，Yin Yiwen.Mining frequent patterns without candidate generation[C]//Proceedings of 2000 ACM SIGMOD International Conference Management of Data，Dallas，TX，2000：1-12.

LI Xiaochun1,ZHONG Xueling2,WANG Xiongzhi3,WANG Guoqing4

1.Department of Information Engineering and Technology,Nanhai Campus,South China Normal University,Nanhai,Guangdong 528225,China
2.Department of Computer,Guangdong University of Finance,Guangzhou 510520,China
3.College of Economics and Management,South China Agriculture University,Guangzhou 510642,China
4.Management School,Jinan University,Guangzhou 510632,China

This paper studies a synchronized zone order picking system in distribution center,considering the picker has different speed,and proposes assignment heuristic algorithm to balance the pickers’workload in different zones by the item location arrangement.Meanwhile,simulated testing is taken to validate its performance and reliability of the algorithm,which provides a reference for the application and the choice of order picking methods.

distribution center;zone order picking;assignment heuristic algorithm;data mining

主要討論配送中心并行分區(qū)揀貨系統(tǒng)的特性，在各分區(qū)揀貨員揀貨速度不同的情況下，提出儲位指派算法，通過對品項在各分區(qū)間儲位的安排以平衡各分區(qū)揀貨員的作業(yè)量；根據(jù)揀貨作業(yè)規(guī)則和優(yōu)化目標，對相關模型及算法進行模擬測試以證明其有效性，為方法的選擇與應用提供了依據(jù)。

配送中心；分區(qū)揀貨；儲位指派算法；數(shù)據(jù)挖掘

A

TP391；F276.3

10.3778/j.issn.1002-8331.1304-0069

LI Xiaochun,ZHONG Xueling,WANG Xiongzhi,et al.Storage location assignment in synchronized zone order picking systems.Computer Engineering and Applications,2013,49（19）：20-24.

教育部人文社會科學研究項目（No.09YJC630088，No.13YJC630239）；華南師范大學南海校區(qū)資助項目（No.NHZL09006）。

李曉春（1983—），女，博士，講師，主要從事物流與供應鏈管理研究；鐘雪靈，博士，副教授；王雄志，博士，副教授；王國慶，博士，教授。E-mail：hellolxch@139.com

2013-04-07

2013-06-01

1002-8331（2013）19-0020-05

CNKI出版日期：2013-06-18http://www.cnki.net/kcms/detail/11.2127.TP.20130618.1559.004.html