2011 | P. Vansteenwegen, W. Souffriau, D. Van Oudheusden
The paper provides a comprehensive survey of the orienteering problem (OP) and its variants, along with their applications and solution approaches. The OP, inspired by the sport of orienteering, involves selecting a subset of vertices to visit within a given time budget to maximize the total score collected. The problem is formally defined and various formulations are presented, including the team orienteering problem (TOP) and the orienteering problem with time windows (OPTW). The paper discusses the mathematical formulations, benchmark instances, and solution approaches for each variant, highlighting both exact algorithms and heuristics. It also reviews the literature on extensions and variants of the OP, such as the generalized orienteering problem (GOP), multi-objective OP, and OP with stochastic profits. The paper concludes by identifying open research questions and suggesting future directions for the field.The paper provides a comprehensive survey of the orienteering problem (OP) and its variants, along with their applications and solution approaches. The OP, inspired by the sport of orienteering, involves selecting a subset of vertices to visit within a given time budget to maximize the total score collected. The problem is formally defined and various formulations are presented, including the team orienteering problem (TOP) and the orienteering problem with time windows (OPTW). The paper discusses the mathematical formulations, benchmark instances, and solution approaches for each variant, highlighting both exact algorithms and heuristics. It also reviews the literature on extensions and variants of the OP, such as the generalized orienteering problem (GOP), multi-objective OP, and OP with stochastic profits. The paper concludes by identifying open research questions and suggesting future directions for the field.