臺灣博碩士論文加值系統

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

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.

ABSTRACT i
摘要 ii
致謝 iii
Table of Contents iv
List of Tables vi
List of Figures viii
Chapter 1 Introduction 1
1.1 Overview and Research Motivation 1
1.2 Research Problems 1
1.3 Research Objective 3
1.4 Thesis Organization 3
Chapter 2 Literature Review 5
2.1 Order Picking 6
2.1.1 Order Batching 6
2.2 Genetic Algorithms 15
2.2.1 Chromosome Encoding 17
2.2.2 Population Initialization 18
2.2.3 Fitness Function 18
2.2.4 Selection Mechanism 19
2.2.5 Crossover Mechanism 21
2.2.6 Mutation Mechanism 23
2.2.7 Stopping Criteria 24
Chapter 3 Research Method 25
3.1 Assumptions and Overview of the Proposed Method 26
3.2 Warehouse Description 28
3.3 Model Definition 30
3.4 The Multiple-GA Method 35
3.4.1 The GA_BATCH Algorithm 36
3.4.1.1 Solution Encoding 39
3.4.1.2 Population Initialization 39
3.4.1.3 Fitness Function 39
3.4.1.4 Selection Mechanism 40
3.4.1.5 Crossover Mechanism 40
3.4.1.6 Mutation Mechanism 41
3.4.1.7 Surviving Mechanism 41
3.4.1.8 Stopping Criteria 41
3.4.1.9 Penalty Mechanism 41
3.4.2 The GA_TSP Algorithm 42
3.4.2.1 Solution Encoding 43
3.4.2.2 Fitness Function 43
3.4.2.3 Crossover Mechanism 44
3.5 A Simple Example for Heuristic Verification 45
Chapter 4 Empirical Results and Discussion 62
4.1 Description of User Interface 62
4.1.1 Order Information Interface 63
4.1.2 The Optimal Order Picking Plan Interface 64
4.2 Sensitivity Analysis 65
4.2.1 Data Settings of the Simulation Experiment 65
4.2.2 The Parameter Settings of GA_BATCH and GA_TSP 66
4.2.3 The s, α, β Ratio 70
4.2.4 The Discussion of s, α, β Combination 74
4.2.5 The Discussion of Batch Number 76
4.2.6 The Discussion of Batching Approaches 78
4.2.7 The Discussion of Order Density 80
Chapter 5 Simulation Experiments 83
5.1 Data of the Test Examples 83
5.2 Computation Result 84
5.3 Comparison of Multiple-GA, Model2, and Model3 98
Chapter 6 Conclusions and Future Researches 102
6.1 Conclusions 102
6.2 Future Researches 103
References 104

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.

Chen, M. C., Huang, C. L., Chen, K. Y., and Wu, H. P., 2005, Aggregation of orders in distribution centers using data mining, Expert Systems with Applications, 28, pp. 453-460.

Chen, M. C., and Wu, H. P., 2005, An association-based clustering approach to order batching considering customer demand patterns, Omega-International Journal of Management Science, 33, pp. 333-343.

Cordon, O., Herrera, F., Hoffmann, F., Magdalena, L., 2001, Genetic fuzzy systems: evolutionary tuning and learning of fuzzy knowledge bases, World Scientific, Singapore.

Coyle, J. J., Bardi, E.J., and Langley Jr., C. J., 1996, The Management of Business Logistics, 6th ed., West Publishing Company, New York.

David A. Taylor, 2004, Supply Chains: A Manager’s Guide, Addison Wesley.

Davis, L., 1985, Applying adaptive algorithms to domains, In Proceedings of the International Joint Conference on
Artificial Intelligence, pp. 162-164.

Elsayed, E. A., 1981, Algorithms for optimal material handling in automatic warehousing systems, International Journal of Production Research, vol. 19, no. 5, pp. 525-535.

Elsayed, E. A., and Lee, M. K., 1996, Order processing in automated storage/retrieval systems with due dates, IIE Transactions, vol. 28, no. 7, pp. 567-577.

Elsayed, E. A., Lee, M. K., Kim, S., and Scherer, E., 1993, Sequencing and batching procedures for minimizing earliness and tardiness penalty of order retrievals, International Journal of Production Research, vol. 31, no. 3, pp. 727-738.

Elsayed, E. A., and Stern, R. G., 1983, Computerized algorithm for ordering in automated warehousing systems, International Journal of Production Research, vol. 21, no. 4, pp. 579-586.

Elsayed, E. A., and Unal, I. O., 1989, Order batching algorithms and travel time estimation for automated storage/retrieval systems, International Journal of Production Research, 27, pp. 1097-1114.

Gademann, A. J. R. M., Jeroen, P. Van Den Berg, and Hassan, H. Van Der Hoff, 2001, An order batching algorithm for wave picking in a parallel-aisle warehouse, IIE Transactions, vol. 33, no. 5, pp. 385-398.

Gen, M., and Cheng, R., 1997, Genetic Algorithms and Engineering Optimization, Wiley, New York.

Gen, M., and Cheng, R., 2000, Genetic Algorithms and Engineering Optimization, Wiley, New York.

Gen, M. and Kim, J. R., 1999, GA-based reliability design: State-of-the-art survey, Computers & Industrial
Engineering, vol. 37, no. 1-2, pp. 151-155.

Gibson, D. R., and Sharp, G. P., 1992, Order batching procedures, European Journal of Operational Research, vol. 58, no. 1, pp. 57-67.

Goetschalckx, M., and Ratliff, H. D., 1988b, An efficient algorithm to cluster order picking items in a wide aisle, Engineering Cost and Production Economics, vol. 13, no. 1, pp. 263-271.

Goldberg, D., Lingle, R., 1985, Alleles, loci, and the traveling salesman problem, In Grefenstette, J., editor, Proceedings of the First International Conference on
Genetic Algorithms, Lawrence Erlbaum Associates, Hillsdale, NJ, pp. 154-159.

Holland, J., 1975, Adaptation in Natural and Artificial Systems, University of Michigan Press.

Hsu, C. M., Chen, K. Y., and Chen, M. C., 2005, Batching orders in warehouses by minimizing travel distance with genetic algorithms, Computers in Industry, 56, pp. 169-178.

Hu, X. B., and Chen, W. H., 2005, Genetic algorithm based on receding horizon control for arrival sequencing and scheduling, Engineering Applications of Artificial Intelligence, vol. 18, no. 5, pp. 633-642.

Hwang, H., Bake, W., and Lee, M. K., 1988, Clustering algorithms for order picking in an automated storage and retrieval systems, International Journal of Production Research, vol. 26, no. 2, pp. 189-201.

Hwang, H., and Lee, M. K., 1988, Order batching algorithms for a man-on-board automated storage and retrieval system, Engineering Cost and Production Economics, 13, pp. 285-294.

Hwang, H. S., 2002, An improved model for vehicle routing problem with time constraint based on genetic algorithm, Computers & Industrial Engineering, vol. 42, no. 2-4, pp. 361-369.

Koster, M. B. M. DE, Pooft, E. S. VAN DER, and Wolters, M., 1999, Efficient order batching methods in warehouses, International Journal of Production Research, vol. 37, no. 7, pp. 1479-1504.

Kusiak, A., Vanelli, A., and Kumar, K. R., 1986, Clustering analysis: models and algorithms, Control and Cybernetics, 15, pp. 139-153.

Lee, K. Y., Han, S. N., and Roh, M. I., 2003, An improved genetic algorithm for facility layout problems having inner structure walls and passages, Computers & Operations Research, vol. 30, no. 1, pp. 117-138.

Liang, J. C., 1998, A study on the order picking policies in automated storage/retrieval system by genetic algorithm, Department of Industrial Engineering and Management Yuan Ze University.

Man, K. F., Tang, K. S., and Kwong, S., 1999, Genetic Algorithms, Springer, London.

Onwubolu, G. C., and Mutingi, M., 2001, A genetic algorithm approach to cellular manufacturing systems, Computers & Industrial Engineering, vol. 39, no. 1-2, pp. 125-144.

Pan, C. H., 1996, Order batching heuristics based on spacefilling curves, Journal of the Chinese Institute of Industrial Engineers, vol. 13, no. 2, pp. 127-133.

Pan, C. H., and Liu, S. Y., 1995, A comparative study of order batching algorithms, Omega, vol. 23, no. 6, pp. 691-700.

Rana, K., 1991, Order-Picking in Narrow-Aisle Warehouse, International Journal of Physical Distribution & Logistics Management, vol. 20, no. 2, pp. 9-15.

Roodbergen, K. J., and de Koster, R., 2001, Routing methods for warehouses with multiple cross aisles, International Journal of Production Research, vol. 39, no.9, pp. 1865-1883.

Rosenwein, M. B., 1996, A comparison of heuristics for the problem of batching orders for warehouse selection, International Journal of Production Research, vol. 34, no. 3, pp. 657-664.

Sadegheih, A., 2006, Scheduling problem using genetic algorithms, simulated annealing and the effects of parameter values on GA performance, Applied Mathematical
Modelling, vol. 30, no. 2, pp.147-154.

Sanchez, E., Shibata, T., Zadeh, L. A., 1997, Genetic algorithms and fuzzy logic systems: soft computing perspectives, World Scientific Pub., River Edge, NJ.

Shi, Z. B., 2004, 揀貨中心之訂單批量揀取策略研究, Institute of Industrial Management National Central University.

Su, C. T., and Li, G.. R., 2002, Reliability design of distribution systems using modified genetic algorithms, Electric Power Systems Research, vol. 60, no. 3, pp. 201-206.

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

Syswerda, G., 1989, Uniform crossover in genetic algorithms. In Proceedings of the Third International Conference on Genetic Algorithms, pp. 2-8, Morgan Kauffman.

Tan, K. C., Lee, L. H., Zhu, Q. L., and Ou, K., 2001, Heuristic methods for vehicle routing problem with time windows, Artificial Intelligence in Engineering, vol. 15, no. 3, pp. 281-295.

Tseng, Y. Y., 2003, 物流中心之訂單批次化與揀貨路徑問題探討, Institute of Industrial Management National Central University.

Van den Berg, J. P., 1999, A literature survey on planning and control of warehousing systems, IIE Transactions, 31, pp. 751-762.

Vinod, H. D., 1969, Integer programming and the theory of grouping, Journal of the American Statistical Association, 64, pp. 506-515.

Wang, L. H., 1999, An integrated storage assignment and order picking sequencing model for distribution centers, Graduate School of Management National Taiwan University of Science and Technology.

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

Wu, H. P., 2002, Order consolidation via data mining techniques for distribution centers, Graduate Institute of Commerce Automation and Management Nation Taipei University of Technology.

Zolfaghari, S., and Liang, M., 2003, A new genetic algorithm for the machine/part grouping problem involving processing times and lot sizes, Computers & Industrial Engineering, vol. 45, no. 4, pp. 713-731.