An adaptive heuristic for the Capacitated Team Orienteering Problem

摘要

The Capacitated Team Orienteering Problem (CTOP) is a new variant of the well-known Team Orienteering Problem (TOP) where an additional constraint is imposed on the vehicles capacities. By associating a profit and a demand to each customer, the objective of solving CTOP is to select the set of customers to be served in such a way that the total amount of profits collected from the visited customers is maximized, while respecting all the resource limitations, i.e., maximum length limit and maximum capacity of each vehicle. We present in this paper a new adaptive heuristic to solve CTOP. Our method is based on an adaptive iterative destructive constructive heuristic, which adjusts its parameters according to the solution progress. Computational experiments applied on the benchmark of CTOP show the effectiveness of our proposed method, which provided some results of high quality with a competitive computational time. Moreover, an improvement was found in the score of one of the hardest instances of the benchmark.