The traveling salesman problem on a graph and some related integer polyhedra

Given a graphG = (N, E) and a length functionl: E , the Graphical Traveling Salesman Problem is that of finding a minimum length cycle goingat least once through each node ofG. This formulation has advantages over the traditional formulation where each node must be visited exactly once. We give some facet inducing inequalities of the convex hull of the solutions to that problem. In particular, the so-called comb inequalities of Grötschel and Padberg are generalized. Some related integer polyhedra are also investigated. Finally, an efficient algorithm is given whenG is a series-parallel graph.Work was supported in part by NSF grant ECS-8205425.     

Improving Christofides' lower bound for the traveling salesman problem

In 1972 Christofides introduced a lower bound for the Traveling Salesman Problem (TSP). The bound is based on solving repeatedly a Linear Assignment Problem. We relate the bound to the Complete Cycle Problem; as a consequence the correctness of the bound is easier to prove.

Further we give improvements for the bound in the symmetric case and we deal with the influence of the triangle equation together with the identification of non-optimal edges for the TSP. The improvements are illustrated by examples and computational results for large problems.     

A note on heuristics for the traveling salesman problem

We introduce subclasses of the traveling salesman problem (TSP) and analyze the behaviour of heuristics on them. We derive bounds for the performance of the algorithms.     

Tight bounds for christofides' traveling salesman heuristic

Christofides [1] proposes a heuristic for the traveling salesman problem that runs in polynomial time. He shows that when the graphG = (V, E) is complete and the distance matrix defines a function onV × V that is metric, then the length of the Hamiltonian cycle produced by the heuristic is always smaller than 3/2 times the length of an optimal Hamiltonian cycle. The purpose of this note is to refine Christofides' worst-case analysis by providing a tight bound for everyn 3, wheren is the number of vertices of the graph. We also show that these bounds are still tight when the metric is restricted to rectilinear distances, or to Euclidean distances for alln 6.This work was supported, in part, by NSF Grant ENG 75-00568 to Cornell University. This work was done when the authors were affiliated with the Center for Operations Research and Econometrics, University of Louvain, Belgium.     

On the refinement of bounds of heuristic algorithms for the traveling salesman problem

A number of heuristics for the traveling salesman problem (TSP) rely on the assumption that the triangle inequality (TI) is satisfied. When TI does not hold, the paper proposes a transformation such that for the transformed problem the TI holds. Consequently, the bounds obtained for heuristics are valid with appropriate modification. Moreover, for a TSP satisfying TI the same transformation strengthens such bounds. The transformation essentially maps the problem into one that is minimal with respect to the property that TI holds. For the symmetric TSP the transformation is particularly simple. For an application of the transformation in the asymmetric case we need the dual solution of an assignment problem.     

A continuous variable representation of the traveling salesman problem

The classic traveling salesman problem is characterized in terms of continuous flows on a specially constructed non-conservative network, in 2n – 1 linear constraints and a cardinality constraint. It is shown that every solution to the network problem is a hamiltonian circuit.     

On the graphical relaxation of the symmetric traveling salesman polytope

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope as well. In this paper we give an affirmative answer to this question for n ≥ 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to the starting vertex. Thus there must have been a third vertex on the way.      

A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone

In this short communication, we observe that the Graphical Traveling Salesman Polyhedron is the intersection of the positive orthant with the Minkowski sum of the Symmetric Traveling Salesman Polytope and the polar of the metric cone. This follows almost trivially from known facts. There are nonetheless two reasons why we find this observation worth communicating: It is very surprising; it helps us understand the relationship between these two important families of polyhedra.     

Creating lasso-solutions for the traveling salesman problem with pickup and delivery by Tabu search

We consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD) where the same costumers might require both deloverie of goods and pickup of other goods. All the goods should be transported from/to the same depot. A vehicle on a TSPPD-tour could often get some practical problems when arranging the load. Even if the vehicle has enough space for all the pickups, one has to consider that they are stored in a way that doesn't block the delivery for the next customer. In real life problems this occurs for instance for breweries when they deliver bottles of beer or mineral water and collects empty bottles from the same customers on the same tour. In these situations we could relax the constraints of only checking Hamiltonian tours, and also try solutions that can visit customers in a way giving rise to a ‘alsso’ model. A solution which first only delivers bottles until the vehicle is partly unloaded, then do both delivery and pickup at the remaining customers and at last picks up the empty bottle from the first visited customers, could in these situations be better than a pure Hamiltonian tour, at least in a practical setting. To find such solutions, we will use the metaheuristic Tabu Search on some well known TSPPD-problems, and compare them to other kinds of solutions on the same problems.     

The adjacency relation on the traveling salesman polytope is NP-Complete

We consider the problem of determining whether two traveling salesman tours correspond to non-adjacent vertices of the convex polytope associated with the traveling salesman problem. This problem is shown to be NP-Complete for both the symmetric and nonsymmetric traveling salesman problem. Several implications are discussed.This Research was supported by NSF Grant GK-420488, the U.S. Army Research Office-Durham under Grant DAHC04-75-G0192, and an IBM Fellowship.     

A restricted Lagrangean approach to the traveling salesman problem

We describe an algorithm for the asymmetric traveling salesman problem (TSP) using a new, restricted Lagrangean relaxation based on the assignment problem (AP). The Lagrange multipliers are constrained so as to guarantee the continued optimality of the initial AP solution, thus eliminating the need for repeatedly solving AP in the process of computing multipliers. We give several polynomially bounded procedures for generating valid inequalities and taking them into the Lagrangean function with a positive multiplier without violating the constraints, so as to strengthen the current lower bound. Upper bounds are generated by a fast tour-building heuristic. When the bound-strengthening techniques are exhausted without matching the upper with the lower bound, we branch by using two different rules, according to the situation: the usual subtour breaking disjunction, and a new disjunction based on conditional bounds. We discuss computational experience on 120 randomly generated asymmetric TSP's with up to 325 cities, the maximum time used for any single problem being 82 seconds. This is a considerable improvement upon earlier methods. Though the algorithm discussed here is for the asymmetric TSP, the approach can be adapted to the symmetric TSP by using the 2-matching problem instead of AP.Research supported by the National Science Foundation through grant no. MCS76-12026 A02 and the U.S. Office of Naval Research through contract no. N0014-75-C-0621 NR 047-048.     

The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities

The graphical relaxation of the Traveling Salesman Problem is the relaxation obtained by requiring that the salesman visit each city at least once instead of exactly once. This relaxation has already led to a better understanding of the Traveling Salesman polytope in Cornuéjols, Fonlupt and Naddef (1985). We show here how one can compose facet-inducing inequalities for the graphical traveling salesman polyhedron, and obtain other facet-inducing inequalities. This leads to new valid inequalities for the Symmetric Traveling Salesman polytope. This paper is the first of a series of three papers on the Symmetric Traveling Salesman polytope, the next one studies the strong relationship between that polytope and its graphical relaxation, and the last one applies all the theoretical developments of the two first papers to prove some new facet-inducing results.This work was initiated while the authors were visiting the Department of Statistics and Operations Research of New York University, and continued during several visits of the first author at IASI.     

The traveling salesman problem with few inner points

We propose two algorithms for the planar Euclidean traveling salesman problem. The first runs in O(k!kn) time and O(k) space, and the second runs in O(2^kk²n) time and O(2^kkn) space, where n denotes the number of input points and k denotes the number of points interior to the convex hull.     

The multi-commodity one-to-one pickup-and-delivery traveling salesman problem

This paper concerns a generalization of the traveling salesman problem (TSP) called multi-commodity one-to-one pickup-and-delivery traveling salesman problem (m-PDTSP) in which cities correspond to customers providing or requiring known amounts of m different commodities, and the vehicle has a given upper-limit capacity. Each commodity has exactly one origin and one destination, and the vehicle must visit each customer exactly once. The problem can also be defined as the capacitated version of the classical TSP with precedence constraints. This paper presents two mixed integer linear programming models, and describes a decomposition technique for each model to find the optimal solution. Computational experiments on instances from the literature and randomly generated compare the techniques and show the effectiveness of our implementation.     

The traveling salesman problem: A duality approach

In this study we formulate the dual of the traveling salesman problem, which extends in a natural way the dual problem of Held and Karp to the nonsymmetric case. The dual problem is solved by a subgradient optimization technique. A branch and bound scheme with stepped fathoming is then used to find optimal and suboptimal tours. Computational experience for the algorithm is presented.This author's work was partially supported by NSF Grant #GK-38337.     

A stochastic dynamic traveling salesman problem with hard time windows

Just-in-time (JIT) trucking service, i.e., arriving at customers within specified time windows, has become the norm for freight carriers in all stages of supply chains. In this paper, a JIT pickup/delivery problem is formulated as a stochastic dynamic traveling salesman problem with time windows (SDTSPTW). At a customer location, the vehicle either picks up goods for or delivers goods from the depot, but does not provide moving service to transfer goods from one location to another. Such routing problems are NP-hard in deterministic settings, and in our context, complicated further by the stochastic, dynamic nature of the problem. This paper develops an efficient heuristic for the SDTSPTW with hard time windows. The heuristic is shown to be useful both in controlled numerical experiments and in applying to a real-life trucking problem.     

Exact algorithms for the traveling salesman problem with draft limits

This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance compared through extensive computational experiments. Optimal solutions are reported for open instances of benchmark problems available in the literature.     

Exploiting planarity in separation routines for the symmetric traveling salesman problem

At present, the most successful approach for solving large-scale instances of the Symmetric Traveling Salesman Problem to optimality is branch-and-cut. The success of branch-and-cut is due in large part to the availability of effective separation procedures; that is, routines for identifying violated linear constraints.

For two particular classes of constraints, known as comb and domino-parity constraints, it has been shown that separation becomes easier when the underlying graph is planar. We continue this line of research by showing how to exploit planarity in the separation of three other classes of constraints: subtour elimination, 2-matching and simple domino-parity constraints.