Steiner Traveling Salesman Problem with Quantum Annealing
This work addresses the STSP, a combinatorial optimization problem relevant for logistics and routing applications, but it appears incremental as it applies existing quantum annealing methods with a preprocessing step.
The paper tackled the Steiner Traveling Salesman Problem (STSP), an NP-hard variant of the Traveling Salesman Problem, by proposing a quantum annealing approach with D-Wave's hardware and a preprocessing method to reduce network size, which significantly decreased problem complexity and showed potential for solving STSP.
The Steiner Traveling Salesman Problem (STSP) is a variant of the classical Traveling Salesman Problem. The STSP involves incorporating steiner nodes, which are extra nodes not originally part of the required visit set but that can be added to the route to enhance the overall solution and minimize the total travel cost. Given the NP-hard nature of the STSP, we propose a quantum approach to address it. Specifically, we employ quantum annealing using D-Wave's hardware to explore its potential for solving this problem. To enhance computational feasibility, we develop a preprocessing method that effectively reduces the network size. Our experimental results demonstrate that this reduction technique significantly decreases the problem complexity, making the Quadratic Unconstrained Binary Optimization formulation, the standard input for quantum annealers, better suited for existing quantum hardware. Furthermore, the results highlight the potential of quantum annealing as a promising and innovative approach for solving the STSP.