An Adaptive Large Neighbourhood Search Algorithm for the Orienteering Problem

We propose a new heuristic algorithm for the well-known Orienteering Problem, which aims at maximising the prize collected at vertices of a graph, visiting them through a simple closed tour whose length (also known as travel time) is limited by an upper bound. The algorithm is based on the Adaptive Large Neighbourhood Search metaheuristic paradigm, and uses a clustering of the graph to operate on groups of nearby vertices. Extensive computational results show that the proposed algorithm is able to find very good solutions (it produced 27 new best known solutions on a set of benchmark instances) and that it fares favourably compared with other state-of-the-art heuristics when tested with both long and short computation time budgets.