Robust Routing in Urban Public Transportation

We study the problem of robust routing in urban public transportation networks. Inorder to propose solutions that are robust for typical delays, we assume that we have pastobservations of real traffic situations available. In particular, we assume that we have “dailyrecords” containing the observed travel times in the whole network for a few past days. Weintroduce a new concept to express a solution that is feasible in any record of a given publictransportation network. We adapt the method of Buhmann et al. for optimization underuncertainty, and develop algorithms that allow its application for finding a robust journeyfrom a given source to a given destination. Finally, we introduce a measure of reliability ofa given journey, and develop algorithms for its computation. The robust routing conceptspresented in this theoretical study are suited specially for public transportation networksof large cities that lack clear hierarchical structure and contain services that run with highfrequencies.