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

[RACTI-RU1-2014-35] Gavalas, Damianos, Kasapakis, Vlasios, Konstantopoulos, Charalampos, Pantziou, Grammati, Vathis, Nikolaos and Zaroliagis, Christos, A Personalized Multimodal Tourist Tour Planner, in: 13th International Conference on Mobile and Ubiquitous Multimedia, pages 73-80, MUM 2014 (ACM), 2014.

Keywords:

Tourist Trip Design Problem, Multimodal Route Planning, Orienteering Problem, Context Awareness, Mobile Application

[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.
[RACTI-RU1-2014-8] Gavalas, Damianos, Konstantopoulos, Charalampos, Mastakas, Konstantinos, Pantziou, Grammati and Vathis, Nikolaos, Efficient Heuristics for the Time Dependent Team Orienteering Problem with Time Windows, in: International Conference on Applied Algorithms - ICAA’2014, pages 151-162, Springer-Verlag, 2014.
Abstract: The Time Dependent Team Orienteering Problem with Time Windows (TDTOPTW) can be used to model several real life problems. Among them, the route planning problem for tourists interested in visiting multiple points of interest (POIs) using public transport. The main objective of this problem is to select POIs that match tourist preferences, while taking into account a multitude of parameters and constraints and respecting the time available for sightseeing in a daily basis. TDTOPTW is NP-hard while almost the whole body of the related literature addresses the non time dependent version of the problem. The only TDTOPTW heuristic proposed so far is based on the assumption of periodic service schedules. Herein, we propose two efficient cluster-based heuristics for the TDTOPTW which yield high quality solutions, take into account time dependency in calculating travel times between POIs and make no assumption on periodic service schedules. The validation scenario for our prototyped algorithms included the metropolitan transit network and real POI sets compiled from Athens (Greece).