۱- Introduction

۲- Existing algorithms for the OP

۳- Clustering and the OP

۴- An ALNS-based heuristic for the OP

۵- Results

۶- Conclusions

References

Abstract

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.

Introduction

The Orienteering Problem (OP) was introduced by Golden et al. (1987) and combines the selection of a set of customers to visit with the determination of the shortest tour to visit them. Imagine a tour operator who has to design a walking tour of a city. He has a vast set of possible interest points and associates a score to each of them, based on their desirability. Because the tour time is limited, he has to operate a selection of points to visit and decide the visit order, with the objective of maximising the scores of the visited points. Besides applications in tourist trip design (Borràs et al., 2014; Souffriau et al., 2008; Vansteenwegen and Van Oudheusden, 2007; Wang et al., 2008), the OP has been considered as a generalisation of the classical Travelling Salesman Problem when the salesman does not have enough time to visit all the cities (Tsiligirides, 1984). In this case, the prizes reflect the expected profit that the salesman can earn in each city. Tsiligirides (1984) also mentions an application in sporting events, which actually gave the name to the OP: an orienteering event is a competition usually held in forests where participants start from and come back to a basecamp within a time limit; during their tour they visit intermediate locations where they are awarded points. The participant who returns to the basecamp with the highest number of points wins. The survey by Vansteenwegen et al. (2011) also mentions applications to the home fuel delivery problem (Golden et al., 1987), where customers need to be resupplied with fuel. The lower is the level of fuel at the customer, the higher the urgency of visiting them during the current day; we can then model this problem as an OP where the prizes are inversely proportional to the fuel level. Another application arises in telecommunication network design (Thomadsen and Stidsen, 2003). The ring topology is often used to build wired networks, since it is resistent to single-failure disruptions. The length of the ring is constrained since noise is proportional to the total length and because a ring too long would increase the probability of double-failure disruptions. If the operator assigns a level of importance to each node, for example proportional to the amount of traffic it is expected to route, the problem of linking the most important nodes with a ring network can be modelled as an OP. A general history of the problem, a description of its many variants, and an overview of exact and heuristic algorithms developed to solve them, can be found in the two surveys by Vansteenwegen et al. (2011) and Gunawan et al. (2016).