Search

The probabilistic traveling salesman problem (PTSP) is defined on a graph G = (V, E), where V is the vertex set and E is the edge set. Each vertex vi has a probability pi of being present. With each edge (vi, vj) is associated a distance or cost cij. In a first stage, an a priori Hamiltonian tour on G is designed. The list of present vertices is then revealed. In a second stage, the a priori tour is followed by skipping the absent vertices. The PTSP consists of determining a first-stage solution that minimizes the expected cost of the second-stage tour. The problem is formulated as an integer linear stochastic program, and solved by means of a branch-and-cut approach which relaxes some of the constraints and uses lower bounding functionals on the objective function. Problems involving up to 50 vertices are solved to optimality.

This paper considers vehicle routing problems (VRPs) with stochastic service and travel times, in which vehicles incur a penalty proportional to the duration of their route in excess of a preset constant. Three mathematical programming models are presented: a chance constrained model, a three-index simple recourse model and a two-index recourse model. A general branch and cut algorithm for the three models is described. Computational results indicate that moderate size problems can be solved to optimality.

This paper describes a branch and bound algorithm for a general class of asymmetrical vehicle routeing problems. Vehicle routes start and end at a central depot. Visits are made to nodes grouped into clusters: every cluster must receive a minimum number of visits. But not all nodes must be visited: there are specified nodes and non-specified nodes. Vehicle routes are also constrained by capacity and distance restrictions. The problem is formulated as an integer linear program. It is then solved by a branch and bound algorithm which exploits the unimodular structure of the subproblems. Computational results are reported.

T = (V, E) is a tree with nonnegative weights associated with each of its vertices. A fleet of vehicles of capacity Q is located at the depot represented by vertex v1. The Capacitated Vehicle Routing Problem on Trees (TCVRP) consists of determining vehicle collection routes starting and ending at the depot such that: the weight associated with any given vertex is collected by exactly one vehicle; the sum of all weights collected by a vehicle does not exceed Q; a linear combination of the number of vehicles and of the total distance traveled by these vehicles is minimized. The TCVRP is shown to be NP-hard. This paper presents lower bounds for the TCVRP based on the solutions of associated bin packing problems. We develop a linear time heuristic (upper bound) procedure and present a bound on its worst case performance. These lower and upper bounds are then embedded in an enumerative algorithm. Numerical results follow.

This paper describes a family of stochastic location-routing problems which consist of simultaneously locating a depot among a set of potential sites, of determining the vehicle fleet size and of designing collection routes through a set of customers having random supplies. In a first stage, decisions regarding depot location, fleet size and planned routes have to be made without knowing the actual supplies, so that the total supply of a route may turn out to exceed the vehicle capacity (i.e. failures may occur). In such an event, a corrective recourse action is taken at a second stage: the vehicle returns to the depot and empties its load before resuming its journey. Such an action generates a penalty. In this paper, two variants are studies: (P1) minimize first stage costs so that the probability of route failure does not exceed a preset threshold; (P2) minimize first stage costs so that the expected penalty of any route does not exceed a fraction of its planned cost. The problems are modelled as integer linear programs and solved to optimality.

Mailbox collection is a complex and costly operation in most postal services. The authors recently undertook a study aimed at improving this operation at the Canada Post Corporation (CPC). This paper describes an improvement to the clustering and routing algorithm currently in use. Various traffic and union rules affecting mailbox collection in an urban context are first described and their effect on shortest distance computations is explained. This is followed by a description of the clustering and routing algorithm currently used at CPC. A model and a generalized travelling salesman algorithm that take the various rules into account are then presented. It is then shown how the CPC routes can sometimes be improved by using the proposed algorithm as a postoptimizer.

Hydraulic turbine runners are used in electricity generation. These consist of a cylinder around which are welded, at regular spacings, a number of blades whose weights differ slightly. It is desired to locate the blades around the cylinder in order to minimize the distance between the center of mass of the blades and the geometric center of the cylinder. The problem can be formulated as a quadratic assignment problem. It is solved by adapting an interchange algorithm devised by Or for the travelling salesman problem. Computational results are reported.

The aim of this article is to develop an exact algorithm for the asymmetrical capacitated vehicle routing problem, i. e., the multiple traveling salesman problem subject to capacity restrictions. The problem is solved by means of a branch and bound tree in which subproblems are modified assignment problems subject to some restrictions. Two branching rules and three partitioning rules are examined. Computational results for problems involving up to 260 nodes (cities) are reported.

On considere le plasma consistant a determiner le circuit ou cycle le plus court dans un graphe contenant n nœuds et de telle sorte que: 1) k nœuds (k≤n) soient visites chacun une et une seule fois; 2) chacun des n-k nœuds restants soit visite au plus une fois. On decrit un algorithme de «branch and bound» pour ce probleme et on presente des resultats numeriques pour des problemes asymetriques contenant jusqu'a 200 nœuds et des problemes symetriques contenant jusqu'a 80 nœuds