臺灣博碩士論文加值系統

本研究以隨機權重多目標基因演算法為基礎設計應用於零散式揀貨倉庫系的啟發式儲貨指派方法。由於儲貨指派問題屬於非決定性多項式集合難題，無法找到最佳解，因此發展出許多啟發式演算法來尋找最佳近似解。 然而，很少有研究同時考慮多目標。本文提出的啟發式隨機權重多目標遺傳演算法以如何減少作業過程中因為缺貨而發生的緊急補貨作業及減少因各個揀貨區中工作量不平衡所導致生產線停滯問題這兩者為目標。在多目標基因演算法加上隨機權重係數可以使結果分散在多維目標空間中，以找出最優近似解，另外菁英保留策略使表現優良的染色體得以保存在菁英群體中，透過將菁英解加入每一個世代，使每一代染色體的水平提高，保留表現優良的基因。 最後，通過數據實驗建立模擬情境，將演算法的結果與隨機儲位指派方法和先到先服務儲位指派方法進行比較，其結果顯示本文所提出的方法優於比較對象。

This paper develops a storage assignment policy base on random weight multi-objective genetic algorithm for storage assignment problem (SAP) in a pick-and-pass warehouse system. Since SAP is an NP-hard problem, many heuristic algorithms have been proposed to find approximation solutions to the SAP. However, few research considered about simultaneously solving the multi-objective solution in SAP. The proposed heuristic random weight multi-objective genetic algorithm considered the workload balance between picking lines and emergency replenishment during picking operation. The random weight coefficient in the proposed algorithm can distribute the possible solution results in multi-dimensional objective space to help obtain the optimal solutions. Besides, the elite preserve strategy of our proposed genetic algorithm keeps the solutions with better performance in the elite solution group, further improving the quality and competitiveness of each solution generation. Finally, using data simulation, our proposed algorithm is compared with random and first-come-first-served assignment policies. The results from the simulation show that the proposed algorithm outperforms the ones with random and first-come-first-served assignment policies.

CONTENTS
摘要 I
ABSTRACT II
致謝 III
CONTENTS IV
TABLE INDEX VI
FIGURE INDEX VII
CHAPTER 1 INTRODUCTION 8
1.1 Research Background and Motivation 8
1.2 Research Objectives 9
1.3 Research Process 10
CHAPTER 2 LITERATURE REVIEW 12
2.1 Pick-and-Pass Warehouse System 12
2.2 Storage Assignment Problem (SAP) 13
2.3 Multi-Objective Genetic Algorithm 14
CHAPTER 3 DESCRIPTION OF PICKING OPERATIONS AND STORAGE ASSIGNMENT PROBLEM 17
3.1 Description of picking operation 17
3.2 Assumption and Notations 19
3.2.1 Assumption 19
3.2.2 Notations 19
3.3 A formulation model for the storage assignment problem 20
CHAPTER 4 DESIGN AND DEVELOPMENT OF HEURISTIC MULTI-OBJECTIVE GENETIC ALGORITHM FOR SAP IN PICK-AND-PASS WAREHOUSE SYSTEM 23
4.1 The storage space allocation 23
4.2 Heuristic Storage Assignment Based on Multi-Objective Genetic Algorithm 23
4.2.1 Encoding 24
4.2.2 Fitness function 26
4.2.3 Selection 27
4.2.4 Crossover 27
4.2.5 Mutation 27
4.2.6 Elite preserve policy 29
4.2.7 Termination criterion 30
4.2.8 Chromosome modification mechanism 30
4.3 Implementation of the proposed MOGA-based heuristic storage assignment algorithm 32
CHAPTER 5 34
NUMERICAL EXPERIMENT 34
5.1 Description of comparison 34
5.2 Analysis of numerical experiment 34
CHAPTER 6 40
CONCLUSIONS AND FUTURE RESEARCH 40
6.1 Conclusion 40
6.2 Future research 41
REFERENCES 42

REFERENCES

[1] Pierre, B., Vannieuwenhuyse, B., Dominanta, D., & Van Dessel, H. (2004). Dynamic ABC storage policy in erratic demand environments. Jurnal Teknik Industri, 5(1), 1-12..
[2] Bottani, E., Cecconi, M., Vignali, G., & Montanari, R. (2012). Optimisation of storage allocation in order picking operations through a genetic algorithm. International Journal of Logistics Research and Applications, 15(2), 127-146.
[3] Cai, J., Kuang, X. A., Song, S., & Zhao, Q. (2016, July). Automated warehouse storage assignment policy based on storage frequency and workload balance. In 2016 International Conference on Logistics, Informatics and Service Sciences (LISS) (pp. 1-6). IEEE.
[4] Coyle, J. J., Bardi, E. J., & Langley, C. J. (1996). The management of business logistics (Vol. 6). St Paul, MN: West publishing company.
[5] Dallari, F., Marchet, G., & Melacini, M. (2009). Design of order picking system. The international journal of advanced manufacturing technology, 42(1-2), 1-12.
[6] de Koster, R. (1994). Performance approximation of pick-to-belt orderpicking systems. European Journal of Operational Research, 72(3), 558-573.
[7] Deb, K., Agrawal, S., Pratap, A., & Meyarivan, T. (2000, September). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In International conference on parallel problem solving from nature(pp. 849-858). Springer, Berlin, Heidelberg.
[8] Fonseca, C. M., & Fleming, P. J. (1995). Multiobjective optimization and multiple constraint handling with evolutionary algorithms 1: A Unified formulation.
[9] Frazele, E. A., & Sharp, G. P. (1989). Correlated assignment strategy can improve any order-picking operation. Industrial Engineering, 21(4), 33-37.
[10] Guan, M., & Li, Z. (2018). Genetic Algorithm for Scattered Storage Assignment in Kiva Mobile Fulfillment System. American Journal of Operations Research, 8(6).
[11] Hajela, P., Lee, E., & Lin, C. Y. (1993). Genetic algorithms in structural topology optimization. In Topology design of structures(pp. 117-133). Springer, Dordrecht
[12] Schaffer, J. D. (1985). Multiple objective optimization with vector evaluated genetic algorithms. In Proceedings of the First International Conference on Genetic Algorithms and Their Applications, 1985. Lawrence Erlbaum Associates. Inc., Publishers.
[13] Chia Jane, C. (2000). Storage location assignment in a distribution center. International Journal of Physical Distribution & Logistics Management, 30(1), 55-71.
[14] Jewkes, E., Lee, C., & Vickson, R. (2004). Product location, allocation and server home base location for an order picking line with multiple servers. Computers & Operations Research, 31(4), 623-636.
[15] Kim, I. Y., & de Weck, O. L. (2005). Adaptive weighted-sum method for bi-objective optimization: Pareto front generation. Structural and multidisciplinary optimization, 29(2), 149-158.
[16] Knowles, J. D., & Corne, D. W. (2000). Approximating the nondominated front using the Pareto archived evolution strategy. Evolutionary computation, 8(2), 149-172.
[17] Koo, P. H. (2009). The use of bucket brigades in zone order picking systems. OR spectrum, 31(4), 759.
[18] Leung, K. H., Choy, K. L., Siu, P. K., Ho, G. T., Lam, H. Y., & Lee, C. K. (2018). A B2C e-commerce intelligent system for re-engineering the e-order fulfilment process. Expert Systems with Applications, 91, 386-401.
[19] Colón, L. A., Maloney, T. D., & Fermier, A. M. (2000). Packing columns for capillary electrochromatography. Journal of chromatography A, 887(1-2), 43-53.
[20] Muppani, V. R., & Adil, G. K. (2008). A branch and bound algorithm for class based storage location assignment. European Journal of Operational Research, 189(2), 492-507.
[21] Murata, T., & Ishibuchi, H. (1995, November). MOGA: Multi-objective genetic algorithms. In IEEE international conference on evolutionary computation (Vol. 1, pp. 289-294).
[22] Pan, J. C. H., & Wu, M. H. (2009). A study of storage assignment problem for an order picking line in a pick-and-pass warehousing system. Computers & Industrial Engineering, 57(1), 261-268.
[23] Pan, J. C. H., Shih, P. H., Wu, M. H., & Lin, J. H. (2015). A storage assignment heuristic method based on genetic algorithm for a pick-and-pass warehousing system. Computers & Industrial Engineering, 81, 1-13.
[24] Petersen, C. G. (2002). Considerations in order picking zone configuration. International Journal of Operations & Production Management, 22(7), 793-805.
[25] Petersen, C. G., & Aase, G. (2004). A comparison of picking, storage, and routing policies in manual order picking. International Journal of Production Economics, 92(1), 11-19.
[26] Petersen, C. G. (2002). Considerations in order picking zone configuration. International Journal of Operations & Production Management, 22(7), 793-805.
[27] rey Horn, J., Nafpliotis, N., & Goldberg, D. E. (1994, June). A niched Pareto genetic algorithm for multiobjective optimization. In Proceedings of the first IEEE conference on evolutionary computation, IEEE world congress on computational intelligence(Vol. 1, pp. 82-87).
[28] Thonemann, U. W., & Brandeau, M. L. (1998). Note. Optimal storage assignment policies for automated storage and retrieval systems with stochastic demands. Management Science, 44(1), 142-148.
[29] Yu, M., & De Koster, R. B. (2009). The impact of order batching and picking area zoning on order picking system performance. European Journal of Operational Research, 198(2), 480-490.
[30] Zitzler, E., & Thiele, L. (1998). An evolutionary algorithm for multiobjective optimization: The strength pareto approach. TIK-report, 43.