Fast Algorithms for Geometric Traveling Salesman Problems

Bentley, Jon Jouis
September 1992
ORSA Journal on Computing;Fall92, Vol. 4 Issue 4, p387
Academic Journal
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). Experiments indicate that most of the algorithms run in O(N log N) time on uniform data sets, and many run almost as fast on very nonuniform data. The program that implements the algorithms is able to solve uniform planar million-city traveling salesman problems to within a few percent of optimal in several midicomputer CPU hours. The algorithms and program apply to many distance metrics and dimensions.


Related Articles

  • Chained Lin-Kernighan for Large Traveling Salesman Problems. Applegate, David; Cook, William; Rohe, AndrĂ© // INFORMS Journal on Computing;Winter2003, Vol. 15 Issue 1, p82 

    We discuss several issues that arise in the implementation of Martin, Otto, and Felten's Chained Lin-Kernighan heuristic for large-scale traveling salesman problems. Computational results are presented for TSPLIB instances ranging in size from 11,849 cities up to 85,900 cities; for each of these...

  • The Accumulated Experience Ant Colony for the Traveling Salesman Problem. Montgomery, James; Randall, Marcus // International Journal of Computational Intelligence & Applicatio;Jun2003, Vol. 3 Issue 2, p189 

    Ant colony optimization techniques are usually guided by pheromone and heuristic cost information when choosing the next element to add to a solution. However, while an individual element may be attractive, usually its long term consequences are neither known nor considered. For instance, a...

  • 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...

  • Computation of the travelling salesman problem by a shrinking blob. Jones, Jeff; Adamatzky, Andrew // Natural Computing;Mar2014, Vol. 13 Issue 1, p1 

    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...

  • An Exact Algorithm for TSP Based on Time-Delay Message Broadcasting Mechanism in Cloud Computing Environment. Hao Jiang; Tundong Liu; Jing Chen // Advances in Information Sciences & Service Sciences;Nov2012, Vol. 4 Issue 20, p299 

    This paper introduces a novel exact algorithm based on cloud computing for successfully solving the traveling salesman problem, which is a classical problem in discrete or combinatorial optimization and belongs to the NP-complete classes. The proposed algorithm, Time-delay Message Broadcasting...

  • Discrete bacteria foraging optimization algorithm for solving TSP. WANG Yong-zhen; CHEN Yan; LI Tao-ying // Application Research of Computers / Jisuanji Yingyong Yanjiu;Dec2014, Vol. 31 Issue 12, p3642 

    Traveling salesman problem (TSP ) is a typical representative of combinatorial optimization problems. This paper proposed a discrete bacteria foraging optimization(DBFO) algorithm to tackle the TSP. It designed a new chemotaxis operator which was combined with 2-opt algorithm so as to handle...

  • 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...

  • 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...


Read the Article


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

Try another library?
Sign out of this library

Other Topics