A matheuristic for transfer synchronization through integrated timetabling and vehicle scheduling

João Paiva Fonseca, Evelien van der Hurk, Roberto Roberti, Allan Larsen

Research output: Contribution to journalArticle

Abstract

Long transfer times often add unnecessary inconvenience to journeys in public transport systems. Synchronizing relevant arrival and departure times through small timetable modifications could reduce excess transfer times, but may also directly affect the operational costs, as the timetable defines the set of feasible vehicle schedules. Therefore better results in terms of passenger service, operational costs, or both, could be obtained by solving these problems simultaneously. This paper addresses the tactical level of the integrated timetabling and vehicle scheduling problem as a bi-objective mixed integer programming problem that minimizes transfer costs and operational costs. Given an initial non-cyclical timetable, and time-dependent service times and passenger demand, the weighted sum of transfer time cost and operational costs 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 with transfer opportunities. A matheuristic is proposed that iteratively solves the mathematical formulation of the integrated timetabling and vehicle scheduling problem allowing timetable modifications for a subset of timetabled trips only, while solving the full vehicle scheduling problem. We compare different selection strategies for defining the sub-problems. Results for a realistic case study of the Greater Copenhagen area indicate that the matheuristic is able to find better feasible solutions faster than a commercial solver and that allowing the addition of dwell time creates a larger potential for reducing transfer costs.

LanguageEnglish
Pages128-149
Number of pages22
JournalTransportation Research. Part B: Methodological
Volume109
Issue numberMarch
Early online date3 Feb 2018
DOIs
StatePublished - Mar 2018

Cite this

Fonseca, João Paiva ; van der Hurk, Evelien ; Roberti, Roberto ; Larsen, Allan. / A matheuristic for transfer synchronization through integrated timetabling and vehicle scheduling. In: Transportation Research. Part B: Methodological. 2018 ; Vol. 109, No. March. pp. 128-149
@article{4ef3c6f112294408bfec360f99ea2736,
title = "A matheuristic for transfer synchronization through integrated timetabling and vehicle scheduling",
abstract = "Long transfer times often add unnecessary inconvenience to journeys in public transport systems. Synchronizing relevant arrival and departure times through small timetable modifications could reduce excess transfer times, but may also directly affect the operational costs, as the timetable defines the set of feasible vehicle schedules. Therefore better results in terms of passenger service, operational costs, or both, could be obtained by solving these problems simultaneously. This paper addresses the tactical level of the integrated timetabling and vehicle scheduling problem as a bi-objective mixed integer programming problem that minimizes transfer costs and operational costs. Given an initial non-cyclical timetable, and time-dependent service times and passenger demand, the weighted sum of transfer time cost and operational costs 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 with transfer opportunities. A matheuristic is proposed that iteratively solves the mathematical formulation of the integrated timetabling and vehicle scheduling problem allowing timetable modifications for a subset of timetabled trips only, while solving the full vehicle scheduling problem. We compare different selection strategies for defining the sub-problems. Results for a realistic case study of the Greater Copenhagen area indicate that the matheuristic is able to find better feasible solutions faster than a commercial solver and that allowing the addition of dwell time creates a larger potential for reducing transfer costs.",
keywords = "Bus timetabling, Matheuristic, Mixed integer linear programming, Public transport, Vehicle scheduling",
author = "Fonseca, {Jo\{~a}o Paiva} and {van der Hurk}, Evelien and Roberto Roberti and Allan Larsen",
year = "2018",
month = "3",
doi = "10.1016/j.trb.2018.01.012",
language = "English",
volume = "109",
pages = "128--149",
journal = "Transportation Research. Part B: Methodological",
issn = "0191-2615",
publisher = "Elsevier Limited",
number = "March",

}

A matheuristic for transfer synchronization through integrated timetabling and vehicle scheduling. / Fonseca, João Paiva; van der Hurk, Evelien; Roberti, Roberto; Larsen, Allan.

In: Transportation Research. Part B: Methodological, Vol. 109, No. March, 03.2018, p. 128-149.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A matheuristic for transfer synchronization through integrated timetabling and vehicle scheduling

AU - Fonseca,João Paiva

AU - van der Hurk,Evelien

AU - Roberti,Roberto

AU - Larsen,Allan

PY - 2018/3

Y1 - 2018/3

N2 - Long transfer times often add unnecessary inconvenience to journeys in public transport systems. Synchronizing relevant arrival and departure times through small timetable modifications could reduce excess transfer times, but may also directly affect the operational costs, as the timetable defines the set of feasible vehicle schedules. Therefore better results in terms of passenger service, operational costs, or both, could be obtained by solving these problems simultaneously. This paper addresses the tactical level of the integrated timetabling and vehicle scheduling problem as a bi-objective mixed integer programming problem that minimizes transfer costs and operational costs. Given an initial non-cyclical timetable, and time-dependent service times and passenger demand, the weighted sum of transfer time cost and operational costs 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 with transfer opportunities. A matheuristic is proposed that iteratively solves the mathematical formulation of the integrated timetabling and vehicle scheduling problem allowing timetable modifications for a subset of timetabled trips only, while solving the full vehicle scheduling problem. We compare different selection strategies for defining the sub-problems. Results for a realistic case study of the Greater Copenhagen area indicate that the matheuristic is able to find better feasible solutions faster than a commercial solver and that allowing the addition of dwell time creates a larger potential for reducing transfer costs.

AB - Long transfer times often add unnecessary inconvenience to journeys in public transport systems. Synchronizing relevant arrival and departure times through small timetable modifications could reduce excess transfer times, but may also directly affect the operational costs, as the timetable defines the set of feasible vehicle schedules. Therefore better results in terms of passenger service, operational costs, or both, could be obtained by solving these problems simultaneously. This paper addresses the tactical level of the integrated timetabling and vehicle scheduling problem as a bi-objective mixed integer programming problem that minimizes transfer costs and operational costs. Given an initial non-cyclical timetable, and time-dependent service times and passenger demand, the weighted sum of transfer time cost and operational costs 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 with transfer opportunities. A matheuristic is proposed that iteratively solves the mathematical formulation of the integrated timetabling and vehicle scheduling problem allowing timetable modifications for a subset of timetabled trips only, while solving the full vehicle scheduling problem. We compare different selection strategies for defining the sub-problems. Results for a realistic case study of the Greater Copenhagen area indicate that the matheuristic is able to find better feasible solutions faster than a commercial solver and that allowing the addition of dwell time creates a larger potential for reducing transfer costs.

KW - Bus timetabling

KW - Matheuristic

KW - Mixed integer linear programming

KW - Public transport

KW - Vehicle scheduling

UR - http://www.scopus.com/inward/record.url?scp=85044542078&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044542078&partnerID=8YFLogxK

U2 - 10.1016/j.trb.2018.01.012

DO - 10.1016/j.trb.2018.01.012

M3 - Article

VL - 109

SP - 128

EP - 149

JO - Transportation Research. Part B: Methodological

T2 - Transportation Research. Part B: Methodological

JF - Transportation Research. Part B: Methodological

SN - 0191-2615

IS - March

ER -