Decentral routing strategies for public transportation

Abstract

In case of large disturbances in public transportation networks, there often is little information available for central dispatching. Moreover, high frequency systems may use decentral dispatching. We consider a local dispatching strategy, where a cyclic order is assigned to the lines. This order determines which route the next vehicle to depart will take and the timetable determines when this will be. It has been proved this system stabilises to the normal schedule, when all lines are operated with the same frequency. When looking at arbitrary frequencies, deciding whether a timetable can be operated with a certain number of vehicles is NP-complete in the strong sense. The goal of this thesis is to consider variations, e.g. star networks or frequencies that are multiples of each other and see if these are NP-complete as well or if we can prove stabilisation results. In case of stabilisation we would also like to know how fast it stabilises. Finally we will consider the stabilised situation to see if we can deduce properties for the stabilised system.