A Quantum-Classical Benders Decomposition for Cargo Routing with Time Windows
- 1Fraunhofer Center for Maritime Logistics and Services CML, Blohmstraße 32, 21079 Hamburg, Germany
Abstract
Quantum Annealing (QA) presents a promising approach for large-scale combinatorial optimization, though its adoption in the shipping industry remains limited. This study considers a Traveling Salesperson Problem with Time Windows and Earliness Penalties (TSPTW-EP) motivated by a break-bulk cargo-routing use case. A vessel must determine a port-visitation sequence while minimizing sailing and early-delivery storage costs and satisfying arrival-time windows. Direct Quadratic Unconstrained Binary Optimization (QUBO) formulations are limited in size by the hardware constraints of existing annealers and may suffer from rugged energy landscapes arising when encoding the continuous time variables in binary variables. Therefore, a hybrid Benders decomposition approach is proposed. The master problem, selecting port visitation sequences, is formulated as a QUBO and explored on a quantum annealer, while the classical subproblem determines arrival times and produces Benders cuts. Benchmark experiments compare different quantum and classical master solvers within the hybrid scheme on realistic maritime instances, assessing solution quality, runtime, and scalability. Results show that on the considered model, the hybrid pipeline struggles with the feasibility of QUBO solutions, especially due to the need for embeddings onto the QPU hardware. However, they also suggest that hybrid Benders terminates in fewer iterations than the classical Benders decomposition, at the cost of an uncertified stopping criterion and lower solution quality. The study aims to quantify the practical benefits and limits of QA-enabled logistics optimization.
Related
- A Spatial Benders Algorithm for Delay Constrained Routing
- Accelerated Benders decomposition for bi-objective mixed integer programming
- A Benders decomposition approach for hierarchical k-medoids
- A Combinatorial Benders Decomposition Framework for Two-Dimensional Irregular Bin Packing Problems with Convex Polygons
- Venusian Radio Occultation Constellation Design and Reconfiguration Problems: A Benders Decomposition Approach
BibTeX
@article{szal2026quantumclassical,
title = {{A Quantum-Classical Benders Decomposition for Cargo Routing with Time Windows}},
author = {Oliver Szal and Joshua Dibbern and Henri Hiep and Jachin Tekle Gemta and Anisa Rizvanolli},
journal = {Mathematics},
year = {2026},
month = nov,
doi = {10.3390/math14214031},
url = {https://www.mdpi.com/2227-7390/14/21/4031},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - A Quantum-Classical Benders Decomposition for Cargo Routing with Time Windows
AU - Oliver Szal
AU - Joshua Dibbern
AU - Henri Hiep
AU - Jachin Tekle Gemta
AU - Anisa Rizvanolli
PY - 2026
DA - 2026/11/04
JO - Mathematics
DO - 10.3390/math14214031
UR - https://www.mdpi.com/2227-7390/14/21/4031
AB - Quantum Annealing (QA) presents a promising approach for large-scale combinatorial optimization, though its adoption in the shipping industry remains limited. This study considers a Traveling Salesperson Problem with Time Windows and Earliness Penalties (TSPTW-EP) motivated by a break-bulk cargo-routing use case. A vessel must determine a port-visitation sequence while minimizing sailing and early-delivery storage costs and satisfying arrival-time windows. Direct Quadratic Unconstrained Binary Optimization (QUBO) formulations are limited in size by the hardware constraints of existing annealers and may suffer from rugged energy landscapes arising when encoding the continuous time variables in binary variables. Therefore, a hybrid Benders decomposition approach is proposed. The master problem, selecting port visitation sequences, is formulated as a QUBO and explored on a quantum annealer, while the classical subproblem determines arrival times and produces Benders cuts. Benchmark experiments compare different quantum and classical master solvers within the hybrid scheme on realistic maritime instances, assessing solution quality, runtime, and scalability. Results show that on the considered model, the hybrid pipeline struggles with the feasibility of QUBO solutions, especially due to the need for embeddings onto the QPU hardware. However, they also suggest that hybrid Benders terminates in fewer iterations than the classical Benders decomposition, at the cost of an uncertified stopping criterion and lower solution quality. The study aims to quantify the practical benefits and limits of QA-enabled logistics optimization.
SN - 2227-7390
ER -