To main content

Combinatorial Learning in Traffic Management

Abstract

We describe an exact combinatorial learning approach to solve dynamic job-shop scheduling problems arising in traffic management. When a set of vehicles has to be controlled in real-time, a new schedule must be computed whenever a deviation from the current plan is detected, or periodically after a short amount of time. This suggests that each two (or more) consecutive instances will be very similar. We exploit a recently introduced MILP formulation for job-shop scheduling (called path&cycle) to develop an effective solution algorithm based on delayed row generation. In our re-optimization framework, the algorithm maintains a pool of combinatorial cuts separated during the solution of previous instances, and adapts them to warm start each new instance. In our experiments, this adaptive approach led to a 4-time average speedup over the static approach (where each instance is solved independently) for a critical application in air traffic management.

Category

Academic article

Language

English

Author(s)

Affiliation

  • SINTEF Digital / Mathematics and Cybernetics

Year

2020

Published in

Lecture Notes in Computer Science (LNCS)

ISSN

0302-9743

Volume

11943 LNCS

Page(s)

384 - 395

View this publication at Norwegian Research Information Repository