Implementation of the Iterative Three-Component Heuristic for the Team Orienteering Problem With Time Windows

The purpose of this thesis is to replicate the Iterative Three-Component Heuristic posed by Hu and Lim [13]. This heuristic is applied to the Team Orienteering Problem with Time Windows in which the aim is to maximize the total profit collected by servicing a set of customers with a limited number of vehicles. The first two components in the heuristic are local search and simulated annealing. They explore neighbourhood solutions and discover new sets of routes. The last component recombines the routes that have been found and tries to find the best solution, namely the one yielding the highest profit. Our computation results show that the computation time is significantly larger than the computation time given in [13]. Moreover, we obtained different and often worse results than reported in [13]. One reason for our replication performing worse is the decrease of the maximum number of iterations (140 instead of 3000) in order to keep the computation time to a limit. We did find new best solutions for c108 (1140) and rc102 (909) for m = 4 vehicles. We extended the original heuristic to include multi-threading which performed 1.6 times faster than the original heuristic. Furthermore, we investigated increased route pool sizes, which lead to better results at the cost of only a small increase in the computation time.