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 custo...

Full description

Saved in:
Bibliographic Details
Published in:IFAC-PapersOnLine 2016, Vol.49 (12), p.1662-1666
Main Authors: Ben-Said, Asma, El-Hajj, Racha, Moukrim, Aziz
Format: Article
Language:English
Subjects:
adaptive destruction/construction heuristic
Capacitated Team Orienteering Problem
iterative local search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2405-8963
2405-8963
DOI:10.1016/j.ifacol.2016.07.819