訂單與貨架選擇於機器人智動揀貨系統 之最佳化初探

Investigation of Optimal Order and Pod Selection in Robotic Mobile Fulfillment Systems

潘芎旂(Chiung-Chi Pan)

指導教授 ： 林則孟 ； 黃建中

國立清華大學/工學院/工業工程與工程管理學系/碩士(2020年)

摘要

機器人智動揀貨系統(Robotic Mobile Fulfillment System, RMFS)系統為一新型貨到人倉儲系統，利用搬運車搬運可移動式貨架至工作站，讓揀貨人員揀貨，並主要應用於電子商務產業。RMFS系統的揀貨決策包含兩階段：任務產生以及任務指派與完成。考量揀貨流程的決策有順序性，越前段所做的決策會對揀貨績效有越大的影響，故本研究欲針對第一階段的任務產生做進一步的探討。
本研究探討主機板產業物流中心的RMFS之揀貨應用，其揀貨特色為：訂單量少、品項需求多且揀貨量多，並且相較於電商產業，需求較易預測。本研究考慮訂單需求量與貨架存量的限制，進行訂單與貨架選擇決策的最佳化。在已知多張訂單來到單一工作站揀貨下，以最小化選擇貨架總距離為目標，同步決定訂單的揀貨順序、貨架來到順序以及品項揀貨量。本研究建構混整數規劃進行求解，證明其為NP困難的問題，並使用best-first branch and bound進行搜尋，其中h值估計上本研究延伸set cover問題提出Interger property與Ratio property、剪枝策略則藉由貨架庫存與訂單需求的關係減少搜尋路徑，分枝策略為依照節點的揀貨狀態分為訂單與貨架分枝，藉由實驗驗證求解效率優於Gurobi算法。
實驗分析上，發現本研究方法對訂單數量以及貨架數量之參數敏感度高，隨著訂單數量增加，可求解的品項與貨架數量隨之減少，進一步的探討3張訂單的情境，將庫存總品項增加至2000種。有兩大發現，第一為在貨架數量與庫存品項增加下，求解時間並無顯著成長，原因為訂單數量少，容易產生可以使用剪枝策略的情況，減少搜尋節點，使求解效率加快；第二為隨著庫存品項與貨架數的增加，可成功求解的資料筆數減少，主要原因在於若無法使用剪枝策略，貨架分枝會產生大量節點，造成暫存空間不足，無法求解。

關鍵字

主機板產業倉儲 ； 機器人智動揀貨系統 ； 貨架選擇 ； 分枝定界

並列摘要

The Robotic Mobile Fulfillment System (RMFS) system is a new type of cargo-to-person warehousing system. It uses mobile robots to transport movable pods to workstations, allowing pickers to pick up goods, and is widely used in the e-commerce industry. The order picking process consists of two phases: “task generation” and “task assignment and completion”. Since order picking process is completed by sequential decisions and the decisions in the first phase have greater impact on the performance of order picking, task generation decisions are further discussed.
The orders in the computer industry warehouse usually requires large amount and many different types of items, and there are few orders every day. Comparing to e-commerce warehouse, demand in the computer industry warehouse is easier to be predicted.
Consider the quantity of order demand and inventory, this study aims to optimize order and pod selection problem. We focus on the picking process in single workstation, where all orders arrive at a time, with the goal of minimizing the total distance of the selected pods. We formulize the problem using mix integer programming and prove that this is an NP-hard problem and apply best-first branch and bound algorithm to optimize the problem. The result proves that the computation time of improved B&B outperforms Gurobi solver.
With regard to the characteristics of computer industry warehouse, we further discuss the case under 3 orders with at most 2000 inventory items. There are two major findings. The first is that the computational time does not increase significantly while the number of shelves and inventory items increase. Because the number of orders are small, and it can use the pruning rule more often, which speeds up the solving. The second is that as the number of inventory items increases, numbers of data that can be solved decreases. Seeing that pod branching may generate massive amount of nodes, which leads to the result of memory error.

並列關鍵字

Warehouse of computer industry ； Robotic Mobile Fulfillment System ； Pick pod selection ； Best-first branch and bound

參考文獻

[1] 鈴木震(1995)，如何利用EIQ 法來進行配送中心系統規劃，中國生產力中心講義

[2] Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to linear optimization (Vol. 6): Athena Scientific Belmont, MA.

[3] Boysen, N., Briskorn, D., & Emde, S. (2017). Parts-to-picker based order processing in a rack-moving mobile robots environment. European Journal of Operational Research, 262(2), 550-562. doi:10.1016/j.ejor.2017.03.053

[4] Dechter, R., & Pearl, J. (1985). Generalized Best-First Search Strategies and the Optimality of A. Journal of the ACM (JACM), 32(3), 505-536. doi:10.1145/3828.3830

[5] Enright, J. J., & Wurman, P. R. (2011). Optimization and coordinated autonomy in mobile fulfillment systems. Paper presented at the Workshops at the Twenty-Fifth AAAI Conference on Artificial Intelligence.