A Population Based Approach for the Team Orienteering Problem
Résumé
The Team Orienteering Problem (TOP) belongs to the family of combinatorial optimization problems, which is also related to the well-known orienteering game. TOP can be viewed as a variant of the vehicle routing problem where its aim is to maximize the total gained profit from the visited customers. In such a problem, the number of vehicles is limited and each vehicle must satisfy the maximum travel time. Therefore, some customers will remain not visited. In this paper, a new strategy is considered in order to tackle the TOP, where efficient intensification (deep searching) and diversification strategies are combined. The proposed approach mimics the main steps of the genetic algorithm, where both destroying and rebuilding strategies are considered trying an enhancement of the method. Throughout a number of instances extracted from the literature, the proposed method is able to match all existing better bounds available in the literature. Then, for the first preliminary study using destroying and rebuilding strategies, encouraging results have been obtained and so, the soft/strong destroying and rebuilding routes with using a black-box solver, like Cplex solver, can be considered as the main future of the method for finding new bounds, especially for large-scale instances. \textcopyright 2019, Computers and Industrial Engineering. All rights reserved.