More Web Proxy on the site http://driver.im/

research-article

Open access

Benchmarking Metaheuristic Optimization Algorithms on Travelling Salesman Problems

Authors:

Christopher Galli,

Rolf DornbergerAuthors Info & Claims

ICSLT '22: Proceedings of the 8th International Conference on e-Society, e-Learning and e-Technologies

Pages 20 - 25

https://doi.org/10.1145/3545922.3545926

Published: 17 September 2022 Publication History

All formats PDF

Abstract

A wide variety of metaheuristic optimization algorithms has been proposed to optimize the travelling salesman problem (TSP), and methods drawing inspiration from nature have been rising in popularity due to their competitive performance in regard to quality of solution and computational efficiency. In this paper, a selection of algorithms, using standardized parameters frequently found in literature, is applied to a multitude of TSPs with differing complexities and sizes, and subsequently benchmarked on solution quality and convergence. We consider the quality of the implemented algorithms using standardized and not a specifically optimized parameter choices according to a certain problem.

References

[1]

C. Blum and A. Roli, ‘Metaheuristics in combinatorial optimization: Overview and conceptual comparison’, ACM Comput. Surv., vol. 35, no. 3, pp. 268–308, Sep. 2003.

Digital Library

[2]

E. Osaba, J. D. Ser, A. Sadollah, M. N. Bilbao, and D. Camacho, ‘A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem’, Applied Soft Computing, vol. 71, pp. 277–290, Oct. 2018.

Digital Library

[3]

H. Zhang, J. Sun, T. Liu, K. Zhang, and Q. Zhang, “Balancing exploration and exploitation in multiobjective evolutionary optimization”, Information Sciences, 497, 129-148, 2019.

Digital Library

[4]

X. S. Yang, S. Deb, T. Hanne, and X. He, “Attraction and diffusion in nature-inspired optimization algorithms”, Neural Computing and Applications, 31(7), 1987-1994, 2019.

Digital Library

[5]

X.-S. Yang, S. Deb, and S. Fong, ‘Metaheuristic Algorithms: Optimal Balance of Intensification and Diversification’, Appl. Math. Inf. Sci., vol. 8, no. 3, pp. 977–983, May 2014.

[6]

G. Reinelt, ‘TSPLIB—A Traveling Salesman Problem Library’, ORSA Journal on Computing, vol. 3, no. 4, pp. 376–384, Nov. 1991.

[7]

E. Osaba, X.-S. Yang, and J. Del Ser, ‘Traveling salesman problem: a perspective review of recent research and new results with bio-inspired metaheuristics’, in Nature-Inspired Computation and Swarm Intelligence, Elsevier, 2020, pp. 135–164.

[8]

]Introduction to Nature-Inspired Optimization. Elsevier, 2017.

[9]

M. Malek, M. Guruswamy, M. Pandya, and H. Owens, ‘Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem’, Ann. Oper. Res., vol. 21, no. 1, pp. 59–84, Dec. 1989.

Digital Library

[10]

Selamoğlu B.İ., Salhi A. (2016) The Plant Propagation Algorithm for Discrete Optimisation: The Case of the Travelling Salesman Problem. In: Yang XS. (eds) Nature-Inspired Computation in Engineering. Studies in Computational Intelligence, vol 637. Springer, Cham. https://doi.org/10.1007/978-3-319-30235-5_3

[11]

M. Nasir, A. Sadollah, Y. H. Choi, and J. H. Kim, ‘A comprehensive review on water cycle algorithm and its applications’, Neural Comput. & Applic., vol. 32, no. 23, pp. 17433–17488, Dec. 2020.

Digital Library

[12]

M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, vol. 26 (1), pp. 29–41, 1996.

Digital Library

[13]

K.-P. Wang, L. Huang, C.-G. Zhou, and W. Pang, “Particle swarm optimization for traveling salesman problem,” in Proceedings of the 2003 International Conference on Machine Learning and Cybernetics (IEEE Cat. No.03EX693), Nov. 2003, vol. 3, pp. 1583-1585 Vol.3.

[14]

D. Karaboga and B. Basturk, “On the performance of artificial bee colony (ABC) algorithm,” Applied Soft Computing, vol. 8, no. 1, pp. 687–697, Jan. 2008.

Digital Library

[15]

C. Rego, D. Gamboa, F. Glover, and C. Osterman, “Traveling salesman problem heuristics: Leading methods, implementations and latest advances,” European Journal of Operational Research, vol. 211, no. 3, pp. 427–441, 2011.

Cited By

Aljalaud FAlohali Y(2024)Optimizing Autonomous Multi-UAV Path Planning for Inspection Missions: A Comparative Study of Genetic and Stochastic Hill Climbing AlgorithmsEnergies10.3390/en1801005018:1(50)Online publication date: 27-Dec-2024
https://doi.org/10.3390/en18010050
Watanabe KXu X(2024)Nonlinear crossing strategy-based particle swarm optimizations with time-varying acceleration coefficientsApplied Intelligence10.1007/s10489-024-05502-154:13-14(7229-7277)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1007/s10489-024-05502-1

Index Terms

Benchmarking Metaheuristic Optimization Algorithms on Travelling Salesman Problems
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Discrete space search
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial optimization

Recommendations

A new hybrid method based on Particle Swarm Optimization, Ant Colony Optimization and 3-Opt algorithms for Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is one of the standard test problems used in performance analysis of discrete optimization algorithms. The Ant Colony Optimization (ACO) algorithm appears among heuristic algorithms used for solving discrete ...
A stochastic nature inspired metaheuristic for clustering analysis

This paper presents a new stochastic nature inspired methodology, which is based on the concepts of Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO), for optimally clustering N objects into K clusters. Due to the nature of stochastic ...
A memetic ant colony optimization algorithm for the dynamic travelling salesman problem

Ant colony optimization (ACO) has been successfully applied for combinatorial optimization problems, e.g., the travelling salesman problem (TSP), under stationary environments. In this paper, we consider the dynamic TSP (DTSP), where cities are replaced ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICSLT '22: Proceedings of the 8th International Conference on e-Society, e-Learning and e-Technologies

June 2022

125 pages

ISBN:9781450396660

DOI:10.1145/3545922

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 September 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ICSLT '22

ICSLT '22: 2022 8th International Conference on e-Society, e-Learning and e-Technologies

June 10 - 12, 2022

Rome, Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
1,247
Total Downloads

Downloads (Last 12 months)769
Downloads (Last 6 weeks)89

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Aljalaud FAlohali Y(2024)Optimizing Autonomous Multi-UAV Path Planning for Inspection Missions: A Comparative Study of Genetic and Stochastic Hill Climbing AlgorithmsEnergies10.3390/en1801005018:1(50)Online publication date: 27-Dec-2024
https://doi.org/10.3390/en18010050
Watanabe KXu X(2024)Nonlinear crossing strategy-based particle swarm optimizations with time-varying acceleration coefficientsApplied Intelligence10.1007/s10489-024-05502-154:13-14(7229-7277)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1007/s10489-024-05502-1

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents