1. MMC
  2. All Volumes and Issues
  3. Volume 10, Number 3, 2023
  4. A new improved simulated annealing for traveling salesman problem

A new improved simulated annealing for traveling salesman problem

MMC.
2023;
Volume 10, Number 3
: pp. 764–771
https://doi.org/10.23939/mmc2023.03.764
Received: February 15, 2023
Revised: July 18, 2023
Accepted: July 19, 2023

Mathematical Modeling and Computing, Vol. 10, No. 3, pp. 764–771 (2023)

Authors:
  1. N. Adil
  2. H. Lakhbab
1
Hassan II University, Fundamental and applied Mathematics Laboratory, Casablanca, Morocco
2
Hassan II University, Fundamental and applied Mathematics Laboratory, Casablanca, Morocco

Simulated annealing algorithm is one of the most popular metaheuristics that has been successfully applied to many optimization problems.  The main advantage of SA is its ability to escape from local optima by allowing hill-climbing moves and exploring new solutions at the beginning of the search process.  One of its drawbacks is its slow convergence, requiring high computational time with a good set of parameter values to find a reasonable solution.  In this work, a new improved SA is proposed to solve the well-known travelling salesman problem.  In order to improve SA performance, a population-based improvement procedure is incorporated after the acceptance phase of SA, allowing the algorithm to take advantage of the social behavior of some solutions from the search space.  Numerical results were carried out using known TSP instances from TSPLIB and preliminary results show that the proposed algorithm outperforms in terms of solution quality, the other comparison algorithms.

 

simulated annealing
travelling salesman problem
metaheuristics
  1. Glover F.  Tabu Search – Part I.  ORSA Journal on Computing.  1 (3), 190–206 (1989).
  2. Kirkpatrick S., Gelatt C. D., Vecchi M. P.  Optimization by Simulated Annealing.  Science.  220 (4598), 671–680 (1983).
  3. Kennedy J., Eberhart R.  Particle swarm optimization.  Proceedings of ICNN'95 – International Conference on Neural Networks.  4, 1942–1948 (1995).
  4. Dantzig G. B., Fulkerson D. R., Johnson S. M.  On a Linear-Programming, Combinatorial Approach to the Traveling-Salesman Problem.  Operations Research.  7 (1), 58–66 (1959).
  5. Brucker P.  $NP$-Complete operations research problems and approximation algorithms.  Zeitschrift für Operations – Research.  23, 73–94 (1979).
  6. Zhong Y., Wang L., Lin M., Zhang H.  Discrete pigeon-inspired optimization algorithm with Metropolis acceptance criterion for large-scale traveling salesman problem.  Swarm and Evolutionary Computation.  48, 134–144 (2019).
  7. Ezugwu A. E., Adewumi A. O., Frоncu M. E.  Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem.  Expert Systems with Applications.  77, 189–210 (2017).
  8. Zhou A.-H., Zhu L.-P., Hu B., Deng S., Song Y., Qiu H., Pan S.  Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming.  Information.  10 (1), 7 (2019).
  9. Zhong Y., Lin J., Wang L., Zhang H.  Discrete comprehensive learning particle swarm optimization algorithm with Metropolis acceptance criterion for traveling salesman problem.  Swarm and Evolutionary Computation.  42, 77–88 (2018).
  10. Geng X., Chen Z., Yang W., Shi D., Zhao K.  Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search.  Applied Soft Computing.  11 (4), 3680–3689 (2011).
  11. Osaba E., Carballedo R., Lopez-Garcia P., Diaz F.  Comparison between Golden Ball Meta-Heuristic, Evolutionary Simulated Annealing and Tabu Search for the Traveling Salesman Problem.  Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion. 1469–1470 (2016).
  12. Zhan S.-h., Lin J., Zhang Z.-j., Zhong Y.-w.  List-Based Simulated Annealing Algorithm for Traveling Salesman Problem.  Computational Intelligence and Neuroscience.  2016, 1712630 (2016).
  13. Schneider J. J., Puchta M.  Investigation of acceptance simulated annealing – A simplified approach to adaptive cooling schedules.  Physica A.  389 (24), 5822–5831 (2010).
  14. Da Silva R., Filho E. V., Alves A.  A thorough study of the performance of simulated annealing in the traveling salesman problem under correlated and long tailed spatial scenarios.  Physica A.  577, 126067 (2021).
  15. Osaba E., Yang X.-S., Diaz F., Lopez-Garcia P., Carballedo R.  An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems.  Engineering Applications of Artificial Intelligence.  48 (24), 59–71 (2016).
  16. Reinelt G.  Tsplib – A Traveling Salesman Problem Library.  ORSA Journal on Computing.  3 (4), 376–384 (1991).
  17. Derrac J., García S., Molina D., Herrera F.  A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms.  Swarm and Evolutionary Computation.  1 (1), 3–18 (2011).
  18. Sundar A., Rahmin N. A. A., Chen C. Y., Nazihah M. A.  Simulated annealing approach for outpatient scheduling in a haemodialysis unit.  Mathematical Modeling and Computing.  9 (4), 860–870 (2022).
  19. Yu V. F., Redi A. A. N. P., Hidayat Y. A., Wibowo O. J.  A simulated annealing heuristic for the hybrid vehicle routing problem.  Applied Soft Computing.  53 (C), 119–132 (2017).