An efficient four-phase heuristic for the generalized orienteering problem

Orienteering is a sport in which a competitor constructs a path from a start to a destination, visiting control points along the path. Each control point has a score (prize) associated with it, and there is a known amount of time (cost) for travel between control points. The problem is to select a path from the origin to the destination that maximizes the total prize such that the total cost of the path is less than a prescribed value. Applications of this problem are several, and arise in vehicle routing and production scheduling situations. This problem has been shown to be NP-hard, and several heuristics have been proposed in the literature. All these heuristics assume the cost function to be Euclidean, and exploit the underlying geometry. In this research, the authors consider general cost functions, and develop an efficient four-phase heuristic to solve the problem. The four phases are termed vertex insertion, cost improvement, vertex deletion and maximal insertions, respectively. The four phases are integrated within an algorithmic framework with five control parameters to guide the search process. The algorithm has been tested extensively, and has been evaluated against the heuristics from the literature for Euclidean cost functions and an exact procedure for general cost functions. The computational results show that the algorithm results in near-optimal solutions, and its computational requirements are minimal. The authors conclude from this research that the proposed algorithm is viable and efficient for solving practical problems with arbitrary cost functions.