The clustered team orienteering problem

• Published in: Computers & operations research 2019-11, Vol.111, p.386-399
• Main Authors: Yahiaoui, Ala-Eddine, Moukrim, Aziz, Serairi, Mehdi
• Format: Article
• Language: English
• Subjects: Adaptive large neighborhood search; Algorithms; Cluster; Clusters; Computer Science; Customers; Cutting; Cutting plane; Heuristic; Heuristic methods; Incompatibility; Operations Research; Orienteering; Planes; Split procedure; Team orienteering problem; Travel time; Vehicles
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2019.07.008

•We introduce a new variant of the TOP called the Clustered Team Orienteering Problem. A mathematical model is proposed.•We propose an efficient exact algorithm based on a cutting planes approach to solve the CluTOP.•We extend our heuristic initially proposed for the COP to cover the case with multiple vehicles.•We extend our heuristic initially proposed for the COP to cover the case with multiple vehicles. In this paper, we present a new variant of the Clustered Orienteering Problem (COP) that we refer to as the Clustered Team Orienteering Problem (CluTOP). In this problem, customers are grouped into subsets called clusters. A profit is associated with each cluster and is gained only if all of its customers are served. A set of available vehicles with a limited travel time collaborates in order to visit the customers of the clusters. The objective is to maximize the total collected profit with respect to a travel time limit. The first contribution of this paper consists of an exact method based on a cutting planes approach. This method includes the consideration of a set of valid inequalities. In particular, an incompatibility-cluster-based valid inequality is proposed. Moreover, a pre-processing procedure is considered in order to compute the incompatibilities between clusters. The second contribution is a hybrid heuristic that combines an Adaptive Large Neighborhood Search (ALNS) and an effective split procedure. These two components cooperate together for the purpose of exploring both direct representation and giant tours search spaces. Experimental results show that the cutting planes based algorithm outperforms the state-of-the-art exact methods, in the particular case of a single vehicle by solving 61 additional instances. Moreover, the hybrid heuristic succeeds in finding 38 new best known solutions for the case of one vehicle. For the case with multiple vehicles, new benchmark instances are generated based on those introduced for the COP. Regarding the performance of the methods, the heuristic method finds the optimal solution for almost all the instances solved by the exact method.