List-Based Simulated Annealing Algorithm for Traveling Salesman Problem

Abstract EN

Simulated annealing (SA) algorithm is a popular intelligent optimization algorithm which has been successfully applied in many fields.

Parameters’ setting is a key factor for its performance, but it is also a tedious work.

To simplify parameters setting, we present a list-based simulated annealing (LBSA) algorithm to solve traveling salesman problem (TSP).

LBSA algorithm uses a novel list-based cooling schedule to control the decrease of temperature.

Specifically, a list of temperatures is created first, and then the maximum temperature in list is used by Metropolis acceptance criterion to decide whether to accept a candidate solution.

The temperature list is adapted iteratively according to the topology of the solution space of the problem.

The effectiveness and the parameter sensitivity of the list-based cooling schedule are illustrated through benchmark TSP problems.

The LBSA algorithm, whose performance is robust on a wide range of parameter values, shows competitive performance compared with some other state-of-the-art algorithms.