The Tourist Trip Design problem is an extension of the Orienteering Problem applied to tourism. The problem consists in selecting a subset of locations to visit, among a larger set, while maximizing the benefit for the tourist. The latter is given by the sum of the rewards collected at each visited location. We consider a variant of the problem dealing not only with "typical" constraints such as budget, opening time hours (i.e., time windows on the locations), and maximum trip duration, but also other practical constraints such as mandatory visits, limits on the number of locations of each type (e.g., no more than X castles, or Y museums), subsets of exclusive locations (e.g., if A is visited then B cannot be visited), subsets locations that must be visited together (e.g., if A is visited, then B must be visited), subsets locations that must be visited in order (e.g. if A, B are both visited, then A must be visited before B).

To solve this complex problem, we propose a branch-and-check approach. In our approach, the master problem selects a subset of locations verifying all constraints but time-related constraints. Then the subproblem checks that a feasible trip can be built. We propose and compare different formulations for the master problem. We also explore different types of valid inequalities aiming to tighten the master problem. The latter are dynamically generated during the execution of the algorithm. We also propose intensification strategies to further improve the performance of the algorithm. We report the experimental results and compare the performance of the proposed algorithm with the state-of-art Mixed Integer Programming solver CPLEX 12.8.