A Boundary Method for Planar Travelling Salesman Problems

An efficient method is described for obtaining near-optimal solutions to planar travelling salesman problems. Firstly, the convex boundary of points is determined and this is subsequently deformed by an iterative process until all the points have been included in the tour. Results are good on some trial problems.     

The Solution of Travelling Salesman Problems Based on Industrial Data

This paper partially replicates a comparison of travelling salesman heuristics carried out by Golden et al. more than a decade ago. It differs in two important ways, however. (1) We consider two heuristics—k-OPT and the space filling curve technique—which were developed after the original comparison. These new techniques appear to add little to the quality of solutions to the test problems utilized here. (2) Instead of test problems using geographical data, ours are based on programs for parts produced by a numerically controlled machine. Because of the different characteristics of these test problems we reach somewhat different conclusions concerning the efficacy of the different procedures.     

Heuristic for the Asymmetric Travelling Salesman Problem

The paper describes a heuristic algorithm for the asymmetric travelling salesman problem. The procedure is a generalization of Webb's Simple Loss 1 Method and is of the sequential type, i.e. in each step one link of the tour is fixed. The method proved to produce "high quality" near optimal solutions in a computing time, which only grows proportional to n^1.82.     

Lineare Charakterisierungen von Travelling Salesman Problemen

Zusammenfassung Wir betrachten die Formulierung des asymmetrischen Travelling Salesman Problems als lineares Programm und leiten mehrere Klassen neuer Ungleichungen ab, die eineschärfere Charakterisierung des Travelling Salesman Polytopen (konvexe Hülle der Touren) in Form von Ungleichungen ergeben.Es zeigt sich, daß einige der neuen Ungleichungen und auch einige der bekannten Kurzzyklus-Bedingungen tatsächlich Facetten des Travelling Salesman Polytopen sind, d.h. daß sie zu der Klasse von Ungleichungen gehören, die die konvexe Hülle aller Touren einesn-Städte Problems in eindeutiger Weise charakterisiert.

---

Summary We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield asharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e. the convex hull of tours.In fact some of the new inequalities as well as some of the well-known subtour elimination constraints are indeedfacets of the travelling salesman polytope, i.e. belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.

     

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.     

旅行推销员问题的算法综述

本文综述了旅行推销员问题 (TSP)近几十年来的算法研究进展 ,给出了一些主要算法的求解思想及其时间复杂度     

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.     

Some Simple Applications of the Travelling Salesman Problem

The travelling salesman problem arises in many different contexts. In this paper we report on typical applications in computer wiring, vehicle routing, clustering and job-shop scheduling. The formulation as a travelling salesman problem is essentially the simplest way to solve these problems. Most applications originated from real world problems and thus seem to be of particular interest. Illustrated examples are provided with each application.     

Visual Interactive (Computer) Solutions for the Travelling Salesman Problem

A visual interactive method of improving solutions for the travelling salesman problem is described. The travelling or multiple travelling salesman problem, when constraints are included, forms the core of the local delivery routing problem. The approach described in this note may be modified to give a visual interactive method of investigating practical physical distribution problem situations.     

Probability Modelling and Optimal Location of a Travelling Salesman

The ‘random part’ of an operations research model may be less satisfactory than the ‘deterministic part’, and it may thus be desirable to design algorithms that require few probability assumptions and make few calls to a suitable ‘probability oracle’. We consider here the problem of locating a service facility on a tree network so as to minimize the expected length of a travelling salesman tour through a random set of demand nodes.     

A Sequential Method for Discrete Optimization Problems and its Application to the Assignment, Travelling Salesman, and Three Machine Scheduling Problems

A discrete optimization problem is defined in which a numberof items are to be arranged in a sequence of positions in orderto obtain a minimum cost configuration. A simple sequentialmethod is proposed for the solution of this problem. The methodis composed of two stages. The first stage builds up an initialarrangement by introducing the items into the positions individually.The second stage adjusts these positions until no further improvementcan be made by a simple alteration of the arrangement. The aimof the method is to provide near optimum results with relativelylittle calculation. The scheme is shown to be successful ona number of well known problems in operations research.     

Some Methods of Producing Approximate Solutions to Travelling Salesman Problems with Hundreds or Thousands of Cities

Many large practical combinatorial problems await methods of solution, especially those involving the scheduling of hundreds or thousands of activities. The travelling salesman problem is archetypal and has attracted much attention, yet published rigorous methods can only be applied to problems encompassing tens of cities and approximate methods appear only to have been applied to problems of up to 105 cities. None of these methods offers scope for extension to much larger problems because of rapidly increasing computing requirements.Some approximate, sequential methods and the results of applying them to thirty problems of between 20 and 500 cities are described. In addition, the results of applying one method to ten 2500 city problems are reported; the solutions produced were, on average, 1·28 times the corresponding lower bound. It appears that satisfactory solutions to some large practical problems may be obtained by developing suitable sequential methods.     

Using cutting planes to solve the symmetric Travelling Salesman problem

Two algorithms using cutting planes are developed for solving the Travelling Salesman Problem. In both algorithms the problem is started with a subset of the set of constraints that define the problem (apart from integrality requirements).However, the two algorithms differ in the order in which the omitted constraints and the cutting planes that are required are generated.The computational experience obtained suggests that cutting planes can provide a competitive approach to other efficient methods of solving the problem.     

Heuristic algorithms for the 2-period balanced Travelling Salesman Problem in Euclidean graphs

In the 2-period Travelling Salesman Problem some nodes, called double nodes, are visited in both of two periods while the remaining ones, called single nodes, are visited in either one of the periods. In this paper we study the case in which a balance constraint is also introduced. We require that the difference between the number of visited nodes in the two periods must be below a fixed threshold. Moreover, we suppose that distances between nodes are Euclidean. The problem is NP-hard, and exact methods, now available, appear inadequate. Here, we propose three heuristics. Computational experiences and a comparison between the algorithms are also given.     

A Travelling Salesman Model for the Sequencing of Duties in Bus Crew Rotas

The paper addresses one aspect of the rostering problem posed to the public transport company operating in Porto, Portugal. The specific problem dealt with in this paper is that of sequencing the duties within each rota (rotating schedule) so as to minimize the variance of the rest periods between successive duties while satisfying constraints on their minimum value. This problem is formulated as a travelling salesman problem. Solutions derived from two heuristics are compared with the optimal ones.     

Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut

Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point of view. The real–world application we aim at is the control of a stacker crane in a warehouse.?We have implemented codes based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms the other two models we considered – at least for our special application – and that the heuristics provide acceptable solutions. Received: August 1999 / Accepted: September 2000?Published online April 12, 2001     

On the Significance of the Initial Solution in Travelling Salesman Heuristics

The quality requirements set by edge exchange heuristics on their initial solutions are evaluated in connection with the travelling salesman problem. The performance of the heuristics is measured using the expected value of the best solution achievable in a certain computing time. The computational results show that the use of initial solutions generated by applying a construction heuristic, instead of random initial solutions, typically improves the performance of edge exchange heuristics. The improvement, however, is dependent on the edge exchange heuristic to be used, the properties of the problem, and the computing time available.     

The Two-Period Travelling Salesman Problem Applied to Milk Collection in Ireland

We describe a new extension to the Symmetric Travelling Salesman Problem (STSP) in which some nodes are visited inboth of 2 periods and the remaining nodes are visited in either 1 ofthe periods. A number of possible Integer Programming Formulationsare given. Valid cutting plane inequalities are defined for thisproblem which result in an, otherwise prohibitively difficult, modelof 42 nodes becoming easily solvable by a combination of cuts andBranch-and-Bound. Some of the cuts are entered in a pool andonly used when it is automatically verified that they are violated.Other constraints which are generalisations of the subtour and combinequalities for the single period STSP, are identified manuallywhen needed. Full computational details of solution process aregiven.     

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.     

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.