研究生: |
郭俊麟 Chun-Lin Kuo |
---|---|
論文名稱: |
應用蟻群演算法於雙深式自動化倉儲之最佳化排程 Applying Ant Colony Optimization to Optimal Scheduling in Double-Deep AS/RS |
指導教授: |
徐勝均
Sheng-Dong Xu |
口試委員: |
蔡協致
Hsieh-Chih Tsai 李俊賢 Jin-Shyan Lee 杜佳穎 Jia-Ying Tu |
學位類別: |
碩士 Master |
系所名稱: |
工程學院 - 自動化及控制研究所 Graduate Institute of Automation and Control |
論文出版年: | 2015 |
畢業學年度: | 103 |
語文別: | 中文 |
論文頁數: | 85 |
中文關鍵詞: | 自動化倉儲系統 、雙深式 、蟻群演算法 、最佳化排程 |
外文關鍵詞: | Automated Storage and Retrieval Systems (AS/RS), Double-Deep, Ant Colony Optimization, Optimal Scheduling |
相關次數: | 點閱:459 下載:2 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
近年來,自動化倉儲系統(Automated Storage and Retrieval System, AS/RS)解決了傳統倉儲系統土地資源浪費、作業速度較慢與儲存成本較高的問題。因自動化倉儲需要快速地、便捷地與準確地執行倉儲管理與控制作業,故其最佳化的搬運策略被視為重要的效能指標。
傳統的自動化倉儲都是由單深式(Single-Deep)的儲貨架所組成,且由存取機Storage and Retrieval (S/R) Machine於該貨架巷道中間的路徑進行運動控制。然而,在一個廠房範圍有限的工廠,如果我們採用雙深式(Double-Deep)自動化倉儲它將可以儲存更多的貨物。文獻回顧指出雙深式自動化倉儲中最佳化排程(Optimal Scheduling)的搬運方式在現代工業化生產中所使用的彈性製造系統(FMS)是非常重要的一環。
本論文應用蟻群演算法(ACO)於雙深式自動化倉儲的最佳化排程。目標是為了得到最小的搬運工作距離,換句話說,也使得S/R Machine有了最短的搬運時間。經由模擬的結果與比較,顯示出研究所提出的方法具有優點與可行性。
In recent years, the Automated Storage and Retrieval Systems (AS/RS) have solved the problems associated with traditional warehouse systems, such as waste of land resources, slow operation speed, and high storage cost. Due to the requirements of AS/RS include the rapid, convenient, and accurate execution of warehouse management and control, the optimal scheduling of retrieval jobs is regarded as an important performance index in the systems.
Traditional AS/RS are almost structured in the single-deep configuration for the storage rack, and the Storage and Retrieval (S/R) machine processes movement control in the middle of the pathway. However, in a range-limited factory, it will store significantly more goods if we adopt the double-deep AS/RS. Literature survey indicates that we have investigated the optimal scheduling of retrieval jobs for double-deep AS/RS is very important for the Flexible Manufacturing System (FMS) used in modern industrial production.
In this paper, Ant Colony Optimization (ACO) is applied to optimal retrieval scheduling in double-deep AS/RS. The objective is to minimize the working distance, i.e., the shortest retrieval time travelled by the S/R machine. Simulation results and comparisons show the advantages and feasibility of the proposed methods.
[1] 董福慶、陳明德,「物流中心儲位管理」,經濟部出版,1995。
[2] 王福壽,「微電腦控制自動倉儲」,第九屆全國技術及職業教育研討會,工業類I,P117~126,1994。
[3] 郭興家、劉新在,「自動化工程」,高立圖書公司,1998。
[4] 廖建榮,「物料中心的系統規劃」,物流技術與戰略,1997。
[5] 黃金印,「規劃供應鏈管理中理想的倉儲轉運系統」,中華民國電子商務年鑑,2000。
[6] 高中職社區化網頁,「自動分類倉儲」,http://web1.knvs.tp.edu.tw/
[7] 盟立自動化股份有限公司網頁,倉儲系統產品介紹。http://www.mirle.com.tw/webc/html/news/show.aspx?num=493/
[8] 饒忻、姜世川,「自動倉儲系統面面觀」,機械月刊,P242-254,1996。
[9] 侯建良,「製造系統與自動化-倉儲技術」,清華大學工業工程管理學系,2012。
[10] 南京貨架網頁,各種倉儲方式的比較與分析。http://www.515huojia.com/html/20111018213041734.htm
[11] 郭幸民,「高效能倉儲物流管理」,國立高雄第一應用大學運籌管理所,課程講義,2014。
[12] 邱彥嵐,「棧板存取系統選取之研究:資料包絡分析法應用」,國立高雄第一應用大學運籌管理所,碩士論文,2009。
[13] T-tracking網頁,產品類別設計。
http://www.t-racking.com/double-deep-pallet-racking/
[14] 尤景玄,「運用遺傳基因演算法於旋轉式自動倉儲系統之系統規劃」,雲林科技大學工業工程與管理研究所,碩士論文,2001。
[15] 李智信,「動態調整型多載量自動倉儲系統之控制」,國立中央大學工業管理研究所,碩士論文,2000。
[16] 劉勝豐,「自動化倉儲的應用與技術發展趨勢」,機械月刊,P141-150,1995。
[17] 江宏志,「輔助輕負載自動倉儲設計之決策支援系統」,清華大學工業工程研究所,碩士論文,1992。
[18] 陳世泓,「應用蟻群最佳化演算法於自動化倉儲系統之動線規劃」,佛光人文社會學院資訊學系,碩士論文,2006。
[19] 經濟部商業司,「物流中心揀貨作業」,經濟部商業自動化系列叢書,1995。
[20] W. Wang and Y. Koren, “Scalability planning for reconfigurable manufacturing systems,” Journal of Manufacturing Systems, vol. 31, no. 2, pp. 83-91, 2012.
[21] G. Zhou and L. Mao, “Design and simulation of storage location optimization module in AS/RS based on FLEXSIM,” International Journal of Intelligent Systems and Applications, vol. 2, pp. 33-40, 2010.
[22] W. Yang, X. Qiu, and H. Wang, “The research of hybrid scheduling model in AS/RS based on multi-agent system and Petri Net,” in Proceedings of the International Conference of Information Science and Management Engineering, pp. 120–124, 2010.
[23] A. Zheng, W. Liu, C. Lu, H. Wang, and C. Song, “Modeling and optimizing research for the steel tube AS/RS system,” in Proceedings of the Chinese Control and Decision Conference, pp. 3979–3983, Mianyang, China, 2011.
[24] C. Huang and S. Fu, “Research on movement control technology of Stacking Crane,” in Proceedings of the International Conference on Electric Information and Control Engineering, pp. 5254–5256, 2011.
[25] Q. Tang and F. Xie, “An approach for picking optimization in automated warehouse,” in Proceedings of the 5th International Conference on Natural Computation (ICNC ’09), pp. 362–366, 2009.
[26] Y. Huang, W. Liu, P. Ding, and H. Liu, “Research on the compound operation optimization problem of AS/RS,” in Proceedings of the IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, pp. 1130–1133, 2010.
[27] W. Yan, “The study on the simulation of a distribution center operating system and optimization of equipment configuration,” in Proceedings of the Chinese Control and Decision Conference, pp. 3452–3456, 2010.
[28] H. D. Ratliff and A. S. Rosenthal “Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem,” Operations Research, vol. 31, no. 3, pp. 507-521, 1983.
[29] M. Goetschalckx and H. D. Ratliff, “Order picking in an aisle,” IIE Transactions, vol. 20, no. 1, pp. 53-62, 1988.
[30] M. Goetschalckx and H. D. Ratliff, “An efficient algorithm to cluster order picking items in a wide aisle,” Engineering Costs and Production Economics, vol. 13, no. 1, 263-271, 1988.
[31] H. Hwang, W. Bake, and M. K. Lee, “Clustering algorithms for order picking in an automated storage and retrieval systems,” International Journal of Production Research, vol. 26, no. 2, pp. 189-201, 1998.
[32] H. Hwang and M. K. Lee, “Order batching algorithms for a man-on-board automated storage and retrieval system,” Engineering Costs and Production Economics, vol. 13, no. 1, pp. 285-294, 1998.
[33] R. W. Hall, “Distance approximations for routing manual pickers in a warehouse,” IIE Transactions, vol. 25, no. 4, pp. 76-87, 1993.
[34] H. Brynzer and M. I. Johansson, “Design and performance of kitting and order picking systems,” International Journal of Production Economics, vol. 41, pp. 115-125, 1995.
[35] H. Brynzer and M. I. Johansson, “Storage location assignment: Using the product structure to reduce order picking times,” International Journal of Production Economics, vol. 46, pp. 595-603, 1996.
[36] C. G. Petersen, “An evaluation of order picking routing policies,” International Journal of Operations & Production Management, vol. 17, no. 11, pp. 1098-1111, 1997.
[37] R. D. Koster and E. V. D. Poort, “Routing order pickers in a warehouse: a comparison between optimal and heuristic solutions,” IIE Transactions, vol. 30, no. 5, pp. 469-480, 1998.
[38] C. H. Lin and I. Y. Lu, “The procedure of determining the order picking strategies in distribution center,” International Journal of Production Economics, vol. 60, no. 1, pp. 301-307, 1999.
[39] A. F. Alkaya and E. Duman, “Application of sequence-dependent traveling salesman problem in printed circuit board assembly,” IEEE Trans. Components, Packaging and Manufacturing Technology, vol. 3, no. 6, pp. 1063-1076, 2013.
[40] D. Perez, J. Togelius, S. Samothrakis, P. Rohlfshagen, and S. M. Lucas, “Automated map generation for the physical traveling salesman problem,” IEEE Trans. Evolutionary Computation, vol. 18, no. 5, pp. 708-720, 2014.
[41] D. Perez, E. J. Powley, D. Whitehouse, P. Rohlfshagen, S. Samothrakis, P. I. Cowling, and S. M. Lucas, “Solving the physical traveling salesman problem: tree search and macro actions,” IEEE Trans. Computational Intelligence and Ai In Games, vol. 6, no. 1, pp. 31-45, 2014.
[42] Y. A. Bozer, E. C. Schorn, and G. P. Sharp, “Geometric Approaches to Solve the Chebyshev Traveling Salesman Problem,” IIE Transactions, vol. 22, no. 3, pp. 38-254, 1990.
[43] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Transactions on System, Man, and Cybernetics - Part B, Cybermetic, vol. 26, pp. 29-41, 1996.
[44] M. Dorigo, G. D. Caro, and L. M. Gambardella, “Ant algorithms for discrete optimization,” Artificial Life, vol. 5, pp. 137-172, 1999.
[45] M. Dorigo and L. M. Gambardella, “Ant colony for the travelling salesman problem,” Biosystems, vol. 43, pp. 73-81, 1997.
[46] M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,IEEE Trans. Evolutionary Computation, vol. 1, no. 1, pp. 53-66, 1997.
[47] M. Dorigo and L. M. Gambardella, “Solving symmetric and asymmetric TSPs by ant colonies,” Proceedings of IEEE International Conference, Evolutionary Computation, Nagoya, May, 20-22, pp. 622-627, 1996.
[48] M. Dorigo and L. M. Gambardella, “The ant colony optimization meta-heuristic,” New Ideas in Optimization, McGraw-Hill, pp. 11-32, 1997.
[49] M. Dorigo, E. Bonabeau, and G. Theraulaz, “Ant algorithms and stigmergy,” Future Generation Computer Systems, vol. 16, pp. 851-871, 2000.
[50] S. C. Chu, J. F. Roddick, and J. S. Pan, “Ant colony system with communication strategies,” Information Sciences, vol. 167, pp. 63-76, 2004.
[51] M. Dorigo, V. Maniezzo, and A. Colorni, “Positive feedback as a search strategy,” Dipartmento Elettronica, Politecnico Milano, Italy, Tech. Rep. 91-016, 1991.
[52] M. Rajkumar, P. Asokan, N. Anilkumar, and T. Page, “A GRASP algorithm for flexible job-shop scheduling problem with limited resource constraints,” International Journal of Production Research, vol. 49, no. 8, pp. 2409–2423, 2011.
[53] O. Casdin, P. Castagna, Z. Sari, and N. Meghelli, “Performance evaluation of in-deep class storage for flow-rack AS/RS,” International Journal of Production Research, vol. 50, pp. 22–24, 2012.
[54] J. P. Vandenberg and A. J. R. M. Gademann, “Optimal routing in an automated storage/retrieval system with dedicated storage,” MI: University of Michigan Press, 1975.
[55] B. Xing, W-J. Gao, F. V. Nelwamondo, K. Battle, and T. Marwala, “Storage and retrieval machine travel route planning strategy in an automated material handling environment,” in Proceedings of the World Automation Congress, 2010.
[56] Y. A. Bozer and J. A. White, “Travel-time models for automated storage/retrieval systems,” IIE Transactions, vol. 16, no. 4, pp. 329-338, 1984.