Annealing Techniques Offer Gains for Complex Airline Scheduling Problems
Summarize this article with:
Scientists are increasingly focused on optimising complex logistical challenges, and airline fleet assignment represents a particularly demanding example of such a problem. Kuntal Adak, Sakshi Kaushik, and Rahul Rana, all from Tata Consultancy Services, present a comparative study of classical binary and integer programming models against quantum annealing techniques for solving this critical task. Their collaborative research rigorously assesses the performance of both approaches, revealing the potential benefits of quantum annealing for specific problem scales while acknowledging existing technological constraints. This work is significant because it contributes valuable insights into the viability of quantum computing for real-world airline operations, potentially leading to substantial improvements in efficiency and cost reduction within the aviation sector. The demand on each flight is considered while adhering to a set of operational constraints. This study explores two distinct mathematical formulations of the Flight Assignment Problem (FAP): a Binary Linear Programming (BLP) model and an Integer Linear Programming (ILP) model. These models are addressed using both SCIP (Solving Constraint Integer Programs) and Quantum Annealers to assess their efficacy in solving this complex problem. The integer model incorporates aircraft balance constraint to track the number of aircraft at a particular location at the end of the day to reuse them. Exponential search space growth and cost optimisation in fleet assignment modelling Initial results demonstrate a clear relationship between problem size and computational efficiency when applying quantum annealing and SCIP solvers to the fleet assignment problem. Specifically, the study establishes that the search space for multi-day fleet type assignment grows exponentially, represented as O ηM, where η signifies the number of fleet types and M denotes the total number of flights across all days. This formulation underscores the inherent intractability of the problem as either the fleet size or flight volume increases. Analysis of the Binary Linear Programming (BLP) model revealed that the objective function minimizes operational cost, incorporating both aircraft capacity and flight demand, alongside a penalty term λ applied to capacity violations. The penalty term, λ, a real positive number, accounts for the difference between aircraft capacity and flight demand, influencing the trade-off between cost and fulfilling passenger needs. Constraints were implemented to ensure each flight receives exactly one fleet type, represented by the equation Xj∈K xijd = 1 for all flights i on day d, and that fleet assignments do not exceed available aircraft, expressed as X i∈Fd xijd ≤Nj for each fleet type j and day d. Further investigation into the ILP model for single-day fleet assignment introduced additional parameters defining airport nodes and flight arrival/departure status, denoted by aik and bik respectively. The decision variable Gkj, representing the number of aircraft of fleet type j grounded at node k, was incorporated as a non-negative integer, adding a layer of complexity to the optimisation process. The formulation of both BLP and ILP models provides a robust framework for tackling the fleet assignment problem, allowing for detailed analysis of operational costs and resource allocation. Comparative performance of quantum annealing and SCIP solvers for airline fleet assignment optimisation Scientists have long sought to efficiently manage aircraft fleets. We demonstrated the application of a model through a set of problem instances generated based on data from an Australian airline, highlighting the benefits of effective fleet assignment in improving fleet utilisation, reducing costs, and enhancing overall operational efficiency. Our experiments reveal that for the Binary Linear Programming (BLP) model, quantum annealers and SCIP provide identical optimal solutions for smaller instances of the problem. However, as the problem size increases, quantum annealers consistently deliver near-optimal solutions with reduced computational time compared to SCIP. In contrast, for the Integer Linear Programming (ILP) model, quantum annealers achieve optimal solutions for smaller instances but struggle to find feasible solutions for larger ones. SCIP, on the other hand, remains effective in managing larger instances, though with increased computational effort. Additionally, we discuss the scalability of the solution approach and its relevance to real-time airline scheduling systems.
This research highlights the potential of quantum annealing in tackling large-scale optimisation problems within the airline industry, demonstrating its efficiency for certain problem sizes while also acknowledging its current limitations. The comparative analysis provides valuable insights into the performance of advanced computational techniques, paving the way for further advancements in optimising fleet assignments in the aviation sector. Airline scheduling is a complex and multifaceted problem involving the optimisation of various interconnected components that include flight scheduling, fleet assignment, crew scheduling, aircraft routing, and maintenance scheduling. The fleet assignment problem (FAP) is a critical component of airline operations and plays an important role in the broader context of airline scheduling. It involves determining the optimal assignment of various aircraft types from an airline’s fleet to a set of scheduled flights, with the goal of balancing capacity with demand and minimising costs. The various models are evaluated based on their applicability to real-world problems in a short-term operational context, while also considering related issues such as maintenance planning and crew assignment.
Applying Integer Linear Programming to the Fleet Assignment Problem formulated and solved the fleet assignment problem as an integer linear programming model, permitting assignment of two or more fleets to a flight schedule simultaneously. Airline fleet assignment concepts, models, and algorithms offer a comprehensive tutorial on the foundational and advanced models and Methods developed for the Fleet Assignment Problem (FAP), including its integration with other airline decision-making processes.
Robust Airline Fleet Assignment: Station Purity Enforcement Using Station Decomposition offers a strong solution by restricting the number of fleet types permitted to operate at each airport in the schedule. Advances in the Optimisation of Airline Fleet Assignment model the problem as mixed-integer multicommodity flow on networks encoding activities linking flight departures which permits a profitability-based tradeoff between operational goals and revenue. Mathematical models in airline schedule planning: A survey survey these various models and solution techniques in the recent past for almost all of the problems related to fleet assignment.
Applying Quantum Annealing to the Tail Assignment Problem where the problem is formulated as a Quadratic Unconstrained Binary Optimisation (QUBO) model, approached using various techniques, and solved with both a classical solver and two hybrid solvers. Applying the Quantum Approximate Optimisation Algorithm to the Tail-Assignment Problem simulate the quantum approximate optimisation algorithm (QAOA) applied to instances of this problem derived from real-world data. The fleet assignment problem is expressed as an optimisation model, utilising both a Binary Linear Programming (BLP) model and an Integer Linear Programming (ILP) model, incorporating the following key components. A. BLP Model for Multi-Day Fleet Type Assignment: Parameters include Qj, the capacity of fleet type j; Did, the demand or forecasted seats for flight i on day d; Cijd, the operational Cost for flight i corresponding to fleet j on day d; Nj, the maximum number of available aircraft of type j; D, the set of days; Fd, the set of flights at day d; and K, the set of fleet types. The decision variable is xijd = 1 if fleet type j is assigned to flight i on day d, and 0 otherwise. The objective function is to minimise the operational cost, accounting for each aircraft’s capacity and the demand on each flight, while adhering to a set of operational constraints, expressed as: min X d∈D,i∈Fd,j∈K Cijdxijd + λd Σi∈Fd (Di, Σj∈K Qj xijd). The search space for each day is ηκd, where η is the number of fleet types and κd = |Fd| is the number of flights on day d. For D days, the overall search space size is the product of the search spaces for each individual day. Therefore, the total size of the search space can be represented as: Y d∈D ηκd = η P d∈D κd ≈O ηM, where M = X d∈D κd. Thus, the search space for the Fleet Type Assignment Problem (FTAP) in a multi-day operation scenario can be succinctly represented as O ηM, where η is the number of fleet types and M is the total number of flights across all days. This highlights the exponential growth in complexity as either the number of aircraft types or the total number of flights increases, which makes this problem intractable in nature. The actual feasible search space may be smaller due to constraints, but the upper bound of the search space remains O ηM. Classical solvers such as SCIP will find it challenging to address complex problems like the FTAP within polynomial time, as the search space expands exponentially with the size of the problem. B. ILP model for Single-Day Fleet Type Assignment Parameters include Qj, the capacity of fleet type j; Di, the demand or forecasted seats for flight i; Cij, the Operational Cost for flight i corresponding to fleet type j; Nj, the maximum number of available aircraft of type j; F, the set of flights; K, the set of fleets; and M, the set.
The Bigger Picture Scientists have long recognised the potential of optimisation algorithms to reshape complex logistical challenges, yet translating theoretical gains into real-world improvements has proven stubbornly difficult. This latest work on fleet assignment, utilising annealing techniques, represents a cautious but significant step forward. For decades, airlines have grappled with the seemingly intractable problem of matching aircraft to routes, balancing capacity with demand and minimising costs. The sheer scale of these operations, hundreds of aircraft, thousands of routes, and constantly shifting passenger numbers, has resisted simple solutions. The value here isn’t necessarily a dramatic leap in performance for all problem sizes, but rather a demonstration of scalability and robustness for very large instances. 👉 More information 🗞 Airline Fleet Assignment Problems with Binary and Integer Programming models: Classical vs Quantum Annealing 🧠 ArXiv: https://arxiv.org/abs/2602.12840 Tags: