Think Global, Act Local - Agent-Based Inline Recovery for Airline Operations

Flight delays can significantly affect airline operations. Airlines use inline recovery actions (e.g., speeding up aircraft cleaning) to mitigate the effect of flight delays. Inline (or tactical) recovery for disruptions mostly relies on human expertise that is locally optimal (e.g., at an airport-level). Because an airline is a complex and stochastic network of dependencies, a locally optimal action may be globally sub-optimal. Considering global effects for inline recovery is computationally challenging with conventional algorithmic approaches for optimization. We complement existing approaches with Stochastic Minplus with State (SMS), a novel agent-based approach for inline recovery. SMS generalizes message passing algorithms for a state-dependent stochastic airline network with resource constraints. We evaluate our approach on a real-world airline network with around 4,000 flights per day for two regimes with 1) normal delays, and 2) interrupted operations. As baselines, we use approaches based on greedy local optimality, integer programming (IP), and constraint programming (CP). Our evaluation shows that: 1) a globally informed SMS improves over greedy locally optimal approach by 24.7% in quality, 2) SMS achieves solutions that are better by 14.1% (10.6%) in quality and 7x (9x) in computation time over IP (CP) with timeout, and 3) SMS achieves solutions within 5% of the optimal solution for simpler problem instances.