UMR CNRS 7253

Outils du site


fr:recherche:toptw

The Team Orienteering Problem with Time Windows - TOPTW

Description

The Team Orienteering Problem with Time Windows (TOPTW) is a natural extension of the Team Orienteering Problem motivated by different practical situations. In the TOPTW, each customer must be visited within a predefined time interval, specified by an earliest and a latest time, into which the service must start. We assume that the time windows are hard constraints. This means that early arrivals to a location are permitted, but the agent must wait for it to be ``open'' before the service can start. Late arrivals, however, are not allowed. Similar to the TOP, the aim of the TOPTW is to design a set of itineraries to visit a set of locations in order to maximize the total collected profit.

Our contribution

We presented an effective neighborhood search for the TOPTW based on (1) the alternation between two different search spaces, and (2) the use of a long term memory mechanism to keep high quality routes encountered in elite solutions. Our approach outperforms state-of-the-art algorithms in terms of overall solution quality and computational time. It finds the current best known solutions for 89% of the literature instances within reasonable runtimes, and was able to improve the best-known solutions for 57 benchmark instances.

Available downloads

  • instances.zip: contains the test instances from [2], [1], and [3]. These files were originally downloaded from here.
  • solutions.zip: contains the best solutions found by our algorithm on the test instances. The file format description is provided inside the .zip file.

People involed

References

[1] Montemanni, R., & Gambardella, L. M. (2009). Ant colony system for team orienteering problems with time windows. Foundations of Computing and Decision Sciences, 34(4), 287-306.
[2] Righini, G., & Salani, M. (2009). Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers & Operations Research, 36(4), 1191-1203.
[3] Vansteenwegen, P., Souffriau, W., Berghe, G. V., & Oudheusden, D. V. (2009). Iterated local search for the team orienteering problem with time windows. Computers & Operations Research, 36(12), 3281-3290.

Outils pour utilisateurs