Well-tuned algorithms for the Team Orienteering Problem with Time Windows

• Main Authors: GUNAWAN, Aldy, LAU, Hoong Chuin, VANSTEENWEGEN, Pieter, LU, Kun
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2017
• Subjects: Orienteering Problem; time windows; Iterated Local Search; Simulated Annealing; hybrid algorithm; Computer Sciences; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/3685; https://ink.library.smu.edu.sg/context/sis_research/article/4687/viewcontent/101057_2Fs41274_017_0244_1.pdf
• Institution: Singapore Management University

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.