Computation of the travelling salesman problem by a shrinking blob

Jones, Jeff; Adamatzky, Andrew
March 2014
Natural Computing;Mar2014, Vol. 13 Issue 1, p1
Academic Journal
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.


Related Articles

  • Wisdom of Artificial Crowds-A Metaheuristic Algorithm for Optimization. Yampolskiy, Roman V.; Ashby, Leif; Hassan, Lucas // Journal of Intelligent Learning Systems & Applications;May2012, Vol. 4 Issue 2, p98 

    Finding optimal solutions to NP-Hard problems requires exponential time with respect to the size of the problem. Consequently, heuristic methods are usually utilized to obtain approximate solutions to problems of such difficulty. In this paper, a novel swarm-based nature-inspired metaheuristic...

  • Open Vehicle Routing Problem by Ant Colony Optimization. GurpreetSingh; Dhir, Vijay // International Journal of Advanced Computer Science & Application;2014, Vol. 5 Issue 3, p63 

    Vehicle routing problem (VRP) is real-world combinatorial optimization problem which determine the optimal route of a vehicle. Generally, to provide the efficient vehicle serving to the customer through different services by visiting the number of cities or stops, the VRP follows the Travelling...

  • Velocity Tentative PSO: An Optimal Velocity Implementation based Particle Swarm Optimization to Solve Traveling Salesman Problem. Akhand, M. A. H.; Akter, Shahina; Rashid, M. A.; Yaakob, S. B. // IAENG International Journal of Computer Science;Sep2015, Vol. 42 Issue 3, p221 

    This paper introduces an effective Particle Swarm Optimization (PSO) based algorithm for solving Traveling Salesman Problem (TSP). Among prominent PSO based methods, the proposed Velocity Tentative PSO (VTPSO) considers Swap Sequence (SS) for velocity operation of the particles. A velocity SS is...

  • A Discrete Fruit Fly Optimization Algorithm for the Traveling Salesman Problem. Jiang, Zi-bin; Yang, Qiong // PLoS ONE;11/3/2016, Vol. 11 Issue 11, p1 

    The fruit fly optimization algorithm (FOA) is a newly developed bio-inspired algorithm. The continuous variant version of FOA has been proven to be a powerful evolutionary approach to determining the optima of a numerical function on a continuous definition domain. In this study, a discrete FOA...

  • Fast Algorithms for Geometric Traveling Salesman Problems. Bentley, Jon Jouis // ORSA Journal on Computing;Fall92, Vol. 4 Issue 4, p387 

    This paper describes efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets. We describe implementations of a dozen starting heuristics (including Nearest Neighbor and Farthest Insertion) and three local optimizations (including 2-Opt and 3-Opt)....

  • Double-ended nearest and loneliest neighbour - a nearest neighbour heuristic variation for the travelling salesman problem. Pimentel, Fernando Guilherme Silvano Lobo // Proceedings of Trends in the Development of Machinery & Associat;2011, p17 

    This paper presents a new tour construction heuristic for the travelling salesman problem that introduces the concept of loneliness of a city computed from the average distance of that city to all others and combines it with ideas from other nearest neighbour heuristics. Having the same time...

  • A backbone based TSP heuristic for large instances. J├Ąger, Gerold; Dong, Changxing; Goldengorin, Boris; Molitor, Paul; Richter, Dirk // Journal of Heuristics;Feb2014, Vol. 20 Issue 1, p107 

    We introduce a reduction technique for large instances of the traveling salesman problem (TSP). This approach is based on the observation that tours with good quality are likely to share many edges. We exploit this observation by neglecting the less important tour space defined by the shared...

  • Performance Assessment over Heuristic Population Seeding Techniques of Genetic Algorithm: Benchmark Analyses on Traveling Salesman Problems. Shanmugam, M.; Saleem Basha, M. S.; Paul, P. Victer; Dhavachelvan, P.; Baskaran, R. // International Journal of Applied Engineering Research;2013, Vol. 8 Issue 10, p1171 

    Traveling Salesman Problem (TSP) is most widely studied combinational optimization problem and Genetic Algorithm (GA) is a familiar meta-heuristic search technique applied to find the optimal solution for the complex problem effectively. In GA, the quality of solutions in population...

  • A CENTROID-BASED HEURISTIC ALGORITHM FOR THE CAPACITATED VEHICLE ROUTING PROBLEM. Kwangcheol SHIN; Sangyong HAN // Computing & Informatics;2011, Vol. 30 Issue 4, p721 

    The vehicle routing problem (VRP) is famous as a nondeterministic polynomial-time hard problem. This study proposes a centroid-based heuristic algorithm to solve the capacitated VRP in polynomial time. The proposed algorithm consists of three phases: cluster construction, cluster adjustment, and...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics