arXiv:2111.09472

Exploring Airline Gate-Scheduling Optimization Using Quantum Computers

Hamed Mohammadbagherpoor, Patrick Dreher, Mohannad Mahjoub Ali Ibrahim, Young-Hyun Oh, James S. Hall, Richard Stone, Mirela Stojković

Published Nov 18, 2021• 6 citations

arXiv HTML PDF

Abstract

This paper investigates the application of quantum computing technology to airline gate-scheduling quadratic assignment problems (QAP). We explore the quantum computing hardware architecture and software environment required for porting classical versions of these type of problems to quantum computers. We discuss the variational quantum eigensolver and the inclusion of space-efficient graph coloring to the Quadratic Unconstrained Binary Optimization (QUBO). These enhanced quantum computing algorithms are tested with an 8 gate and 24 flight test case using both the IBM quantum computing simulator and a 27 qubit superconducting transmon IBM quantum computing hardware platform.

DOI: 10.48550/arxiv.2111.09472

Related papers

Chapitre 5. L’horizon quantique : les défis et les promesses d’un nouveau monde

Giuliano Benenti, Giulio Casati, Simone Montangero +1 more

This paper investigates the application of quantum computing technology to airline gate-scheduling quadratic assignment problems (QAP).We explore the quantum computing hardware architecture and software environment required for porting classical versions of these type of problems to quantum computers.We discuss the variational quantum eigensolver and the inclusion of space-efficient graph coloring to the Quadratic Unconstrained Binary Optimization (QUBO).These enhanced quantum computing algorithms are tested with an 8 gate and 24 flight test case using both the IBM quantum computing simulator and a 27 qubit superconducting transmon IBM quantum computing hardware platform.

Cairn.infoJan 1, 20260 citations

Quantum Optimization for Airline Itinerary and Scheduling: A QUBO and QAOA Approach

Vaibhav V. Khedekar

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.

Apr 22, 20250 citations

Benchmarking of D-Wave's and IBM's Devices on Known Quantum Solutions to NP-Complete Problems

Junjie Zhu, Filippo Orazi, Sara Marzella +2 more

Quantum computing has the potential to revolutionize the way we solve problems that are computationally infeasible for classical computers. This paper explores the application of quantum computing to NP-complete problems, and by focusing on the Graph Coloring Problem (GCP) we benchmark the performance of two prominent quantum computing devices: D-Wave's quantum annealer and IBM's gatebased quantum processors. After mapping instances of the GCP native formulation, we evaluate the effectiveness and limitations of quantum annealing and gate-based approaches in tackling such combinatorial problems. For annealers, the problem is cast into Quadratic Unconstrained Binary Optimization (QUBO) forms, while gate-based quantum devices employ variational algorithms like the Quantum Approximate Optimization Algorithm (QAOA). The research includes a comparative analysis, highlighting the scalability, accuracy, and practical challenges faced by current quantum hardware.

IEEE International Conference on Quantum Artificial Intelligence (QAI)Nov 2, 20250 citations

Quantum Scheduling Optimization for Airline and Space Missions: A Hybrid Quantum-Classical Approach

Yalla Jnan Devi Satya Prasad, Shaik Fathima Masthan

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.

Oct 6, 20250 citations

Solving the traveling salesman problem via different quantum computing architectures

Venkat Aneesh Padmasola, zhuangbin li, Rupak Chatterjee +1 more

In this paper, we study the application of emerging photonic and quantum computing architectures to solving the Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem. We investigate several approaches: Simulated Annealing (SA), Quadratic Unconstrained Binary Optimization (QUBO-Ising) methods implemented on quantum annealers and Optical Coherent Ising Machines, as well as the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Phase Estimation (QPE) algorithm on gate-based quantum computers. QAOA and QPE were tested on the IBM Quantum platform. The QUBO-Ising method was explored using the D-wave quantum annealer, which operates on superconducting Josephson junctions, and the Quantum Computing Inc (QCi) Dirac-1 entropy quantum optimization machine. Gate-based quantum computers demonstrated accurate results for small TSP instances in simulation. However, real quantum devices are hindered by noise and limited scalability. Circuit complexity grows with problem size, restricting performance to TSP instances with a maximum of six nodes. In contrast, Ising-based architectures show improved scalability for larger problem sizes. SQUID-based Ising machines can handle TSP instances with up to 12 nodes, while entropy computing implemented in hybrid optoelectronic components extend this capability to 18 nodes. Nevertheless, the solutions tend to be suboptimal due to hardware limitations and challenges in achieving ground state convergence as the problem size increases. Despite these limitations, Ising machines demonstrate significant time advantages over classical methods, making them a promising candidate for solving larger-scale TSPs efficiently.

arXiv:2502.17725International Journal of Quantum InformationOct 11, 20257 citations

Solving the Job Shop Scheduling Problem: QUBO model and Quantum Annealing

Riad Aggoune, Samuel Deleplanque

Quantum optimization which is the use of quantum computers and algorithms for solving complex optimization problems, is one of the topics in quantum computing with the highest potential. Two types of approaches are generally used to solve combinatorial optimization problems with quantum computers: exact methods such as the Grover’s search algorithm, and meta-heuristics such as the Quantum Annealing and the Quantum Approximate Optimization Algorithm (QAOA). Exact methods and variational methods like QAOA make use of universal gate-based quantum computers, such as the ones developed by the IBM company.Quantum annealing is designed for analogic quantum computers developed by D-Wave. Solving a combinatorial optimization problem with heuristics generally requires a transformation of the problem to a format suitable for the quantum computer. While some existing frameworks can cope with Constrained Quadratic Models (CQM), Quadratic Unconstrained Binary Optimization (QUBO) is the best option to map an optimization problem to a quantum computer or simulator. We consider in this paper the job shop scheduling problem.

Apr 17, 20230 citations