一種兩類貨到人訂單揀選系統(tǒng)機械工程學報六十年慶

1、一種兩類“貨到人”訂單揀選系統(tǒng)的適用性選擇方法王艷艷1 周以齊2 沈長鵬1 吳耀華1(1山東大學控制科學與工程學院 山東 濟南 250061； 2山東大學機械工程學院 山東 濟南 250061)摘要：本文提出了一種在兩類“貨到人”訂單揀選系統(tǒng)（即AS/RS系統(tǒng)和Carousel系統(tǒng)）之間，根據(jù)不同訂單類型進行系統(tǒng)適用性選擇的系統(tǒng)化方法。訂單揀選系統(tǒng)最常用的兩種作業(yè)策略分區(qū)策略和分批策略本質上都是對訂單的聚類，因此訂單可以被分為很多一維單元化網格；根據(jù)各系統(tǒng)的邏輯運動關系，可得到單元化網格的揀選時間表達式；利用作業(yè)時間模型和空間填充線，對單元化網格進行聚類，得到二維系統(tǒng)的總訂單揀選時間，并采用遺

2、傳算法、蟻群算法、粒子群算法三種常用智能算法分別計算各系統(tǒng)的最優(yōu)值；通過比較各系統(tǒng)的時間選擇更適用的系統(tǒng)，即選擇總訂單揀選時間更小的系統(tǒng)。本文通過對四類不同類型的訂單進行實驗研究，初步得出兩類系統(tǒng)對四類訂單的適用性分析和系統(tǒng)參數(shù)敏感性分析。關鍵詞：訂單揀選系統(tǒng)；貨到人；訂單網格化聚類；智能算法；適用性；選擇中圖分類號：F253.5An Applicability Selection Method of Two Parts-to-picker Order Picking SystemsWANG Yan-yan1 Zhou Yi-qi2 Shen chang-peng1 WU Yao-hua1 (

3、1 School of Control Science and Engineering, Shandong University, Jinan 250061, China；2 School of Mechanical Engineering, Shandong University, Jinan 250061, China )Abstract：A systemic method is presented to choose the suitable order picking system between AS/RS system and Carousel system for differe

4、nt types of customer orders. As both batching and zoning, the two frequently-used operational policies, are essentially order clustering, the customer order sheet can be divided into many unit grids. After the time formulation for each system in one-dimensional unit is defined according to the logic

5、al movements, we present a time sequence models for two-dimensional systems and use filling curves to link the one-dimensional unit grids. Three intelligence algorithms, which are genetic algorithm, ant colony optimization algorithm and particle swarm optimization algorithm, are adopted to search th

6、e optimal value for each system. In the experimental study, we not only get the suitability of each system for given orders with the hypothetic value of parameters by comparing the order picking time, but also discuss the effect of some key factors on suitability such as zone number and batch size.K

7、ey words：Order picking system; parts-to-picker; order cluster; intelligence algorithm; applicability; selection0 引言* 國家自然科學基金資助項目(50175064)。XXXXXXXX收到初稿，XXXXXXXX收到修改稿訂單揀選消耗了配送中心內的主要勞力，決定著對下游客戶的服務水平，是配送中心內部最重要的作業(yè)流程1。選擇合適的訂單揀選系統(tǒng)對于提高訂單揀選效率、提高客戶服務水平，有著至關重要的作用。文獻2將實踐中應用最多的采用人工的訂單揀選系統(tǒng)分為人到貨、推式、貨到人三類系統(tǒng)。其中，貨

8、到人揀選系統(tǒng)由于自動化程度較高、具有倉儲和分揀一體化的特點，已逐漸得到越來越多的應用。常用的貨到人揀選系統(tǒng)主要包括自動存儲及取貨系統(tǒng)（以下簡稱AS/RS系統(tǒng)）和旋轉式貨架系統(tǒng)（以下簡稱Carousel系統(tǒng)）。AS/RS多數(shù)系統(tǒng)采用巷道式提升機獲取一個或多個存貨單元，并運至巷道終端的揀選工位，由揀選員揀取所需數(shù)量的物品，剩余的將被送回至原存儲位3。Carousel系統(tǒng)由旋轉布置于雙向閉環(huán)上的大量料架或廚柜組成4，需要揀選物品時所有存儲位上的物品同時向揀選位運動。不同的揀選系統(tǒng)適應于不同的訂單類型。但是，目前對AS/RS系統(tǒng)和Carousel系統(tǒng)的研究主要集中在各自獨立的控制、調度、優(yōu)化、設計等方

9、面，對于兩者針對不同訂單的適用性比較研究還很缺乏。本文根據(jù)訂單揀選系統(tǒng)最常用的兩種作業(yè)策略（分批策略和分區(qū)策略）對訂單進行網格化聚類，并結合各系統(tǒng)的邏輯運動關系和作業(yè)時間模型，計算各系統(tǒng)的總訂單揀選時間，通過比較時間選擇更適用的系統(tǒng)（即時間更小的系統(tǒng)）；本文還通過對四類不同類型的訂單進行實驗研究，初步得出兩類系統(tǒng)對四類訂單的適用性分析和系統(tǒng)參數(shù)敏感性分析。1 訂單網格化聚類1.1 作業(yè)策略訂單揀選系統(tǒng)實際應用時可采用不同的作業(yè)策略，作業(yè)策略不同則所需的訂單揀選時間也不同。因此訂單揀選系統(tǒng)比選時，各系統(tǒng)均須在相同條件下選擇各自最優(yōu)的策略再進行比較。與訂單揀選系統(tǒng)相關的作業(yè)策略包括分區(qū)、分批、倉儲

10、、布局、路徑、合單及分揀等5，其中布局、路徑、合單及分揀與配送中心和訂單揀選系統(tǒng)的具體尺寸密切相關，在系統(tǒng)選擇階段沒有各類具體尺寸的前提下，重點應考慮的策略是分區(qū)、分批和倉儲策略。1.2 基于訂單網格化的分區(qū)和分批策略分區(qū)策略是指將揀選區(qū)劃分為很多區(qū)，每個區(qū)指派一名揀選員負責本區(qū)的揀選工作。常用的分區(qū)策略包括串行分區(qū)和并行分區(qū)，“貨到人”揀選系統(tǒng)適用并行分區(qū)，即各區(qū)的揀選員同時揀選一個或一批訂單行，各自的揀選完成后再開始下一個或下一批訂單行的揀選。分批策略是指將多個訂單行合并為一個批次，在一個行走過程中完成本批所有訂單行的揀選。分區(qū)策略和分批策略本質上都是對訂單表的聚類，分區(qū)是將物品聚類到一個

11、區(qū)內，分批是將訂單行聚類到一個批次內。應用分區(qū)和分批策略后，訂單表可以被劃分為M行N列的網格，如圖1所示。圖1 網格化聚類的訂單本文用(m,n)表示第m行第n列的網格，即第m批訂單行和第n個物品分區(qū)，其中1mM，1nN。同時，定義表示每個訂單行的序號，表示每個物品的序號。1.3 基于COI的倉儲策略本文用Heskett提出的單位訂單行容積指標COI，來進行每個分區(qū)內的儲位分配優(yōu)化6。COI是某物品所需倉儲空間和被訂購頻次的比值，如公式（1）所示；物品按照COI進行升序排列，并按非降序從開始端逐個進行儲位分配。 (1)其中，是物品j所需的空間，是物品j被各訂單行訪問的總次數(shù)。可由Barthold

12、i提出的Fluid模型進行求解7。Fluid模型證明了為保證最少的從倉儲區(qū)到揀選區(qū)的補貨次數(shù)，物品j在分揀區(qū)所需空間的比例應為：(2)其中，為每個物品j的年銷量。則本文定義物品j所需的空間為：(3)其中，為的平均值；為和比值后取整；若，則設。2 系統(tǒng)作業(yè)時間建模2.1 訂單揀選作業(yè)時間構成根據(jù)某些調查，訂單揀選時間可分解為行走、尋找、揀取、安裝及其他等時間8，如表1所示。表1 訂單揀選作業(yè)時間構成活動所占總時間比例行走50%尋找20%揀取15%安裝10%其他5%對于“貨到人”訂單揀選系統(tǒng)，尋找、安裝及其他活動可以忽略，行走和揀取是構成訂單揀選作業(yè)時間的主要活動。2.2 一維單元化網格的作業(yè)時間

13、2.2.1 AS/RS系統(tǒng)的一維作業(yè)時間自動堆垛機可采用不同的作業(yè)模式：單命令循環(huán)、雙命令循環(huán)和多命令循環(huán)。單命令循環(huán)是指一個存貨單元從揀選位運至存儲位或者從存儲位運至揀選位。雙命令循環(huán)是指一個存貨單元從揀選位運至存儲位，然后下一個存貨單元從貨架上獲取。多命令循環(huán)是指自動堆垛機具有一個以上的叉伸位，可以在一個循環(huán)獲取或存放多個存貨單元9。本文選擇實際應用最多的雙命令循環(huán)模式作為AS/RS系統(tǒng)的應用策略。圖2 AS/RS系統(tǒng)的運動邏輯AS/RS系統(tǒng)在一維網格(m,n)中的作業(yè)時間為：(4)其中，為網格(m,n)的揀選時間；為第n個區(qū)內物品的品種數(shù)；為堆垛機在第m批訂單行、第k次行程取貨時的行走時

14、間；為在倉儲位取貨的時間；為堆垛機從取貨位到揀選位的行走時間；為揀取物品的時間；為堆垛機從揀選位返回取貨位的行走時間；為物品被揀選的位置；為每物品倉儲位的長度；為堆垛機行走速度；為每類物品的取貨時間；為(m,n)內的物品品種數(shù)；為每個物品的揀取時間；為(m,n)內的物品個數(shù)。2.2.2 Carousel系統(tǒng)的一維作業(yè)時間在Carousel系統(tǒng)中，所有存儲位上的物品同時向揀選位運動，所以從存儲位到揀選位的距離總體上要小于AS/RS系統(tǒng)，尤其是所需物品的存儲位相鄰時更為明顯。由于Carousel系統(tǒng)可雙向旋轉，可采用的旋轉策略主要有兩種：單向旋轉SD策略和最近物品NI策略。SD策略是指Carous

15、el總是按照一個方向進行旋轉，而這個方向是由第一次揀選時距離揀選位最近的需揀選物品的位置決定的； NI策略是指Carousel總是以揀選位為基準，向最近的需揀選的物品旋轉。文獻10證明了NI策略下的行走時間永遠不大于SD策略下的行走時間，因此我們采用NI策略。圖3 Carousel系統(tǒng)的運動邏輯Carousel系統(tǒng)在一維網格(m,n)中的作業(yè)時間為：(5)其中，為網格(m,n)的揀選時間；為第n個區(qū)內物品的品種數(shù)；為第m批訂單行、第k次行程取貨時所需物品從倉儲位到揀選位的行走時間；為揀取物品的時間；為物品被揀選的位置；為每物品倉儲位的長度；為旋轉貨架的旋轉線速度；為每個物品的揀取時間；為(m,

16、n)內的物品個數(shù)。2.3 二維系統(tǒng)的總體作業(yè)時間2.3.1 基于空間填充線的二維系統(tǒng)利用空間填充線可將一維的單元化網格連接為二維或三維系統(tǒng)11。本文以二維系統(tǒng)為研究對象，“貨到人”系統(tǒng)采用并行分區(qū)策略后的二維系統(tǒng)布局，如圖4所示。圖4 “貨到人”系統(tǒng)的二維系統(tǒng)布局2.3.2 二維作業(yè)時間模型“貨到人”系統(tǒng)采用并行分區(qū)策略，各分區(qū)可以有兩種并行作業(yè)模式：一種是所有分區(qū)全部完成某批訂單行的揀選后再開始下一批訂單行的揀選，另一種是本分區(qū)完成某批訂單行的揀選后就開始下一批訂單行的揀選。本文選用前一種作業(yè)模式，具體模型如圖5所示。圖5 “貨到人”系統(tǒng)的并行作業(yè)時間模型由模型知，每一批訂單行的累積作業(yè)時間

17、為：(6)第一批訂單行的累積作業(yè)時間為： (7)則，二維系統(tǒng)的總訂單揀選時間為： (8)3 目標函數(shù)與遺傳算法3.1 目標函數(shù)以效率為標準，顯見應當選擇耗時最少的系統(tǒng)作為優(yōu)選方案。我們以兩種系統(tǒng)同等條件下各自最優(yōu)的總訂單揀選時間的比值為判斷標準。之所以選擇最優(yōu)的總訂單揀選時間作為比較的因素，是因為在現(xiàn)實應用中，任何一種系統(tǒng)都會合理使用分區(qū)、分批等各種作業(yè)策略以使自身的總訂單揀選時間趨于最優(yōu)。 (9)其中，、分別為AS/RS、Carousel系統(tǒng)的最優(yōu)的總訂單揀選時間。當R>1時，選擇Carousel系統(tǒng)；反之，選擇AS/RS系統(tǒng)。R越大，則選擇Carousel系統(tǒng)的趨勢越大；反之，則更該

18、選擇AS/RS系統(tǒng)。對于AS/RS、Carousel系統(tǒng)總訂單揀選時間公式里的各參數(shù)，, , , 由訂單揀選系統(tǒng)本身決定，而, , , 由訂單聚類方式決定。對于給定的訂單揀選系統(tǒng)，參數(shù), , , 為常量，因此尋求訂單揀選系統(tǒng)最優(yōu)的總訂單揀選時間的途徑是尋找最合理的, , , ，即最優(yōu)的訂單聚類方式。3.2 智能算法最優(yōu)的總訂單揀選時間與最優(yōu)的訂單聚類方式之間存在何種邏輯關系很難直接數(shù)理推導，只能通過啟發(fā)式算法去探求。本文采用遺傳算法、蟻群優(yōu)化算法、粒子群優(yōu)化算法三種常用的啟發(fā)式智能算法來獲取最優(yōu)的訂單聚類方式，進而求得最優(yōu)的總訂單揀選時間。客戶訂單實質上可以看作是由若干行訂單和若干列物品組成的

19、矩陣，該矩陣進行如圖1所示的網格化聚類后，將得到如圖6所示的“訂單/物品”矩陣。圖6 “訂單/物品”矩陣其中，表示矩陣中的某個單元化網格，即第n個分區(qū)內的第m批訂單；, 表示第i個訂單行所在單元化網格的批次編號，其取值為，M表示訂單批次的數(shù)量；, 表示第j個物品所在單元化網格的分區(qū)編號，其取值為，N表示物品分區(qū)的數(shù)量。為方便地表示“訂單/物品”矩陣的變化，我們用I+J位的一維編碼表示I行J列的二維矩陣，如下所示。當?shù)趇位或第j位編碼的值發(fā)生變化時，表示訂單行i所屬的批次或物品j所屬的分區(qū)發(fā)生變化，即矩陣的聚類發(fā)生變化；此時對應的目標函數(shù)值即訂單揀選時間。通過搜索最優(yōu)的一維編碼值的組合，就可以尋

20、得最優(yōu)的訂單揀選時間。3.2.1 遺傳算法遺傳算法的優(yōu)化機理與本問題的特性非常匹配，一維編碼相當于遺傳算法中的基因，訂單揀選時間相當于適度函數(shù)。設和為基因，則可以組成具有I+J個基因的染色體。為尋找適度函數(shù)的近似最優(yōu)解，可按如下步驟執(zhí)行遺傳算法。（1）初始化。隨機產生一組個體作為初始種群，每個個體對應于一組一維編碼，即一個訂單聚類方式。（2）評價。計算種群中每個個體的適應函數(shù)值，即總訂單揀選時間函數(shù)。（3）選擇。運用輪盤賭規(guī)則選取擁有最低適應函數(shù)值的多個個體，并賦予作為下一代父輩的更高的概率。（4）交叉。按照一定的交叉概率，在“選擇”操作后的種群中兩兩選取兩個個體作為父輩，兩個父輩均從和的交界

21、處切開，每個父輩的前半部分與另外一個父輩的后半部分組合。（5）變異。按照一定的變異概率，在“交叉”操作后的種群中選取用于變異的個體，并給所選取個體的某個基因賦予另外一個可行的值。（6）替換。在完成選擇、交叉、變異后，如發(fā)現(xiàn)更低的適應函數(shù)值，則對最不適合的父輩用其子輩替換掉。（7）重復。從第2步開始重復，當?shù)螖?shù)達到上限時遺傳算法終止。3.2.2 蟻群優(yōu)化算法蟻群優(yōu)化算法同樣可以用于求解最優(yōu)的一維編碼和最優(yōu)的訂單揀選時間；一維編碼相當于螞蟻尋找食物的路徑，各位編碼相當于螞蟻每一步所經歷的各個節(jié)點（可重復），最小的訂單揀選時間是蟻群尋找的食物，訂單揀選時間值為適度函數(shù)，本文設最小的訂單揀選時間為

22、0并以迭代上限次數(shù)為終止條件。（1）初始化。給信息素矩陣賦一個相同的常數(shù)值，給禁忌表賦一個隨機初始值。（2）路徑選擇。每個螞蟻在第一步選擇要經歷的節(jié)點時，根據(jù)概率進行選擇，概率與信息素有關，信息素越大，則被選擇的概率越大；當所有的螞蟻選擇完編碼以后，開始選擇下一個編碼，直到所有螞蟻完成一次周游為止，即每只螞蟻均有一個一維編碼。每只螞蟻的路徑存于禁忌表中。（3）根據(jù)螞蟻的路徑（即一維編碼），計算所有螞蟻的適度函數(shù)值。尋找本次迭代的局部最優(yōu)函數(shù)值和路徑。（4）進行全局信息素更新：子代的信息素按照適度函數(shù)值的倒數(shù)增加，同時子代的信息素相對于父代的信息素按照固定的衰減比率進行衰減。（5）禁忌表清零。（

23、6）循環(huán)，直到迭代次數(shù)達到上限。3.2.3 粒子群優(yōu)化算法粒子群優(yōu)化算法根據(jù)粒子的速度來尋求最優(yōu)解；一維編碼相當于粒子尋找食物的方向，訂單揀選時間值相當于粒子尋找食物的速度；在粒子群優(yōu)化算法中，粒子具有記憶性，只有速度最大的粒子給出方向信息給其他的粒子，整個搜索更新過程是跟隨當前最優(yōu)解的過程。（1）初始化。給粒子群中的每個粒子賦一個隨機初始方向即一維編碼的值。（2）速度計算。計算出本代中每一個粒子尋找食物的速度，即一維編碼所對應的訂單揀選時間值距離最小訂單揀選時間0的遠近，訂單揀選時間值越小表明粒子的速度越大。（3）粒子選擇。比較本代速度最大粒子（即局部最優(yōu)解）與全局速度最大粒子（即全局最優(yōu)解

24、）的速度值，速度更大（即訂單揀選時間更?。┑牧Ｗ訉⒆鳛樾碌娜炙俣茸畲蟮牧Ｗ?。（4）信息傳遞。將全局速度最大粒子的方向作為下一代粒子群的主要方向，并允許一定的隨機選擇；本文以全局最大速度粒子的每一位一維編碼值為均值，按照正態(tài)分布確定下一代各粒子的一維編碼值。（5）記憶表更新。將全局速度最大的粒子的方向（即一維編碼）和速度值（訂單揀選時間值）存入記憶表中。（6）循環(huán)，直到迭代次數(shù)達到上限。4 實驗研究4.1 輸入分析4.1.1 試驗訂單為評價系統(tǒng)對于不同訂單的適用性，本文根據(jù)訂單密度（即訂單中累計被訂購品種數(shù)占累計總品種數(shù)的比例，亦即訂單矩陣中非0的比例）和訂購數(shù)量（即被訂購品種所被訂購的數(shù)量范

25、圍）產生了四種典型訂單。對每種訂單，我們均假設有大客戶、大品牌的存在，即假設訂單行和物品均服從于正態(tài)分布，如圖7所示。圖7 各類訂單的物品服從正態(tài)分布訂單的主要參數(shù)如表2所示。表2 訂單的主要參數(shù)因素值訂單行數(shù)400物品種數(shù)400訂單密度20%, 80%訂購數(shù)量1, 1100.5m4.1.2 系統(tǒng)參數(shù)訂單揀選系統(tǒng)的參數(shù)對訂單揀選時間的影響很大。為保證公平的比較，我們設置多數(shù)參數(shù)具有相同的值，如表3所示。表3 揀選系統(tǒng)的主要參數(shù)參數(shù)單位AS/RS系統(tǒng)Carousel系統(tǒng)s22s10s11m0.50.5單批訂單行數(shù)1,2,3,4,5物品分區(qū)數(shù)2,3,4,5,64.1.3 算法參數(shù)通過測試比較多組值

26、，我們設定了求解效果較優(yōu)的遺傳算法的參數(shù)值，如表4所示。表4 遺傳算法的主要參數(shù)參數(shù)值種群10迭代次數(shù)100交叉概率0.8變異概率0.01表5 蟻群優(yōu)化算法的主要參數(shù)參數(shù)值種群10迭代次數(shù)100信息素蒸發(fā)系數(shù)0.5表6 粒子群優(yōu)化算法的主要參數(shù)參數(shù)值種群10迭代次數(shù)100精英原則正態(tài)分布4.2 輸出分析4.2.1 系統(tǒng)適用性分析根據(jù)設置的參數(shù)值和實驗訂單，進行仿真后，得到兩系統(tǒng)揀選時間的比值R，通過比較R與1的大小，就可以判斷實驗訂單對于兩種系統(tǒng)的適用性。對于本例中的所有實驗訂單，R均大于1，所以Carousel是更加適合的揀選系統(tǒng)，如圖8所示。事實上，在實際應用中AR/RS系統(tǒng)更多的是作為倉

27、儲系統(tǒng)使用，而不是作為揀選系統(tǒng)使用。AS/RS系統(tǒng)要作為揀選系統(tǒng)有更廣泛的應用，需要做某些改進，如：某類國外醫(yī)藥企業(yè)較多采用的AS/RS系統(tǒng)，每層貨架都有一個堆垛機，大大提高了分區(qū)策略的應用，總的訂單揀選時間大大降低。此外，通過觀察R值大小可見，訂單密度越大、揀選數(shù)量越小的訂單越適合選用Carousel系統(tǒng)。圖8 各類訂單的適用性和敏感性4.2.2 參數(shù)敏感性分析通過觀察每條曲線的相對位置和自身斜率，我們可以發(fā)現(xiàn)：分區(qū)數(shù)量N越大，則R越小，則越適合采用AS/RS系統(tǒng)；分批數(shù)量M越大（即每批次所含的訂單行越少），則R越大，則越適合采用Carousel系統(tǒng)。同時，對比R值的變化幅度，可以發(fā)現(xiàn)：分區(qū)

28、策略比分批策略對系統(tǒng)選擇的影響更加顯著。5 結論與研究展望通過實驗研究，我們可以發(fā)現(xiàn)本方法不僅能夠較好地應用于系統(tǒng)的選擇，還可以用于主要參數(shù)的敏感性分析。粗略地講，對于經典的AS/RS系統(tǒng)和Carousel系統(tǒng)，Carousel系統(tǒng)更適用于多數(shù)訂單；而且，訂單的訂單密度越大、揀選數(shù)量越小，則越適合采用Carousel系統(tǒng)。此外，一些主要參數(shù)如分區(qū)數(shù)量、分批數(shù)量等對于系統(tǒng)的選擇具有一定的影響，其中分區(qū)數(shù)量M的影響顯著。本方法的不足是需要一定的時間開發(fā)系統(tǒng)和運行計算。如果通過測試大量的實驗訂單或實際訂單能夠發(fā)現(xiàn)某些定律或指標，那么我們就可以通過短時間內對訂單的觀察來決定系統(tǒng)的選取。潛在的定律可以用

29、訂單行數(shù)、物品品種數(shù)、訂單密度、訂購數(shù)量、物品或周轉箱尺寸、訂單行和物品的分布函數(shù)等參數(shù)來進行描述。參考文獻：1. BURINSKIENE A. Order picking process at warehousesJ. International Journal of Logistics Systems and Management, 2010, 6(2):162-782. DALLARI F, MARCHET G, MELACINI M. Design of order picking systemJ. International Journal of Advanced Manufactu

30、ring Technology, 2009, 42:1-123. MANZINI R, GAMBERI M, REGATTIERI A. Design and control of an AS/RSJ. International Journal of Advanced Manufacturing Technology,2006,28:766-7744. BATHOLDI J J, PLATZMAN L K. Retrieval strategies for a carousel conveyorJ. IIE Transaction, 1986, 18:166-1735. KOSTER R D, LE D T, ROODBERGEN K J. Design and control of warehouse order picking: A literature reviewJ. European Journal of Operational Research, 2007, 182