The Clustered Orienteering Problem

The Clustered Orienteering Problem

0.00 Avg rating0 Votes
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: , ,
Keywords: combinatorial optimization
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.