This research highlights the potential of quantum annealing in tackling large-scale optimization 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 optimizing fleet assignments in the aviation sector.
This research highlights the potential of quantum annealing in tackling large-scale optimization 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 optimizing fleet assignments in the aviation sector.
Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.
Airline companies struggle every day trying to schedule crew, flights and aircraft.Tail Assignment is the problem of allocating individual aircraft to a set of flights, while ensuring multiple constraints and aiming to minimise an objective function, such as operational costs.Given the enormous amount of possibilities and constraints involved, this problem has been a study case for the last decade.Many solutions have emerged using classical computing, but with limitations regarding performance.Quantum Annealing (QA) is a heuristic technique for finding global minimum energy levels over an energy landscape using quantum mechanics.Due to its characteristics, it has been proved to have a clear advantage in solving some complex optimisation problems, being a promising technique to apply in multiple fields.In this study, Tail Assignment Problem was set as a Quadratic Unconstrained Binary Optimisation (QUBO) model, using two different techniques, and was solved using a classical and two hybrid solvers.Tests were run based on extractions from real-world data, analysing the performance of the implementation in terms of time, scalability and quality (i.e., the lowest operational costs) of the obtained solutions.We concluded that using a library for modelling the problem as well as considering individual flights rather than pre-aggregating them in strings can be a bottleneck when it comes to its scalability.Furthermore, we found out that there was a higher probability of obtaining better solutions for this problem using one of the hybrid solvers when compared with the classical heuristic algorithms such as Simulated Annealing (SA).These findings can serve as foundations for further studies.
Quantum computing is widely discussed for its potential to solve challenging optimization problems much faster. However, real-world airline problem sizes currently exceed the capabilities of existing quantum hardware. Preparing for larger quantum hardware requires developing and benchmarking problem formulations most suitable for quantum implementation. In this study, we use the crew pairing problem from aviation as an use case to benchmark different problem formulations: a set partitioning model and two compact formulations, a constrained flow assignment problem and a satisfiability problem (SAT). For classical benchmarking we solve these formulations using mixed integer programming and SAT solvers. For quantum benchmarking we translate the formulations into quadratic unconstrained binary optimization and Ising formulations. Our benchmarking shows that the problem formulations lead to different classical and quantum properties. Among the formulations considered, the SAT formulation emerges as the most promising candidate for future implementation on quantum hardware with the lowest share of non-zero elements and highest spectral gap, despite its larger ratio of linear term coefficients.
Optimization algorithms for combinatorial problems play a critical role in a wide range of applications, from logistics and scheduling to cryptography and artificial intelligence. Traditional classical methods, such as simulated annealing, genetic algorithms, and branch-and-bound techniques, have been widely employed to solve these problems, but they often face limitations in terms of computational efficiency and scalability as problem complexity grows. In recent years, quantum computing has emerged as a promising alternative, with quantum annealing offering a novel approach to solving combinatorial optimization problems. This study provides a comparative analysis of quantum annealing and classical optimization methods, highlighting their respective strengths and limitations. We explore how quantum annealing, through leveraging quantum tunnelling and superposition, has the potential to outperform classical algorithms in specific problem domains and Noisy Mean Field Annealing (NMFA) is used to comparisons of all algorithms. Benchmarking various combinatorial problems, such as the Traveling Salesman Problem (TSP), Max-Cut, Knapsack, and Quadratic Assignment Problem (QAP), this paper discusses performance metrics, computational time, and scalability. The findings suggest that while classical methods remain robust and practical for many real-world problems, quantum annealing holds significant promise, especially as quantum hardware continues to mature. However, there remain challenges in terms of noise, coherence, and problem mapping, which currently limit the full realization of quantum annealing's potential. This study offers insights into the future directions of optimization techniques and the evolving role of quantum computing in solving complex combinatorial problems.
Airline and space mission scheduling present complex combinatorial optimization challenges, requiring sophisticated coordination of multiple resources under stringent operational constraints. This paper introduces a novel hybrid quantum-classical framework for scheduling optimization, the Quantum Scheduling Optimization Algorithm (QSOA), addressing crew assignment, gate allocation, and trajectory planning through advanced quantum machine learning techniques. We formulate the scheduling problems as stochastic multi-objective optimization and propose three integrated solution approaches: (1) hybrid quantum optimization via QAOA with constraint-aware loss functions and problem decomposition strategies, (2) classical-quantum integration using graph partitioning and variational circuit optimization, and (3) comprehensive baselines including mixed-integer programming, genetic algorithms, and reinforcement learning formulations. For multi-objective handling, we develop Pareto-optimal sampling techniques combining quantum superposition with classical post-processing for constraint repair and solution refinement. Our experimental evaluation on realistic airline crew scheduling benchmarks and space mission simulators demonstrates significant improvements: the hybrid QSOA achieves 19.2\% cost reduction in airline scheduling compared to classical heuristics, while quantum methods provide competitive solutions for moderate-sized space mission subproblems with 15-18\% improvement in multi-objective trade-offs. The framework shows promise for scalable deployment in real-world transportation networks, with practical implications for next-generation scheduling optimization in complex operational environments.
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.