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

2、傳算法、蟻群算法、粒子群算法三種常用智能算法分別計算各系統的最優值；通過比較各系統的時間選擇更適用的系統，即選擇總訂單揀選時間更小的系統。本文通過對四類不同類型的訂單進行實驗研究，初步得出兩類系統對四類訂單的適用性分析和系統參數敏感性分析。關鍵詞：訂單揀選系統；貨到人；訂單網格化聚類；智能算法；適用性；選擇中圖分類號：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收到修改稿訂單揀選消耗了配送中心內的主要勞力，決定著對下游客戶的服務水平，是配送中心內部最重要的作業流程1。選擇合適的訂單揀選系統對于提高訂單揀選效率、提高客戶服務水平，有著至關重要的作用。文獻2將實踐中應用最多的采用人工的訂單揀選系統分為人到貨、推式、貨到人三類系統。其中，貨

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、訂單行數、物品品種數、訂單密度、訂購數量、物品或周轉箱尺寸、訂單行和物品的分布函數等參數來進行描述。參考文獻：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