A matheuristic for integrated timetabling and vehicle scheduling. (September 2019)

• Record Type: Journal Article
• Authors: Carosi, Samuela; Frangioni, Antonio; Galli, Laura; Girardi, Leopoldo; Vallese, Giuliano
• Is Part Of: Transportation research. Volume 127(2019)
• Page Start: 99
• Page End: 124
• Publication Date: 2019-09
• Subjects: Public transport -- Timetabling -- Vehicle-scheduling -- Integrated approach -- Matheuristic; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2019.07.004
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: A new model for integrated timetabling (TT) and vehicle scheduling (VS). First matheuristic for integrated TT and VS with regularity objective function. Tested on real-world instances of service providers for three major Italian cities. Our solutions consistently improve on those obtained manually by experts. Abstract: Planning a public transportation system is a complex process, which is usually broken down in several phases, performed in sequence. Most often, the trips required to cover a service with the desired frequency (headway) are decided early on, while the vehicles needed to cover these trips are determined at a later stage. This potentially leads to requiring a larger number of vehicles (and, therefore, drivers) that would be possible if the two decisions were performed simultaneously. We propose a multicommodity-flow type model for integrated timetabling and vehicle scheduling. Since the model is large-scale and cannot be solved by off-the-shelf tools with the efficiency required by planners, we propose a diving-type matheuristic approach for the problem. We report on the efficiency and effectiveness of two variants of the proposed approach, differing on how the continuous relaxation of the problem is solved, to tackle real-world instances of bus transport planning problem originating from customers of M.A.I.O.R., a leading company providing services and advanced decision-support systems to public transport authorities and operators. The results show that the approach can be used to aid even experienced planners in either obtaining better solutions, or obtaining them faster and with less effort, or both.