A Hybrid Algorithm for Automated Guided Vehicle Routing Problem

Abstract

Nowadays, 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.

Keywords

• Automated Guided Vehicle,Flexible Manufacturing Systems,Simulated Annealing Algorithm,Dijkstra,Routing,Vehicle Route Planning,Automatic Systems

References

1. [1] 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
2. [2] 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
3. [3] 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
4. [4] 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
5. [5] 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
6. [6] 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
7. [7] 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
8. [8] 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

9. [9] 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
10. [10] 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
11. [11] 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
12. [12] 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
13. [13] 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
14. [14] Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik 1: 269–271. doi:10.1007/BF01386390.