A hybrid adaptive large neighborhood search heuristic for the team orienteering problem

摘要

The Team Orienteering Problem (TOP) is a well-known NP-Hard vehicle routing problem in which one maximizes the collected profits for visiting some nodes. In this paper, we propose a Hybrid Adaptive Large Neighborhood Search (HALNS) to solve this problem. Our algorithm combines the exploration power of ALNS with local search procedures and an optimization stage using a Set Packing Problem to further improve the solutions. Extensive computational experiments demonstrate the high performance of our HALNS outperforming all the competing algorithms in the literature on a large set of benchmark instances in terms of solution quality and/or computational time. Our HALNS identifies all the 387 Best Known Solutions (BKS) from the literature on a first dataset including small-scale benchmark instances and all the 333 BKS for large-scale benchmark instances within very short computational times. Moreover, we improve one large-scale instance solution. (C) 2020 Elsevier Ltd. All rights reserved.