Invited Review
The orienteering problem: A survey

https://doi.org/10.1016/j.ejor.2010.03.045Get rights and content

Abstract

During the last decade, a number of challenging applications in logistics, tourism and other fields were modelled as orienteering problems (OP). In the orienteering problem, a set of vertices is given, each with a score. The goal is to determine a path, limited in length, that visits some vertices and maximises the sum of the collected scores. In this paper, the literature about the orienteering problem and its applications is reviewed. The OP is formally described and many relevant variants are presented. All published exact solution approaches and (meta) heuristics are discussed and compared. Interesting open research questions concerning the OP conclude this paper.

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.Maxp=1Pi=2N-1Siyip,p=1Pj=2Nx1jp=p=1Pi=1N-1xiNp=P,i=1N-1xikp=j=2Nxkjp=ykp;k=2,,N-1;p=1,,P,sip+tij-sjpM(1-xijp);i,j=1,,N;p=1,,P,p=1

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)

  • C. Keller

    Algorithms to solve the orienteering problem: A comparison

    European Journal of Operational Research

    (1989)
  • G. Laporte et al.

    The selective travelling salesman problem

    Discrete Applied Mathematics

    (1990)
  • A. Leifer et al.

    Strong linear programming relaxations for the orienteering problem

    European Journal of Operational Research

    (1994)
  • R. Ramesh et al.

    An efficient four-phase heuristic for the generalized orienteering problem

    Computers and Operations Research

    (1991)
  • G. Righini et al.

    Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming

    Computers & Operations Research

    (2009)
  • H. Tang et al.

    A tabu search heuristic for the team orienteering problem

    Computer and Operations Research

    (2005)
  • F. Tricoire et al.

    Heuristics for the multi-period orienteering problem with multiple time windows

    Computers and Operations Research

    (2010)
  • P. Vansteenwegen et al.

    A guided local search metaheuristic for the team orienteering problem

    European Journal of Operational Research

    (2009)
  • P. Vansteenwegen et al.

    Iterated local search for the team orienteering problem with time windows

    Computers and Operations Research

    (2009)
  • C. Archetti et al.

    The capacitated team orienteering and profitable tour problems

    Journal of the Operational Research Society

    (2009)
  • Archetti, C., Feillet, D., Hertz, A., Speranza, M. in press. The undirected capacitated arc routing problem with...
  • C. Archetti et al.

    Metaheuristics for the team orienteering problem

    Journal of Heuristics

    (2007)
  • Arkin, E., Mitchell, J., Narasimhan, G. 1998. Resource-constrained geometric network optimisation. In: Proc. 14th ACM...
  • S. Boussier et al.

    An exact algorithm for the team orienteering problem

    4OR

    (2007)
  • Chao, I. 1993. Algorithms and solutions to multi-level vehicle routing problems. Ph.D. Dissertation, Applied...
  • J.-F. Cordeau et al.

    A tabu search heuristic for periodic and multi-depot vehicle routing problems

    Networks

    (1997)
  • D. Feillet et al.

    Travelling salesman problems with profits

    Transportation Science

    (2005)
  • D. Feillet et al.

    The profitable arc tour problem: Solution with a branch-and-price algorithm

    Transportation Science

    (2005)
  • M. Fischetti et al.

    Solving the orienteering problem through branch-and-cut

    INFORMS Journal on Computing

    (1998)
  • Gendreau, M., Laporte, G., Semet, F. 1995. A branch-and-cut algorithm for the undirected selective travelling salesman...
  • M. Gendreau et al.

    A branch-and-cut algorithm for the undirected selective travelling salesman problem

    Networks

    (1998)
  • B. Golden et al.

    The orienteering problem

    Naval Research Logistics

    (1987)
  • Cited by (811)

    View all citing articles on Scopus
    View full text