A Hybrid Algorithm for Automated Guided Vehicle Routing Problem
AbstractNowadays, automatic systems become crucial in many factories to achieve some tasks such as minimizing cost, maximizing efficiency, quality, and reliability. The planning is important for manufacturing systems to adopt changing conditions. Also, manufacturers want to obtain fast, reliable, qualified and economic products. Flexible Manufacturing Systems (FMSs) are used to meet this need. FMSs make production fast, qualified, reliable and economic by using computer-controlled structure that includes robots and transportation systems. Automated Guided Vehicles (AGVs) and FMS are thought to be integrated because FMSs use AGVs as a part of transportation in the factory. AGVs are used to carry loads, in other words products, in production areas, warehouses, factories that use magnets, landmarks, laser sensors, lines to know where they are. AGV scheduling and routing is NP-hard and open-ended problems. In the literature, there are many algorithms and methods are proposed to solve these problems. In this study, we present a hybrid algorithm that is composed of simulated annealing (SA) and Dijkstra’s algorithm to solve the routing problem. The hybrid algorithm is compared with SA algorithm in terms of distance cost using benchmark problems in the literature.
Luka Kalinovcic, Tamara Petrovic, Stjepan Bogdan, Vedran Bobanac (2011). Modified Banker’s Algorithm for Scheduling in Multi-AGV Systems. Automation Science and Engineering (CASE), 2011 IEEE Conference on, Trieste, Italy. Pages. 351-356
Vedran Bobanac and Stjepan Bogdan (2008). Routing and Scheduling in Multi-AGV Systems Based on Dynamic Banker Algorithm, Control and Automation, 2008 16th Mediterranean Conference on, Ajaccio, France. Pages. 1168-1173
Pei-Sen Liu and Li-Chen Fu (1989). Planning and Scheduling in a Flexible Manufacturing System Using a Dynamic Routing Method for Automated Guided Vehicles, Robotics and Automation, 1989. Proceedings., 1989 IEEE International Conference on, Scottsdale, AZ, 1989. Pages. 1584-1589
Zbigniew J. Czech and Piotr Czarnas (2002). Parallel Simulated Annealing for Vehicle Routing Problem with Time Windows, Parallel, Distributed and Network-based Processing, 2002. Proceedings. 10th Euromicro Workshop on, Canay Island. Pages. 376-383
Shih-Wei Lin, Kuo-Ching Ying, Zne-Jung Lee and F.-H. Hsi (2006), Applying Simulated Annealing Approach for Capacitated Vehicle Routing Problems”, 2006 IEEE International Conference on Systems, Man and Cybernetics, Taipei, Taiwan. Pages. 639-644
Takashi Onoyama,,Takuya Maekawa,Sen Kubota, Norihisa Komoda (2006). GA Applied VRP Solving Method for a Cooperative Logistics Network, 2006 IEEE Conference on Emerging Technologies and Factory Automation, Prague. Pages. 1101-1106
Yusuke Morihiro, Toshiyuki Miyamoto, Sadatoshi Kumagai (2006). An Initial Task Assignment Method for Autonomous Distributed Vehicle Systems with Finite Buffer Capacity, 2006 IEEE Conference on Emerging Technologies and Factory Automation, Prague. Pages. 805-812
NaiQi Wu and MengChu Zhou (2007), Shortest Routing of Bidirectional Automated Guided Vehicles Avoiding Deadlock and Blocking, IEEE/ASME Transactions on Mechatronics, Vol. 12, No. 1. Pages. 63-72
Lyamine Bouhafs, Amir Hajjam and Abderrafiaa Koukam (2008), A Tabu Search and Ant Colony System Approach for the Capacitated Location-Routing Problem, Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2008. SNPD '08. Ninth ACIS International Conference on, Phuket,. Pages. 46-50
Cui-hua Guan, Yan Cao, Jing Shi (2010). Tabu Search Algorithm for Solving the Vehicle Routing Problem, Information Processing (ISIP), 2010 Third International Symposium on, Qingdao. Pages. 74-77
Haihua Li, Zongyan Xu, Feifei Zhou (2012). A Study on Vehicle Routing Problem with Fuzzy Demands Based on Improved Tabu Search, Computational and Information Sciences (ICCIS), 2012 Fourth International Conference on, Chongqing. Pages. 73-76
Cheng Zhu, Luohao Tang, Weiming Zhang (2014). Multi-vehicle Coordination and Flexible Scheduling based on Simulated Annealing Algorithm, The 26th Chinese Control and Decision Conference (2014 CCDC), Changsha. Pages. 2686-2691
Pelin Alcan and Hüseyin Başligil (2010).A literature Review for the Simulated Annealing Method on the Parallel Machines Since 2003, 14th International Research/Expert Conference, Pages. 289-292
Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik 1: 269–271. doi:10.1007/BF01386390.
Copyright (c) 2018 International Journal of Intelligent Systems and Applications in Engineering
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.
IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.