The Team Orienteering Problem with Time Windows (TOPTW) is the extension of the Orienteering Problem (OP) where each node is limited by a predefined time window during which the service has to start. The objective of the TOPTW is to maximize the total collected score by visiting a set of nodes with a limited number of paths. We propose two algorithms, Iterated Local Search and a hybridization of Simulated Annealing and Iterated Local Search (SAILS), to solve the TOPTW. As indicated in multiple research works on algorithms for the OP and its variants, determining appropriate parameter values in a statistical way remains a challenge. We apply Design of Experiments, namely factorial experimental design, to screen and rank all the parameters thereby allowing us to focus on the parameter search space of the important parameters. The proposed algorithms are tested on benchmark TOPTW instances. We demonstrate that well-tuned ILS and SAILS lead to improvements in terms of the quality of the solutions. More precisely, we are able to improve 50 best known solution values on the available benchmark instances.
Orienteering Problem, time windows, Iterated Local Search, Simulated Annealing, hybrid algorithm
Databases and Information Systems | Data Storage Systems
Data Management and Analytics
Journal of the Operational Research Society
GUNAWAN, Aldy; LAU, Hoong Chuin; VANSTEENWEGEN, Pieter; and LU, Kun.
Well-tuned algorithms for the Team Orienteering Problem with Time Windows. (2017). Journal of the Operational Research Society. 68, (8), 861-876. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3685
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.