Problem

The Orienteering Problem (OP) is a classical combinatorial optimization challenge focused on finding a path that visits a subset of locations to maximize collected rewards, subject to a limited resource budget such as time or distance. Unlike problems like the Traveling Salesman Problem that aim to visit all locations, the OP's selective nature makes it highly relevant for resource-constrained applications including urban logistics, tourism, and drone path planning. While earlier surveys covered the field up to 2017, significant advancements have occurred since then, introducing new structural variants like Set and Dubins OPs, incorporating uncertainty and multi-period decision-making, and leveraging learning-based methods. This review addresses the existing gap by providing a unified structural framework to connect these recent models and solution methodologies, clarifying how their underlying components impact computational properties and algorithm design.

Method

This systematic review analyzes OP research published between 2017 and 2025, adhering to PRISMA (Preferred Reporting Items for Systematic Reviews and Meta-Analyses) guidelines. The authors identified and scrutinized 112 peer-reviewed studies from the Web of Science Core Collection, focusing on those introducing new models, algorithms, or substantial methodological improvements. A novel component-based taxonomy was developed, categorizing OP variants into time-, path-, node-, structure-, and information-based extensions. Solution approaches were also classified, including exact algorithms, heuristics and metaheuristics, and emerging learning-based methods, with particular attention to matheuristics and advancements in artificial intelligence like reinforcement learning and neural networks.

Results

The survey's key contributions include a comprehensive component-based taxonomy that unifies diverse OP variants and an analysis of how each component influences computational complexity and polyhedral properties. It synthesizes recent advancements, highlighting a convergence between exact and heuristic methods, where matheuristics increasingly embed exact components, and exact algorithms incorporate heuristic-inspired strategies for scalability. Solution representations have evolved from direct edge selection to giant tours or clusters, enabling solvers to handle thousands of customers. For variants with high uncertainty (e.g., Stochastic and Time-Dependent OPs), there's a trend towards integrating simulation with optimization and the growing use of Machine Learning for real-time responsiveness. Conversely, for structurally complex variants (e.g., OPMV, CluOP), there's a resurgence of exact methods and advanced Branch-and-Cut-and-Price algorithms. Emerging models extend temporal dimensions to multi-period planning, introduce complex reward attributes, incorporate vehicle kinematics for UAVs and robots, modify combinatorial structures for group-level coverage (Set OP), and integrate advanced uncertainty management through probabilistic, dynamic, uncertain, and robust frameworks.

Implications

The review identifies four critical avenues for future research to address the escalating scale and complexity of the Orienteering Problem. Firstly, enhancing scalability and AI integration involves developing ML-aided exact methods, leveraging Generative AI and Large Language Models for heuristics, and utilizing Transformer-based architectures for multi-agent coordination, alongside Explainable AI. Secondly, improving robustness and uncertainty management calls for exploring Distributionally Robust Optimization, integrating Digital Twins with IoT data for dynamic re-routing, and developing multi-objective variants. Thirdly, promoting sustainability and green logistics requires focusing on the Green Orienteering Problem, including models for non-linear battery degradation and charging station planning for electric fleets. Finally, tailoring OP models to domain-specific applications, such as UAV kinematics, bioinformatics, and public health, will strengthen practical relevance. These interdisciplinary efforts are crucial for balancing computational costs with solution effectiveness to tackle complex real-world challenges.