The on-line asymmetric traveling salesman problem

We consider two on-line versions of the asymmetric traveling salesman problem with triangle inequality. For the homing version, in which the salesman is required to return in the city where it started from, we give a $\frac{3+\sqrt{5}}{2}$-competitive algorithm and prove that this is best possible. For the nomadic version, the on-line analogue of the shortest asymmetric Hamiltonian path problem, we show that the competitive ratio of any on-line algorithm depends on the amount of asymmetry of the space in which the salesman moves. We also give bounds on the competitive ratio of on-line algorithms that are zealous, that is, in which the salesman cannot stay idle when some city can be served.     

Uncertain multiobjective traveling salesman problem

Traveling salesman problem is a fundamental combinatorial optimization model studied in the operations research community for nearly half a century, yet there is surprisingly little literature that addresses uncertainty and multiple objectives in it. A novel TSP variation, called uncertain multiobjective TSP (UMTSP) with uncertain variables on the arc, is proposed in this paper on the basis of uncertainty theory, and a new solution approach named uncertain approach is applied to obtain Pareto efficient route in UMTSP. Considering the uncertain and combinatorial nature of UMTSP, a new ABC algorithm inserted with reverse operator, crossover operator and mutation operator is designed to this problem, which outperforms other algorithms through the performance comparison on three benchmark TSPs. Finally, a new benchmark UMTSP case study is presented to illustrate the construction and solution of UMTSP, which shows that the optimal route in deterministic TSP can be a poor route in UMTSP.     

Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem

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²) time, the same as for the homogeneous case, instead of O(n³) as first reported in the literature.     

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.     

On the high multiplicity traveling salesman problem

This paper considers a version of the traveling salesman problem where the cities are to be visited multiple times. Each city has its own required number of visits. We investigate how the optimal solution and its objective value change when the numbers of visits are increased by a common multiplicator. In addition, we derive lower bounds on values of the multiplicator beyond which further increase does not improve the average tour length. Moreover, we show how and when the structure of an optimal tour length can be derived from tours with smaller multiplicities.     

Genetic algorithms for the traveling salesman problem

This paper is a survey of genetic algorithms for the traveling salesman problem. Genetic algorithms are randomized search techniques that simulate some of the processes observed in natural evolution. In this paper, a simple genetic algorithm is introduced, and various extensions are presented to solve the traveling salesman problem. Computational results are also reported for both random and classical problems taken from the operations research literature.     

A bilevel programming approach to the travelling salesman problem

We show that the travelling salesman problem is polynomially reducible to a bilevel toll optimization program. Based on natural bilevel programming techniques, we recover the lifted Miller-Tucker-Zemlin constraints. Next, we derive an O(n²) multi-commodity extension whose LP relaxation is comparable to the exponential formulation of Dantzig, Fulkerson and Johnson.     

Continuous line drawings via the traveling salesman problem

We describe how to use the traveling salesman problem to create continuous line drawings of target pictures.     

Iterative patching and the asymmetric traveling salesman problem

Although Branch-and-Bound (BnB) methods are among the most widely used techniques for solving hard problems, it is still a challenge to make these methods smarter. In this paper, we investigate iterative patching, a technique in which a fixed patching procedure is applied at each node of the BnB search tree for the Asymmetric Traveling Salesman Problem. Computational experiments show that iterative patching results in general in search trees that are smaller than the classical BnB trees, and that solution times are lower for usual random and sparse instances. Furthermore, it turns out that, on average, iterative patching with the Contract-or-Patch procedure of Glover, Gutin, Yeo and Zverovich (2001) and the Karp–Steele procedure are the fastest, and that ‘iterative’ Modified Karp–Steele patching generates the smallest search trees.     

On the nearest neighbor rule for the traveling salesman problem

Rosenkrantz et al. (SIAM J. Comput. 6 (1977) 563) and Johnson and Papadimitriou (in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 1985, pp. 145-180, (Chapter 5)) constructed families of TSP instances with n cities for which the nearest neighbor rule yields a tour-length that is a factor above the length of the optimal tour.We describe two new families of TSP instances, for which the nearest neighbor rule shows the same bad behavior. The instances in the first family are graphical, and the instances in the second family are Euclidean. Our construction and our arguments are extremely simple and suitable for classroom use.     

Transforming asymmetric into symmetric traveling salesman problems

We describe how to transform an asymmetric traveling salesman problem into a symmetric one at the cost of almost doubled problem size. Use and consequences are discussed shortly.     

An O(N log N) planar travelling salesman heuristic based on spacefilling curves

N points in a square of area A may be sorted according to their images under a spacefilling mapping to give a tour of length at most 2√NA. If the points are statistically independent under a smooth distribution, with N large, then the tour will be roughly 25% longer than optimum (and a simple enhancement reduces this to 15%). The algorithm is easily coded: a complete BASIC program is included in the appendix. Since the algorithm consists essentially of sorting, points are easily added or removed. Our method may also be used with simple dynamic programming to solve TSP path problems.     

A new class of cutting planes for the symmetric travelling salesman problem

A comprehensive class of cutting planes for the symmetric travelling salesman problem (TSP) is proposed which contains the known comb inequalities, the path inequalities and the 3-star constraints as special cases. Its relation to the clique tree inequalities is discussed. The cutting planes are shown to be valid for a relaxed version of the TSP, the travelling salesman problem on a road network, and—under certain conditions—to define facets of the polyhedron associated with this problem.     

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.     

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 comparison of lower bounds for the symmetric circulant traveling salesman problem

When the matrix of distances between cities is symmetric and circulant, the traveling salesman problem (TSP) reduces to the so-called symmetric circulant traveling salesman problem (SCTSP), that has applications in the design of reconfigurable networks, and in minimizing wallpaper waste. The complexity of the SCTSP is open, but conjectured to be NP-hard, and we compare different lower bounds on the optimal value that may be computed in polynomial time. We derive a new linear programming (LP) relaxation of the SCTSP from the semidefinite programming (SDP) relaxation in [E. de Klerk, D.V. Pasechnik, R. Sotirov, On semidefinite programming relaxation of the traveling salesman problem, SIAM Journal of Optimization 19 (4) (2008) 1559-1573]. Further, we discuss theoretical and empirical comparisons between this new bound and three well-known bounds from the literature, namely the Held-Karp bound [M. Held, R.M. Karp, The traveling salesman problem and minimum spanning trees, Operations Research 18 (1970) 1138-1162], the 1-tree bound, and the closed-form bound for SCTSP proposed in [J.A.A. van der Veen, Solvable cases of TSP with various objective functions, Ph.D. Thesis, Groningen University, The Netherlands, 1992].     

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.     

A note on the prize collecting traveling salesman problem

We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.Research supported in part by ONR contract N00014-90-J-1649 and NSF contract DDM-8922712.