A matheuristic for passenger service optimization through timetabling with free passenger route choice

Abstract

Designing a public transport timetable that maximizes passenger service, measured in weighted travel time, is an intricate problem. The weighted travel time depends on the free route choice of passengers. Passenger route choice depends on the timetable. In turn, the timetable that minimizes weighted travel time depends on the route choice of passengers—and therefore requires passenger route choice information. Consequently, a sequential approach where timetables are designed provided pre-fixed passenger assignment to routes may not find the optimal timetable. This paper aims to integrate passenger route choice and timetabling. It addresses the problem of designing maximal passenger service public transport timetables in systems with free route choice within a budget for operating costs. Operating costs are defined by the minimal cost vehicle schedule required to operate the timetable. The proposed methodology integrates a matheuristic for timetabling and vehicle scheduling with a passenger assignment model in an iterative framework, where different forms of integration are evaluated. Focus is on long- to medium-term timetabling, provided an initial timetable. The results for a realistic case study in the Greater Copenhagen area indicate that our approach consistently leads, at no additional cost, to timetables that represent a reduction in passenger weighted travel time in comparison with both an initial timetable and a non-integrated timetabling method that receives a single-passenger assignment as input.