Time-dependent shortest paths through a fixed sequence of nodes: application to a travel planning problem

In this paper, we introduce a travel planning problem which is solved by computing time-dependent shortest paths through a fixed sequence of nodes. Given a predetermined itinerary, our travel planning problem consists in finding the best travel plan, involving planes and hotels, based on the traveler's preferences. Our time-dependent framework therefore models plane flights, hotels, stays in each city as well as global time constraints. Given the large size of time-dependent networks, an exact decomposition algorithm is devised to solve instances of realistic size in reasonable computation times.