An Optimal Algorithm for the Orienteering Tour Problem

Abstract

Orienteering is a sport in which a competitor selects a path from a start to a destination, visiting control points along the path. Each control point has an associated score, and the travel between control points involves a certain cost. The problem is to select a set of control points to visit, so that the total score is maximized subject to a budget constraint on total cost. Several versions of this problem exist. In the version considered in this research, the start and the destination are the same, and the problem is to construct a subtour of the set of control points. The orienteering problem is a variant of the traveling salesman problem, and arises in vehicle routing and production scheduling situations. This problem has been shown to be NP-hard in the literature. We develop an optimal algorithm to solve this problem, using Lagrangean relaxation within a branch-and-bound framework. The Lagrangean relaxation is solved by a degree-constrained spanning tree procedure. Characteristics of the Lagrangean relaxation are studied, and several implementation features to improve the performance of the algorithm are presented. Detailed computational results for problems having up to 150 control points are presented. The results show that the proposed approach is viable for solving problems of medium to large size. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.