TrajectMe: planning sightseeing tours with hotel selection from trajectory data

Abstract

In this work, we propose TRAJECTME, an algorithm that solves the orienteering problem with hotel selection in several cities, taking advantage of the tourists’ trajectories extracted from location-based services. This method is an extension of the state-of-the-art memetic-based algorithm proposed by Ali Divsalar in 2014. To this end, we collect data from services such as Foursquare and Flickr to reconstruct the trajectories of tourists. Next, we build a hotel graph model (HGM) using a set of trajectories and a set of hotels to infer typical sequences of hotels and point of interest (PoI). The HGM is applied in the initialization phase and in the genetic operations of the memetic algorithm to provide sequences of hotels, whereas the associated sequence of PoIs evolved by applying local search moves. We evaluate our proposal using a large and real dataset from three Italian cities using up to 1000 hotels. The results show that the proposed algorithm outperforms the state-of-the-art when using large real datasets. Our approach is better than the baseline algorithm by up to 208% concerning the solution score and proved to be more profitable toward PoI visiting time, being 54% better than state-of-the-art.