Computation of the travelling salesman problem by a shrinking blob

Jones, Jeff; Adamatzky, Andrew

Abstract

The travelling salesman problem (TSP) is a well known and challenging combinatorial optimisation problem. Its computational intractability has attracted a number of heuristic approaches to generate satisfactory, if not optimal, candidate solutions. Some methods take their inspiration from natural systems, extracting the salient features of such systems for use in classical computer algorithms. In this paper we demonstrate a simple unconventional computation method to approximate the Euclidean TSP using a virtual material approach. The morphological adaptation behaviour of the material emerges from the low-level interactions of a population of particles moving within a diffusive lattice. A 'blob' of this material is placed over a set of data points projected into the lattice, representing TSP city locations, and the blob is reduced in size over time. As the blob shrinks it morphologically adapts to the configuration of the cities. The shrinkage process automatically stops when the blob no longer completely covers all cities. By manually tracing the perimeter of the blob a path between cities is elicited corresponding to a TSP tour. Over 10 runs on 20 randomly generated datasets consisting of 20 cities this simple and unguided method found tours with a mean average tour length of 6.41 % longer than the minimum tours computed by a TSP solver (mean best performance was 4.27 % longer and mean worst performance was 9.22 % longer). We examine the insertion mechanism by which the blob constructs a tour, note some properties and limitations of its performance, and discuss the relationship between the blob TSP and proximity graphs which group points on the plane. The method is notable for its simplicity, novelty and the spatially represented mechanical mode of its operation. We discuss similarities between this method and previously suggested models of human performance on the TSP and suggest possibilities for further improvement. © 2013 Springer Science+Business Media Dordrecht.

Citation

Jones, J., & Adamatzky, A. (2014). Computation of the travelling salesman problem by a shrinking blob. Natural Computing, 13(1), 1-16. https://doi.org/10.1007/s11047-013-9401-x

• Journal Article Type: Article
• Online Publication Date: Oct 16, 2013
• Publication Date: Mar 1, 2014
• Journal: Natural Computing
• Print ISSN: 1567-7818
• Electronic ISSN: 1572-9796
• Publisher: Springer (part of Springer Nature)
• Peer Reviewed: Peer Reviewed
• Volume: 13
• Issue: 1
• Pages: 1-16
• DOI: https://doi.org/10.1007/s11047-013-9401-x
• Keywords: travelling salesman problem, multi-agent, virtual material, unconventional computation, material computation
• Public URL: https://uwe-repository.worktribe.com/output/820774
• Publisher URL: http://dx.doi.org/10.1007/s11047-013-9401-x