The Clustered Orienteering Problem

The class of routing problems with profits is composed by a wide variety of problems which share the same characteristic: in contrast to what happens in classical routing problems, not all customers need to be served. Instead, a profit is typically associated with each customer and the problem is to choose the right set of customers to serve satisfying a number of side constraints while optimizing a given objective function (maximize the total collected pro.fit, minimize the traveling cost, maximize the difference among profits and costs,...).

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.