Meta-Heuristic Approaches for Solving Travelling Salesman Problem

Arash Mazidi, Elham Damghanijazi

Abstract


Travelling Salesman Problem (TSP) is one of the problems which is being widely used in transportation industry which its optimization would speed up services and increase customer satisfaction. In this paper, first, TSP is optimized using dynamic programming for Iran59 dataset and a dataset including 10 cities of Iran. Then this problem is solved using 5 meta-heuristic algorithms including Hill Climbing, Simulated Annealing, PSO, Ant Colony and Genetic Algorithm and performance of these algorithms is compared with the optimized solution. Comparison is performed in terms of optimal solution, execution time, and memory. Results show that simulated annealing and hill climbing stop at the local minimum and the proposed tour is longer than other methods. But other algorithms result in better solutions and GA achieves the optimal solution. Comparing the algorithms in terms of execution time shows that GA achieves the optimal solution in shortest time. Moreover, hill climbing method has the lowest memory consumption.

Keywords


Travelling salesman problem; Meta-heuristic algorithms; Genetic algorithm; Dynamic programming

Full Text:

PDF

References


. D. L. Applegate., R. E. Bixby, V. Chvatal, and W. J. Cook. The traveling salesman problem: a computational study. Princeton university press, 2011.

. Giagkiozis, R. C. Purshouse, and P. J. Fleming. "An overview of population-based algorithms for multi-objective optimisation." International Journal of Systems Science, Vol. 46, No. 9 pp. 1572-1599, 2015.

. A. Mazidi, M. Fakhrahmad, and M. Sadreddini. "A Meta-heuristic Approach to CVRP Problem: Local Search Optimization Based on GA and Ant Colony." Journal of Advances in Computer Research, Vol. 7, No. 1, pp. 1-22, 2016.

. S. Joshi and S. Kaur. "Ant Colony Optimization Meta-heuristic for Solving Real Travelling Salesman Problem." In Emerging Research in Computing, Information, Communication and Applications, pp. 55-63. Springer Singapore, 2016.

. K. Kanthavel and P. Prasad. "Optimization of Capacitated Vehicle Routing Problem by Nested Particle Swarm Optimization". American Journal of Applied Sciences, Vol. 8, No. 2, pp. 107-112, 2011.

. L. Sánchez, "Parallel Genetic Algorithms on a GPU to Solve the Travelling Salesman Problem." Revista en Ingeniería y Tecnología, UAZ , Vol.8, No. 2 , 2015.

. W. F. Tan, L.S. Lee, Z.A. Majidi and H. W. Seow, "Ant Colony Optimization for Capacitated Vehicle Routing Problem.", Journal of Computer Science, Vol. 8, No. 6, pp. 846-852, 2012.

. H. Lei, G. Laporte and B. Guo, "The Capacitated Vehicle Routing Problem with Stochastic Demands and Time Windows", Computers & Operations Research, Vol. 38, No.12, pp. 1775-1783, 2011.

. S. Urrutia, A. Milanés, and A. Løkketangen. "A dynamic programming based local search approach for the double traveling salesman problem with multiple stacks." International Transactions in Operational Research, Vol. 22, No. 1, pp. 61-75, 2015.

. Y. Marinakis, and M. Marinaki, "A Hybrid Genetic–Particle Swarm Optimization Algorithm for the Vehicle Routing Problem". Expert Systems with Applications, Vol. 37, No. 2, pp. 1446-1455, 2010.

. S. Mazzeo, and I. Loiseau, "An Ant Colony Algorithm for the Capacitated Vehicle Routing.", Electronic Notes in Discrete Mathematics, Vol. 18, pp. 181-186, 2004.

. B. Yu, Z.Z. Yang, and B. Yao. "An Improved ant Colony Optimization for Vehicle Routing Problem", European Journal of Operational Research, Vol. 196, No. 1, pp. 171-176, 2009.

. V. L. De Matos, A. B. Philpott, and E. C. Finardi. "Improving the performance of stochastic dual dynamic programming." Journal of Computational and Applied Mathematics 290, pp. 196-208, 2015.

. Y. Bykov and S. Petrovic. "A Step Counting Hill Climbing Algorithm applied to University Examination Timetabling." Journal of Scheduling, pp. 1-14, 2014.

. S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi. "Optimization by Simmulated Annealing.", Science, 220(4598), pp. 671-680, 1983

. Sh. Zhan, J. Lin, Z. Zhang, and Y. Zhong. "List-Based Simulated Annealing Algorithm for Traveling Salesman Problem." Computational intelligence and neuroscience 2016, 2016.

. F. Glover and M. Laguna, Tabu Search, Kluwer Academic Publishers, 1997simulated annealing, Science, Vol. 220, No. 4598, pp. 671–680, (1983).

. M. Yousefi Khoshbakht and A. Zafari, A new ant colony algorithm for solving multiple traveling salesman problem. The 2th Joint Congress on Intelligent and Fuzzy Systems (ISFS2008), 28-30. October, Malek-Ashtar University of Technology, Tehran, Iran. (2008).

. Horri, A., Rahmanian, A., & Dastghaibyfard, G. H. (2015). Energy and performance-aware virtual machine consolidation in Cloud computing a two dimensional approach. Turkish Journal of Engineering, 1, 20–35.

. Rahmanian, A., Dastghaibyfard, G., & Tahayori, H. (2017). Penalty-aware and cost-efficient resource management in cloud data centers. International Journal of Communication Systems, 30(8).

. Ghobaei-Arani, M., Shamsi, M., & Rahmanian, A. A. (2017). An efficient approach for improving virtual machine placement in cloud computing environment. Journal of Experimental & Theoretical Artificial Intelligence, 1–23.




DOI: https://doi.org/10.26483/ijarcs.v8i5.3560

Refbacks

  • There are currently no refbacks.


Bookmark and Share


Copyright (c) 2017 International Journal of Advanced Research in Computer Science