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 [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - 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 metadatas

https://hal.inria.fr/hal-01925451
Contributor : Martine Labbé <>
Submitted on : Friday, November 16, 2018 - 4:55:50 PM
Last modification on : Friday, March 22, 2019 - 1:37:03 AM
Long-term archiving on : Sunday, February 17, 2019 - 3:12:26 PM

File

Transportation-Science-railway...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01925451, version 1

Collections

Citation

Veronica Dal Sasso, Luigi de Giovanni, Martine Labbé. Strengthened Formulations and Valid Inequalities for Single Delay Management in Public Transportation. Transportation Science, INFORMS, In press. ⟨hal-01925451⟩

Share

Metrics

Record views

41

Files downloads

50