并行分區揀貨系統儲位優化設計

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

1.華南師范大學南海校區信息工程與技術系，廣東南海 528225

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

3.華南農業大學經濟管理學院，廣州 510642

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

并行分區揀貨系統儲位優化設計

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

1.華南師范大學南海校區信息工程與技術系，廣東南海 528225

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

3.華南農業大學經濟管理學院，廣州 510642

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

1 引言

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

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

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

圖1 并行分區揀貨系統示意圖

2 儲位策略優化模型

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

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

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

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

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

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

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

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

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

模型中涉及的參數如下所示。

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

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

3 儲位指派算法

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

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

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

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

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

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

4 算法性能測試

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

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

表1 品項在歷史數據庫中出現次數及揀選率（依次數遞減統計）

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

圖3 訂單品項出現次數統計圖

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

表2 并行分區揀貨系統模擬測試結果

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

5 結論

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

[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]王雄志.配送中心配貨作業計劃方法研究[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]李曉春，鐘雪靈，王雄志，等.配送中心動態分區揀貨系統優化設計[J].華南師范大學學報：自然科學版，2011（3）：54-60.

[11]張貽弓.基于分區揀選策略的分揀機系統綜合優化研究[D].濟南：山東大學，2011.

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

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

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

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

[16]李曉春.配送中心揀貨作業設計與優化管理[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

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

配送中心；分區揀貨；儲位指派算法；數據挖掘

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）；華南師范大學南海校區資助項目（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