Abstract The transportation problem considered in this work consists of minimizing the sum of penalties for tardiness in the delivery of the product from the base to clients. We propose an innovative method for constructing hybrid algorithms using quantum annealing that guarantees the optimality of the solution. The hybrid algorithm alternately performs calculations on a classical computer equipped with a silicon CPU and a quantum annealer with a QPU processor. The entire method is based on the branch and bound scheme. The lower and upper bounds are calculated on the QPU, while the CPU is responsible for organizing the calculations, recalling the solution tree. The problem under consideration is of great practical importance because it is a component of many complex issues related to solving the traveling repairmen problem, which are very difficult or even impossible to solve today using classical methods. Undoubtedly, an important application of quantum computers in the future is NP‐hard optimization tasks related to transportation scheduling and logistics.
Abstract The transportation problem considered in this work consists of minimizing the sum of penalties for tardiness in the delivery of the product from the base to clients. We propose an innovative method for constructing hybrid algorithms using quantum annealing that guarantees the optimality of the solution. The hybrid algorithm alternately performs calculations on a classical computer equipped with a silicon CPU and a quantum annealer with a QPU processor. The entire method is based on the branch and bound scheme. The lower and upper bounds are calculated on the QPU, while the CPU is responsible for organizing the calculations, recalling the solution tree. The problem under consideration is of great practical importance because it is a component of many complex issues related to solving the traveling repairmen problem, which are very difficult or even impossible to solve today using classical methods. Undoubtedly, an important application of quantum computers in the future is NP‐hard optimization tasks related to transportation scheduling and logistics.
Accurately solving discrete optimization problems is still a serious challenge for classical computing systems. Despite significant progress, it is still impossible to optimally solve examples of the size found in real-world applications. This article examines the problem of scheduling tasks on one machine. Each task has an associated execution time, desired completion date, and a late penalty feature weight. The order of executing tasks should be determined in a manner that minimizes the sum of delay costs. Despite the simplicity of the formulation, this problem is NP-hard and is representative of optimization challenges encountered in the practice of production control, management, and logistics.In this work, we propose using a quantum computing environment to solve it. The main disadvantage of calculations on quantum computers is their nondeterminism. Therefore, there is no guarantee of optimality of solutions to discrete optimization problems determined on a quantum computer.We propose a novel approach to constructing hybrid algorithms that guarantee the optimality of the solution. The algorithm for solving the task scheduling problem considered here is based on the branch and bound method. Calculations are performed alternately on a classical computer and a quantum computer. The lower and upper bounds of the criterion function are determined on a quantum computer. Computational experiments were performed on the D-Wave quantum computer. In small examples, the algorithm runs faster and generates significantly fewer solution tree vertices than its counterpart running on a classic computer. For larger examples, the proposed runtime-constrained method, acting as a heuristic, is an interesting alternative to using quantum computing hardware in relation to classical approaches based on silicon computers.
Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. However, the solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. In order to deal with this issue, we propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits. We analyze the performance of this method on two problems, the knapsack problem and the traveling salesman problem. Our results show the advantages of this method, that balances the number of steps that the algorithm has to make with the amount of error in the solution found by the quantum hardware that the user is willing to risk. The results are obtained using the commercially available quantum hardware D-Wave Advantage, and they outline the strategy for a practical application of the quantum annealers.
Abstract The efficient management of complex production systems is a challenge in today’s logistics. In the field of intelligent and sustainable logistics, the optimization of production batches, especially in the context of a rapidly changing product range, requires fast and precise computational solutions. This paper explores the potential of quantum computers for solving these problems. Traditional computational methods are often limited when it comes to optimizing complex logistics systems. In response to these challenges, the paper proposes the use of a hybrid algorithm that combines quantum technologies with classical computational methods. Such integration allows the computational power of both types of technologies to be harnessed, leading to faster and more efficient identification of optimal solutions. In this work, we consider the knapsack problem, a classic NP-hard optimization problem that is commonly used to verify the effectiveness of new algorithm construction methods. The algorithm presented is based on the Branch and Bound method and aims to ensure solution optimality in the context of the non-determinism of quantum computers. Within the algorithm, computations are performed alternately on a classical processor and a quantum processor. In addition, the lower and upper bounds of the objective function are computed in constant time using the D-Wave quantum machine.
This study investigates the application of quantum annealing in solving logistics and scheduling problems, areas traditionally challenged by combinatorial complexity. Using a case study approach, quantum annealing was applied to optimize delivery routing and job-shop scheduling problems. The methodology incorporated D-Wave's quantum processing unit (QPU), and performance was benchmarked against classical simulated annealing. Results indicate a significant improvement in computational efficiency and solution optimality, particularly for mid-sized problem instances. The research identifies key parameters influencing performance and provides insights into hybrid quantum-classical integration. These findings contribute to the growing field of quantum computing applications in operations research. Keywords: Quantum annealing, logistics optimization, scheduling algorithms, quantum computing, operations research
The Traveling Salesman Problem is a classical NP-hard combinatorial optimization problem that has been extensively studied in operations research. A major challenge in Traveling Salesman Problem formulations is the large number of subtour elimination constraints required to ensure a valid tour. To address this issue, we adopt an iterative approach grounded in well-established operations research techniques, in which subtour elimination constraints are generated dynamically. In addition, we integrate a preprocessing phase to reduce the number of candidate arcs. In this work, we investigate both classical and quantum optimization approaches for solving the problem using the proposed framework. In particular, for quantum optimization we analyze quantum annealing techniques within the D-Wave framework, considering both direct quantum execution on the QPU and hybrid quantum classical solvers. Computational experiments show that the proposed strategies significantly reduce the model size and lead to positive improvements in computational performance across classical, direct quantum, and hybrid optimization approaches.
Quantum computing has paved a new way for faster and more efficient solutions to large-scale, real-world optimization problems that are challenging for classical computing systems. For instance, selective traveling salesman problem (sTSP) that is famous in such fields as logistic optimization and has attracted increasing attention from the research community, however, is known as an NP-Hard problem. Solving the sTSP is, therefore, extremely complex because the optimization function potentially comes with an exponential number of variables that cannot be solved in polynomial time in general. To this end, we propose a quantum annealing framework for time-bounded and near-optimal solutions for the sTSP, overcoming hardware limits of near-term quantum devices. In particular, we put forth an efficient Hamiltonian (QUBO) to encode the complex decision-making for the sTSP on noisy intermediate-scale quantum (NISQ) annealer. Furthermore, experimental results we obtained on the D-Wave 2000Qquantum hardware demonstrate that the optimal solutions for several instances can be attained.