On the equivalence between some local and global Chinese postman and traveling salesman graphs

A connected graph G=(V,E), a vertex in V and a non-negative weight function defined on E can be used to induce Chinese postman and traveling salesman (cooperative) games. A graph G=(V,E) is said to be locally (respectively, globally) Chinese postman balanced (respectively, totally balanced, submodular) if for at least one vertex (respectively, for all vertices) in V and any non-negative weight function defined on E, the corresponding Chinese postman game is balanced (respectively, totally balanced, submodular). Local and global traveling salesman balanced (respectively, totally balanced, submodular) graphs are similarly defined.In this paper, we study the equivalence between local and global Chinese postman balanced (respectively, totally balanced, submodular) graphs, and between local and global traveling salesman submodular graphs.     

An asymmetric analog of van der Veen conditions and the traveling salesman problem (II)

J.A.A. van der Veen [A new class of pyramidally solvable symmetric traveling salesman problems, SIAM J. Discrete Math. 7 (1994) 585–592] proved that for the traveling salesman problem (TSP) which satisfies some symmetric conditions (called van der Veen conditions), a shortest pyramidal tour is optimal, that is, an optimal tour can be computed in polynomial time. In this paper, we prove that a class satisfying an asymmetric analog of van der Veen conditions is polynomially solvable. An optimal tour of the instance in this class forms a tour which is an extension of pyramidal ones. Moreover, this class properly includes some known polynomially solvable classes.     

Match twice and stitch: a new TSP tour construction heuristic

We present a new symmetric traveling salesman problem tour construction heuristic. Two sequential matchings yield a set of cycles over the given point set; these are then stitched to form a tour. Our method outperforms all previous tour construction methods, but is dominated by several tour improvement heuristics.     

Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms

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.     

On the solutions of stochastic traveling salesman problems

We consider the n-city traveling salesman problem where the distances between the cities are nondeterministic. Our purpose is to estimate the expectation of the length of the optimal tour. This is done by calculating the expectations of a lower bound and an upper bound for the length of the optimal tour. Because the upper bound is formed by the well-known nearest neighbour rule, we can simultaneously find the cases where this rule is effective in the mean. If we let the number of cities grow, we obtain symptotic results that are totally determined by the behaviour of the distribution of the distance between any two points in the neighbourhood of the distance zero.     

Algorithms for the universal and a priori TSP

We present two simple results for generalizations of the traveling salesman problem (TSP): for the universal TSP, we show that one can compute a tour that is universally optimal whenever the input is a tree metric. A (randomized) O(logn)-approximation algorithm for the a priori TSP follows as a corollary.     

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.     

On estimating the distribution of optimal traveling salesman tour lengths using heuristics

The traveling salesman problem is an important combinatorial optimization problem due to its significance in academic research and its real world applications. The problem has been extensively studied and much is known about its polyhedral structure and algorithms for exact and heuristic solutions. While most work is concentrated on solving the deterministic version of the problem, there also has been some research on the stochastic TSP. Research on the stochastic TSP has concentrated on asymptotic properties and estimation of the TSP-constant. Not much is, however, known about the probability distribution of the optimal tour length. In this paper, we present some empirical results based on Monte Carlo simulations for the symmetric Euclidean and Rectilinear TSPs. We derive regression equations for predicting the first four moments of the distribution of estimated TSP tour lengths using heuristics. We then show that a Beta distribution gives excellent fits for small to moderate sized TSP problems. We derive regression equations for predicting the parameters of the Beta distribution. Finally we predict the TSP constant using two alternative approaches.     

On inverse traveling salesman problems

The inverse traveling salesman problem belongs to the class of ??inverse combinatorial optimization?? problems. In an inverse combinatorial optimization problem, we are given a feasible solution for an instance of a particular combinatorial optimization problem, and the task is to adjust the instance parameters as little as possible so that the given solution becomes optimal in the new instance. In this paper, we consider a variant of the inverse traveling salesman problem, denoted by ITSP _W,A , by taking into account a set W of admissible weight systems and a specific algorithm. We are given an edge-weighted complete graph (an instance of TSP), a Hamiltonian tour (a feasible solution of TSP) and a specific algorithm solving TSP. Then, ITSP _W,A , is the problem to find a new weight system in W which minimizes the difference from the original weight system so that the given tour can be selected by the algorithm as a solution. We consider the cases ${W \in \{\mathbb{R}^{+m}, \{1, 2\}^m , \Delta\}}$ where ?? denotes the set of edge weight systems satisfying the triangular inequality and m is the number of edges. As for algorithms, we consider a local search algorithm 2-opt, a greedy algorithm closest neighbor and any optimal algorithm. We devise both complexity and approximation results. We also deal with the inverse traveling salesman problem on a line for which we modify the positions of vertices instead of edge weights. We handle the cases ${W \in \{\mathbb{R}^{+n}, \mathbb{N}^n\}}$ where n is the number of vertices.     

A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem

We present a variable neighborhood search approach for solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers such that each of the customers either supplies (pickup customers) or demands (delivery customers) a given amount of a single product, and by a vehicle, whose given capacity must not be exceeded, that starts at the depot and must visit each customer only once. The objective is to minimize the total length of the tour. Thus, the considered problem includes checking the existence of a feasible travelling salesman’s tour and designing the optimal travelling salesman’s tour, which are both NP-hard problems. We adapt a collection of neighborhood structures, k-opt, double-bridge and insertion operators mainly used for solving the classical travelling salesman problem. A binary indexed tree data structure is used, which enables efficient feasibility checking and updating of solutions in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solutions of all benchmark instances from the literature (with 200 to 500 customers). We are also able to solve instances with up to 1000 customers.     

A random-key genetic algorithm for the generalized traveling salesman problem

The generalized traveling salesman problem is a variation of the well-known traveling salesman problem in which the set of nodes is divided into clusters; the objective is to find a minimum-cost tour passing through one node from each cluster. We present an effective heuristic for this problem. The method combines a genetic algorithm (GA) with a local tour improvement heuristic. Solutions are encoded using random keys, which circumvent the feasibility problems encountered when using traditional GA encodings. On a set of 41 standard test problems with symmetric distances and up to 442 nodes, the heuristic found solutions that were optimal in most cases and were within 1% of optimality in all but the largest problems, with computation times generally within 10 seconds. The heuristic is competitive with other heuristics published to date in both solution quality and computation time.     

A general variable neighborhood search variants for the travelling salesman problem with draft limits

In this paper, we present two general variable neighborhood search (GVNS) based variants for solving the traveling salesman problem with draft limits (TSPDL), a recent extension of the traveling salesman problem. TSPDL arises in the context of maritime transportation. It consists of finding optimal Hamiltonian tour for a given ship which has to visit and deliver products to a set of ports while respecting the draft limit constraints. The proposed methods combine ideas in sequential variable neighborhood descent within GVNS. They are tested on a set of benchmarks from the literature as well as on a new one generated by us. Computational experiments show remarkable efficiency and effectiveness of our new approach. Moreover, new set of benchmarks instances is generated.     

The time dependent traveling salesman problem: polyhedra and algorithm

The time dependent traveling salesman problem (TDTSP) is a generalization of the classical traveling salesman problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. In this work, we study the polytope associated to the TDTSP formulation by Picard and Queyranne, which can be viewed as an extended formulation of the TSP. We determine the dimension of the TDTSP polytope and identify several families of facet-defining cuts. We obtain good computational results with a branch-cut-and-price algorithm using the new cuts, solving almost all instances from the TSPLIB with up to 107 vertices.     

An improved assignment lower bound for the euclidean traveling salesman problem

A simple transformation of the distance matrix for the Euclidean traveling salesman problem is presented that produces a tighter lower bound on the length of the optimal tour than has previously been attainable using the assignment relaxation. The improved lower bound is obtained by exploiting geometric properties of the problem to produce fewer and larger subtours on the first solution of the assignment problem. This research should improve the performance of assignment based exact procedures and may lead to improved heuristics for the traveling salesman problem.     

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.     

On no-wait and no-idle flow shops with makespan criterion

The paper deals with the NP-hard problems of minimizing the makespan in m-machine no-wait and no-idle permutation flow shops. We identify networks whose longest path lengths represent the makespans. These networks reveal the duality between the two problems, and show graphical explanations of the fact that under no-wait and no-idle conditions the makespan can be a decreasing function of some job processing times. Moreover, they also lead to a natural reduction of the no-wait flow shop problem to the traveling salesman problem, some lower bounds on the shortest makespan, and new efficiently solvable special cases.     

Traveling salesman games

In this paper we discuss the problem of how to divide the total cost of a round trip along several institutes among the institutes visited. We introduce two types of cooperative games—fixed-route traveling salesman games and traveling salesman games—as a tool to attack this problem. Under very mild conditions we prove that fixed-route traveling salesman games have non-empty cores if the fixed route is a solution of the classical traveling salesman problem. Core elements provide us with fair cost allocations. A traveling salesman game may have an empty core, even if the cost matrix satisfies the triangle inequality. In this paper we introduce a class of matrices defining TS-games with non-empty cores.     

New TSP Construction Heuristics and Their Relationships to the 2-Opt

Correction heuristics for the traveling salesman problem (TSP), with the 2-Opt applied as a postprocess, are studied with respect to their tour lengths and computation times. This study analyzes the 2-Opt dependency, which indicates how the performance of the 2-Opt depends on the initial tours built by the construction heuristics. In accordance with the analysis, we devise a new construction heuristic, the recursive-selection with long-edge preference (RSL) method, which runs faster than the multiple-fragment method and produces a comparable tour when they are combined with the 2-Opt.     

Notes on the single route lateral transhipment problem

Previous research has analyzed deterministic and stochastic models of lateral transhipments between different retailers in a supply chain. In these models the analysis assumes given fixed transhipment costs and determines under which situations (magnitudes of excess supply and demand at various retailers) the transhipment is profitable. However, in reality, these depend on aspects like the distance between retailers or the transportation mode chosen. In many situations, combining the transhipments may save transportation costs. For instance, one or more vehicle routes may be used to redistribute the inventory of the potential pickup and delivery stations. This can be done in any sequence as long as the vehicle capacity is not violated and there is enough load on the vehicle to satisfy demand. The corresponding problem is an extension of the one-commodity pickup and delivery traveling salesman and the pickup and delivery vehicle routing problem. When ignoring the routing aspect and assuming given fixed costs, transhipment is only profitable if the quantities are higher than a certain threshold. In contrast to that, the selection of visited retailers is dependent on the transportation costs of the tour and therefore the selected retailers are interrelated. Hence the problem also has aspects of a (team) orienteering problem. The main contribution is the discussion of the tour planning aspects for lateral transhipments which may be valuable for in-house planning but also for price negotiations with external contractors. A mixed integer linear program for the single route and single commodity version is presented and an improved LNS framework to heuristically solve the problem is introduced. Furthermore, the effect of very small load capacity on the structure of optimal solutions is discussed.     

On Gilmore-Gomory's open question for the bottleneck TSP

Consider the traveling salesman problem where the distance between two cities A and B is an integrable function of the y-coordinate of A and the x-coordinate of B. This problem finds important applications in operations management and combinatorial optimization. Gilmore and Gomory (Oper. Res. 12 (1964) 655) gave a polynomial time algorithm for this problem. In the bottleneck variant of this problem (BP), we seek a tour that minimizes the maximum distance between any two consecutive cities. For BP, Gilmore and Gomory state that they “do not yet know how to solve the problem for general integrable functions”. We show that BP is strongly NP-complete. Also, we use this reduction to provide a method for proving NP-completeness of other combinatorial problems.