Enhanced List-Based Simulated Annealing Algorithm for Large-Scale Traveling Salesman Problem
Lijin Wang, Rongying Cai, Min Lin et al. · IEEE Access · 2019
List-based simulated annealing (LBSA) algorithm is a novel simulated annealing algorithm where list-based cooling scheme is used to control the change of parameter temperature. Aiming to improve the efficiency of the LBSA algorithm for large-scale optimization problems, this paper proposes an enhanced LBSA (ELBSA) algorithm for solving large-scale traveling salesman problem (TSP). The ELBSA algorithm can drive more sampling at more suitable temperatures and from more promising neighborhoods. Specifically, heuristic augmented sampling strategy is used to ensure that more neighbors are from promising neighborhoods, systematic selection strategy is proposed to guarantee that each component of the current solution has a chance to be improved, and variable Markov chain length (VMCL), based on arithmetic sequence, is used to sample more neighbors at more suitable temperatures. Extensive experiments were performed to show the contribution of the heuristic augmented sampling strategy, and to verify the advantage of using systematic selection and VMCL. Comparative experiments, which were conducted on a wide range of large-scale TSP instances, show that the ELBSA algorithm is better than or competitive with most other state-of-the-art metaheuristics.
Cited by 44 works. doi:10.1109/access.2019.2945570 Open-access PDF
Authors
References
- Optimization by Simulated Annealing
- Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
- TSPLIB—A Traveling Salesman Problem Library
- Simulated Annealing
- A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 Special Session on Real Parameter Optimization
- A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems
- Discrete cuckoo search algorithm for the travelling salesman problem
- A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem
- Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques
- Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search