Aigaion: RACTI / RU1 Technical Report Series (Web Based)

[RACTI-RU1-2013-27] Gavalas, Damianos, Konstantopoulos, Charalampos, Mastakas, Konstantinos, Pantziou, Grammati and Tasoulas, Yiannis, Cluster-based Heuristics for the Team Orienteering Problem with Time Windows, in: 12th International Symposium on Experimental Algorithms - SEA’2013, pages 390-401, Springer-Verlag, V. Bonifaci et al. (Eds.), Rome, Italy, 2013.

Keywords:

Tourist Trip Design Problem, Point of Interest, Team Orienteering Problem with Time Windows, Iterated Local Search, Clustering

[RACTI-RU1-2013-27] Gavalas, Damianos, Konstantopoulos, Charalampos, Mastakas, Konstantinos, Pantziou, Grammati and Tasoulas, Yiannis, Cluster-based Heuristics for the Team Orienteering Problem with Time Windows, in: 12th International Symposium on Experimental Algorithms - SEA’2013, pages 390-401, Springer-Verlag, V. Bonifaci et al. (Eds.), Rome, Italy, 2013.
Abstract: 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 \prot" value and a visiting time window) so as to maximize the overall \prot", while respecting a specied 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 protable 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.