Title: Solution attractor of local search in travelling salesman problem (part 2): computational study

Authors: Weiqi Li; Xue Li

Addresses: University of Michigan - Flint, 303 E. Kearsley Street, Flint, MI 48502, USA ' Shaanxi Normal University, 199 South Changan Road, Yanta District, Xian, 710062, China

Abstract: This paper is the second part of our study. In the first part, we introduced the concept of solution attractor of local search system for the travelling salesman problem (TSP), described a procedure for constructing the solution attractor, and presented an attractor-based search system to solve the dynamic multi-objective TSP. In this paper, we report the results of our recent empirical study on some important properties of the solution attractor of local search system for the TSP. These properties include the nature of convergence of local search trajectories, the size of the constructed solution attractor, the relationship between the size of the problem and the size of the constructed solution attractor, the best tour in the solution attractor, and computational complexity in the attractor-based search system.

Keywords: travelling salesman problem; TSP; global optimisation; analysis of heuristics; convergence of local search; solution attractor.

DOI: 10.1504/IJMHEUR.2019.098260

International Journal of Metaheuristics, 2019 Vol.7 No.2, pp.93 - 126

Accepted: 06 Apr 2018
Published online: 07 Mar 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article