Cluster based branching for the asymmetric traveling salesman problem
European Journal of Operational ResearchPublished 1 December 1999
Jens Lysgaard
Citations14
SJR quartileQ1
SJR score2.24
SNIP2.62
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new branching scheme for the asymmetric traveling salesman problem (ATSP) based on clusters is presented, implemented in a branch and bound algorithm using a well-known additive bounding procedure.
Abstract
This paper presents a new branching scheme for the asymmetric traveling salesman problem (ATSP) based on clusters. A cluster is defined as a node set with the characteristic that there exists an optimal solution in which the nodes in the node set are visited consecutively. The paper considers identification of clusters, implementation of a cluster based branching scheme, and cluster based dominance tests. The new approach is implemented in a branch and bound algorithm using a well-known additive bounding procedure. Considerable savings in computing time are obtained compared to previously published assignment based branch and bound algorithms for the ATSP.
Keywords
Computer ScienceEngineering
INFORMS Journal on ComputingTSPLIB—A Traveling Salesman Problem Library
2,570 Citations1991Gerhard Reinelt
This paper contains the description of a traveling salesman problem library (TSPLIB) which is meant to provide researchers with a broad set of test problems from various sources and with various properties.
Journal of the Society for Industrial and Applied MathematicsA Dynamic Programming Approach to Sequencing Problems
1,253 Citations1962Michael Held, Richard M. Karp
Mathematical ProgrammingA lift-and-project cutting plane algorithm for mixed 0–1 programs
722 Citations1993Egon Balas, Sebastián Ceria +1 more
A cutting plane algorithm for mixed 0–1 programs based on a family of polyhedra which strengthen the usual LP relaxation and shows how to generate a facet of a polyhedron in this family which is most violated by the current fractional point.
SIAM Journal on ComputingA Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
172 Citations1979Richard M. Karp
The algorithm first solves the assignment problem for the matrix D, and then patches the cycles of the optimum assignment together to form a tour, which tends to give nearly optimal solutions when the number of cities is extremely large.
Management ScienceSome New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
165 Citations1980G. Carpaneto, Paolo Toth
This paper presents a breadth-first branch and bound algorithm which differs from the method of Smith, Srinivasan and Thompson in the selection of the subtour to be split, in the ordering of the arcs in the selected subtour, and in the computation of different partial lower bounds and in different data structures to facilitate the updating of the cost matrix.
Mathematical ProgrammingA restricted Lagrangean approach to the traveling salesman problem
147 Citations1981Egon Balas, Nicos Christofides
An algorithm for the asymmetric traveling salesman problem (TSP) using a new, restricted Lagrangean relaxation based on the assignment problem (AP) that can be adapted to the symmetric TSP by using the 2-matching problem instead of AP is described.
Operations ResearchPathology of Traveling-Salesman Subtour-Elimination Algorithms
128 Citations1971Mandell Bellmore, John C. Malone
An underlying theory for the traveling-salesman problem is developed, pathological performance of some existing techniques are predicted, and two algorithms are presented, based upon the theory, with predictable polynomial growth in expected computation time and resistence to pathological problems.
Operations ResearchAn Additive Bounding Procedure for Combinatorial Optimization Problems
117 Citations1989Matteo Fischetti, Paolo Toth
An additive approach for computing lower bounds that yields an increasing sequence of values and an application to the traveling salesman problem with precedence constraints is presented to exemplify the technique.
Mathematical ProgrammingAn additive bounding procedure for the asymmetric travelling salesman problem
83 Citations1992Matteo Fischetti, Paolo Toth
New lower bounds for the asymmetric travelling salesman problem are presented, based on spanning arborescences, in an additive procedure whose theoretical performance is compared with that of the Balas and Christofides procedure (1981).
Operations ResearchTechnical Note—Bounds for the Travelling-Salesman Problem
55 Citations1972Nicos Christofides
A tight lower bound to the travelling-salesman problem is found by an iterative procedure with guaranteed convergence and is shown to require a computation time only about 9 per cent greater than the time required to solve an equivalent assignment problem.
INFORMS Journal on ComputingAn Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
42 Citations1993Matteo Fischetti, Paolo Toth
An efficient algorithm for the solution of the Min-Sum Arborescence Problem with fixed root-vertex in complete digraphs is presented, based on the well-known Edmonds method, leading to improvements affecting both computing times and memory requirements.
Operations ResearchTechnical Note—On Partitioning the Feasible Set in a Branch-and-Bound Algorithm for the Asymmetric Traveling-Salesman Problem
30 Citations1973Robert Garfinkel
This note develops a branching scheme for a branch-and-bound algorithm for the traveling-salesman problem that improves on the algorithm of Bellmore and Malone in that a partition of the feasible set is achieved at every vertex of the enumeration tree.