Title: The Multiconstraint Team Orienteering Problem with Multiple Time Windows
Authors: Souffriau, Wouter
Vansteenwegen, Pieter ×
Vanden Berghe, Greet
Van Oudheusden, Dirk #
Issue Date: Feb-2013
Publisher: INFORMS
Series Title: Transportation Science vol:47 issue:1 pages:53-63
Abstract: This paper introduces the multiconstraint team orienteering problem with multiple time windows (MC-TOPMTW). 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.
ISSN: 0041-1655
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:
File Description Status SizeFormat
trsc0377 paper version.pdfmain article - paper version Published 175KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


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

© Web of science