Til hovedinnhold

A novel formulation for job-shop scheduling in traffic management

A novel formulation for job-shop scheduling in traffic management

Kategori
Vitenskapelig foredrag
Sammendrag
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.
Oppdragsgiver
  • Research Council of Norway (RCN) / 267554
Språk
Engelsk
Institusjon(er)
  • SINTEF Digital / Mathematics and Cybernetics
  • Universitetet i Oslo
Presentert på
ISMP 2018
Dato
01.07.2018 - 06.07.2018
År