A matheuristic for transfer synchronization through integrated timetabling and vehicle scheduling. (March 2018)

• Record Type: Journal Article
• Authors: Fonseca, João Paiva; van der Hurk, Evelien; Roberti, Roberto; Larsen, Allan
• Is Part Of: Transportation research. Volume 109(2018)
• Page Start: 128
• Page End: 149
• Publication Date: 2018-03
• Subjects: Public transport -- Bus timetabling -- Vehicle scheduling -- Mixed integer linear programming -- Matheuristic; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2018.01.012
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: The paper studies the integration of timetabling and vehicle scheduling with the aim to reduce passenger associated costs and operating costs, thereby contributing to the current trend of integrating planning phases in public transport. It proposes a matheuristic approach based on a new mathematical for-mulation that allows for a far wider set of timetable modifi cations than considered in previous research. The matheuristic is able to nd better feasible solutions faster than a commercial solver. It includes a real-life case study for the express bus network in the Greater Copenhagen area, for which the proposed matheuristic can nd provably good solutions in reasonable amounts of computational time. 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.