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.

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.

• 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.

• Youcef Amarouche
• Rym Guibadj
• Aziz Moukrim

[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.