Quantum Approximate Multi-Objective Optimization in Routing Problems
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.
Related
- Binary Optimization with Complex Constraints via Quantum Approximate Multi-Objective Optimization
- A Bi-Objective Routing Framework for Hybrid Terrestrial-Satellite Quantum Networks
- Depth analysis of the Quantum Approximate Optimization Algorithm with a Grover mixer
- Optimal FALQON for Quantum Approximate Optimization via Layer-wise Parameter Tuning
- The Overlap Gap Property: Separating Quantum and Quantum-Inspired Approximate Optimization Algorithms
BibTeX
@misc{lussi2026quantum,
title = {{Quantum Approximate Multi-Objective Optimization in Routing Problems}},
author = {Eduardo Willwock Lussi and Alisson dos Passos Fumaco and Marcos Vinicius Reballo and José Carlos Libois Neto and Fernando Augusto Caletti de Barros and Eduardo Inacio Duzzioni},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00168},
eprint = {2610.00168},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00168},
}
RIS
TY - UNPB
TI - Quantum Approximate Multi-Objective Optimization in Routing Problems
AU - Eduardo Willwock Lussi
AU - Alisson dos Passos Fumaco
AU - Marcos Vinicius Reballo
AU - José Carlos Libois Neto
AU - Fernando Augusto Caletti de Barros
AU - Eduardo Inacio Duzzioni
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00168
UR - https://arxiv.org/abs/2610.00168
AB - 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.
ER -