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).
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).
Recent advances in quantum computing and the increasing availability of quantum hardware have substantially enhanced the practical relevance of quantum approaches to discrete optimization. Among these, the Quadratic Unconstrained Binary Optimization (QUBO) formulation provides a unifying modeling framework for a broad class of NP-hard problems and is naturally suited to quantum computing and quantum-inspired algorithms. Location science, network design, and logistics represent core application domains of discrete optimization, combining high practical impact with substantial computational challenges. In this work, we develop QUBO formulations for several fundamental problems in these domains, including a nonlinear integer formulation of the Discrete Ordered Median Problem (DOMP). Beyond their modeling relevance, these QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware. We further derive a tight bound for the penalty parameter ensuring equivalence between the QUBO formulation and its underlying integer program. Finally, we conduct a comprehensive computational study using QAOA, WS-QAOA, and classical heuristics for QUBO instances of the p-Median Problem and the Fixed-Charge Facility Location Problem (FCFLP), and introduce two effective warm-start strategies for WS-QAOA based on its linear programming relaxation.
We propose the Steiner Traveling Salesman Problem with Time Windows and Pickup and Delivery, an advanced and practical extension of classical routing models. This variant integrates the characteristics of the Steiner Traveling Salesman Problem with time-window constraints, pickup and delivery operations and vehicle capacity limitations. These features closely mirror the complexities of contemporary logistics challenges, including last-mile distribution, reverse logistics and on-demand service scenarios. To tackle the inherent computational difficulties of this NP-hard problem, we propose two specialized mathematical formulations: an arc-based model and a node-oriented model, each designed to capture distinct structural aspects of the problem. We further introduce a preprocessing reduction method that eliminates redundant arcs, significantly enhancing computational performance and scalability. We also introduce a benchmark instance generator designed to create diverse and scalable test scenarios, providing a flexible framework for assessing the performance and robustness of both classical and quantum optimization methods. Both formulations are implemented using classical and quantum optimization approaches. In particular, the classical models are solved with Gurobi, whereas the quantum implementation is carried out on D-Wave’s LeapCQMHybrid platform, a hybrid quantum–classical environment that integrates quantum annealing with classical optimization techniques for constrained problem solving. Numerical experiments are conducted to validate the proposed formulations and the preprocessing reduction method. The analyses performed assess the structural properties of the two models, their computational behavior, and the impact of preprocessing on problem size and solution efficiency.
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.
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.
This paper investigates several Quadratic Unconstrained Binary optimisation (QUBO) formulations for the parallel machine scheduling problem P m | | C max with the goal of assessing their suitability for quantum annealing and related heuristic optimisation methods. Three QUBO models are constructed, ranging from formulations derived from classical integer and one-hot encodings to a more compact load-balancing based representation. Extensive computational experiments using Simulated Annealing (SA) and Quantum Annealing (QA) reveal substantial differences in scalability and solution quality among the formulations. The alternative load-balanced model consistently yields near-optimal makespans, typically within 1%–3% of the theoretical lower bound, highlighting its stability and effectiveness compared to the more penalty sensitive formulations, whose performance deteriorates for larger instances. Sensitivity analyses further reveal that the appropriate selection of penalty weights and problem-specific parameter tuning significantly influences both solution accuracy and computational effort in QUBO formulations. While current quantum hardware limitations restrict experimentation to small problem sizes, the findings illustrate how compact QUBO designs can better exploit quantum optimisation frameworks. The insights gained in this study provide practical modelling guidelines for future quantum scheduling research and lay the groundwork for extending QUBO-based approaches to more complex scheduling environments. • Three QUBO formulations are compared for identical parallel machine scheduling. • A compact load-balancing QUBO avoids auxiliary variables. • Load balancing yields makespans on average within 1–3%. • Both simulated and quantum annealing produce near-optimal schedules. • Penalty selection and encoding strongly affect scalability and solution quality.
The Steiner Tree Problem (STP) is a well-known NP-hard combinatorial optimization problem, which has wide applications in network design, integrated circuit layout, bioinformatics, and other fields. However, traditional algorithms often struggle to balance efficiency and solution quality when dealing with large-scale STP instances. In this paper, we propose a new quantum annealing-based algorithm for solving the STP: we first model the STP into a quadratic unconstrained binary optimization (QUBO) form suitable for quantum annealing, then design a corresponding encoding strategy, and finally verify the algorithm through experimental tests. The results show that our quantum annealing-based method can obtain high-quality solutions with relatively low computational overhead for moderate-scale STP instances, providing a new feasible path for handling this intractable combinatorial optimization problem.