2011 | P. Vansteenwegen, W. Souffriau, D. Van Oudheusden
The orienteering problem (OP) is a combinatorial optimization problem where the goal is to find a path that maximizes the total score collected from a set of vertices, subject to a time constraint. The OP is a combination of the Knapsack Problem (KP) and the Travelling Salesperson Problem (TSP). It has applications in logistics, tourism, and other fields. The paper reviews the literature on the OP, its variants, and solution approaches. It discusses the OP, the team orienteering problem (TOP), the orienteering problem with time windows (OPTW), and the team orienteering problem with time windows (TOPTW). The paper also presents benchmark instances and solution approaches for these problems. The OP is NP-hard, and exact algorithms are time-consuming, so heuristics are often used. The paper highlights open research questions and discusses various solution strategies, including exact algorithms, heuristics, and metaheuristics. The paper concludes with a summary of the key findings and future research directions.The orienteering problem (OP) is a combinatorial optimization problem where the goal is to find a path that maximizes the total score collected from a set of vertices, subject to a time constraint. The OP is a combination of the Knapsack Problem (KP) and the Travelling Salesperson Problem (TSP). It has applications in logistics, tourism, and other fields. The paper reviews the literature on the OP, its variants, and solution approaches. It discusses the OP, the team orienteering problem (TOP), the orienteering problem with time windows (OPTW), and the team orienteering problem with time windows (TOPTW). The paper also presents benchmark instances and solution approaches for these problems. The OP is NP-hard, and exact algorithms are time-consuming, so heuristics are often used. The paper highlights open research questions and discusses various solution strategies, including exact algorithms, heuristics, and metaheuristics. The paper concludes with a summary of the key findings and future research directions.