應用多階遺傳演算法於批次揀貨問題：同時考量旅行距離與訂單期限

Using A Multiple-GA Approach to Solve Batch-picking Problem: Considering the Travel Distance and Order Due Time

黃婷媺(Ting-Mei Huang)

指導教授 ： 蔡介元

元智大學/工程學院/工業工程與管理學系/碩士(2006年)

https://doi.org/10.6838/YZU.2006.00222

摘要

倉儲管理是增強公司物流的重要關鍵之一。而有效的批次揀取，更可以有效地提升倉儲系統的揀貨效率。雖然過去也有許多學者針對此議題提出了許多建議，然而探討的問題主要著重於較小規模的訂單問題或是在簡單的倉儲環境內；此外，過去所提出的方法，不是單獨考量如何減少旅行距離（旅行時間），就是單獨考量如何根據訂單到期日，以計算出最佳揀貨順序。然而過去所提出的這些方法，較難適用於現今複雜且以快速回應為導向的倉儲環境。
因此，本研究提出一個同時考量旅行距離與訂單期限的多階遺傳演算法，以最小化總成本（旅行成本+早到和晚到成本），有效地將需要被撿取的品項分批，藉此解決倉儲系統內複雜的批次揀貨問題。而為了驗證本研究所提出方法的效益，另外兩個分批方法被提出做為比較。最後，並以六個不同訂單規模和倉儲環境的測試例題，分別代表不同的實際狀況，去驗證是否被提的方法適應於任何批次撿取問題。實驗結果顯示，本研究所提出應用於批次揀貨問題的多階遺傳演算法，在各種訂單規模和倉儲環境組合下，均可達到較高的分批效益。

關鍵字

批次撿取 ； 倉儲 ； 遺傳演算法

並列摘要

Warehouse management is one of the critical keys to strengthen company logistics. Effective batch picking operations can increase the productivity of a warehouse. To attain better batch picking efficiency, previous researches mainly focus on the problems of smaller order size and specific warehouse layouts. In addition, their methods either consider travel cost or earliness and tardiness penalty separately. These drawbacks make these methods hard to be adopted in current complex and quick-response oriented environment.
In this thesis, we develop a multiple-GA (Genetic Algorithm) method, which consider both travel cost and earliness and tardiness penalty, for automatically grouping the required items into batches to solve the complex batch picking problem in the warehouse systems. Performance comparisons between the proposed multiple-GA approach and other two heuristic methods are given for various problems including small-, medium- and large-size batch picking problems. Based on the experiment result, the proposed multiple-GA approach is more effective in solving the batch picking problems in terms of solution quality.

並列關鍵字

Batch picking ； Warehouse ； Genetic algorithms

參考文獻

Su, T. S., 2002, Optimizing order picking in distribution centers, Institute of Industrial Management National Central University.

Wu, C. R., 1998, The development and comparison of heuristic of order batching and picking, Department of Business Administration National Chung Cheng University.

Adel El-Baz, M., 2004, A genetic algorithm for facility layout problems of different manufacturing environments, Computers & Industrial Engineering, vol. 47, no. 2-3, pp. 233-246.

Armstrong, R. D., Cook, W. D., and Saipe, A. L., 1979, Optimal batching in a semi-automated order picking system, Journal of the Operational Research Society, vol. 30, no. 8, pp. 711-720.

Bartholdi, J. J., and Platzman, L. K., 1982, An O (N log N) planar traveling salesman heuristic based on spacefilling curves, Operations Research Letters, vol. 1, no. 4, pp. 121-125.