Book Description
Provides an in-depth treatment of the Traveling Salesman problem--the archetypical problem in combinatorial optimization. Each chapter deals with a different aspect of the problem, and has been written by an acknowledged expert in the field. Focusses on the essential ideas in a self-contained manner. Includes exercises and an extensive bibliography. ... Read more

Book Description

This book presents the latest findings on one of the most intensely investigated subjects in computational mathematics--the traveling salesman problem. It sounds simple enough: given a set of cities and the cost of travel between each pair of them, the problem challenges you to find the cheapest route by which to visit all the cities and return home to where you began. Though seemingly modest, this exercise has inspired studies by mathematicians, chemists, and physicists. Teachers use it in the classroom. It has practical applications in genetics, telecommunications, and neuroscience.

The authors of this book are the same pioneers who for nearly two decades have led the investigation into the traveling salesman problem. They have derived solutions to almost eighty-six thousand cities, yet a general solution to the problem has yet to be discovered. Here they describe the method and computer code they used to solve a broad range of large-scale problems, and along the way they demonstrate the interplay of applied mathematics with increasingly powerful computing platforms. They also give the fascinating history of the problem--how it developed, and why it continues to intrigue us.

Customer Reviews (1)

Twenty years in the making
The coauthors have been working at solving large scale traveling saleman problem instances for more than 20 years. This book, along with the publicly available Concorde code, is the culmination of that twenty years of work.

The first four chapters of the book (130 pages or so) are an extremely readable description of the use and history of the traveling salesman problem.For our field, the traveling salesman problem has been an exemplar of a hard combinatorial problem, commonly used to test new ideas in problem solving.It is no coincidence that the first papers on simulated annealing, DNA computing, and other approaches for combinatorial problems describe their methods in the context of the TSP:it is the most well known of all the problems in operations research.

The authors' primary emphasis is on computation:how can optimal tours be found?The history of TSP computation is very much the history of computational combinatorial optimization.From the fundamental work of Dantzig, Fulkerson, and Johnson in solving the famous 42-city example, through Held and Karp's relaxations andLin-Kernighan's improvement heuristics, to modern-day branch-and-cut, the TSP has been at the forefront of computational methods in our field.The description of this history is outstanding, and appropriately nontechnical, suitable for reading by beginners in operations research.

The main part of the book is on the computational approaches needed to solve large TSPs.This part is well-written, though beyond a beginner level.Despite that, it has broad interest in the way it melds computational issues (like data structures and heuristic ordering) with the theory.

At the end, this book is an exemplar for how to do research in computational operations research.While not aimed at the non-specialist, it is perfectly readable by those who have gone through an introduction in optimization or operations research.
... Read more

Book Description
This volume, which contains chapters written by reputable researchers, provides the state of the art in theory and algorithms for the traveling salesman problem (TSP). The book covers all important areas of study on TSP, including polyhedral theory for symmetric and asymmetric TSP, branch and bound, and branch and cut algorithms, probabilistic aspects of TSP, thorough computational analysis of heuristic and metaheuristic algorithms, theoretical analysis of approximation algorithms, including the emerging area of domination analysis of algorithms, discussion of TSP software and variations of TSP such as bottleneck TSP, generalized TSP, prize collecting TSP, maximizing TSP, orienteering problem, etc. The book is appropriate as a reference work or as a main or supplemental textbook in graduate and senior undergraduate courses and projects. ... Read more

Product Description
This is a AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH SCHOOL OF ENGINEERING AND MANAGEMENT report procured by the Pentagon and made available for public release. It has been reproduced in the best form available to the Pentagon. It is not spiral-bound, but rather assembled with Velobinding in a soft, white linen cover. The Storming Media report number is A100293. The abstract provided by the Pentagon follows: The surveillance mission requires aircraft to fly from a starting point through defended terrain to targets and return to a safe destination (usually the starting point). The process of selecting such a flight path is known as the Mission Route Planning (MRP) Problem and is a three-dimensional, multi-criteria (fuel expenditure, time required, risk taken, priority targeting, goals met, etc.) path search. Planning aircraft routes involves an elaborate search through numerous possibilities, which can severely task the resources of the system being used to compute the routes. Operational systems can take up to a day to arrive at a solution due to the combinatoric nature of the problem. This delay is not acceptable because timeliness of obtaining surveillance information is critical in many surveillance missions. Also, the information that the software uses to solve the MRP may become invalid during computation. An effective and efficient way of solving the MRP with multiple aircraft and multiple targets is desired. One approach to finding solutions is to simplify and view the problem as a two-dimensional, minimum path problem. This approach also minimizes fuel expenditure, time required, and even risk taken. The simplified problem is then the Traveling Salesman Problem (TSP). ... Read more

Book Description
This digital document is a journal article from European Journal of Operational Research, published by Elsevier in 2005. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
Data structures play a crucial role in the efficient implementation of local search algorithms for problems that require circuit optimization in graphs. The traveling salesman problem (TSP) is the benchmark problem used in this study where two implementations of the stem-and-cycle (S&C) ejection chain algorithm are compared. The first implementation uses an Array data structure organized as a doubly linked list to represent TSP tours as well as the S&C reference structure. The second implementation considers a two-level tree structure. The motivation for this study comes from the fact that the S&C neighborhood structure usually requires subpaths to be reversed in order to preserve a feasible orientation for the resulting tour. The traditional Array structure proves to be inefficient for large-scale problems since to accomplish a path reversal it is necessary to update the predecessor and the successor of each node on the path to be reversed. Computational results performed on a set of benchmark problems up to 316,228 nodes clearly demonstrate the relative efficiency of the two-level tree data structure. ... Read more

Book Description
This digital document is a journal article from Computers and Operations Research, published by Elsevier in 2005. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
As size of the traveling salesman problem (TSP) increases, it is unreasonable to find efficiently an optimum or near-optimum. Instead of considering all arcs, if we select and consider only some arcs more likely to be included in an optimal solution, we can find efficiently an optimum or near-optimum. A candidate arc set is a group of some good arcs. For the lack of study in the asymmetric TSP, it needs to research systematically for the candidate arc set of the asymmetric TSP. In this paper, we suggest a regression function determining a candidate arc set for the asymmetric TSP. We established the regression function based on 2100 experiments, and we proved the goodness of fit for it through various 787 problems. Also, we applied it to the Out-of-Kilter heuristic. We tested it on 220 random instances and 23 real-world instances. Because the complexity of the heuristic depends on the number of arcs and we considered only the candidate arc set, we found good solutions about 2-5 fold faster than considering all arcs. ... Read more

Book Description
This digital document is a journal article from Computers and Operations Research, published by Elsevier in 2004. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
We propose a heuristic algorithm for the solution of the period traveling salesman problem. Computational results obtained on the classical test instances of the literature show that the total distance obtained by the algorithm is not worse than the best-known total distance in 95% of the instances and is strictly better in 18 of the 40 tested instances. ... Read more

Book Description
This digital document is a journal article from Transportation Research Part E, published by Elsevier in 2005. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
This paper investigates the development and application of a general meta-heuristic, Meta-RaPS (meta-heuristic for randomized priority search), to the traveling salesman problem (TSP). The Meta-RaPS approach is tested on several established test sets. The Meta-RaPS approach outperformed most other solution methodologies in terms of percent difference from optimal. Additionally, an industry case study that incorporates Meta-RaPS TSP in a large truck route assignment model is presented. The company estimates a more than 50% reduction in engineering time and over $2.5 million annual savings in transportation costs using the automated Meta-RaPS TSP tool compared to their current method. ... Read more

Book Description
This digital document is a journal article from European Journal of Operational Research, published by Elsevier in 2004. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
We show that some asymmetric traveling salesman problem (ATSP) instances are approximable within bounds equal to 3 and 9/5, when they satisfy sufficient conditions more restrictive than the triangle inequality, very simple to test and nicely structured: they only depend on a measure of satisfaction of the triangle inequality and a measure of the graph asymmetry. We discuss the applicability of such conditions and we present two preprocessing linear programs to reformulate ATSP instances into equivalent ones achieving data-dependent bounds by the same approximation algorithms. ... Read more

Book Description
This digital document is a journal article from European Journal of Operational Research, published by Elsevier in 2005. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
The probabilistic traveling salesman problem concerns the best way to visit a set of customers located in some metric space, where each customer requires a visit only with some known probability. A solution to this problem is an a priori tour which visits all customers, and the objective is to minimize the expected length of the a priori tour over all customer subsets, assuming that customers in any given subset must be visited in the same order as they appear in the a priori tour. This problem belongs to the class of stochastic vehicle routing problems, a class which has received increasing attention in recent years, and which is of major importance in real world applications. Several heuristics have been proposed and tested for the probabilistic traveling salesman problem, many of which are a straightforward adaptation of heuristics for the classical traveling salesman problem. In particular, two local search algorithms (2-p-opt and 1-shift) were introduced by Bertsimas. In a previous report we have shown that the expressions for the cost evaluation of 2-p-opt and 1-shift moves, as proposed by Bertsimas, are not correct. In this paper we derive the correct versions of these expressions, and we show that the local search algorithms based on these expressions perform significantly better than those exploiting the incorrect expressions. ... Read more

Book Description
This digital document is a journal article from Computers and Operations Research, published by Elsevier in 2006. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
In the probabilistic traveling salesman problem (PTSP), customers require a visit with a given probability, and the best solution is the tour through all customers with the lowest expected final tour cost. The PTSP is an important problem, both operationally and strategically, but is quite difficult to solve with realistically sized problem instances. One alternative is to aggregate customers into regions and solve the PTSP on the reduced problem. This approach raises questions such as how to best divide customers into regions and what scale is necessary to represent the full objective. This paper addresses these questions and presents computational results from experiments with both uniformly distributed and clustered data sets. The focus is on large problem instances where customers have a low probability of requiring a visit and the CPU time available is quite limited. For this class of instances, aggregation can yield very tight estimates of the full objective very quickly, and solving an aggregated form of the problem first can often lead to full solutions with lower expected costs. ... Read more

Book Description
This digital document is a journal article from Computers and Operations Research, published by Elsevier in 2007. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
The probabilistic traveling salesman problem (PTSP) is an important theoretical and practical topic in the study of stochastic network problems. It provides researchers with a modeling framework for exploring the stochastic effects in routing problems. This paper focuses on developing the hybrid scatter search (HSS) by incorporating the nearest neighbor rule (NNR), threshold accepting (TA) and edge recombination (ER) crossover into a scatter search conceptual framework to solve the PTSP. A set of numerical experiments were conducted to test the validity of the HSS based on the test problems from Tang and Miller-Hooks' study. The numerical results showed that the HSS can effectively solve the PTSP in most of the tested cases in terms of objective function value. Moreover, the results also indicated that incorporating threshold accepting into the scatter search framework can further increase the computation efficiency while maintaining solution quality. These findings show the potential of the proposed HSS in solving the large-scale PTSP. ... Read more

Book Description
This digital document is a journal article from European Journal of Operational Research, published by Elsevier in 2007. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
In real life scheduling, variations of the standard traveling salesman problem are very often encountered. The aim of this work is to present a new heuristic method for solving three such special instances with a common approach. The proposed algorithm uses a variant of the threshold accepting method, enhanced with intense local search, while the candidate solutions are produced through an insertion heuristic scheme. The main characteristic of the algorithm is that it does not require modifications and parameter tuning in order to cope with the three different problems. Computational results on a variety of real life and artificial problems are presented at the end of this work and prove the efficiency and the ascendancy of the proposed method over other algorithms found in the literature. ... Read more

Book Description
This digital document is a journal article from European Journal of Operational Research, published by Elsevier in 2007. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
The probabilistic traveling salesman problem is a well known problem that is quite challenging to solve. It involves finding the tour with the lowest expected cost for customers that will require a visit with a given probability. There are several proposed algorithms for the homogeneous version of the problem, where all customers have identical probability of being realized. From the literature, the most successful approaches involve local search procedures, with the most famous being the 2-p-opt and 1-shift procedures proposed by Bertsimas [D.J. Bertsimas, L. Howell, Further results on the probabilistic traveling salesman problem, European Journal of Operational Research 65 (1) (1993) 68-95]. Recently, however, evidence has emerged that indicates the equations offered for these procedures are not correct, and even when corrected, the translation to the heterogeneous version of the problem is not simple. In this paper we extend the analysis and correction to the heterogeneous case. We derive new expressions for computing the cost of 2-p-opt and 1-shift local search moves, and we show that the neighborhood of a solution may be explored in O(n^2) time, the same as for the homogeneous case, instead of O(n^3) as first reported in the literature. ... Read more

Product Description
This is a AIR FORCE INST OF TECH WRIGHT-PATTERSONAFB OH SCHOOL OFENGINEERING report procured by the Pentagon and made available for public release. It has been reproduced in the best form available to the Pentagon. It is not spiral-bound, but rather assembled with Velobinding in a soft, white linen cover. The Storming Media report number is A123873. The abstract provided by the Pentagon follows: The traveling salesman problem (TSP) is a combinatorial optimizationproblem that is mathematically modeled as a binary integer program. The TSP is a very important problem for the operations research academician and practitioner. This research demonstrates a Group Theoretic Tabu Search (GTTS) Java algorithmfor the TSP. The tabu search metaheuristic continuously finds near-optimalsolutions to the TSP under various different implementations. Algebraic grouptheory offers a more formal mathematical setting to study the TSP providing atheoretical foundation for describing tabu search. Specifically, this thesisuses the Symmetric Group on n letters, S(n), which is the set of all n!permutations on n letters whose binary operation is permutation multiplication,to describe the TSP solution space. Thus, the TSP is studied as a permutationproblem rather than an integer program by applying the principles of grouptheory to define the tabu search move and neighborhood structure. The grouptheoretic concept of conjugation (an operation involving two group elements)simplifies the move definition as well as the intensification and diversification strategies. Conjugation in GTTS diversifies the search byallowing large rearrangement moves within a tour in a single move operation.Empirical results are presented along with the theoretical motivations for theresearch. ... Read more

Book Description
This digital document is a journal article from Computers and Operations Research, published by Elsevier in 2006. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
The state-of-the-art of local search heuristics for the traveling salesman problem (TSP) is chiefly based on algorithms using the classical Lin-Kernighan (LK) procedure and the stem-and-cycle (S&C) ejection chain method. Critical aspects of implementing these algorithms efficiently and effectively rely on taking advantage of special data structures and on maintaining appropriate candidate lists to store and update potentially available moves. We report the outcomes of an extensive series of tests on problems ranging from 1000 to 1,000,000 nodes, showing that by intelligently exploiting elements of data structures and candidate lists routinely included in state-of-the-art TSP solution software, the S&C algorithm clearly outperforms all implementations of the LK procedure. Moreover, these outcomes are achieved without the use of special tuning and implementation tricks that are incorporated into the leading versions of the LK procedure to enhance their computational efficiency. y. ... Read more