Article ID: | iaor20142012 |
Volume: | 238 |
Issue: | 2 |
Start Page Number: | 404 |
End Page Number: | 414 |
Publication Date: | Oct 2014 |
Journal: | European Journal of Operational Research |
Authors: | Archetti C, Angelelli E, Vindigni M |
Keywords: | combinatorial optimization |
In this paper we study a generalization of the Orienteering Problem (OP) which we call the Clustered Orienteering Problem (COP). The OP, also known as the Selective Traveling Salesman Problem, is a problem where a set of potential customers is given and a profit is associated with the service of each customer. A single vehicle is available to serve the customers. The objective is to find the vehicle route that maximizes the total collected profit in such a way that the duration of the route does not exceed a given threshold. In the COP, customers are grouped in clusters. A profit is associated with each cluster and is gained only if all customers belonging to the cluster are served. We propose two solution approaches for the COP: an exact and a heuristic one. The exact approach is a branch‐and‐cut while the heuristic approach is a tabu search. Computational results on a set of randomly generated instances are provided to show the efficiency and effectiveness of both approaches.