Optimization is central to urban mobility, where ride-sharing platforms must continuously match passengers with vehicles under complex constraints such as destination compatibility, cost, route efficiency, and acceptable waiting time. Classical exact methods like integer programming scale poorly as the problem size grows and struggle with highly dynamic inputs such as fluctuating demand, travel times, and vehicle capacities. Quantum computing offers an alternative paradigm: by exploiting superposition and interference, quantum search algorithms can explore large combinatorial spaces more efficiently than classical brute-force search. This study presents a proof-of-concept quantum formulation of a foundational ride-sharing assignment problem and investigates the use of Grover’s search algorithm. The model considers five unique passengers (Mehmet, Aytuğ, Filiz, Alara, and Ayliz) and two vehicles. Each passenger must be assigned to one of the two vehicles, subject to a balanced distribution objective (either a 3–2 or 2–3 split) and individual feasibility constraints. The problem is encoded on a 5-qubit quantum register, where the state of each qubit (|0⟩ or |1⟩) denotes assignment to Vehicle A or Vehicle B, mapping the full 2⁵ = 32-state Hilbert space to all possible allocations. A Grover oracle is designed to “mark” all assignments that satisfy the balanced-split and feasibility conditions by applying a phase flip to those computational basis states. The algorithm is implemented and simulated using IBM’s Qiskit framework. The results show that, after two Grover iterations, the total probability of measuring one of the ten valid “balanced” states increases from 31.25% to over 95%, in line with the expected quadratic speed-up of Grover’s algorithm over classical exhaustive search, which requires O(N) evaluations for N = 32 states. Although intentionally simplified—excluding realistic factors such as travel times, traffic, capacities, and time windows—this work demonstrates that a vehicle-sharing assignment problem can be cast as a quantum search task. Future work will focus on scaling to larger instances, incorporating richer operational constraints, and exploring quantum-classical hybrid approaches for real-world logistics optimization.
Optimization is central to urban mobility, where ride-sharing platforms must continuously match passengers with vehicles under complex constraints such as destination compatibility, cost, route efficiency, and acceptable waiting time. Classical exact methods like integer programming scale poorly as the problem size grows and struggle with highly dynamic inputs such as fluctuating demand, travel times, and vehicle capacities. Quantum computing offers an alternative paradigm: by exploiting superposition and interference, quantum search algorithms can explore large combinatorial spaces more efficiently than classical brute-force search. This study presents a proof-of-concept quantum formulation of a foundational ride-sharing assignment problem and investigates the use of Grover’s search algorithm. The model considers five unique passengers (Mehmet, Aytuğ, Filiz, Alara, and Ayliz) and two vehicles. Each passenger must be assigned to one of the two vehicles, subject to a balanced distribution objective (either a 3–2 or 2–3 split) and individual feasibility constraints. The problem is encoded on a 5-qubit quantum register, where the state of each qubit (|0⟩ or |1⟩) denotes assignment to Vehicle A or Vehicle B, mapping the full 2⁵ = 32-state Hilbert space to all possible allocations. A Grover oracle is designed to “mark” all assignments that satisfy the balanced-split and feasibility conditions by applying a phase flip to those computational basis states. The algorithm is implemented and simulated using IBM’s Qiskit framework. The results show that, after two Grover iterations, the total probability of measuring one of the ten valid “balanced” states increases from 31.25% to over 95%, in line with the expected quadratic speed-up of Grover’s algorithm over classical exhaustive search, which requires O(N) evaluations for N = 32 states. Although intentionally simplified—excluding realistic factors such as travel times, traffic, capacities, and time windows—this work demonstrates that a vehicle-sharing assignment problem can be cast as a quantum search task. Future work will focus on scaling to larger instances, incorporating richer operational constraints, and exploring quantum-classical hybrid approaches for real-world logistics optimization.
Quantum computing (QC) stands at the cusp of revolutionizing computation, yet its near-term potential, constrained by Noisy Intermediate-Scale Quantum (NISQ) devices, remains underexplored. This dissertation investigates how hybrid quantum-classical algorithms can address combinatorial optimization challenges in logistics, focusing on vehicle routing and drone delivery—NP-hard problems with exponential solution spaces that defy classical exhaustive methods. Amidst NISQ limitations like limited qubits and high noise, we confront key challenges: encoding complex constraints, e.g., time windows, battery capacity, into quantum models, balancing quantum and classical components for scalability, and accessing scarce quantum resources. By integrating quantum annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA) with classical heuristics, this work demonstrates QC’s practical utility, advancing both optimization theory and real-world logistics applications. The dissertation unfolds across four core contributions. First, the Hybrid Quantum Tabu Search (HQTS) optimally solves the 50-location Capacitated Vehicle Routing Problem (CVRP), achieving a 4.72% optimality gap. Secondly, we refine HQTS to reach a 2.15% gap with enhanced QA utilization, outperforming prior hybrids on standard datasets. Third, adapting HQTS for the CVRPTWwith D-Wave’s Constrained Quadratic Model solver yields a 3.85% gap on 100-location instances, leveraging a novel heuristic to ensure time-window feasibility where quantum outputs falter. Lastly, QUADRO, a pioneering framework for drone delivery, employs QAOA-driven routing and hybrid scheduling, minimizing transit time and makespan for fleets of 2–11 drones needing fewer than 100 qubits, rivaling classical benchmarks on adapted Augerat datasets. These advances, tested via D-Wave’s Advantage system and Qiskit simulations, showcase hybrid strategies that mitigate NISQ constraints, delivering scalable, feasible solutions to logistics challenges. This work establishes near-term QC’s viability for combinatorial optimization, bridging theoretical promise with practical impact. Synthesizing quantum exploration with classical refinement achieves competitive performance, e.g., matching or surpassing Google ORTools in select CVRPTW cases, while illuminating NISQ limits, such as feasibility degradation beyond small scales. These hybrid strategies deliver scalable, feasible solutions, from a 2.15% optimality gap for CVRP to effective drone fleet management with fewer than 100 qubits, illuminating quantum computing’s potential despite its current constraints. Ultimately, this dissertation positions hybrid QC as a transformative tool for optimization challenges, offering a robust foundation for scaling quantum optimization into operational reality.
The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.
Route determination and optimization is a persistent challenge in transportation networks due to combinatorial explosion of options, dynamically changing conditions, competing optimization criteria, and complexity of real-world systems. Classical algorithms struggle to efficiently solve route optimization at scale due to exponential growth of possibilities, NP-hardness, limitations of dynamic programming approaches, and inability to leverage quantum parallelism. This paper explores the potential application of Grover’s algorithm in optimizing road transportation. Grover’s quantum algorithm offers a potential solution by using an oracle function to recognize optimal routes based on constraints and objectives encoded in a quantum state representing all possible paths. Constructive interference and amplitude amplification drive the system toward optimal solutions. By utilizing Grover’s algorithm, road transportation networks can benefit from improved route planning, traffic management, and resource allocation, ultimately enhancing efficiency and reducing congestion. The transportation network must be efficiently encoded into a quantum representation. An optimization oracle tailored to routing objectives then recognizes optimal solutions, which are amplified via a diffusion operator utilizing interference. Repeated application concentrates amplitude in optimal routes, which can be measured. Key challenges include encoding the network effectively within qubit resource constraints, designing an oracle to evaluate routes based on real-world conditions and optimization criteria, and translating the optimized quantum state into actionable routing guidance. If these challenges can be met, Grover’s algorithm may enable route optimization at a scale intractable for classical techniques.
We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem. The original formulation is a Mixed Integer Linear Program with continuous variables and inequality constraints. To separate inequality constraints that are difficult for quantum routines we use a decomposition in master and pricing problems: the former targets the assignment of vehicles to reservations and the latter suggests vehicle exploitation plans that respect the battery state-of-charge constraints. The master problem is equivalent to the search for an optimal set partition. In our hybrid scheme, the master problem is reformulated in a quadratic unconstrained binary optimization problem which can be solved with quantum annealing on the DWave Advantage system. On large instances, we benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics: simulated annealing, tabu search, and vector annealing by NEC. The numerical results with purely classical solvers are comparable to the solutions from the traditional mixed integer linear programming approaches in terms of solution quality while being faster. In addition, it scales better to larger instances. The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints. We show this by initial studies on DWave hardware where optimal solutions can be found for small instances.
The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.
Intelligent Transportation Systems (ITS) occupy a pivotal position in the contemporary societal landscape, with one of their widespread applications being the vehicle routing problem, renowned for its classification as an NP-hard challenge. Traditional algorithms often require considerable time to address such problems or can only provide approximate solutions. Recent progress in quantum computation, however, offer a promising alternative by utilizing the parallelism inherent in quantum mechanics. In this study, we propose to solve the vehicle routing problem using the Grover adaptive algorithm. Compared to classical algorithms and existing quantum methods, our innovative algorithm achieves a quadratic speedup, with a time complexity ofO(KMN). Additionally, it is applicable to a broader range of real-world scenarios, as it can directly handle linear inequality constraints without introducing slack variables. Notably, the algorithm operates independently of classical optimizers and gradient-based methods, thereby circumventing potential challenges such as the “barren plateaus” phenomenon. Experimental results from four instances demonstrate the feasibility and correctness of the proposed approach, highlighting its capability to handle inequality constraints easily.