Tabu Search for the Orienteering Problem with Hotel Selection

Two metaheuristic solution approaches for the Orienteering Problem with Hotel Selection (OPHS) are compared in this thesis. The goal of the OPHS is to select the best vertices and the right sequence of hotels, such that the total score of the vertices is maximal and the trips along the selected vertices satisfy the time restrictions. We implement the Skewed Variable Neighborhood Search (SVNS) algorithm of Divsalar et al. (2013) and show that it is outperformed by a Tabu Search (TS) algorithm. Both algorithms have the same construction method for the initial solution. We try to improve this solution with two shakes in the SVNS algorithm and apply these two shakes with an additional Cross-over shake in the TS algorithm. Local Search or TS with nine moves is performed after each shake. Next, the algorithms decide on the solution that is used in the following iteration, which can be a solution with a better or a worse score. Concluding, this TS algorithm produced near-optimal solutions with an average gap of 0.675%.