Invited ReviewThe orienteering problem: A survey
Introduction
The name “Orienteering Problem” (OP) originates from the sport game of orienteering (Chao et al., 1996b). In this game, individual competitors start at a specified control point, try to visit as many checkpoints as possible and return to the control point within a given time frame. Each checkpoint has a certain score and the objective is to maximise the total collected score. The OP is a combination of vertex selection and determining the shortest Hamiltonian path between the selected vertices. As a consequence, the OP can be seen as a combination between the Knapsack Problem (KP) and the Travelling Salesperson Problem (TSP). The OP’s goal is to maximise the total score collected, while the TSP tries to minimise the travel time or distance. Furthermore, not all vertices have to be visited in the OP. Determining the shortest path between the selected vertices will be helpful to visit as many vertices as possible in the available time.
The OP is also known as the selective travelling salesperson problem (Laporte and Martello, 1990, Gendreau et al., 1998b, Thomadsen and Stidsen, 2003), the maximum collection problem (Kataoka and Morito, 1988, Butt and Cavalier, 1994) and the bank robber problem (Arkin et al., 1998). During the last decade, a number of challenging practical applications were modelled as orienteering problems and many exact and heuristic solution approaches were published.
The surveys about the TSP with profits (Feillet et al., 2005a) and the Hamiltonian and non-Hamiltonian problems (Laporte and Rodriguez Martin, 2007) clearly situate the OP between other routing problems (with and without profits) and indicate the differences. Both papers briefly discuss the OP, some solution strategies and a few extensions and variants.
Our paper focuses entirely on the OP itself, discussing the literature about its extensions and variants and many solution strategies and applications. The paper is organised as follows. Sections 2 Orienteering problem, 3 Team orienteering problem, 4 Orienteering problem with time windows, 5 Team orienteering problem with time windows define and discuss, respectively, the orienteering problem, the team orienteering problem, the orienteering problem with time windows and the team orienteering problem with time windows. Each of these sections presents a formal problem definition and a mathematical formulation, together with an overview of the applications, benchmark instances and solution approaches in the literature. Section 6 discusses several other variants of the OP. Section 7 concludes the paper and points out some interesting open research questions.
Section snippets
Problem definition and mathematical formulation
In the OP, a set of N vertices i is given, each with a score Si. The starting point (vertex 1) and the end point (vertex N) are fixed. The time tij needed to travel from vertex i to j is known for all vertices. Not all vertices can be visited since the available time is limited to a given time budget Tmax. The goal of the OP is to determine a path, limited by Tmax, that visits some of the vertices, in order to maximise the total collected score. The scores are assumed to be entirely additive
Problem definition and mathematical formulation
The Team Orienteering Problem (TOP) (Chao et al., 1996a, Tang and Miller-Hooks, 2005) or multiple tour maximum collection problem (MTMCP) (Butt and Cavalier, 1994) is an OP where the goal is to determine P paths, each limited by Tmax, that maximises the total collected score. The TOP corresponds to playing the game of orienteering by teams of several persons, each collecting scores during the same time span.
The TOP can be formulated as an integer problem with these decision variables: xijp = 1
Problem definition and mathematical formulation
Recently, the Orienteering Problem with Time Windows (OPTW) and the Team Orienteering Problem with Time Windows (TOPTW), discussed in the next section, received a lot of attention (Boussier et al., 2007, Righini and Salani, 2009, Montemanni and Gambardella, 2009, Vansteenwegen et al., 2009d, Tricoire et al., 2010). The main reason is that instances with time windows should be solved in a very different way than instances without time windows. For instance, the well-known 2-Opt move is
Problem definition and mathematical formulation
Based on the notation introduced earlier, the TOPTW can be formulated as a mixed integer problem with the following decision variables: xijp = 1 if, in path p, a visit to vertex i is followed by a visit to vertex j – 0 otherwise; yip = 1 if vertex i is visited in path p – 0 otherwise; sip = the start of the service at vertex i in path p; M a large constant.
Variants of the orienteering problem
The OP can be formulated as a TSP With Profits (TSPWP) (Feillet et al., 2005a, Bérubé et al., 2009) or as a special case of the Resource Constrained TSP (RCTSP) (Pekny and Miller, 1990). A TSPWP can be seen as a bicriteria TSP with two opposite objectives: collecting profits by travelling around and minimising travel costs. When the travel cost objective is stated as a constraint, this problem corresponds to an OP. A TSPWP classification and an extensive literature survey about TSPWP
Conclusions and possible future research lines
A number of challenging practical applications can be modelled as an orienteering problem or a variant of the orienteering problem. The routing of technicians, athlete recruitment or military applications can benefit from (team) orienteering algorithms. Tourism applications, for instance, require very fast and effective solution approaches. It can be expected that the orienteering problem will play a prominent role in future developments in tourist planning problems.
The performance of many
Acknowledgement
Dr. P. Vansteenwegen is a post-doctoral research fellow of the “Fonds Wetenschappelijk Onderzoek – Vlaanderen (FWO)”.
References (64)
- et al.
Solving the prize-collecting rural postman problem
European Journal of Operational Research
(2009) - et al.
On approximating a geometric prize-collecting travelling salesman problem with time windows
Journal of Algorithms
(2005) - et al.
An exact ε-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits
European Journal of Operational Research
(2009) - et al.
A heuristic for the multiple tour maximum collection problem
Computers and Operations Research
(1994) - et al.
An optimal solution procedure for the multiple tour maximum collection problem using column generation
Computers and Operations Research
(1999) - et al.
Theory and methodology – the team orienteering problem
European Journal of Operational Research
(1996) - et al.
Theory and methodology – a fast and effective heuristic for the orienteering problem
European Journal of Operational Research
(1996) - et al.
Approximation algorithms for time-dependent orienteering
Information Processing Letters
(2002) - et al.
A tabu search heuristic for the undirected selective travelling salesman problem
European Journal of Operational Research
(1998) - et al.
Ants can solve the team orienteering problem
Computers and Industrial Engineering
(2008)
Algorithms to solve the orienteering problem: A comparison
European Journal of Operational Research
The selective travelling salesman problem
Discrete Applied Mathematics
Strong linear programming relaxations for the orienteering problem
European Journal of Operational Research
An efficient four-phase heuristic for the generalized orienteering problem
Computers and Operations Research
Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming
Computers & Operations Research
A tabu search heuristic for the team orienteering problem
Computer and Operations Research
Heuristics for the multi-period orienteering problem with multiple time windows
Computers and Operations Research
A guided local search metaheuristic for the team orienteering problem
European Journal of Operational Research
Iterated local search for the team orienteering problem with time windows
Computers and Operations Research
The capacitated team orienteering and profitable tour problems
Journal of the Operational Research Society
Metaheuristics for the team orienteering problem
Journal of Heuristics
An exact algorithm for the team orienteering problem
4OR
A tabu search heuristic for periodic and multi-depot vehicle routing problems
Networks
Travelling salesman problems with profits
Transportation Science
The profitable arc tour problem: Solution with a branch-and-price algorithm
Transportation Science
Solving the orienteering problem through branch-and-cut
INFORMS Journal on Computing
A branch-and-cut algorithm for the undirected selective travelling salesman problem
Networks
The orienteering problem
Naval Research Logistics
Cited by (811)
An efficient hybrid adaptive large neighborhood search method for the capacitated team orienteering problem
2024, Expert Systems with ApplicationsDisinfection robots scheduling and routing problem for healthy buildings
2024, Journal of Building EngineeringEfficient post-earthquake reconnaissance planning using adaptive batch-mode active learning
2024, Advanced Engineering InformaticsSimulated annealing with reinforcement learning for the set team orienteering problem with time windows
2024, Expert Systems with ApplicationsThe priority-based traveling backpacker problem: Formulations and heuristics
2024, Expert Systems with Applications