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
2018