Advanced search
1 file | 179.63 KB

The multiconstraint team orienteering problem with multiple time windows

(2013) TRANSPORTATION SCIENCE. 47(1). p.53-63
Author
Organization
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.
Keywords
ITERATED LOCAL SEARCH, ALGORITHM, MAXIMUM COLLECTION PROBLEM, TRAVELING SALESMAN PROBLEM, HEURISTICS, orienteering problem, grasp, iterated local search, vehicle routing

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 179.63 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Souffriau, Wouter, Pieter Vansteenwegen, Greet Vanden Berghe, and Dirk Van Oudheusden. 2013. “The Multiconstraint Team Orienteering Problem with Multiple Time Windows.” Transportation Science 47 (1): 53–63.
APA
Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., & Van Oudheusden, D. (2013). The multiconstraint team orienteering problem with multiple time windows. TRANSPORTATION SCIENCE, 47(1), 53–63.
Vancouver
1.
Souffriau W, Vansteenwegen P, Vanden Berghe G, Van Oudheusden D. The multiconstraint team orienteering problem with multiple time windows. TRANSPORTATION SCIENCE. 2013;47(1):53–63.
MLA
Souffriau, Wouter, Pieter Vansteenwegen, Greet Vanden Berghe, et al. “The Multiconstraint Team Orienteering Problem with Multiple Time Windows.” TRANSPORTATION SCIENCE 47.1 (2013): 53–63. Print.
@article{1922875,
  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.},
  author       = {Souffriau, Wouter and Vansteenwegen, Pieter and Vanden Berghe, Greet and Van Oudheusden, Dirk},
  issn         = {0041-1655},
  journal      = {TRANSPORTATION SCIENCE},
  keyword      = {ITERATED LOCAL SEARCH,ALGORITHM,MAXIMUM COLLECTION PROBLEM,TRAVELING SALESMAN PROBLEM,HEURISTICS,orienteering problem,grasp,iterated local search,vehicle routing},
  language     = {eng},
  number       = {1},
  pages        = {53--63},
  title        = {The multiconstraint team orienteering problem with multiple time windows},
  url          = {http://dx.doi.org/10.1287/trsc.1110.0377},
  volume       = {47},
  year         = {2013},
}

Altmetric
View in Altmetric
Web of Science
Times cited: