In real-time traffic management, a new schedule for the vehicles must be computed whenever a deviation from the current plan is detected, or periodically after some time. If this time interval is relatively small, then each two consecutive instances are likely to be similar. We exploit this aspect to derive an exact reoptimization framework for dynamic scheduling problems based on the Path&Cycle formulation. The Path&Cycle (PC) is a non-compact formulation for job-shop scheduling, recently introduced as an effective alternative to the classic big-M and time-indexed formulations. In our approach, PC is solved via delayed row generation and the constraints separated while solving previous instances can be adapted to provide a warm start for the current instance. In other words, we maintain over time a pool of valid constraints that adapts to the evolving underlying systems, drastically reducing the computation time of similar consecutive instances. We systematize this novel approach by giving a simple and more direct derivation of PC (also extending its original interpretation), and describing an application to a relevant problem in air traffic management.
Article
View An exact (re)optimization framework for real-time traffic management