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

Veronica Dal Sasso (), Luigi De Giovanni () and Martine Labbé ()
Additional contact information
Veronica Dal Sasso: Dipartimento di Matematica “Tullio Levi–Civita,” Università degli Studi di Padova, 35121 Padova, Italy
Luigi De Giovanni: Dipartimento di Matematica “Tullio Levi–Civita,” Università degli Studi di Padova, 35121 Padova, Italy
Martine Labbé: Graphes et Optimisation Mathématique, Université Libre de Bruxelles, 1050 Bruxelles, Belgium

Transportation Science, 2019, vol. 53, issue 5, 1271–1286

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.

Keywords: delay management; mixed integer linear programming; polyhedral study; branch and cut (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0874 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:5:p:1271-1286

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().