The Vacation Planning Problem: A multi-level clustering-based metaheuristic approach. (February 2023) - Vathis, Nikolaos; Konstantopoulos, Charalampos; Pantziou, Grammati; Gavalas, Damianos
Abstract: We study the Vacation Planning Problem (VPP), an extension of the Tourist Trip Design Problem which is suitable for modelling scenarios wherein a tourist wishes to explore a large geographical area (e.g. an administrative region), rather than a single urban destination. Further to deriving personalized daily tourist routes i.e., ordered visits to points of interest (POIs) that maximize tourist satisfaction (profit), VPP also recommends intermediate destinations along the trip (most typically, towns to stay overnight) and accommodation areas, as well as optimal distribution of trip days among the different destinations. Herein, we formally define the VPP and present an innovative multi-level clustering scheme to group POIs together and an efficient dynamic programming approach for solving the problem. The proposed method yields higher-profit results compared to an existing approach, as it adopts a sophisticated approach in rendering the geography of the region to be visited by the tourist. Highlights: VPP models the selection of destinations, the duration of stay on them and the planning of daily routes. VPP is solved using a novel hierarchical multi-level clustering scheme. The algorithm adopts a sophisticated approach in rendering the geography of the touristic region. The algorithm offers meaningful high-profit vacation plans in low response time.