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.     

Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection

We introduce and study the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection (TSP-MTWHS), which generalises the well-known Travelling Salesman Problem with Time Windows and the recently introduced Travelling Salesman Problem with Hotel Selection. The TSP-MTWHS consists in determining a route for a salesman (eg, an employee of a services company) who visits various customers at different locations and different time windows. The salesman may require a several-day tour during which he may need to stay in hotels. The goal is to minimise the tour costs consisting of wage, hotel costs, travelling expenses and penalty fees for possibly omitted customers. We present a mixed integer linear programming (MILP) model for this practical problem and a heuristic combining cheapest insert, 2-OPT and randomised restarting. We show on random instances and on real world instances from industry that the MILP model can be solved to optimality in reasonable time with a standard MILP solver for several small instances. We also show that the heuristic gives the same solutions for most of the small instances, and is also fast, efficient and practical for large instances.     

Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation

Central European Journal of Operations Research - We define a geometric transformation of Euclidean Travelling Salesman Problem (TSP) tours that leads to a new formulation of the TSP. For every...     

A self-organising model for the travelling salesman problem

This work describes a new algorithm, based on a self-organising neural network approach, to solve the Travelling Salesman Problem (TSP). Firstly, various features of the available adaptive neural network algorithms for TSP are reviewed and a new algorithm is proposed. In order to investigate the performance of the algorithms, a comprehensive empirical study has been provided. The simulations, which are conducted on a series of standard data, evaluate the overall performance of this approach by comparing the results with the best known or the optimal solutions of the problems. The proposed algorithm shows significant advances in both the quality of the solution and computational effort for most of the experimental data. The deviation from the optimal solution of this algorithm was, in the worst case, around 2%. This fact indicates that the self-organising neural network may be regarded as a promising heuristic approach for optimisation problems.     

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 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.     

The travelling maintainer problem: integration of condition-based maintenance with the travelling salesman problem

The Travelling Salesman Problem (TSP) is one of the most studied problems in the literature due to its applicability to a large number of real cases. Most variants of the TSP consider total distance travelled. This paper presents a new generalised formulation of the TSP that aims to minimise the sum of functions of latencies to cities, rather than total distance travelled. Then, a new problem that uses a special function using the latency as input is presented, called the Travelling Maintainer Problem (TMP). The TMP integrates the output of prognostics in Condition-based Maintenance (CBM) with the TSP. CBM aims to minimise the failure and maintenance cost by identifying and predicting upcoming failures through the analysis of sensory information collected in real-time. Maintenance scheduling is performed using the predicted failure information obtained from the CBM. When the systems to be maintained are geographically distributed, maintenance scheduling requires integrated analysis of travel times and their effects on the failure progression in systems. This paper also presents Genetic Algorithm and Particle Swarm Optimisation-based solutions and their comparisons for the TMP on a case study.     

An iterated local search algorithm for the Travelling Salesman Problem with Pickups and Deliveries

The Travelling Salesman Problem with Pickups and Deliveries (TSPPD) consists in designing a minimum cost tour that starts at the depot, provides either a pickup or delivery service to each of the customers and returns to the depot, in such a way that the vehicle capacity is not exceeded in any part of the tour. In this paper, the TSPPD is solved by considering a metaheuris-tic algorithm based on Iterated Local Search with Variable Neighbourhood Descent and Random neighbourhood ordering. Our aim is to propose a fast, flexible and easy to code algorithm, also capable of producing high quality solutions. The results of our computational experience show that the algorithm finds or improves the best known results reported in the literature within reasonable computational time.     

Clustering of search trajectory and its application to parameter tuning

This paper is concerned with automated classification of Combinatorial Optimization Problem instances for instance-specific parameter tuning purpose. We propose the CluPaTra Framework, a generic approach to CLUster instances based on similar PAtterns according to search TRAjectories and apply it on parameter tuning. The key idea is to use the search trajectory as a generic feature for clustering problem instances. The advantage of using search trajectory is that it can be obtained from any local-search based algorithm with small additional computation time. We explore and compare two different search trajectory representations, two sequence alignment techniques (to calculate similarities) as well as two well-known clustering methods. We report experiment results on two classical problems: Travelling Salesman Problem and Quadratic Assignment Problem and industrial case study.     

Computing the variance of tour costs over the solution space of the TSP in polynomial time

We give an O(n ²) time algorithm to find the population variance of tour costs over the solution space of the n city symmetric Traveling Salesman Problem (TSP). The algorithm has application in both the stochastic case, where the problem is specified in terms of edge costs which are pairwise independently distributed random variables with known mean and variance, and the numeric edge cost case. We apply this result to provide empirical evidence that, in a range of real world problem sets, the optimal tour cost correlates with a simple function of the mean and variance of tour costs.     

Some Applications of the Generalized Travelling Salesman Problem

In the Generalized Travelling Salesman Problem (GTSP), the aim is to determine a least cost Hamiltonian circuit or cycle through several clusters of vertices. It is shown that a wide variety of combinatorial optimization problems can be modelled as GTSPs. These problems include location-routeing problems, material flow system design, post-box collection, stochastic vehicle routeing and arc routeing.     

A new ILP-based refinement heuristic for Vehicle Routing Problems

In this paper we address the Distance-Constrained Capacitated Vehicle Routing Problem (DCVRP), where k minimum-cost routes through a central depot have to be constructed so as to cover all customers while satisfying, for each route, both a capacity and a total-distance-travelled limit. Our starting point is the following refinement procedure proposed in 1981 by Sarvanov and Doroshko for the pure Travelling Salesman Problem (TSP): given a starting tour, (a) remove all the nodes in even position, thus leaving an equal number of ``empty holes' in the tour; (b) optimally re-assign the removed nodes to the empty holes through the efficient solution of a min-sum assignment (weighted bipartite matching) problem. We first extend the Sarvanov-Doroshko method to DCVRP, and then generalize it. Our generalization involves a procedure to generate a large number of new sequences through the extracted nodes, as well as a more sophisticated ILP model for the reallocation of some of these sequences. An important feature of our method is that it does not rely on any specialized ILP code, as any general-purpose ILP solver can be used to solve the reallocation model. We report computational results on a large set of capacitated VRP instances from the literature (with symmetric/asymmetric costs and with/without distance constraints), along with an analysis of the performance of the new method and of its features. Interestingly, in 13 cases the new method was able to improve the best-know solution available from the literature. Work supported by M.I.U.R. and by C.N.R., Italy.     

Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP

De Klerk et al., (2008) give a semidefinite programming constraint for the Traveling Salesman Problem (TSP) based on the matrix-tree theorem. This constraint says that the aggregate weight of all spanning trees in a solution to a TSP relaxation is at least that of a cycle graph. In this note, we show that the semidefinite constraint holds for any weighted 2-edge-connected graph and, in particular, is implied by the subtour elimination constraints.     

基于遗传算法的固定起讫点危险品配送路线优化

为科学选择危险品配送路线,保障运输安全,将传统TSP(Travelling SalesmanProblem)问题加以推广和延伸,建立以路段交通事故率、路侧人口密度、环境影响因子和路段运输费用为指标的固定起讫点危险品配送路线优化模型.以遗传算法基本框架为基础,引入新的遗传算子,构建了可用于实现模型的多目标遗传算法.实例仿真表明,所建模型和算法在求解固定起讫点危险品配送路线优化问题中有较好的实用性.     

Maximum travelling salesman problem

We present different types of techniques for designing algorithms with worst-case performances for the Maximum Travelling Salesman Problem. Supported by Byelarussian Fundamental Science Found and DAAD     

Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and set-up times using the Travelling Salesman Problem with time windows

In this paper we consider the Discrete Lotsizing and Scheduling Problem with sequence dependent set-up costs and set-up times (DLSPSD). DLSPSD contains elements from lotsizing and from job scheduling, and is known to be NP-Hard. An exact solution procedure for DLSPSD is developed, based on a transformation of DLSPSD into a Travelling Salesman Problem with Time Windows (TSPTW). TSPTW is solved by a novel dynamic programming approach due to Dumas et al. (1993). The results of a computational study show that the algorithm is the first one capable of solving DLSPSD problems of moderate size to optimality with a reasonable computational effort.     

Multi-depot Multiple TSP: a polyhedral study and computational results

We study the Multi-Depot Multiple Traveling Salesman Problem (MDMTSP), which is a variant of the very well-known Traveling Salesman Problem (TSP). In the MDMTSP an unlimited number of salesmen have to visit a set of customers using routes that can be based on a subset of available depots. The MDMTSP is an NP-hard problem because it includes the TSP as a particular case when the distances satisfy the triangular inequality. The problem has some real applications and is closely related to other important multi-depot routing problems, like the Multi-Depot Vehicle Routing Problem and the Location Routing Problem. We present an integer linear formulation for the MDMTSP and strengthen it with the introduction of several families of valid inequalities. Certain facet-inducing inequalities for the TSP polyhedron can be used to derive facet-inducing inequalities for the MDMTSP. Furthermore, several inequalities that are specific to the MDMTSP are also studied and proved to be facet-inducing. The partial knowledge of the polyhedron has been used to implement a Branch-and-Cut algorithm in which the new inequalities have been shown to be very effective. Computational results show that instances involving up to 255 customers and 25 possible depots can be solved optimally using the proposed methodology.     

An approximation algorithm for a symmetric Generalized Multiple Depot, Multiple Travelling Salesman Problem

In this paper, we present an algorithm with an approximation factor of 2 for a Generalized, Multiple Depot, Multiple Travelling Salesman Problem (GMTSP) when the costs are symmetric and satisfy the triangle inequality. The algorithm requires finding a degree constrained minimum spanning tree which we compute using a Lagrangian relaxation.     

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.     

New lower bounds for the Symmetric Travelling Salesman Problem

In this paper new lower bounds for the Symmetric Travelling Salesman Problem are proposed and combined in additive bounding procedures. Efficient implementations of the algorithms are given; in particular, fast procedures for computing the linear programming reduced costs of the Shortest Spanning Tree (SST) Problem and for finding all ther-SST of a given graph, are presented. Computational results on randomly generated test problems are reported.