Quantum Approaches to Urban Logistics: From Core QAOA to Clustered Scalability
F. Picariello, G. Turati, R. Antonelli, I. Bailo, S. Bonura, G. Ciarfaglia, S. Cipolla, P. Cremonesi, M. Ferrari Dacrema, M. Gabusi, I. Gentile, V. Morreale, A. Noto
quant-phcs.LGSubmitted Dec 11, 2025• Announced Dec 12, 2025• 0 citations
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.
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.
The Traveling Salesman Problem (TSP) is a cornerstone of combinatorial optimization with widespread applications in logistics and transportation. As problem sizes increase, classical algorithms often fail to deliver high-quality solutions within practical time constraints. This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical algorithm, to address TSP instances under realistic conditions. We present a QUBO-based formulation of the TSP that integrates practical constraints reflecting real-world conditions—such as vehicle capacity, road accessibility, and time windows—while maintaining compatibility with limitations of current quantum hardware. Our analysis is conducted in a simulated environment, leveraging high-performance computing (HPC) resources to evaluate the algorithm’s performance across varying problem sizes and circuit depths. This approach enables a comprehensive assessment of QAOA’s capabilities and limitations in solving constrained TSP scenarios, thereby laying the groundwork for its deployment on future large-scale quantum hardware.
This study explores quantum computing for combinatorial optimization, focusing on the Traveling Salesman Problem (TSP). Using Qiskit, the Quantum Approximate Optimization Algorithm (QAOA) is implemented on simulators and quantum hardware, and compared with classical optimization using Gurobi. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with quadratic penalties enforcing degree and subtour constraints. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound methods achieve better solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, performance degrades with problem size due to sensitivity to parameter tuning, penalty scaling, and hardware noise. Among the tested classical optimizers, COBYLA provides the best balance of efficiency and noise tolerance. Overall, this work establishes a reproducible quantum-classical workflow, provides performance baselines, and identifies critical factors such as encoding design, optimizer choice, and error mitigation for improving near-term quantum heuristic performance.
The Traveling Salesperson Problem (TSP) is a fundamental NP-hard optimisation challenge with widespread applications in logistics, operations research, and network design. While classical algorithms effectively solve small to medium-sized instances, they struggle with scalability due to exponential complexity. In this work, we present a hybrid quantum-classical approach that leverages IBM's Qiskit Runtime to integrate quantum optimisation techniques with classical machine learning methods, specifically K-Means clustering and Random Forest classifiers. These machine learning components aid in problem decomposition and noise mitigation, improving the quality of quantum solutions. Experimental results for TSP instances ranging from 4 to 8 cities reveal that the quantum-only approach produces solutions up to 21.7% worse than the classical baseline, while the hybrid method reduces this cost increase to 11.3% for 8 cities. This demonstrates that hybrid approaches improve solution quality compared to purely quantum methods but remain suboptimal compared to classical solvers. Despite current hardware limitations, these results highlight the potential of quantum-enhanced methods for combinatorial optimisation, paving the way for future advancements in scalable quantum computing frameworks.
The traveling salesman problem (TSP) is one of the most often-used NP-hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also heavily used as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this paper, we tackle the TSP using the quantum approximate optimization algorithm (QAOA) approach by formulating it as an optimization problem. By adopting an improved qubit encoding strategy and a layer-wise learning optimization protocol, we present numerical results obtained from the gate-based digital quantum simulator, specifically targeting TSP instances with 3, 4, and 5 cities. We focus on the evaluations of three distinctive QAOA mixer designs, considering their performances in terms of numerical accuracy and optimization cost. Notably, we find that a well-balanced QAOA mixer design exhibits more promising potential for gate-based simulators and realistic quantum devices in the long run, an observation further supported by our noise model simulations. Furthermore, we investigate the sensitivity of the simulations to the TSP graph. Overall, our simulation results show that the digital quantum simulation of problem-inspired ansatz is a successful candidate for finding optimal TSP solutions.
The Multiple Traveling Salesman Problem (m-TSP) is a well-known combinatorial optimisation problem with diverse applications in various fields, including transportation, logistics, and network design. The m-TSP involves finding the optimal routes for multiple salesmen to visit a set of cities, minimising the total travel distance while ensuring that each city is visited exactly once. Traditional computational approaches struggle to efficiently solve large-scale instances of the m-TSP due to its inherent complexity. In recent years, quantum computing has emerged as a promising field for tackling combinatorial optimisation problems. In this study, we investigate the application of the Quantum Approximate Optimisation Algorithm (QAOA) to solve the m-TSP, leveraging the inherent parallelism and quantum computational power to potentially obtain high-quality solutions.
Multi-objective optimization (MOO) problems are common in logistics, where routing decisions must balance conflicting objectives such as travel distance, delivery time, and operational risk. A recently proposed Quantum Approximate Optimization Algorithm (QAOA) parameter-transfer strategy solves multi-objective MAX-CUT problems by reusing parameters trained on smaller instances, avoiding costly reoptimization for each scalarized problem. However, its effectiveness has only been demonstrated on proof-of-concept instances tailored to quantum hardware connectivity. In this work, we evaluate the applicability of this strategy to realistic routing problems. We formulate the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) as Quadratic Unconstrained Binary Optimization (QUBO) models, reduce them to MAX-CUT, and assess the parameter-transfer framework under conditions matching the original study. Validation is performed through classical simulations and experiments on IBM quantum hardware. The resulting Pareto fronts are compared with those obtained using an adapted classical ε-constraint method, using hypervolume as the primary quality metric. Results indicate that parameter transfer remains effective, frequently achieving higher hypervolume and often finding competitive solutions earlier. However, performance depends on problem structure. The approach is consistently effective for TSP instances but less stable for the more constrained VRP, suggesting that QAOA parameter transferability decreases as the optimization landscape becomes more complex. These results provide the first comprehensive evaluation of QAOA parameter transfer on realistic multi-objective routing problems and demonstrate its potential beyond proof-of-concept MAX-CUT benchmarks.