Aperiodic public transport timetabling with flexible line plans

Timetabling problems in public transport take as input line plans, stopping patterns and desired hourly frequencies. In the aperiodic timetabling problem with line planning elements (AT-LP) we allow changes in the line plans with the objective of maximizing passenger service, measured as a function of in-vehicle travel time, transfer time, transfer penalty, and waiting time.

For a timetable to be feasible it must respect track section headways, station headways, station capacities. Furthermore we define lower and upper bounds on how much line plans may be changed. We present a heuristic approach to solve the AT-LP. Given a fixed Origin-Destination-Time matrix, we compute an initial feasible timetable.

Modifications to the timetable in the form of shifting trips, adding and removing dwell time, skipping and adding stops, and increasing and decreasing frequency are then applied. Solutions that maximize passenger service respecting a budget on operational costs (measured as train.minutes cost) are accepted.

Results for a case study using a train network in The Netherlands indicate that including line planning modifications allows obtaining timetables with increased passenger service when compared with using only timetable modifications. We use a lower bound on passenger service to compare the results obtained by our methodology.