The Clustered Orienteering Problem |
| |
Authors: | E Angelelli C Archetti M Vindigni |
| |
Institution: | Department of Economics and Management, University of Brescia, Italy |
| |
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. |
| |
Keywords: | Orienteering Problem Branch-and-cut Tabu search |
本文献已被 ScienceDirect 等数据库收录! |