A Hybrid Algorithm for Automated Guided Vehicle Routing Problem

Year 2016, Volume: 4 Issue: Special Issue-1, 158 - 161, 26.12.2016

Cansu Söyleyici , Sinem Bozkurt Keser

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