research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleCluster-based Heuristics for the Team Orienteering Problem with Time Windows
Bibtex cite IDRACTI-RU1-2013-27
Booktitle 12th International Symposium on Experimental Algorithms - SEA’2013
Series LNCS
Year published 2013
Volume 7933
Pages 390-401
Publisher Springer-Verlag, V. Bonifaci et al. (Eds.)
Location Rome, Italy
Keywords Tourist Trip Design Problem,Point of Interest,Team Orienteering Problem with Time Windows,Iterated Local Search,Clustering
The Team Orienteering Problem with Time Windows (TOPTW) deals with deriving a number of tours comprising a subset of candidate nodes (each associated with a \pro t" value and a visiting time window) so as to maximize the overall \pro t", while respecting a speci ed time span. TOPTW has been used as a reference model for the Tourist Trip Design Problem (TTDP) in order to derive near-optimal multiple-day tours for tourists visiting a destination featuring several points of inter- est (POIs), taking into account a multitude of POI attributes. TOPTW is an NP-hard problem and the most ecient known heuristic is based on Iterated Local Search (ILS). However, ILS treats each POI separately; hence it tends to overlook highly pro table areas of POIs situated far from the current location, considering them too time-expensive to visit. We propose two cluster-based extensions to ILS addressing the afore- mentioned weakness by grouping POIs on disjoint clusters (based on geographical criteria), thereby making visits to such POIs more attrac- tive. Our approaches improve on ILS with respect to solutions quality, while executing at comparable time and reducing the frequency of overly long transfers among POIs.
Gavalas, Damianos
Konstantopoulos, Charalampos
Mastakas, Konstantinos
Pantziou, Grammati
Tasoulas, Yiannis
SEA\'13.pdf (main file)
Publication ID1010