A Closer Look at the Travelling Salesman Problem

A Closer Look at the Travelling Salesman Problem first defines the travelling salesman problem and then discusses important methods for solving it. The authors describe a novel search system, the attractor-based search system; this system uses a local search process to construct the solution attractor, and then completely searches the constructed solution attractor to find the optimal tour, solving the travelling salesman problem efficiently. Additionally, the hybrid of improvement and construction heuristics is presented, which produces a better cost-quality solution in lesser time. In the worst case, it creates a 1.91, 2.86 times better cost-quality compared to improvement and construction heuristics, respectively. The closing study reports on the solution of four 6-city, asymmetric traveling salesman problems on the D-Wave quantum processor. About 35% of the optimal tours were found by quantum means for a problem with 24 optimal tours and for another problem with 6 optimal tours.