Back

G-87-15

The Selective Travelling Salesman Problem

and

BibTeX reference

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

This cahier was revised in June 1989

Research Axis

Research application