The periodic service intention as a conceptual framework for generating timetables with partial periodicity

Many railway companies in Europe operate periodic timetables. Yet most timetables are not entirely periodic but have a mixture of different periodicities and many exceptions to cope with changing demand. Current approaches for automatic timetable generation are not able to deal with such partially periodic structures but consider only fully periodic inputs. We therefore introduce the periodic Service Intention (pSI) as a framework where customer-relevant information about train services can be described, including their periodicity information. We then address the problem of finding a feasible timetable that fulfills the requirements specified in a pSI without the need for manual post-processing. We solve this problem by projecting intended train runs over equivalence classes and thereby reducing the pSI to an augmented instance of periodic timetabling. Thus it is possible to use existing models for periodic scheduling, such as Periodic Event Scheduling Problem, to generate periodic timetables with partial periodicity, which are finally rolled out to obtain the desired daily schedule according to the commercial requirements of the pSI. Results for a test case from the timetable for central Switzerland in 2008 show that this approach needs only slightly longer computation time than for a fully periodic instance, but the additional time is compensated by the fact that post-processing becomes unnecessary and by the better quality of the solution. The approach is particularly well suited for offers with a strong periodicity but some irregularities, which could not be treated properly by existing methods.