A multifaceted heuristic for the orienteering problem

The orienteering problem involves the selection of a path between an origin and a destination which maximizes total score subject to a time restriction. In previous work the authors presented an effective heuristic for this NP-hard problem that outperformed other heuristics from the literature. In this article they describe and test a significantly improved procedure. The new procedure is based on four concepts-center of gravity, randomness, subgravity, and learning. These concepts combine to yield a procedure which is much faster and which results in more nearly optimal solutions than previous procedures.