Title: Iterated local search for the team orienteering problem with time windows
Authors: Vansteenwegen, Pieter ×
Souffriau, Wouter
Vanden Berghe, Greet
Van Oudheusden, Dirk #
Issue Date: 24-Mar-2009
Series Title: Computers & operations research vol:36 issue:12 pages:3281-3290
Abstract: A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a Team Orienteering Problem with Time Windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximise the sum of the collected scores, by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.
ISSN: 0305-0548
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Centre for Industrial Management / Traffic & Infrastructure
Informatics Section
Computer Science Technology TC, Technology Campuses Ghent and Aalst
Technologiecluster Computerwetenschappen
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science