A transportation-grounded constraint-aware Quantum Alternating Operator Ansatz (QAOA+) framework that embeds feasibility-preserving logic directly into the search operator, and shows that constraint-handling architecture strongly influences feasible-route sampling, convergence behavior, and probability concentration over low-cost feasible routes.
Abstract
Transportation routing problems such as the Traveling Salesperson Problem (TSP) and the Vehicle Routing Problem (VRP) are characterized by strict feasibility requirements involving customer assignment and visit rules, route sequencing, and depot-return logic alongside cost minimization. Most quantum routing formulations adopt Quadratic Unconstrained Binary Optimization (QUBO) encodings, where feasibility is incorporated indirectly via penalty terms in the cost Hamiltonian. While convenient for standard implementations of the Quantum Approximate Optimization Algorithm (QAOA), QUBO encodings allow the quantum search dynamics to allocate substantial probability to infeasible route configurations. This study develops a transportation-grounded constraint-aware Quantum Alternating Operator Ansatz (QAOA+) framework that embeds feasibility-preserving logic directly into the search operator. We introduce a custom mixer that functions as a quantum analogue of feasibility-preserving routing neighborhoods, using column-wise swap moves, it restricts evolution to feasible configurations while enabling structured exploration of valid routes. We compare three constraint-handling architectures: penalty-based QUBO QAOA, penalty free QAOA+ with the feasibility-preserving mixer, and a Hybrid QAOA+ combining mixer based feasibility with and penalty guidance. Results on small TSP and VRP instances show that constraint-handling architecture strongly influences feasible-route sampling, convergence behavior, and probability concentration over low-cost feasible routes. These findings position constraint-aware quantum search as a methodological extension of transportation routing search approaches, where feasibility is enforced through admissible quantum transitions rather than post-hoc penalties.
The warehouse layout problem (WLP), also known as warehouse slotting problem, aims to determine the assignment of products to storage locations while minimizing the total travel distance for picking operations. It is combinatorial in nature and well-known to be NP-hard. To obtain high-quality solutions to medium and large WLP instances efficiently remains a computational challenge, which has motivated our work on applying quantum optimization algorithms for this problem. We reformulate the classical quadratic assignment programming (QAP) model of the WLP to a quadratic unconstrained binary optimization (QUBO) model. Our QUBO model avoids adding slack variables and reduces additional overheads as in the typical QUBO reformulation approach, which facilitates the application of the D-Wave Leap Hybrid solver. Computational study is performed on a use case with 30 stock-keeping-units (SKUs) and 32 storage slots, for which the QUBO formulation has 960 binary decision variables. We show that the D-Wave Leap Hybrid solver finds better solution to the base scenario than the exact IBM CPLEX mixed-integer quadratic programming (MIQP) solver operating under a 60-second wall-clock limit, one-tenth of the 600-second budget allocated to CPLEX in this experimental design. A sensitivity analysis across 30 scenarios, generated by crossing five annual pick volume profiles with six co-picking matrix density levels (0.5 to 1.0), shows that the D-Wave hybrid solver outperforms CPLEX MIQP solver in 26 of 30 cases, with solution quality improvements of 0.4 to 12.1%. D-Wave’s advantage generally increases as the density of co-picking matrix decreases. These results demonstrate quantum utility for WLP and motivate further investigation of hybrid quantum-classical methods for combinatorial logistics optimization at industrial strength scales.
Optimization of vehicle-to-station assignments under capacity and distance constraints represents a challenging combinatorial problem relevant to automated planning, logistics, and autonomous mobility systems. Classical methods such as Mixed Integer Linear Programming (MILP) or metaheuristics often struggle to scale efficiently with problem dimensionality, motivating the exploration of hybrid quantum-classical paradigms. This paper presents a normalized Quantum Approximate Optimization Algorithm (QAOA) framework tailored for constrained assignment problems, where vehicle-station distances are encoded into a normalized cost Hamiltonian. Capacity violations and unused resources are incorporated through dynamically scaled penalty terms, producing a cost landscape that effectively guides the quantum search process. The proposed pipeline integrates parameter optimization using COBYLA to refine the QAOA angles, ensuring convergence toward low-cost feasible configurations. Experimental simulations in Cirq on a 10-qubit system demonstrate that the normalized QAOA pipeline consistently identifies near-optimal assignments while substantially reducing the combinatorial search space. These results provide empirical evidence for the viability of hybrid QAOA formulations in real-world planning and scheduling scenarios, establishing a foundation for future implementations on noisy intermediatescale quantum (NISQ) hardware.
Jakub Kołota· International Conference on...· 0 citations
This paper presents a comprehensive investigation of quantum annealing and hybrid quantum-classical algorithms applied to unit load device (ULD) configuration and disruption management in air cargo and multimodal logistics networks, and provides a practical roadmap for near-term adoption of quantum technologies in high-stakes logistics environments.
V. Sharma· International Journal of Cre...· 0 citations
The results suggest that quantum kernels may serve as complementary routing-aware decomposition modules within classical optimization pipelines, particularly for offline structural preprocessing.
We introduce the Vehicle Routing Problem with Resource-Constrained Pickup and Delivery (VRP-RPD), where agents deploy finite identical resources at customer locations for processing before retrieval and redeployment. Applications include portable medical equipment, tool rental, and disaster relief. Unlike classical pickup-and-delivery variants, VRP-RPD permits different agents to perform dropoff and pickup for the same customer—creating inter-route dependencies absent from standard formulations. We provide a complete mixed-integer linear programming formulation and demonstrate that exact methods are intractable even for small instances. Problems with 16 customers cannot be solved to optimality within two hours of computational time. We develop a Biased Random-Key Genetic Algorithm (BRKGA) with a four-gene-per-customer encoding. Two genes assign dropoff and pickup agents independently, while two priority keys determine sequencing. A simulation decoder guarantees feasibility by deferring operations until resources become available. Experiments on 14 TSPlib-derived benchmarks across five variants of processing time (base, 2X, 5X, 1R10, 1R20) compare four configurations. Warm-start BRKGA achieves 13–67% makespan reduction over the heuristics, with larger gains on higher-resource instances. Ablation tests show warm-start initialization is the primary driver of performance. Friedman tests (p < 0.01) confirm warm-start BRKGA superiority across all instance variants.
M. Sodhi, Romesh Prasad· Annual Conference on Genetic...· 0 citations
This work presents Collaborative Routing Constructors (CoRC), a routing framework that enables independently solved subproblems to exchange customers and vehicles during optimization rather than relying solely on a fixed partition or a subsequent global re-optimization stage.
