Bochar Laarabi and Bouchaib Radi, A Two-Phase Heuristic Method for Solving Team Orienteering Problem, Volume 2017, Number 6, Pages 10-19, 2017

Bochar Laarabi and Bouchaib Radi, A Two-Phase Heuristic Method for Solving Team Orienteering Problem, Volume 2017, Number 6, Pages 10-19, 2017

Abstract: The Team Orienteering Problem $(TOP)$ is an catchy variant of the Vehicle Routing Problem $(VRP)$. The aim at maximizing the total amount of profit collected by a fleet of vehicles while not exceeding a predefined travel cost limit on each vehicle. In this paper,we propose a two-phase heuristic method to find solutions for $TOP$. In phase 1,We determine the initial solution using the $k$-means clustering by not exceeding the constraints of the total cost. In phase 2, an improvement heuristic search for a better solution based on the initial solution in phase 1 is developed. The obtained results show the performance of the new proposed methodology. We evaluated our algorithm on the standard benchmark of $TOP$. The results show that the algorithm is competitive and is able to prove the optimality for the instances previously unsolved.

Key words: Team orienteering problem; algorithm $k$-means; heuristic.