Genetic Algorithm for Improving Route of Travelling Salesman Problem Generated by Savings Algorithm
Abstract
Travelling Salesman Problem (TSP) is the problem for finding the shortest route starting from start node then visiting number of nodes exactly once and finally go back to start node. If a TSP has a lot of nodes, it will be a NP-Hard Problem. Algorithms working based on heuristic and metaheuristic can be a solution for solving NP-Hard Problem. Savings Algorithm is a heuristic algorithm, so it’s solution may be not the best solution, therefore there is a chance to improve it. Genetic Algorithm is a metaheuristic that can be applied on many optimization problems, including TSP. This paper will discuss about GA for improving route TSP generated by Savings Algorithm. On testing of 10 instances, showing that algorithm based on GA can improve route of TSP generated by Savings Algorithm.
References
Applegate, D.L., Bixby, R.E., Chvatal, V., & Cook, W.J. (2006). The Traveling Salesman Problem A Computational Study, Princeton University Press – New Jersey
Bhagya, T.G. (2021). Algoritma Genetik Pada Penjadwalan Transportasi Kapal Laut (Studi Kasus PT. Pelni). Journal of Industrial and Manufacture Engineering, 5(2), 81-92.
Chiarandini, M. (2020). Construction Heuristics for Traveling Salesman Problem, University of Southern – Denmark
Clarke, G., & Wright, J.W. (1964). Scheduling of Vehicles from A Central Depot to A Number of Delivery Points, Operations Research
Frutos, M., & Tohme, F. (2012). A New Approach to The Optimization of The CVRP through Genetic Algorithm, American Journal of Operations Research
Hansen, J.S. (2011). GNU Octave Beginner’s Guide, PACKT – Birmingham
Kramer, O. (2017). Genetic Algorithm Essentials, Springer – Switzerland
Labadie, N., Prins, C., & Prodhon, C. (2016). Metaheuristics for Vehicle Routing Problem, ISTE – London
Lavrov, M. (2020). The Traveling Salesman Problem, University of Illinois at Urbana-Champaign - USA
Lysgaard, J. (2007). Clarke & Wright’s Savings Algorithm, Department of Management Science and Logistics – The Aarhus School of Business – Denmark
Reinelt, G. (1995). TSPLIB 95, Institut fur Angewandte Mathematik – Universitat Heidelberg – Germany
Sanggala, E., Dimyati, T.T., & Yogaswara, Y. (2021). Genetic Algorithm Untuk Memperbaiki Rute Travelling Salesman Problem Yang Dihasilkan Dari Nearest Neighbour, Jurnal Logistik Bisnis – Politeknik POS Indonesia
Talbi, E. (2009). Metaheuristics from Design to Implementation, John Wiley & Sons – USA
