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 cutting plane procedure for the travelling salesman problem on road networks

A cutting plane algorithm for the exact solution of the symmetric travelling salesman problem (TSP) is proposed. The real tours on a usually incomplete road network, which are in general non-Hamiltonian, are characterized directly by an integer linear programming model. The algorithm generates special cutting planes for this model. Computational results for real road networks with up to 292 visiting places are reported, as well as for classical problems of the literature with up to 120 cities. Some of the latter problems have been solved for the first time with a pure cutting plane approach.     

A domination algorithm for {0,1}‐instances of the travelling salesman problem

We present an approximation algorithm for ‐instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, we give a polynomial‐time algorithm which has domination ratio . In other words, given a ‐edge‐weighting of the complete graph on vertices, our algorithm outputs a Hamilton cycle of with the following property: the proportion of Hamilton cycles of whose weight is smaller than that of is at most . Our analysis is based on a martingale approach. Previously, the best result in this direction was a polynomial‐time algorithm with domination ratio for arbitrary edge‐weights. We also prove a hardness result showing that, if the Exponential Time Hypothesis holds, there exists a constant such that cannot be replaced by in the result above. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 427–453, 2016     

The biobjective travelling purchaser problem

The purpose of this article is to present and solve the Biobjective Travelling Purchaser Problem, which consists in determining a route through a subset of markets in order to collect a set of products, minimizing the travel distance and the purchasing cost simultaneously. The most convenient purchase of the product in the visited markets is easily computed once the route has been determined. Therefore, this problem contains a finite set of solutions (one for each route) and the problem belongs to the field of the Biobjective Combinatorial Optimization. It is here formulated as a Biobjective Mixed Integer Linear Programming model with an exponential number of valid inequalities, and this model is used within a cutting plane algorithm to generate the set of all supported and non-supported efficient points in the objective space. A variant of the algorithm computes only supported efficient points. For each efficient point in the objective space exactly one Pareto optimal solution in the decision space is computed by solving a single-objective problem. Each of these single-objective problems, in turn, is solved by a specific branch-and-cut approach. A heuristic improvement based on saving previously generated cuts in a common cut-pool structure has also been developed with the aim of speeding up the algorithm performance. Results based on benchmark instances from literature show that the common cut-pool heuristic is very useful, and that the proposed algorithm manages to solve instances containing up to 100 markets and 200 different products. The general procedure can be extended to address other biobjective combinatorial optimization problems whenever a branch-and-cut algorithm is available to solve a single-objective linear combination of these criteria.     

Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times

This paper presents a variant of the asymmetric traveling salesman problem (ATSP) in which the traveling time between each pair of cities is represented by an interval of values (wherein the actual travel time is expected to lie) instead of a fixed (deterministic) value as in the classical ATSP. Here the ATSP (with interval objective) is formulated using the usual interval arithmetic. To solve the interval ATSP (I-ATSP), a genetic algorithm with interval valued fitness function is proposed. For this purpose, the existing revised definition of order relations between interval numbers for the case of pessimistic decision making is used. The proposed algorithm is based on a previously published work and includes some new features of the basic genetic operators. To analyze the performance and effectiveness of the proposed algorithm and different genetic operators, computational studies of the proposed algorithm on some randomly generated test problems are reported.     

On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem

The travelling salesman problem (TSP)   is one of the most prominent NP-hard combinatorial optimisation problems. After over fifty years of intense study, the TSP continues to be of broad theoretical and practical interest. Using a novel approach to empirical scaling analysis, which in principle is applicable to solvers for many other problems, we demonstrate that some of the most widely studied types of TSP instances tend to be much easier than expected from previous theoretical and empirical results. In particular, we show that the empirical median run-time required for finding optimal solutions to so-called random uniform Euclidean (RUE) instances – one of the most widely studied classes of TSP instances – scales substantially better than Θ(2ⁿ)$\Theta (2^n)$ with the number n of cities to be visited. The Concorde solver, for which we achieved this result, is the best-performing exact TSP solver we are aware of, and has been applied to a broad range of real-world problems. Furthermore, we show that even when applied to a broad range of instances from the prominent TSPLIB benchmark collection for the TSP, Concorde exhibits run-times that are surprisingly consistent with our empirical model of Concorde’s scaling behaviour on RUE instances. This result suggests that the behaviour observed for the simple random structure underlying RUE is very similar to that obtained on the structured instances arising in various applications.     

POPMUSIC for the travelling salesman problem

POPMUSIC— Partial OPtimization Metaheuristic Under Special Intensification Conditions — is a template for tackling large problem instances. This metaheuristic has been shown to be very efficient for various hard combinatorial problems such as p-median, sum of squares clustering, vehicle routing, map labelling and location routing. A key point for treating large Travelling Salesman Problem (TSP) instances is to consider only a subset of edges connecting the cities. The main goal of this article is to present how to build a list of good candidate edges with a complexity lower than quadratic in the context of TSP instances given by a general function. The candidate edges are found with a technique exploiting tour merging and the POPMUSIC metaheuristic. When these candidate edges are provided to a good local search engine, high quality solutions can be found quite efficiently. The method is tested on TSP instances of up to several million cities with different structures (Euclidean uniform, clustered, 2D to 5D, grids, toroidal distances). Numerical results show that solutions of excellent quality can be obtained with an empirical complexity lower than quadratic without exploiting the geometrical properties of the instances.     

Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.     

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.     

Approximate algorithms for the travelling purchaser problem

In this paper we study the generalized savings heuristics of Golden, Levy and Dahl and propose several new heuristic procedures for solving the travelling purchaser problem. A comparative study of the four heuristics considered is provided.     

Identification of non-optimal arcs for the travelling salesman problem

Conditions are presented for the identification of (directed) arcs for the traveling salesman problem, that can be eliminated with at least one optimal solution remaining. The conditions are not based on lower or upper bounds; the presence of an identified arc in a solution implies that the solution is not 3-optimal. An example illustrates how to use the conditions.     

The shortest multipaths problem in a capacitated dense channel

In this paper, we present a simple polynomial-time algorithm solving the shortest multipaths problem in particular grid graphs called dense channels. Our work extends the results of Formann et al. [M. Formann, D. Wagner, F. Wagner, Routing through a dense channel with minimum total wire length, Journal of Algorithms 15 (1993) 267–283], by considering arbitrary horizontal and vertical capacities.     

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.     

Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem

The probabilistic traveling salesman problem is a paradigmatic example of a stochastic combinatorial optimization problem. For this problem, recently an estimation-based local search algorithm using delta evaluation has been proposed. In this paper, we adopt two well-known variance reduction procedures in the estimation-based local search algorithm: the first is an adaptive sampling procedure that selects the appropriate size of the sample to be used in Monte Carlo evaluation; the second is a procedure that adopts importance sampling to reduce the variance involved in the cost estimation. We investigate several possible strategies for applying these procedures to the given problem and we identify the most effective one. Experimental results show that a particular heuristic customization of the two procedures increases significantly the effectiveness of the estimation-based local search.     

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.     

Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs

The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 1994] by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408-427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408-427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems.     

Facets and valid inequalities for the time-dependent travelling salesman problem

The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the traditional TSP where the travel cost between two cities depends on the moment of the day the arc is travelled. In this paper, we focus on the case where the travel time between two cities depends not only on the distance between them, but also on the position of the arc in the tour. We consider two formulations proposed in the literature, we analyze the relationship between them and derive several families of valid inequalities and facets. In addition to their theoretical properties, they prove to be very effective in the context of a Branch and Cut algorithm.     

Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem

The generalized traveling salesman problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once.