Skip to Main content Skip to Navigation
Journal articles

Strengthened Formulations and Valid Inequalities for Single Delay Management in Public Transportation

Veronica Dal Sasso 1 Luigi de Giovanni 1 Martine Labbé 2
2 INOCS - Integrated Optimization with Complex Structure
ULB - Université libre de Bruxelles, Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : The Delay Management Problem arises in Public Transportation networks, often characterized by the necessity of connections between different vehicles. The attractiveness of Public Transportation networks is strongly related to the reliability of connections, which can be missed when delays or other unpredictable events occur. Given a single initial delay at one node of the network, the Delay Management Problem is to determine which vehicles have to wait for the delayed ones, with the aim of minimizing the dissatisfaction of the passengers. In this paper, we present strengthened mixed integer linear programming formulations and new families of valid inequalities. The implementation of branch-and-cut methods and tests on a benchmark of instances taken from real networks show the potential of the proposed formulations and cuts.
Document type :
Journal articles
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Martine Labbé Connect in order to contact the contributor
Submitted on : Friday, November 16, 2018 - 4:55:50 PM
Last modification on : Tuesday, October 19, 2021 - 12:55:40 PM
Long-term archiving on: : Sunday, February 17, 2019 - 3:12:26 PM


Files produced by the author(s)




Veronica Dal Sasso, Luigi de Giovanni, Martine Labbé. Strengthened Formulations and Valid Inequalities for Single Delay Management in Public Transportation. Transportation Science, INFORMS, 2019, 53 (5), pp.1213-1499. ⟨10.1287/trsc.2018.0874⟩. ⟨hal-01925451⟩



Record views


Files downloads