A Closer Look at the Travelling Salesman Problem


Christina V. Østergaard (Editor)

Series: Mathematics Research Developments
BISAC: MAT042000

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.
(Imprint: Novinka)



Table of Contents


Chapter 1. Travelling Salesman Problem and Its Applications
(Taskeen Zaidi, Department of Computer Science and Engineering, Shri Ramswaroop Memorial University, Barabanki, Uttar Pradesh, India)

Chapter 2. The Attractor Approach to Computational Complexity of the Traveling Salesman Problem
(Weiqi Li, School of Management, University of Michigan-Flint, Flint, MI, US)

Chapter 3. Study on Heuristic Approaches for Symmetric Traveling Salesman Problem
(Pramod Yelmewad and Basavaraj Talawar, System, Parallelization and Architecture Research at NITK, Department of Computer Science and Engineering, National Institute of Technology Karnataka, Surathkal, Mangalore, India)

Chapter 4. Quantum Solutions of 6-City Traveling Salesman Problems
(Richard H. Warren, Lockheed Martin Corporation [Retired], King of Prussia, PA, US)


Additional information