Title: Solution attractor of local search in travelling salesman problem: concept, construction and application

Authors: Weiqi Li; Mingyuan Feng

Addresses: University of Michigan – Flint, 303 E. Kearsley Street, Flint, MI 48502, USA ' Nanjing University of Posts and Telecommunications, 66 New Mofan Road, Gulou, Nanjing, China

Abstract: The travelling salesman problem (TSP) is one of the most intensely investigated problems in optimisation applications. This paper introduces the concept of solution attractor in local search process for TSP. A solution attractor drives the local search trajectories to converge into a small region in the solution space, which contains the most promising solutions to the problem. This paper presents a method for constructing the solution attractor of local search in TSP, and then demonstrates how to apply the attractor concept to design a search strategy to tackle a complex TSP - dynamic multi-objective TSP (DMOTSP).

Keywords: local search; solution attractor; dynamic multiobjective optimisation; parallel algorithm; travelling salesman problem; TSP; metaheuristics.

DOI: 10.1504/IJMHEUR.2013.056388

International Journal of Metaheuristics, 2013 Vol.2 No.3, pp.201 - 233

Received: 26 Apr 2012
Accepted: 19 Apr 2013
Published online: 05 Jul 2014 *

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