An agile optimization algorithm for the tourist trip design problem with type-covering constraints

The tourist trip design problem with type-covering constraints (TTDP-TC) is a novel variant of the well-established orienteering problem (OP) designed to address the complex preferences of tourists planning multi-day trips. Unlike classical routing problems, which require visiting all points of interest (POIs), the TTDP-TC allows selective visitation based on perceived value, subject to a maximum travel time constraint. This variant introduces a type-covering requirement, ensuring that each trip includes at least one POI of every specified type, adding a layer of complexity to the optimization process. In this paper, an agile optimization algorithm to solve the TTDP-TC efficiently is proposed, which aims to maximize the total profit collected from visited POIs while ensuring compliance with type-covering requirements and travel time limits. Our approach applies the coverage rules to the overall routing plan, instead of just to singular itineraries as in other recent studies. The algorithm's performance is validated through extensive computational experiments, demonstrating its ability to generate high-quality solutions within short computational times. To further validate the competitiveness of our approach, an exact method to compare the results of our approach is also implemented. The proposed approach showcases significant potential for practical applications in tourist decision support systems, offering a flexible and robust solution for planning enriched and diverse tourist experiences.