The clustered team orienteering problem

doi:10.1016/j.cor.2019.07.008

2019-11-01

Ala‐Eddine Yahiaoui *

Aziz Moukrim

Mehdi Serairi

DOI：10.1016/j.cor.2019.07.008

原文链接

查看原文

摘要

En 中文

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. (C) 2019 Elsevier Ltd. All rights reserved.

Keyword:

Team orienteering problem

Cluster

Cutting plane

Adaptive large neighborhood search

Split procedure