Meta-Heuristic Approaches for Solving Travelling Salesman Problem

Article Sidebar

PDF
Published: Jun 20, 2017
DOI: https://doi.org/10.26483/ijarcs.v8i5.3560
Keywords:
Travelling salesman problem, Meta-heuristic algorithms, Genetic algorithm, Dynamic programming

Main Article Content

Arash Mazidi
Islamic Azad University of Aliabad Katool Branch
Elham Damghanijazi
Islamic Azad University of Aliabad Katool Branch

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.

Downloads

Download data is not yet available.

Article Details

Issue
Vol. 8 No. 5 (2017): May-June 2017
Section
Articles

COPYRIGHT

Submission of a manuscript implies: that the work described has not been published before, that it is not under consideration for publication elsewhere; that if and when the manuscript is accepted for publication, the authors agree to automatic transfer of the copyright to the publisher.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work
  • The journal allows the author(s) to retain publishing rights without restrictions.
  • The journal allows the author(s) to hold the copyright without restrictions.

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.