A multi-day tourist trip planning with multiple time windows and multiple levels of service

Document Type : Original Article


Department of Industrial Engineering, Faculty of Materials and Industrial Engineering, Babol Noshirvani University of Technology, Babol, Iran


To plan a trip, a tourist should start with collecting information from various sources. Then, he might want to select a number of available points of interest (POI) according to his personal interests and considering many criteria such as, time and budget limitation and the opening and closing times of POIs. Therefore, planning such a daily tour becomes a complex and important task. This problem in its general form is called the Tourist Trip Design Problem (TTDP) in the literature. In this study, we have considered a variant of TTDP in which a number of POIs are taken as mandatory points to visit and the goal is to create a tour in such a way that all mandatory points are included and the total score collected by visiting the optional points of interest are maximized, taking into account different daily opening hours. Moreover, constraints on the length of the route and the maximum budget of the trip should be satisfied. Furthermore, some POIs, are considered to provide multiple levels of services to the visitor. This means that one might select a preferred level of service among the available ones on top of selecting among different POIs according to the associated score and cost. This variant of the TTDP is modeled as a variant of the Orienteering Problem (OP) which we call the Multi-Level Multi-Period Orienteering Problem with Multiple Time Windows (ML-MP-OP-MTW). The proposed integer program is implemented using the CPLEX optimization software. Then, based on available data from the literature, a number of numerical instances are developed and solved. The results show that CPLEX is able to solve only small size instances of the problem in a limited computational time of one hour using a personal computer.