Optimizing itineraries in public transportation with walks between rides

•All possible walks are initially considered.•A framework is developed for identifying efficient walks.•A vast majority of all walks can be left out of consideration because they will never be part of an optimal itinerary.•A real life case shows that allowing for walks between rides has considerable benefits.

We study the problem of finding an optimal itinerary to travel from a starting location to a destination location using public transport, where we allow travelers to alternate rides with (short) walks. The main difference with previous research is that we take all possible walks that a traveler can make into consideration. This large number of possible walks poses a potential computational difficulty. However, in this paper we derive theorems for identifying a small subset of walks that only need to be considered. These results are embedded in a solution algorithm, which is tested in a real-life setting for bus transportation in a medium sized city. An extensive numerical study leads to encouraging results. First, only 1% of all possible walks needs to be considered, so that the optimal itinerary can be determined very efficiently. Second, allowing walks has considerable benefits; reducing the travel time in about 6% of all randomly generated examples by more than 10% on average.