Reliability in public transport networks

Efficient public transport is fundamental to increase the life quality of people, especially if they live in big cities, where traffic can be an issue. Effective public transport can have a variety of positive effects on the life quality of people, involving money and health. In order to make people to fully exploit public transport, we need to take into account reliability, which plays a very important role in this context. In particular, we are interested in having reliable networks, and in developing reliable journey planners. The first problem addressed in this thesis is the development of algorithms useful to analyze the structural reliability of the directed graph underlying the topology of a public transport network. Indeed, we introduce and analyze concepts of graph theory which are of key importance to investigate the reliability of a network, such as strong articulation points and strong bridges. We thus provided the first linear-time algorithms to compute all the strong articulation points and all the strong bridges of a directed graph. We remark that the algorithms presented in this thesis represent a considerable advance with respect to previously known state of the art solutions. In addition, we engineered the implementations of such algorithms, testing them against large-scale graphs. Our solutions turned to be extremely efficient in practice, being able to run in about a dozen minutes for graphs with up to half a billion edges, on standard machines. The second problem addressed in this thesis is the computation of reliable journeys, exploiting the availability of GPS data, which describe the actual movements of transit vehicles in the network. State of the art algorithms for computing journeys in public transport networks are extremely efficient, but they are timetable-based, i.e., they assume implicitly that all transit vehicles run on schedule. This assumption is not always realistic, especially in the case of big cities, where delays are not rare events. It is thus natural to wonder what is the impact of the unreliable schedule on timetable-based journey planning. Moreover, we investigated how we can leverage the availability of GPS data. We remark that, to the best of our knowledge, no previous work considered to use GPS data directly in the planning stage. Our experiments showed that timetable-based journey planning might fail to deliver highly reliable solutions, while GPS data can help in improving the reliability of journeys. Moreover, combining algorithmic techniques explicitly taking into account reliability, and the exploitation of GPS data, we can greatly improve the reliability of the journeys computed. In addition, we proposed a new algorithm specifically designed to improve the reliability of a journey. Our experimental analysis validated the expected advantages of the proposed approach: we get the highest accuracy of the estimated time for a given journey among all the considered approaches, at the cost of a small increase of travel times.