The logistics industry is widely regarded as a promising application domain for emerging optimization paradigms, including quantum computing. The Rider-Order Assignment problem is a practically motivated optimization problem arising in online food delivery and related logistics applications. While the problem is closely related to the classical matching problem, the inclusion of realistic operational constraints renders it computationally challenging. In this work, we formulate the Rider-Order Assignment problem as a constrained binary optimization problem and perform a comparative analysis of classical, quantum-inspired, and gate-based quantum solvers for this problem across multiple instance sizes. Solver performance is assessed using solution quality, computational runtime, and constraint satisfaction, with a consistent post-processing procedure applied to ensure feasibility.
Comments
Accepted to QC4C3 workshop at QCNC 2026, 7 pages, 7 figures
The logistics industry is widely regarded as a promising application domain for emerging optimization paradigms, including quantum computing. The Rider-Order Assignment problem is a practically motivated optimization problem arising in online food delivery and related logistics applications. While the problem is closely related to the classical matching problem, the inclusion of realistic operational constraints renders it computationally challenging. In this work, we formulate the Rider-Order Assignment problem as a constrained binary optimization problem and perform a comparative analysis of classical, quantum-inspired, and gate-based quantum solvers for this problem across multiple instance sizes. Solver performance is assessed using solution quality, computational runtime, and constraint satisfaction, with a consistent post-processing procedure applied to ensure feasibility.
The increasing complexity of industrial scheduling and transport routing problems motivates the study of alternative optimization formulations and computational paradigms. In this work, we study how higher-order unconstrained binary optimization (HUBO) formulations of such problems map onto quantum optimization workflows in both noisy and fault-tolerant regimes. We consider three representative logistics and manufacturing use cases and formulate each as a HUBO problem. This captures process intricacies, such as highly correlated assembly-line scheduling rules, which are difficult to express faithfully with the standard quadratic (QUBO) form, while at the same time reducing the number of binary variables required in the quantum mapping, thus lowering qubit demand. We compare the HUBO formulations with corresponding QUBO encodings, highlighting a key trade-off: while HUBO reduces qubit requirements through compact binary encoding, it introduces higher-order interaction terms that increase circuit depth, limiting feasibility on current quantum hardware. The proposed formulations are validated using classical solvers across several problem instances and benchmark small routing problem instances using bias-field digitized counterdiabatic quantum optimization in classical simulation. We complement these results with a resource and scalability analysis, focusing on the capacitated vehicle routing problem as a representative large-scale industrial use case. Our analysis indicates that while HUBO formulations offer advantages in qubit scaling compared to QUBO encodings, their practical implementation is constrained by gate fidelity, coherence, and circuit depth, making hybrid quantum-classical workflows and early fault-tolerant quantum hardware the most plausible settings for their practical use.
Abstract As interest in quantum and related optimization paradigms continues to grow, fairly and systematically comparing their performance across practical problem settings remains challenging. This challenge arises because these approaches often target different problem classes, use different mathematical representations, and are affected differently by modeling choices. As a result, observed performance depends not only on the solver itself, but also on how a problem is formulated, reformulated, and translated into a solver-specific input language. This work presents a publicly available and extensible benchmarking framework that unifies advances in quantum, quantum-hybrid, quantum-inspired, and classical optimization by enabling consistent comparison across use cases, solvers, and models. We address the diversity of solver “languages”—from mixed-integer programming (MIP) formulations for branch-and-bound methods over quadratic unconstrained binary optimization (QUBO) models for quantum annealers to constrained quadratic models (CQM) for hybrid approaches — as well as the influence of modeling choices, such as binary encodings and penalty formulations, on both performance and solution fidelity. By supporting systematic variation across the three dimensions of use case, solver, and model, the framework reveals trade-offs that single-dimension benchmarks overlook, clarifies when native formulations are preferable, and enables rigorous evaluation of practical combinatorial optimization problems. The two case studies, vehicle routing and maximum cut, illustrate this principle: their contrasting outcomes show that the effectiveness of a solver depends strongly on how well the chosen model representation matches the solver backend and the use case.
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.
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.
Recent advances in quantum computing and the increasing availability of quantum hardware have substantially enhanced the practical relevance of quantum approaches to discrete optimization. Among these, the Quadratic Unconstrained Binary Optimization (QUBO) formulation provides a unifying modeling framework for a broad class of NP-hard problems and is naturally suited to quantum computing and quantum-inspired algorithms. Location science, network design, and logistics represent core application domains of discrete optimization, combining high practical impact with substantial computational challenges. In this work, we develop QUBO formulations for several fundamental problems in these domains, including a nonlinear integer formulation of the Discrete Ordered Median Problem (DOMP). Beyond their modeling relevance, these QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware. We further derive a tight bound for the penalty parameter ensuring equivalence between the QUBO formulation and its underlying integer program. Finally, we conduct a comprehensive computational study using QAOA, WS-QAOA, and classical heuristics for QUBO instances of the p-Median Problem and the Fixed-Charge Facility Location Problem (FCFLP), and introduce two effective warm-start strategies for WS-QAOA based on its linear programming relaxation.
This study explores quantum-inspired optimization algorithms (QIOAs) as practical tools for solving constrained combinatorial problems on classical machines. We analyze tasks that can be formulated in Ising or QUBO forms and benchmark three representative approaches: Simulated Bifurcation (SB), Quantum-Inspired Particle Swarm Optimization (QPSO), and a tensor-network (TN) method. A unified evaluation protocol is introduced that captures solution quality, feasibility, runtime, energy consumption, parameter sensitivity, and scalability. To ensure reliable performance, we develop automated penalty-adjustment and schedule-calibration strategies. Experimental results across diverse benchmarks show that SB and TN together yield the best trade-offs between accuracy and runtime: SB is efficient on dense instances with moderate penalties and low energy use, while TN is advantageous for sparse or modular networks, especially on GPUs. QPSO is competitive in smoother landscapes but more sensitive to hyperparameters. By linking performance to structural properties such as spectral gaps and constraint activity, we provide guidance for selecting suitable algorithms. Overall, QIOAs emerge as effective intermediaries between existing classical heuristics and emerging quantum devices, supported by a reproducible, energy-aware evaluation framework.
Maruthu Pandi
Surya Prakash Palanivel
Tharrmashastha SAPV