arXiv:2610.00168
Quantum Approximate Multi-Objective Optimization in Routing Problems
Eduardo Willwock Lussi, Alisson dos Passos Fumaco, Marcos Vinicius Reballo, José Carlos Libois Neto, Fernando Augusto Caletti de Barros, Eduardo Inacio Duzzioni
Abstract
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.
AI Summary
The paper asks whether an existing QAOA parameter-transfer strategy for multi-objective MAX-CUT extends to constrained routing problems. It formulates three-objective traveling-salesman (TSP) and vehicle-routing (VRP) instances as QUBOs, reduces them to weighted MAX-CUT, and approximates Pareto fronts by sampling weighted-sum scalarizations. Parameters trained on smaller random graphs are reused without per-scalarization optimization; sampled solutions are filtered for feasibility and dominance. Experiments cover TSP instances with 4–6 customers and VRP instances with 3–5 customers and 1–2 vehicles, requiring 17–43 qubits, with three random seeds. Simulations use matrix-product states with bond dimension $\chi=20$, QAOA depths $p=1$–$6$, and 5,000 scalarizations with 5,000 shots each. Comparisons use an adapted classical $\epsilon$-constraint method and hypervolume. Transfer is more consistent for TSP: for six customers, parameters transferred from 27 qubits reach the highest observed hypervolume at $p=1$ and $p=4$. VRP results vary more strongly; some configurations generate no feasible solutions or fall below the classical baseline. “Maximum” hypervolume means the best observed across tested configurations, not a certified optimum. Timing comparisons assume 10,000 quantum shots per second rather than measured end-to-end execution. The largest VRP lacks a classical comparison because of solver-license limits. IBM hardware tests produce no feasible solutions: transpiled circuits require 11,707 and 31,794 CZ gates, with durations exceeding typical coherence times. Stated limitations include small instances, problem-dependent transferability, and hardware noise; broader benchmarking and improved hardware or circuit implementation are left open.
Central claim may not hold: Neither IBM hardware experiment produced a feasible routing solution, so the positive evidence for effectiveness comes from simulation rather than successful hardware validation. The claimed timing advantages compare measured classical runtime with quantum times inferred from an assumed 10,000 shots/s, a rate exceeding the sequential execution ceilings of the reported hardware-tested circuits. The classical baseline misses the best observed hypervolume in only four of 18 compared instance–seed cases, and the reported maximum hypervolume is not a certified optimum. The VRP penalty λ6(Nk−1)^2 penalizes valid routes serving multiple customers and therefore does not faithfully encode the stated requirement that each vehicle serve at least one customer. The stated MAX-CUT reduction maximizes the supplied routing quadratic form, while the routing QUBOs require minimization, with no necessary sign reversal documented.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.