Combinatorial Learning in Traffic Management

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.