The orienteering problem: A survey
European Journal of Operational ResearchPublished 6 April 2010Open access
Pieter Vansteenwegen, Wouter Souffriau, Dirk Van Oudheusden
Citations924
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The OP is formally described and many relevant variants are presented and all published exact solution approaches and (meta) heuristics are discussed and compared.
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.
Keywords
Engineering
Operations ResearchAlgorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
4,181 Citations1987Marius M. Solomon
This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints and finds that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.
Lectu re Notes in Economics and Mathematical Systems
2,409 Citations1975Martin J. Beckmann, H. P. Kunzi
The first in vitro biochemical characterization of 13 missense mutations involved in PGM1 deficiency shows compromised catalysis and differential effects on recombinant protein folding/stability are found, suggesting both protein misfolding and catalytic impairment may play a role in the disorder.
Journal of the ACMInteger Programming Formulation of Traveling Salesman Problems
1,994 Citations1960Casey Miller, A. W. Tucker +1 more
The present paper provides yet another example of the versatility of integer programming as a mathematical modeling device by representing a generalization of the well-known “Travelling Salesman Problem” in integer programming terms.
Bell System Technical JournalComputer Solutions of the Traveling Salesman Problem
1,960 Citations1965Shen Lin
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer and are based on a general heuristic approach believed to be of general applicability to various optimization problems.
NetworksA tabu search heuristic for periodic and multi-depot vehicle routing problems
828 Citations1997Jean-Fran�ois Cordeau, Michel Gendreau +1 more
Naval Research Logistics (NRL)The orienteering problem
762 Citations1987Bruce Golden, Larry Levy +1 more
Transportation ScienceTraveling Salesman Problems with Profits
617 Citations2005Dominique Feillet, Pierre Dejax +1 more
A classification of TSPs with profits is proposed, and the existing literature is surveyed, and different classes of applications, modeling approaches, and exact or heuristic solution techniques are identified and compared.
ASME Press eBooksIntelligent Engineering Systems through Artificial Neural Networks
611 Citations2009Artificial Neural Networks in Engineering Conference < 2009, Saint Louis, Mo.>, Dagli, Cihan H. +1 more
Journal of the Operational Research SocietyHeuristic Methods Applied to Orienteering
568 Citations1984T. Tsiligirides
A ‘good’, if not ‘optimal’ solution by means of an efficient and computationally feasible method is derived and discussed and this solution is obtained by the use of either of two algorithms based on approximate methods.
European Journal of Operational ResearchThe team orienteering problem
556 Citations1996I‐Ming Chao, Bruce Golden +1 more
A fast and effective heuristic is presented and tested on 353 problems ranging in size from 21 to 102 points and the computational results are presented in detail.
Limited discrepancy search
515 Citations1995William D. Harvey, Matthew L. Ginsberg
This paper develops a search procedure that is more likely to find a solution in any given time limit than existing methods such as chronological backtracking and iterative sampling and shows formally and experimentally that limited discrepancy search can be expected to outperform existing approaches.
Discrete Applied MathematicsThe selective travelling salesman problem
412 Citations1990Gilbert Laporte, Silvano Martello
European Journal of Operational ResearchAn exact -constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits
363 Citations2007Jean‐François Bérubé, Michel Gendreau +1 more
It is shown in this paper that the Pareto front of bi-objective problems can be efficiently generated with the [epsilon]-constraint method and heuristics based on information gathered from previous subproblems that significantly speed up the method are described.
Computers & Operations ResearchIterated local search for the team orienteering problem with time windows
342 Citations2009Pieter Vansteenwegen, Wouter Souffriau +2 more
A simple, fast and effective iterated local search meta-heuristic to solve the TOPTW and an insert step is combined with a shake step to escape from local optima, produces a heuristic that performs very well on a large and diverse set of instances.
European Journal of Operational ResearchA fast and effective heuristic for the orienteering problem
321 Citations1996I‐Ming Chao, Bruce Golden +1 more
A fast and extremely effective heuristic is presented and tested on 67 problems taken from the literature and 40 new test problems and the computational results are presented in detail.
INFORMS journal on computingSolving the Orienteering Problem through Branch-and-Cut
308 Citations1998Matteo Fischetti, Juan‐José Salazar‐González +1 more
A branch-and-cut algorithm for finding an optimal OP solution, based on several families of valid inequalities, is described and proved to be able to solve to optimality large-scale instances involving up to 500 nodes, within acceptable computing time.
Computers & Operations ResearchA TABU search heuristic for the team orienteering problem
268 Citations2003Hao Tang, Elise Miller-Hooks
Results from computational experiments show that the proposed tabu search heuristic consistently produces high-quality solutions and outperforms other published heuristics tbr the TOP.
NetworksNew dynamic programming algorithms for the resource constrained elementary shortest path problem
267 Citations2007Giovanni Righini, Matteo Salani
The resource constrained elementary shortest path problem (RCESPP) arises as a pricing subproblem in branch‐and‐price algorithms for vehicle‐routing problems with additional constraints and is addressed by addressing the optimization of the RCESPP and presenting and comparing three methods.
Journal of the Operational Research SocietyComputer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points
242 Citations1972Anthony Wren, A. C. HOLLIDAY
A new algorithm is presented that allows routes from several depots to be constructed simultaneously, subject to restrictions on numbers of vehicles at individual depots, and a flexible priority rule will select those to be served.
OR InsightThe Mobile Tourist Guide: An OR Opportunity
232 Citations2007Pieter Vansteenwegen, Dirk Van Oudheusden
The Tourist Trip Design Problem (TTDP) is defined as an extension of the Orienteering Problem (OP) and based on real-time and reliable data, the MTG, a handheld embedded device, can immediately suggest new integrated holiday plans.
Lecture notes in computer scienceHarmony Search for Generalized Orienteering Problem: Best Touring in China
226 Citations2005Zong Woo Geem, Chung‐Li Tseng +1 more
The HS was applied to a TSP-like NP-hard Generalized Orienteering Problem (GOP) which is to find the utmost route under the total distance limit while satisfying multiple goals and showed that the algorithm could find good solutions when compared to those of artificial neural network.
Computers & Operations ResearchA heuristic for the multiple tour maximum collection problem
223 Citations1994Steven E. Butt, Tom M. Cavalier
A heuristic for the multiple tour maximum collection problem is developed that has the ability to handle large problems in a very short amount of computation time and will always produce a feasible solution if one exists.
4ORAn exact algorithm for team orienteering problems
219 Citations2006Sylvain Boussier, Dominique Feillet +1 more
The solution method proposed here is based on a Branch & Price algorithm, and is the first exact method proposed for such problems, except for a preliminary work from Gueguen and a work from Butt and Ryan.
Applied Artificial IntelligenceA PERSONALIZED TOURIST TRIP DESIGN ALGORITHM FOR MOBILE TOURIST GUIDES
218 Citations2008Wouter Souffriau, Pieter Vansteenwegen +3 more
A combined artificial intelligence and metaheuristic approach to solve tourist trip design problems (TTDP) enables fast decision support for tourists on small footprint mobile devices and produces solutions of better quality.
European Journal of Operational ResearchA tabu search heuristic for the undirected selective travelling salesman problem
205 Citations1998Michel Gendreau, Gilbert Laporte +1 more
A tabu search (TS) heuristic for the undirected Selective Travelling Salesman Problem, which iteratively inserts clusters of vertices in the current tour or removes a chain of Vertices.
Computers & Operations ResearchHeuristics for the multi-period orienteering problem with multiple time windows
194 Citations2009Fabien Tricoire, Martin Romauch +2 more
This work presents the multi-period orienteering problem with multiple time windows (MuPOPTW), a new routing problem combining objective and constraints of the orienteering Problem (OP) and teamorienteering problem (TOP), constraints from standard vehicle routing problems, and original constraints from a real-world application.
European Journal of Operational ResearchA guided local search metaheuristic for the team orienteering problem
194 Citations2008Pieter Vansteenwegen, Wouter Souffriau +2 more
Guided local search (GLS) is used to improve two of the proposed heuristics of the literature and an extra heuristic is added to regularly diversify the search in order to explore more areas of the solution space.
Computers & Industrial EngineeringAnts can solve the team orienteering problem
181 Citations2007Liangjun Ke, Claudia Archetti +1 more
An ant colony optimization (ACO) approach is proposed for the team orienteering problem and four methods are proposed to construct candidate solutions in the framework of ACO, i.e., the sequential, deterministic-concurrent and random-constable and simultaneous methods.
NetworksA branch-and-cut algorithm for the undirected selective traveling salesman problem
162 Citations1998Michel Gendreau, Gilbert Laporte +1 more
Several classes of valid inequalities for the symmetric STSP are developed and used in a branch-and-cut algorithm that can solve instances involving up to 300 vertices.
Swarm IntelligenceMetaheuristics for the bi-objective orienteering problem
159 Citations2009Michael Schilde, Karl F. Doerner +2 more
Two heuristic solution techniques for the multi-objective orienteering problem are developed and applied using the Pareto ant colony optimization algorithm and the design of the variable neighborhood search method, hybridized with path relinking procedures.
Journal of the Operational Research SocietyThe capacitated team orienteering and profitable tour problems
155 Citations2008Claudia Archetti, Dominique Feillet +2 more
The computational results show that the heuristic procedures often find the optimal solution and in general cause very limited errors.
Computers & Operations ResearchDecremental state space relaxation strategies and initialization heuristics for solving the Orienteering Problem with Time Windows with dynamic programming
153 Citations2008Giovanni Righini, Matteo Salani
This work compares different strategies proposed in the literature to guide decremental state space relaxation and proposes a new heuristic technique to initialize the critical vertex set and provides experimental evidence of its effectiveness.
Journal of the Operational Research SocietyThe Orienteering Problem with Time Windows
147 Citations1992Marisa G. Kantor, Moshe B. Rosenwein
Computers & Operations ResearchAn optimal solution procedure for the multiple tour maximum collection problem using column generation
125 Citations1999Steven E. Butt, David M. Ryan
An optimal solution procedure is presented for the Multiple Tour Maximum Collection Problem based on a set-partitioning formulation and makes efficient use of both column generation and constraint branching.
Computers & Operations ResearchA Path Relinking approach for the Team Orienteering Problem
121 Citations2009Wouter Souffriau, Pieter Vansteenwegen +2 more
A Path Relinking metaheuristic approach for solving the Team Orienteering Problem (TOP), a particular routing problem in which a score is earned for visiting a location, which improves the best known results in five instances.
IIE TransactionsThe orienteering problem with stochastic profits
105 Citations2008Taylan İlhan, Seyed M. R. Iravani +1 more
The experimental results identify conditions under which the Orienteering Problem with Stochastic Profits results in significant improvements in reaching the target profit when compared with the solution from the deterministic variant of the problem.
INFORMS Journal on ComputingAn Optimal Algorithm for the Orienteering Tour Problem
99 Citations1992R. Ramesh, Yong-Seok Yoon +1 more
An optimal algorithm is developed to solve the orienteering problem, using Lagrangean relaxation within a branch-and-bound framework, and is solved by a degree-constrained spanning tree procedure.
Naval Research Logistics (NRL)A multifaceted heuristic for the orienteering problem
97 Citations1988Bruce Golden, Qiwen Wang +1 more
A significantly improved procedure for the orienteering problem is described and test, based on four concepts—center of gravity, randomness, subgravity, and learning, which results in more nearly optimal solutions than previous procedures.
Computers & Operations ResearchAn efficient four-phase heuristic for the generalized orienteering problem
97 Citations1991R. Ramesh, Kathleen M. Brown
This research considers general cost functions, develops an efficient four-phase heuristic to solve the problem, and concludes that the proposed algorithm is viable and efficient for solving practical problems with arbitrary cost functions.
Information Processing LettersApproximation algorithms for time-dependent orienteering
89 Citations2002Fedor V. Fomin, Andrzej Lingas
A (2 + ɛ)-approximation algorithm is provided for the time-dependent orienteering problem which runs in polynomial time if the ratio between the maximum and minimum traveling time between any two sites is constant.
Resource-constrained geometric network optimization
88 Citations1998Esther M. Arkin, Joseph S. B. Mitchell +1 more
This work resolves the well-publicized open problem on the approximabiity of the rooted “orienteering problem” for the case in which the sites are given as points in the plane and the network required is a cycle.
Annals of Operations ResearchUsing artificial neural networks to solve the orienteering problem
80 Citations1995Qiwen Wang, Xiaoyun Sun +2 more
A modified, continuous Hopfield neural network is applied to the traveling salesman problem to attack this NP-hard optimization problem and is shown to perform quite well.
Lecture notes in economics and mathematical systemsMetaheuristics for Tourist Trip Planning
80 Citations2009Pieter Vansteenwegen, Wouter Souffriau +2 more
An overview of metaheuristics used in tourism is presented and Skewed VNS is introduced to solve the team orienteering problem (TOP) and the results are almost of the same quality as the best known heuristics but the computational time is reduced significantly.
Journal of the Operations Research Society of JapanAN ALGORITHM FOR SINGLE CONSTRAINT MAXIMUM COLLECTION PROBLEM
77 Citations1988Seiji Kataoka, Susumu Morito
This paper considers the following problem: "Given items with known values located at nodes of network, one wants to collect items so that their total value is maximized, under the assumption that a tour starting from the "center" node and returning to the center node is completed within a predetermined time limit."
European Journal of Operational ResearchAlgorithms to solve the orienteering problem: A comparison
76 Citations1989Christina Keller
The multiobjective vending problem (MVP) (Keller, 1985) is a generalization of the traveling salesman problem (TSP) where it is not necessary to visit all nodes in the problem definition.
European Journal of Operational ResearchStrong linear programming relaxations for the orienteering problem
72 Citations1994Adrienne C. Leifer, Moshe B. Rosenwein
The quality of upper bound obtained is significantly enhanced over the bound obtained from solving the basic LP relaxation, and the procedure to obtain upper bounds by solving three successive linear programs is proposed.
Computers & Operations ResearchThe undirected capacitated arc routing problem with profits
66 Citations2009Claudia Archetti, Dominique Feillet +2 more
A branch-and-price algorithm and several heuristics are proposed that can solve exactly instances with up to 97 profitable edges and find the optimal solution on most of instances where it is available.
Operations research, computer science. Interface seriesUsing a Genetic Algorithm to Solve the Generalized Orienteering Problem
65 Citations2008Xia Wang, Bruce Golden +1 more
This chapter shows that a straightforward GA can yield comparable results in the generalized orienteering problem (GOP), which is more difficult than the OP, which is itself NP-hard.
Transportation ScienceThe Profitable Arc Tour Problem: Solution with a Branch-and-Price Algorithm
61 Citations2005Dominique Feillet, Pierre Dejax +1 more
This article introduces a new arc routing problem that is defined on a graph in which profits and travel costs are associated with the arcs, and proposes a branch-and-price algorithm for its solution.
Journal of AlgorithmsOn approximating a geometric prize-collecting traveling salesman problem with time windows
58 Citations2004Reuven Bar-Yehuda, Guy Even +1 more
A dynamic programming algorithm is presented that finds a tour that visits at least OPT/density locations during their time windows and can be extended to deal with non-unit job profits and processing times.
European Journal of Operational ResearchSolving the Prize-collecting Rural Postman Problem
57 Citations2008Julián Aráoz, Elena Fernández +1 more
This work proposes a solution algorithm where iteratively the authors solve relaxed models with a small number of inequalities, that provide upper bounds, and proposes exact separation procedures for generating violated cuts when possible and a simple heuristic to generate feasible solutions that provide lower bounds at each iteration.
Meta heuristics for the orienteering problem
45 Citations2003Yun-Chia Liang, Sadan Kulturel-Konak +1 more
Two meta-heuristic techniques, ant colony optimization and tabu search, are presented for the orienteering problem, a general version of the well-known traveling salesman problem with many relevant applications in industry.
Operations ResearchExploring Variants of 2-Opt and 3-Opt for the General Routing Problem
44 Citations2005Luc Muyldermans, Patrick Beullens +2 more
This paper describes how the well-known 2-opt and 3-opt local search procedures for node routing problems can be adapted to solve arc and general routing problems successfully.
4ORPlanning in tourism and public transportation
44 Citations2008Pieter Vansteenwegen
In this work different operations research techniques are applied to solve several scheduling problems in two different domains to deal with improved passenger service in railway systems and the automated selection of the most interesting tourist attractions by means of a hand-held personalised electronic tourist guide.
Lecture notes in economics and mathematical systemsMetaheuristics in the Service Industry
40 Citations2009Martin Josef Geiger
A Hybrid Algorithm for Vehicle Routing of Less-Than-Truckload Carriers and Metaheuristics for the Index Tracking Problem.
Algorithms and solutions to multi-level vehicle routing problems
35 Citations1993I‐Ming Chao, Bruce Golden
NetworksLocating a cycle in a transportation or a telecommunications network
33 Citations2007Gilbert Laporte, Inmaculada Rodríguez‐Martín
A classification of cycle location problems under two main headings is proposed, modeled within a unified framework and algorithmic strategies are provided, together with computational results.
Archivio Istituzionale della Ricerca (Universita Degli Studi Di Milano)Dynamic programming for the orienteering problem with time windows
29 Citations2006Giovanni Righini, Matteo Salani
This work compares different strategies proposed in the literature to guide decremental state space relaxation and proposes a new heuristic technique to initialize the critical vertex set and provides experimental evidence of its effectiveness.
Telecommunication SystemsEfficient heuristics for the design of ring networks
26 Citations1995Michel Gendreau, Martine Labbé +1 more
An integer programming formulation for the RDP is proposed, as well as several ring construction and post-optimization heuristics, which are tested and compared on a series of test problems.
An exact parallel algorithm for the resource constrained traveling salesman problem with application to scheduling with an aggregate deadline
20 Citations1990Joseph F. Pekny, Donald L. Miller
The RCTSP algorithm is used to optimally schedule a processing facility involving sequence dependent transition costs and an aggregate due date on all job completion times.
Lecture notes in computer scienceA Detailed Analysis of Two Metaheuristics for the Team Orienteering Problem
8 Citations2009Pieter Vansteenwegen, Wouter Souffriau +1 more
The presented techniques are applied to analyse the performance of two different metaheuristics for the team orienteering problem to improve the metaheuristic design and insight in the problem at hand.
Lirias (KU Leuven)Planning in Tourism and Public Transportation - Attraction Selection by Means of a Personalised Electronic Tourist Guide and Train Transfer Scheduling
2 Citations2008Vansteenwegen, Pieter