The Multiconstraint Team Orienteering Problem with Multiple Time Windows

Wouter Souffriau (), Pieter Vansteenwegen (), Greet Vanden Berghe () and Dirk Van Oudheusden ()
Additional contact information
Wouter Souffriau: CODes, Industrial Sciences, KaHo St.-Lieven, B-9000 Ghent, Belgium; and Centre for Industrial Management, Katholieke Universiteit Leuven, B-3000 Leuven, Belgium
Pieter Vansteenwegen: Department of Industrial Management, Ghent University, B-9052 Zwijnaarde, Belgium
Greet Vanden Berghe: CODes, Industrial Sciences, KaHo St.-Lieven, B-9000 Ghent, Belgium
Dirk Van Oudheusden: Centre for Industrial Management, Katholieke Universiteit Leuven, B-3000 Leuven, Belgium

Transportation Science, 2013, vol. 47, issue 1, 53-63

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: orienteering problem; grasp; iterated local search; vehicle routing (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (31)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1110.0377 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:47:y:2013:i:1:p:53-63

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().