寧方華，何超群，李英德

(1.浙江理工大學機械與自動控制學院，杭州 310018；2.浙江工業(yè)大學機械工程學院，杭州 310014)

貨到人作業(yè)模式下的魚骨型布局貨位優(yōu)化

寧方華1，何超群1，李英德2

(1.浙江理工大學機械與自動控制學院，杭州 310018；2.浙江工業(yè)大學機械工程學院，杭州 310014)

為提高揀選效率，針對貨到人模式的揀選特點，在魚骨型布局中提出了基于品項相關性和貨架相關性的貨位優(yōu)化方法。首先根據(jù)品項的相關性和訂購頻次劃分品項簇，建立以最小化揀選路程為目標的貨位分配模型，然后設計基于貨架相關性的禁忌搜索算法(TS_SC)求解模型。該算法根據(jù)訂單體積指數(shù)方法(COI)生成初始解，應用交換方式將相關性強的貨架就近存儲，縮短揀選路程。實驗結果表明：相較于禁忌搜索算法，該算法收斂速度快，尋優(yōu)能力強；相較于COI方法，該算法可有效減少貨架搬運次數(shù)26.3%～39.6%，縮短揀選路程34.2%～48.6%。因此充分利用品項相關性和貨架相關性進行貨位優(yōu)化，有利于提高貨到人模式下的揀選效率。

魚骨型布局；貨到人；貨位優(yōu)化；相關性

隨著物流自動化的推進，貨到人揀選模式逐漸受到物流配送中心的重視。在物流配送中心的各項作業(yè)中，訂單揀選時間占配送中心總作業(yè)時間的40%以上，揀選成本占總運營成本的65%以上，訂單揀選消耗了配送中心的主要勞動力，是作業(yè)過程中最重要的流程[1]。因此高效的揀選作業(yè)可以提高配送中心的揀選效率，而貨位優(yōu)化是提高揀選效率的有效方法[2]。在基于移動式貨架的貨到人揀選模式中，貨架處于運動狀態(tài)，揀選人員固定在揀選臺旁，AGV小車根據(jù)系統(tǒng)指令到達指定貨架下，舉起貨架，將貨架搬至指定揀選臺前。由于揀選過程中AGV小車代替人工進行作業(yè)，極大地提高了物流揀選效率[3]。

貨位優(yōu)化研究中應用基于周轉率和相關性的分配原則較多。其中基于周轉率的貨位分配研究起步較早，如Peterse等[4]提出了以品項所需倉儲空間和被訂購頻次的比值為貨位分配原則，Bernhard等[5]提出了ABC分類存儲原則，該分配原則在需求不相關的情況下優(yōu)化顯著。考慮相關性的貨位優(yōu)化方法是將相關性強的品項指派到相近的貨位中，如Mamzini[6]提出了在人至物揀貨模式中獲取相關性關系的3個啟發(fā)式規(guī)則，李英德等[7]針對穿越策略下分區(qū)分批揀貨時品項間相關性關系，提出了貨位指派優(yōu)化方法。

考慮品項相關性、訂購頻次的分配原則也適用于貨到人作業(yè)模式，如：李珍萍等[8]根據(jù)訂單中兩種圖書出現(xiàn)的次數(shù)，定義了兩種圖書之間的相關性，并以最大化同一貨架上圖書之間的平均關聯(lián)度為目標建立了數(shù)學模型；周方圓等[9]根據(jù)貨品的訂購頻次對物品進行聚類分組，并以總揀選成本最小化為目標確定了每個貨架擺放的物品。應用品項相關性和訂購頻次對貨位進行優(yōu)化，降低了揀選成本、提高了揀選效率。但在貨到人作業(yè)模式中，貨架可移動且AGV小車可以在貨架下行走，因此貨位優(yōu)化時不僅要將相關性強訂購頻次高的品項存儲于一個貨架中，減少貨架搬運次數(shù)，還應將相關性強的貨架就近擺放，減少AGV小車的行走路程。

本文研究貨到人作業(yè)模式下的貨位優(yōu)化問題。首先根據(jù)訂單信息，按品項的訂購頻次和相關性劃分品項簇，將相關性強且訂購頻次高的品項簇存儲于一個貨架，并以最小化揀選路程為目標建立數(shù)學模型；然后設計TS_SC算法求解貨位優(yōu)化模型，將相關性強的貨架就近存放，從而減少貨架搬運次數(shù)，縮短揀選路程，提高作業(yè)效率。

一、問題描述與模型構建

(一)貨位優(yōu)化問題描述

傳統(tǒng)的倉庫布局一般由平行揀選巷道和與之垂直的橫向通道構成，但Pohl等[10]、Roodbergen等[11]研究指出：橫向通道不僅減少了貨物的存儲面積，尤其當一人揀選多位時增加了揀選貨物的路程。針對傳統(tǒng)布局方法的不足，Gue等[12]提出了魚骨型倉儲布局(如圖1所示)，魚骨型布局由對角方向的中間通道、上方的垂直揀選巷道(區(qū)域2)、下方的水平揀選巷道(區(qū)域1、3)組成。該布局方法與傳統(tǒng)的倉儲布局相比，可減少20%左右的揀選路程，因此本文中的貨架采用魚骨型布局進行擺放。

圖1 魚骨型布局的貨到人揀選模式注：← →表示AGV小車往返于貨架與揀選臺。

在魚骨型布局中，采用基于可移動式貨架的貨到人揀選模式。揀選過程中，AGV小車根據(jù)控制系統(tǒng)的指令到達待揀選品項所在的貨架下，舉起貨架搬運至指定的揀選臺，揀選人員根據(jù)訂單信息依次完成揀選任務，揀選完成后AGV小車根據(jù)指令移動至下一個揀選臺或將貨架搬回原始位置，從而開始下一個揀選任務，而空載的AGV小車可在貨架下行走。對于單行訂單，揀選人員直接將品項推至復核包裝環(huán)節(jié)，而多行訂單揀選人員需將品項先放入周轉箱中，待訂單揀選完成后再將周轉箱轉至復核包裝環(huán)節(jié)。

(二)貨位優(yōu)化模型

針對貨到人作業(yè)模式的特點，貨位優(yōu)化的目標有：a)最大化貨架內品項的相關性，減少貨架的搬運次數(shù)，其中兩個品項同時出現(xiàn)在一個訂單中，那么這兩個品項相關，出現(xiàn)的次數(shù)越多，相關性越強；b)最大化貨架間的相關性，減少AGV在貨架間的行走路程，其中一個訂單需揀選兩個貨架，那么這兩個貨架相關，兩組貨架共同完成的訂單數(shù)量越多，相關性越強。

根據(jù)以上目標，分兩步對品項進行貨位優(yōu)化：

a)根據(jù)訂單信息將品項相關性強且訂購頻次高的品項劃分為一簇，建立以揀選路程最小化為目標的數(shù)學模型；

b)根據(jù)貨架相關性，設計求解貨位優(yōu)化模型的TS_SC算法，將相關性強的貨架就近存放。

本文采用劉華婷等[13]提出的Apriori_LB算法對品項進行聚類。針對貨到人作業(yè)模式的特點，應用該算法時將最后的頻繁集降序排列后以貨架的存儲位數(shù)為閾值進行分組，使相關性強、訂購頻次高的品項盡量分配在一個貨架中。

在聚類基礎上，建立數(shù)學模型。模型假設：a)AGV小車從點st出發(fā)并最終回到st點；b)AGV小車按逆時針方向到各個揀選臺進行揀選作業(yè)；c)每個儲位上存放的物品數(shù)量足夠每次揀選作業(yè)；d)每個貨架只能存儲一個品項簇；e)每個品項簇只能被指派到一個貨架；f)揀選時AGV選擇最近的貨架進行搬運。

引入以下參數(shù)與變量：I為品項總數(shù)，品項編號為i=1,2,3,…,I；J為品項簇總數(shù)，品項簇編號為j=1,2,3,…,J；M為揀選通道總數(shù)，揀選通道編號為m=1,2,3,…,M；N為貨架編號總數(shù)，貨架編號為n=±1,±2,±3,…,±N；Q為揀選臺總數(shù)，揀選臺編號為q=1,2,3,…,Q；S為U型線的路程；f為揀選區(qū)域的長度；p為揀選區(qū)域，編號p=1,2,3；b為貨架的長度；w為對角通道在水平和垂直方向的寬度；dv為垂直通道在對角通道方向的距離，dh為水平通道在對角通道方向的距離；α為對角通道傾斜的角度；Fj,j+1表示AGV小車揀選完品項簇j后去往下一個品項簇的路程；Hn：如果貨架n為AGV小車第一個或最后一個搬運對象，其值為3，否則為2；Gnq,如果貨架n訪問了揀選臺q，其值為1，否則為0。

決策變量xjpmn：如果品項簇j被指派到第p個揀選區(qū)域第m個揀選通道的第n個貨架，其值為1，否則為0。

由圖1中AGV小車揀選A、B、C三個貨架的路線可知，AGV小車的行走路程分為三部分：往返于貨架與揀選臺的路程(虛線所示)、往返于揀選臺間的路程(實線所示)、去往下一個貨架的路程(點線所示)。

(1)

目標函數(shù)：

(2)

約束條件：

(3)

(4)

(5)

xjpmn,Gnq∈(0,1)

(6)

Hn∈(3,2)

(7)

模型中，式(2)表示以最小化揀選路程D為目標；式(3)表示每個貨架只能存放一個品項簇；式(4)表示一個品項簇只能存放在一個貨架上；式(5)表示一個訂單至少需要搬運一個貨架；式(6)和式(7)表示相關變量的取值范圍。

二、貨位優(yōu)化方法

將品項簇指派到合適的位置上，相當于裝箱問題，可應用禁忌搜索算法進行求解。算法采用禁忌策略回避搜索過程陷入局部最優(yōu)的狀況，應用特赦準則釋放一些優(yōu)良的禁忌對象，提高了搜索效率和解質量[14-15]。因此本文在禁忌搜索算法(tabu search,TS)的基礎上，提出了基于貨架相關性的禁忌搜索算法(tabu search considering shelf correlation，TS_SC)。該算法根據(jù)貨架相關性設計鄰域結構，應用交換貨架位置的策略將相關性強的貨架指派到相近且距離揀選臺近的位置來提高揀選效率。

該算法的具體步驟如下：

第1步：設定最大迭代次數(shù)T、候選解集數(shù)量β、禁忌長度值η等參數(shù)，應用COI(cube-per-order index)方法產生初始解C0，令當前解C=C0，置空禁忌表。

初始解：統(tǒng)計每類品項簇的訂購頻次，根據(jù)訂購頻次進行儲位指派，其中訂購頻次高的品項簇存放在距離揀選臺近的貨架上，同一通道內訂購頻次高的品項簇存儲于距離通道入口近的貨架上。

禁忌表：存放禁忌對象的容器，放入禁忌表中的禁忌對象只有被解禁后才能被再次搜索。

第2步：判斷是否達到最大迭代次數(shù)要求t=T，如果達到，則算法結束，輸出結果；否則，轉至下一步。

第3步：根據(jù)當前解C的鄰域結構生成鄰域解，并從中確定β個候選解C′。

鄰域結構：在當前解的基礎上，應用移動策略產生一定數(shù)目的新解。TS算法的鄰域結構為品項簇隨機排序生成的表格，隨機生成兩個品項簇編號,交換編號對應的品項簇，多次進行該步驟產生鄰域解。TS_SC算法采用基于貨架相關性的鄰域結構，即根據(jù)訂單信息，統(tǒng)計任意兩個品項簇的相關性強度，刪除重復數(shù)據(jù)，將剩余的數(shù)據(jù)排列，在算法搜索過程中以隨機方式選擇其中一對品項簇，進行位置交換。

第4步：判斷候選解是否滿足特赦準則。將滿足DC-DC,<0的最佳狀態(tài)C′替換C成為新的當前解，并將C′對應的禁忌對象替換最早進入禁忌表的禁忌對象，同時用C′替換“best so far”的狀態(tài)，得到當前最優(yōu)解C*=C′，令C=C*，然后轉至第6步；否則，轉第5步。

禁忌對象：加入禁忌表的禁忌對象需設置禁忌長度值，搜索中每迭代一次，各禁忌對象的禁忌長度值自動減1，當禁忌長度值為0時，則刪除該禁忌對象。

第5步：判斷候選解C′對應各對象的禁忌情況，選擇候選解集中非禁忌對象對應的最佳狀態(tài)成為新的當前最優(yōu)解C*=C′，令C=C*，并用與之對應的禁忌對象替換最早進入禁忌表的禁忌對象。

第6步：t=t+1,轉第2步。

三、算法測試與分析

為分析考慮相關性對揀選效率的影響以及算法的效果，設計如下實驗：隨機生成一組訂單，對比TS算法，分析驗證TS_SC算法的優(yōu)越性；隨機生成多組不同數(shù)量的訂單和貨架儲位組合數(shù)據(jù)，對比COI方法分析相關性對揀選效率的影響。

在VS 2010環(huán)境下實現(xiàn)COI方法、TS算法、TS_SC算法求解貨位優(yōu)化問題的測試程序。在WIN8 64Bit操作系統(tǒng)、8GB內存和Intel(R) Core(TM) i5-4200(2.29GHz)環(huán)境下進行實驗，基本參數(shù)設置如表1所示。

表1 基本參數(shù)

(一)算法性能測試

隨機生成250張訂單，每張訂單隨機包含1～15個訂單行，貨架存儲貨位數(shù)為8。利用表1數(shù)據(jù)對TS算法和TS_SC算法進行收斂性、運行速度測試結果如圖2所示?？梢钥闯觯?/p>

a)收斂性：兩種算法都能收斂于某點。TS_SC算法約迭代至320代達到平衡，相對于TS算法迭代450代達到平衡，收斂速度得到了改善，可見基于相關性的貨位搜索策略提高了算法的收斂速度，縮短了檢索時間。

b)尋優(yōu)能力：TS_SC算法的尋優(yōu)能力要好于TS算法。TS_SC算法得到的總揀選距離是2.75 km，相對于TS算法解2.94 km縮短了6.9%。TS_SC算法采用基于相關性的品項簇交換策略進行移動搜索，提高了搜索效率；同時使較差個體得到改善，增強了算法的尋優(yōu)能力。

圖2 兩種算法基本性能測試結果

(二)揀選效率

為檢驗TS_SC算法的優(yōu)越性，設計不同訂單數(shù)量f=600、800、1000，貨架存儲位數(shù)nog=8、12、16的實驗組合，對比根據(jù)訂貨頻次對品項進行聚類劃分，按照品項簇訂購頻次的高低決定存放距離揀選臺遠近貨架的COI方法，實驗運行不同訂單數(shù)量和存儲位數(shù)排列組合后的揀選過程，取貨架搬運次數(shù)、最優(yōu)解的平均值。其中LCOI、LTS_SC分別表示COI、TS_SC算法的貨架搬運次數(shù)，DCOI、DTS_SC表示COI、TS_SC方法求解出貨位優(yōu)化后的總揀選路程。

1.貨架搬運次數(shù)

a)訂單數(shù)量與貨架搬運次數(shù)實驗結果曲線見圖3，由圖3可知，當貨架存儲貨位的數(shù)量一定時，貨架搬運次數(shù)(LCOI、LTS_SC)隨著訂單數(shù)量的增長而趨于平緩；說明訂單數(shù)量越多，品項相關性越明顯，貨架搬運次數(shù)相對減少。

圖3 訂單數(shù)量與搬運次數(shù)

b)貨架存儲位數(shù)與搬運次數(shù)實驗結果曲線見圖4，由圖4可知，當訂單數(shù)量一定時，貨架搬運次數(shù)(LCOI、LTS_SC)隨著貨架存儲位數(shù)量的增大而減少；說明貨架儲位越多，貨架相關性越強，貨架搬運次數(shù)越少。

圖4 貨架存儲位數(shù)與搬運次數(shù)

c)COI、TS_SC方法求解的貨架搬運次數(shù)結果見圖5，由圖5可知，在不同存儲位數(shù)、訂單數(shù)量的組合情況下，相較于COI方法，TS_SC方法減少了26.3%～39.6%的貨架搬運次數(shù)。

圖5 兩種算法求解的貨架搬運次數(shù)注：三組數(shù)據(jù)的訂單數(shù)量依次是600、800、1000張。

2.揀選路程

由圖6(a)揀選次數(shù)與揀選距離可知，在相同訂單數(shù)和貨架儲位數(shù)時，TS_SC方法的揀選路程(DTS_SC)普遍低于COI方法求解的揀選路程(DCOI)。由圖6(b)優(yōu)化結果看出，相較于COI方法，TS_SC算法縮短了34.2%～48.6%的揀選路程。由此說明，TS_SC方法對提高揀選效率有顯著效果。

圖6 兩種算法求解的揀選路程注：三組數(shù)據(jù)的訂單數(shù)量依次是600、800、1000張。

四、結 論

本文研究了貨到人作業(yè)模式下魚骨型布局中的貨位優(yōu)化問題，根據(jù)品項的訂購頻次和相關性進行聚類，建立了以最小化揀選路程為目標的數(shù)學模型，提出了TS_SC算法，并隨機生成一批訂單，對算法性能和效果進行實驗。結果表明：a)相較于TS算法，TS_SC算法具有較快的收斂速度，較優(yōu)的尋優(yōu)能力；b)隨著訂單的增長，品項相關性越明顯；c)隨著貨架存儲數(shù)量的增多，貨架相關性增強，貨架的搬運次數(shù)減少，訂單完成率提高；d)相較于COI方法，TS_SC方法減少了貨架搬運次數(shù)，縮短了搬運路程，提高了揀選效率。

后續(xù)研究將考慮以最少的貨架和最優(yōu)的貨位分配來提高揀選效率，進一步降低成本。

[1] 吳穎穎,孟祥旭,王艷艷,等.“貨到人”揀選系統(tǒng)訂單排序優(yōu)化[J].機械工程學報,2016,52(4):206-212.

[2] KOSTER R D, DUC T L,ROODBERGEN K J. Design and control of warehouse order picking: A literature review[J].European Journal of Operation Reserch,2007,182(2):481-501.

[3] 鄒爽心.倉儲機器人的應用現(xiàn)狀與發(fā)展戰(zhàn)略探討[J].物流工程與管理,2013,35(6):171-172.

[4] PETERSE C G, AASE G R, HEISER D R. Improving order picking performance through the implementation of class-based storage[J].International Journal of Physical and Logistical Management,2004,34(7):534-544.

[5] BERMHARD F, ANDREAS K. Distribution Logistics: Advanced Solutions to Practical Problems [M].Berlin: Springer,2005:185-200.

[6] MAMZINI R. Correlated storage assignment in an order picking system[J]. International Journal of Industrial Engineering,2006,13(4):1675-1692.

[7] 李英德,魯建廈,潘國強.穿越策略下考慮相關性的貨位優(yōu)化方法[J].浙江大學學報(工學版),2012,46(8):1424-1430.

[8] 李珍萍,李文玉.網上書店智能倉庫系統(tǒng)儲位優(yōu)化研究[J].物流技術,2014,23:340-342.

[9] 周方圓,李珍萍.基于“貨到人”揀選模式的儲位分配模型與算法[J].物流技術,2015,34(9):242-246.

[10] POHL L M, MELLER R D, GUE K R. An analysis of dual-command operations in common warehouse designs[J]. Transportation Research Part E Logistics & Transportation Review,2009,45(3):367-379.

[11] ROODBERGEN K J, KOSTER R D. Routing order pickers in a warehouse with a middle aisle[J]. European Journal of Operational Research,2001,133(1):32-43.

[12] GUE R K, MELLER D R. Aisle configurations for unit-load warehouses[J]. IIE Transactions,2009,41(3):171-182.

[13] 劉華婷,郭仁祥,姜浩.關聯(lián)規(guī)則挖掘Apriori算法的研究與改進[J].計算機應用與軟件,2009,26(1):146-149.

[14] 王凌.智能優(yōu)化算法及其應用[M].北京:清華大學出版社,2001:62-82．

[15] 董宗然,周慧.禁忌搜索算法評述[J].軟件工程師,2010(s1):96-98.

(責任編輯： 康 鋒)

Study on Slotting Optimization of Fishbone Layout Based on Rack-to-Picker Mode

NINGFanghua1,HEChaoqun1,LIYingde2

(1.Faculty of Mechanical Engineering & Automation, Zhejiang Sci-Tech University, Hangzhou 310018, China; 2.College of Mechanical Engineering,Zhejiang University of Technology, Hangzhou 310014, China)

In order to improve the picking efficiency of the rack-to-picker picking mode, this paper puts forward slotting optimization method based on SKUs correlation and shelf correlation in the fishbone layout. Firstly, the SKU clusters were divided according to the SKUs correlation and the order frequency, and slotting allocation mode with the goal of minimizing picking route was established. Then, tabu search algorithm based on shelf correlation (TS-SC) was designed to solve the mathematical model. The algorithm generates the initial solution according to the COI solution and applies the way of exchange to store the shelves with strong correlation to shorten the picking route. The results show that compared with tabu search algorithm, this algorithm has faster rate of convergence and stronger optimization ability. Compared with COI method, this algorithm can effectively reduce the number of rack movements from 26.3% to 39.6% and shorten picking route from 34.2% to 48.6%. So, making the best of SKUs correlation and shelf correlation for slotting optimization contributes to improving picking efficiency under rack-to-picker mode.

fishbone layout; rack-to-picker; slotting optimization; correlation

10.3969/j.issn.1673-3851.2017.08.002

2016-11-22 網絡出版日期：2017-03-28

寧方華(1978-)，女，山東泰安人，副教授，主要從事物流與供應鏈管理、生產系統(tǒng)建模與仿真方面的研究。

TP399

A

1673- 3851 (2017) 04- 0293- 06