G-87-15
The Selective Travelling Salesman Problem
Gilbert Laporte et Silvano Martello
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.
Paru en mai 1987 , 20 pages
Ce cahier a été révisé en juin 1989