Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

From MINLP to QUBO: A Quantum-Inspired Approach for Bulk Carrier Routing with Time Windows

Joshua Aaron Heinrich Dibbern, Oliver Szal, Anisa Rizvanolli

Published Sep 22, 2025• 0 citations
OpenAlex

Abstract

Emerging optimization paradigms like Quantum Annealing (QA) offer potential for tackling large-scale combinatorial problems, yet applications in the shipping industry remain scarce. This paper addresses the cargo routing problem for bulk carriers, where fuel consumption depends nonlinearly on vessel speed and strict time windows must be respected. We formulate the problem as a Mixed-Integer Nonlinear Program (MINLP) and derive a tractable model through velocity discretization, yielding a Travelling Salesman Problem with Time Windows (TSPTW). A Quadratic Unconstrained Binary Optimization (QUBO) model enables exploration with QA, and performance is evaluated using classical solvers and Simulated Annealing (SA).

Related papers

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

Oliver Szal, Joshua Dibbern, Henri Hiep +2 more

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.

Mathematics•Nov 4, 2026•0 citations

QUBO Formulation of the Pickup and Delivery Problem with Time Windows for Quantum Annealing

Cosmin Ștefan Curuliuc, Florin Leon

This paper addresses the Pickup and Delivery Problem with Time Windows (PDPTW), an NP-hard combinatorial optimization problem with major practical relevance in logistics and transportation. The study focuses on a quadratic unconstrained binary optimization (QUBO) formulation for quantum annealing and benchmarks it against two classical optimization paradigms. A modular Python framework is developed that encodes PDPTW in three ways: a mixed-integer linear programming (MILP) model that serves as an exact reference, a genetic algorithm (GA) metaheuristic, and a QUBO model that is compatible with quantum annealers. The framework supports test scenarios with increasing structural complexity, with both feasible and intentionally infeasible instances. An additional contribution is the conceptual design and preliminary analysis of an automatic-penalty weight-tuning scheme for the QUBO model. Experimental results show that the proposed QUBO formulation can produce high-quality solutions for simpler PDPTW instances, but its performance strongly depends on the careful calibration of penalty weights. MILP provides optimal baselines on small instances but becomes intractable as problem size grows. The GA scales to the largest scenario and finds feasible solutions of reasonable quality, but they are not necessarily optimal. The evaluation also includes a large number of problem instances and runs on IBM Quantum hardware using the Quantum Approximate Optimization Algorithm (QAOA).

Applied Sciences•Feb 8, 2026•1 citation

ILP-Based QUBO Encodings of the Traveling Salesman Problem: Derivation and Benchmarking on Quantum Annealing Hardware

Katarzyna Nałęcz-Charkiewicz

The Traveling Salesman Problem (TSP) has been one of the most intensively studied problems in theoretical computer science for decades. Being NP-hard, it is unlikely to be solved in polynomial time; hence, despite numerous classical exact and approximate methods, quantum-inspired approaches are also explored. In this study, we analyze several formulations of the TSP suitable for quantum annealing, focusing not only on qubit requirements but also on practical performance, i.e., how frequently feasible and optimal solutions are obtained. We consider both complete and non-complete graphs, reflecting common real-world scenarios. One of the analyzed formulations corresponds to a previously established Quadratic Unconstrained Binary Optimization (QUBO) model, while the others originate from classical Integer Linear Programming (ILP) formulations. We provide a unified, step-by-step translation of selected compact ILP TSP formulations into QUBO models. We analytically show that for non-complete graphs these encodings are asymptotically smaller than the commonly used baseline formulation. We benchmark the formulations using simulated and quantum annealing to evaluate their feasibility and optimality rates. The results are discussed in the context of current quantum annealing hardware limitations, including QPU size and embedding overhead.

International Journal of Electronics and Telecommunications•Oct 29, 2026•0 citations

Quantum-enhanced Optimization for LNG Ship Routing: Integrating Digital Twins with QAOA

Elif Ak, Dang Van Huynh, Trung Q. Duong

Liquefied natural gas (LNG) shipping poses unique optimization challenges in global logistics due to strict operational constraints, dynamic environmental conditions, and the need to minimize both costs and delays. This study explores the integration of quantum optimization and digital twin technology to address the complexities of LNG ship routing. Specifically, we formulate the ship routing problem as a mixed-integer linear programming (MILP) problem aimed at minimizing costs and travel time while incorporating constraints such as ship capacities and weather variability. Given the NP-hard nature of the problem, classical optimization methods struggle to scale efficiently. To overcome this, we transform the MILP into a quadratic unconstrained binary optimization (QUBO) format and employ the quantum approximate optimization algorithm (QAOA) to solve it. The proposed framework integrates real-time data via digital twins, enabling dynamic updates to the optimization process.

IEEE International Conference on Communications workshops•Jun 8, 2025•0 citations

Potential Energy Savings from Quantum Computing-Based Route Optimization

Ayush Nadiger, Adriana Caraeni, Katie Schouten

We investigate the potential of the Quantum Approximate Optimization Algorithm (QAOA) for reducing energy consumption in route planning, a key challenge in logistics due to the NP-hard nature of the Traveling Salesman and Vehicle Routing Problems. By encoding route optimization as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implementing QAOA circuits at depth p = 3-5 alongside classical baselines of Simulated Annealing (SA) and Genetic Algorithms (GA), we perform systematic benchmarks on Euclidean graphs of sizes N = 5, 10, and 20. Our results demonstrate that QAOA attains higher solution quality with approximation ratios of 0.953 (N = 5), 0.921 (N = 10), and 0.903 (N = 20), outperforming SA and GA by 2.7-4.4%. Wall-clock runtimes for QAOA are 2-3x faster than SA across all tested sizes, and energy consumption measurements reveal a three-order-of-magnitude reduction, remaining in the picojoule range versus nanojoules for classical methods. Translating these gains to real-world logistics suggests an 8.2% improvement in routing efficiency could save approximately 2.62 EJ of fuel annually in the U.S., avoiding nearly 1.94 x 10^8 tonnes of CO2 emissions. These findings highlight QAOA's promise as a fast, energy-efficient optimizer for sustainable logistics applications and underscore its potential role in next-generation fleet-management systems.

arXiv:2604.16718•Apr 17, 2026•0 citations

Unconstrained binary models of the travelling salesman problem variants for quantum optimization

Özlem Salehi, Adam Glos, Jarosław Adam Miszczak

Abstract Quantum computing is offering a novel perspective for solving combinatorial optimization problems. To fully explore the possibilities offered by quantum computers, the problems need to be formulated as unconstrained binary models, taking into account limitation and advantages of quantum devices. In this work, we provide a detailed analysis of the travelling salesman problem with time windows (TSPTW) in the context of solving it on a quantum computer. We introduce quadratic unconstrained binary optimization and higher-order binary optimization formulations of this problem. We demonstrate the advantages of edge-based and node-based formulations of the TSPTW problem. Additionally, we investigate the experimental realization of the presented methods on a quantum annealing device. The provided results pave the path for utilizing quantum computer for a variety of real-world tasks which can be cast in the form of travelling salesman problem with time windows.

arXiv:2106.09056•Quantum Information Processing•Jan 22, 2022•78 citations
Emerging optimization paradigms like Quantum Annealing (QA) offer potential for tackling large-scale combinatorial problems, yet applications in the shipping industry remain scarce. This paper addresses the cargo routing problem for bulk carriers, where fuel consumption depends nonlinearly on vessel speed and strict time windows must be respected. We formulate the problem as a Mixed-Integer Nonlinear Program (MINLP) and derive a tractable model through velocity discretization, yielding a Travelling Salesman Problem with Time Windows (TSPTW). A Quadratic Unconstrained Binary Optimization (QUBO) model enables exploration with QA, and performance is evaluated using classical solvers and Simulated Annealing (SA).
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.
This paper addresses the Pickup and Delivery Problem with Time Windows (PDPTW), an NP-hard combinatorial optimization problem with major practical relevance in logistics and transportation. The study focuses on a quadratic unconstrained binary optimization (QUBO) formulation for quantum annealing and benchmarks it against two classical optimization paradigms. A modular Python framework is developed that encodes PDPTW in three ways: a mixed-integer linear programming (MILP) model that serves as an exact reference, a genetic algorithm (GA) metaheuristic, and a QUBO model that is compatible with quantum annealers. The framework supports test scenarios with increasing structural complexity, with both feasible and intentionally infeasible instances. An additional contribution is the conceptual design and preliminary analysis of an automatic-penalty weight-tuning scheme for the QUBO model. Experimental results show that the proposed QUBO formulation can produce high-quality solutions for simpler PDPTW instances, but its performance strongly depends on the careful calibration of penalty weights. MILP provides optimal baselines on small instances but becomes intractable as problem size grows. The GA scales to the largest scenario and finds feasible solutions of reasonable quality, but they are not necessarily optimal. The evaluation also includes a large number of problem instances and runs on IBM Quantum hardware using the Quantum Approximate Optimization Algorithm (QAOA).
The Traveling Salesman Problem (TSP) has been one of the most intensively studied problems in theoretical computer science for decades. Being NP-hard, it is unlikely to be solved in polynomial time; hence, despite numerous classical exact and approximate methods, quantum-inspired approaches are also explored. In this study, we analyze several formulations of the TSP suitable for quantum annealing, focusing not only on qubit requirements but also on practical performance, i.e., how frequently feasible and optimal solutions are obtained. We consider both complete and non-complete graphs, reflecting common real-world scenarios. One of the analyzed formulations corresponds to a previously established Quadratic Unconstrained Binary Optimization (QUBO) model, while the others originate from classical Integer Linear Programming (ILP) formulations. We provide a unified, step-by-step translation of selected compact ILP TSP formulations into QUBO models. We analytically show that for non-complete graphs these encodings are asymptotically smaller than the commonly used baseline formulation. We benchmark the formulations using simulated and quantum annealing to evaluate their feasibility and optimality rates. The results are discussed in the context of current quantum annealing hardware limitations, including QPU size and embedding overhead.
Liquefied natural gas (LNG) shipping poses unique optimization challenges in global logistics due to strict operational constraints, dynamic environmental conditions, and the need to minimize both costs and delays. This study explores the integration of quantum optimization and digital twin technology to address the complexities of LNG ship routing. Specifically, we formulate the ship routing problem as a mixed-integer linear programming (MILP) problem aimed at minimizing costs and travel time while incorporating constraints such as ship capacities and weather variability. Given the NP-hard nature of the problem, classical optimization methods struggle to scale efficiently. To overcome this, we transform the MILP into a quadratic unconstrained binary optimization (QUBO) format and employ the quantum approximate optimization algorithm (QAOA) to solve it. The proposed framework integrates real-time data via digital twins, enabling dynamic updates to the optimization process.
We investigate the potential of the Quantum Approximate Optimization Algorithm (QAOA) for reducing energy consumption in route planning, a key challenge in logistics due to the NP-hard nature of the Traveling Salesman and Vehicle Routing Problems. By encoding route optimization as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implementing QAOA circuits at depth p = 3-5 alongside classical baselines of Simulated Annealing (SA) and Genetic Algorithms (GA), we perform systematic benchmarks on Euclidean graphs of sizes N = 5, 10, and 20. Our results demonstrate that QAOA attains higher solution quality with approximation ratios of 0.953 (N = 5), 0.921 (N = 10), and 0.903 (N = 20), outperforming SA and GA by 2.7-4.4%. Wall-clock runtimes for QAOA are 2-3x faster than SA across all tested sizes, and energy consumption measurements reveal a three-order-of-magnitude reduction, remaining in the picojoule range versus nanojoules for classical methods. Translating these gains to real-world logistics suggests an 8.2% improvement in routing efficiency could save approximately 2.62 EJ of fuel annually in the U.S., avoiding nearly 1.94 x 10^8 tonnes of CO2 emissions. These findings highlight QAOA's promise as a fast, energy-efficient optimizer for sustainable logistics applications and underscore its potential role in next-generation fleet-management systems.
Abstract Quantum computing is offering a novel perspective for solving combinatorial optimization problems. To fully explore the possibilities offered by quantum computers, the problems need to be formulated as unconstrained binary models, taking into account limitation and advantages of quantum devices. In this work, we provide a detailed analysis of the travelling salesman problem with time windows (TSPTW) in the context of solving it on a quantum computer. We introduce quadratic unconstrained binary optimization and higher-order binary optimization formulations of this problem. We demonstrate the advantages of edge-based and node-based formulations of the TSPTW problem. Additionally, we investigate the experimental realization of the presented methods on a quantum annealing device. The provided results pave the path for utilizing quantum computer for a variety of real-world tasks which can be cast in the form of travelling salesman problem with time windows.