The Periodic Assignment Problem (PAP) May Be Solved Greedily
Liebchen, Christian
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Many public transportation companies operate their networks periodically. One major step in their planning process is to construct a periodic timetable for one abstract period, independently from times during the day. In this paper we show that we may evaluate a periodic timetable very quickly with the number of vehicles required to operate it. This is due to the fact that the Periodic Assignment Problem (PAP) can be solved by a greedy approach. It helps us, at least within a genetic algorithm, to cope with the quadratic objective function in the problem of finding a periodic timetable requiring as few vehicles as possible.
