Orienteering Problem: A survey of recent variants, solution approaches and applications

•This work extends earlier surveys related to the OP and its variants.•A chronological summary of recent works related to the classical OP is presented.•A comprehensive survey of new variants of the Orienteering Problem is presented.•A number of recent applications and practical extensions of the OP is summarized.•Benchmark instances and directions of future research are summarized.

The Orienteering Problem (OP) has received a lot of attention in the past few decades. The OP is a routing problem in which the goal is to determine a subset of nodes to visit, and in which order, so that the total collected score is maximized and a given time budget is not exceeded. A number of typical variants has been studied, such as the Team OP, the (Team) OP with Time Windows and the Time Dependent OP. Recently, a number of new variants of the OP was introduced, such as the Stochastic OP, the Generalized OP, the Arc OP, the Multi-agent OP, the Clustered OP and others. This paper focuses on a comprehensive and thorough survey of recent variants of the OP, including the proposed solution approaches. Moreover, the OP has been used as a model in many different practical applications. The most recent applications of the OP, such as the Tourist Trip Design Problem and the mobile-crowdsourcing problem are discussed. Finally, we also present some promising topics for future research.