Centralized multi-visitor trip planning with activity reservations in crowded destinations

We study the problem of centralised planning of leisure trips in congested areas for visitor groups with reservations for activities. We develop an algorithm that through a combination of customization and coordination can improve average happiness considerably. Extensive numerical experimentation with both synthetic and real-life data show that our algorithm strongly outperforms the classical First-Come-First-Served reservation policy, both in terms of visitor happiness and in terms of fairness among visitors. Moreover, our results show that our algorithm leads to good solutions for small-sized problem instances (with errors typically within 5%–10% from an optimal solution obtained via Integer Linear Programming). Finally, the computational effort with regard to number of visitors is bounded by the capacity and the number of activities, while the increase in computation time for the number of attractions is bounded by the average number of activities that fit into a trip. As a result, our approach leads to good solutions within minutes in realistic settings with more than 10 thousand visitors a day.