A Comparison of Exact and Heuristic Algorithms to Solve the Travelling Salesman Problem

Matthew Chatting

Abstract


This article provides an overview to the Travelling Salesman Problem (TSP) and the relevant aspects of graph theory and computational complexity theory to understand the TSP. Beyond this, two algorithms capable of solving the TSP are introduced, explained and analysed in terms of their efficiency. The first algorithm is a random search heuristic ‘hill climber’ and the second is an exact ‘branch and bound’ algorithm. The benefits and drawbacks of each algorithm are discussed alongside their performance on distinct instances of the TSP. Consideration is also given to current research on the factors contributing to the complexity of instances.


Full Text:

PDF

Refbacks

  • There are currently no refbacks.


Creative Commons License 
This work is licensed under a Creative Commons Attribution 3.0 License

ISSN 1754-2383 [Online] ©University of Plymouth