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.

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.

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