An adaptive heuristic for the Capacitated Team Orienteering ProblemReportar como inadecuado

An adaptive heuristic for the Capacitated Team Orienteering Problem - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Labex MS2T - Laboratoire d-Excellence -Maîtrise des Systèmes de Systèmes Technologiques- 2 Heudiasyc - Heuristique et Diagnostic des Systèmes Complexes Compiègne 3 Lebanese University Beirut

Abstract : 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.

Keywords : Capacitated Team Orienteering Problem iterative local search adaptive destruction-construction heuristic

Autor: Asma Ben-Said - Racha El-Hajj - Aziz Moukrim -



Documentos relacionados