Synchronizing transfers through integrated timetabling and vehicle scheduling - an iterative matheuristic approach with public transit traffic assignment

Transfer times add inconvenience to journeys and thus synchronizing departures and arrival times of relevant lines improves the service for passengers. As the timetable changes passengers may also change their travel itineraries. Additionally, introducing small timetable modifications may also affect the operational costs, as the timetable defines a set of feasible vehicle schedules. We address the Integrated Timetabling and Vehicle Scheduling Problem (IT-VSP) with Public Transit Traffic Assignment (PTTA). The IT-VSP is formulated as a MILP that minimizes transfer costs with a budget on operational costs. Given an initial noncyclical timetable, time-dependent service times and passenger demands, the transfer time cost is minimized by allowing modifications to the timetable that respect a set of headway constraints. Timetable modifications consist of shifts in departure time and addition of dwell time at intermediate stops. We propose to solve the problem iterating between solving a matheuristic for the IT-VSP and re-computing the PTTA. The matheuristic solves the ITVSP MILP allowing timetable modifications for a subset of timetabled trips only, while solving the full vehicle scheduling problem. Results for the Greater Copenhagen area indicate that our approach finds better solutions faster than a commercial solver and that allowing the addition of dwell time creates a larger potential for reducing transfer costs. We also show that
the integration with the PTTA model generated solutions with lower transfer costs then the solutions obtained with a version that does not compute new passenger assignments once the timetables change.