Quantum annealing‐driven branch and bound for the total weighted tardiness traveling salesman problem on the D‐Wave quantum computer

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.