Groupe d’études et de recherche en analyse des décisions

G-87-15

The Selective Travelling Salesman Problem

et

Given a weighted graph with profits associated with the vertices, the selective travelling salesman problem (or orienteering problem) consists of selecting a simple circuit of maximal total profit, whose length does not exceed a prespecified bound. This paper provides integer linear programming formulations for the problem. Upper and lower bounds are then derived and embedded in exact enumerative algorithms. Computational results are reported.

, 20 pages

Ce cahier a été révisé en juin 1989