The Multiconstraint Team Orienteering Problem with Multiple Time Windows
Transportation SciencePublished 6 October 2011
Wouter Souffriau, Pieter Vansteenwegen, Greet Vanden Berghe, Dirk Van Oudheusden
Citations150
SJR quartileQ1
SJR score2.32
SNIP2.03
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
This paper introduces the multiconstraint team orienteering problem with multiple time windows MC-TOP-MTW, and presents a fast and effective algorithm for tackling this problem, by hybridizing iterated local search with a greedy randomized adaptive search procedure.
Abstract
This paper introduces the multiconstraint team orienteering problem with multiple time windows (MC-TOP-MTW). In the MC-TOP-MTW, a set of vertices is given, each with a service time, one or more time windows, and a score. The goal is to maximize the sum of the collected scores, by a fixed number of tours. The tours are limited in length and restricted by the time windows and additional constraints. Next to a mathematical formulation of the MC-TOP-MTW, the main contribution of this paper is a fast and effective algorithm for tackling this problem, by hybridizing iterated local search with a greedy randomized adaptive search procedure. On a large test set, an average run has a score gap of only 5.19% with known high quality solutions, using 1.5 seconds of computational time. For 32% of the test instances, the known high quality solution was found or improved. This solution method also performs well on test instances of the TOPTW, the selective vehicle routing problem with time windows, and the MC-TOP-TW. A sensitivity analysis shows that the performance of the algorithm is insensitive to small changes in the parameter settings.
Keywords
Engineering
Tabu Search
5,702 Citations1997Fred Glover, Manuel Laguna
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.
Tabu Search
2,936 Citations1997Fred Glover, Manuel Laguna
This book explores the meta-heuristics approach called tabu search, which is dramatically changing the authors' ability to solve a host of problems that stretch over the realms of resource planning, telecommunications, VLSI design, financial analysis, scheduling, spaceplanning, energy distribution, molecular engineering, logistics, pattern classification, flexible manufacturing, waste management,mineral exploration, biomedical analysis, environmental conservation and scores of other problems.
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.
Operations Research LettersA probabilistic heuristic for a computationally difficult set covering problem
1,026 Citations1989Thomas A. Feo, Maurício G. C. Resende
An efficient probabilistic set covering heuristic is presented that provides the best known solutions to all other instances attempted to solve set covering problems that arise from Steiner triple systems.
European Journal of Operational ResearchThe orienteering problem: A survey
924 Citations2010Pieter Vansteenwegen, Wouter Souffriau +1 more
The OP is formally described and many relevant variants are presented and all published exact solution approaches and (meta) heuristics are discussed and compared.
NetworksA tabu search heuristic for periodic and multi-depot vehicle routing problems
828 Citations1997Jean-Fran�ois Cordeau, Michel Gendreau +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.
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.
Discrete Applied MathematicsThe selective travelling salesman problem
412 Citations1990Gilbert Laporte, Silvano Martello
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.
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.
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.
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.
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.
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.
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.
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.
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."
Méthodes de résolution exacte pour les problèmes de tournées de véhicules
28 Citations1999Cyrille Gueguen
Lirias (KU Leuven)Solving Multi Constrained Team Orienteering Problems to Generate Tourist Routes
14 Citations2009Ander García, Pieter Vansteenwegen +3 more
An iterated local search metaheuristic to solve the MCTOPTW, in order to generate personalized tourist routes in real-time, and extensive experimental results with new and existing benchmark instances prove the appropriateness of the algorithm.