A Polyhedral Study for Delay Management in Public Transportation

AbstractThe attractiveness of intermodal public transportation networks is strongly related to the reliability of connections between vehicles. As a consequence, operational decisions are required to manage connections in case of unpredictable events like breakdowns or vehicle delays. In such cases, the network operators have to determine if connected vehicles should wait for the delayed ones or keep their schedule. The Delay Management Problem (DMP) consists in defining a wait/depart policy that minimizes the total delay incurred by passengers. In this work we present a polyhedral study for DMP: starting from a previous integer linear programming formulation and from results on the Mixed 0-1 Knapsack Polytope, we derive new valid inequalities and we show that they define facets of the convex-hull of some special cases