TY - JOUR
T1 - A matheuristic for passenger service optimization through timetabling with free passenger route choice
AU - Fonseca, João Paiva
AU - Zündorf, Tobias
AU - van der Hurk, Evelien
AU - Zhu, Yongqiu
AU - Larsen, Allan
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - Bus timetabling
KW - Matheuristic
KW - Mixed integer linear programming
KW - Passenger route choice
KW - Public transport
UR - http://www.scopus.com/inward/record.url?scp=85132613421&partnerID=8YFLogxK
U2 - 10.1007/s00291-022-00681-0
DO - 10.1007/s00291-022-00681-0
M3 - Article
AN - SCOPUS:85132613421
SN - 0171-6468
VL - 44
SP - 1087
EP - 1129
JO - OR Spectrum
JF - OR Spectrum
IS - 4
ER -