A Quantum-Classical Benders Decomposition for Cargo Routing with Time Windows

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.