Abstract
A central problem in traffic management is that of scheduling
the movements of vehicles so as to minimize the cost of
the schedule. This problem can be modeled as a job-shop
scheduling problem. We present a new MILP formulation
which is alternative to classical approaches such as big-M
and time-indexed formulations. It does not make use of artificially
large coefficients and its constraints correspond to
basic graph structures, namely paths, cycles and trees. The new formulation can be obtained by strengthening and lifting the constraints of a classical Benders’ reformulation. We successfully tested our approach on real-life instances of two
relevant traffic management problems: the Hotspot Problem,
which consists of rescheduling flight trajectories to prevent
congested airborne sectors while minimizing overall delay;
and train dispatching, which consists of rescheduling the
movements of rolling stocks in railway lines, typically due to
delays or disruptions.
the movements of vehicles so as to minimize the cost of
the schedule. This problem can be modeled as a job-shop
scheduling problem. We present a new MILP formulation
which is alternative to classical approaches such as big-M
and time-indexed formulations. It does not make use of artificially
large coefficients and its constraints correspond to
basic graph structures, namely paths, cycles and trees. The new formulation can be obtained by strengthening and lifting the constraints of a classical Benders’ reformulation. We successfully tested our approach on real-life instances of two
relevant traffic management problems: the Hotspot Problem,
which consists of rescheduling flight trajectories to prevent
congested airborne sectors while minimizing overall delay;
and train dispatching, which consists of rescheduling the
movements of rolling stocks in railway lines, typically due to
delays or disruptions.