The Plymouth Student Scientist
Document Type
Engineering, Computing and Mathematics Article
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.
Publication Date
2018-12-01
Publication Title
The Plymouth Student Scientist
Volume
11
Issue
2
First Page
53
Last Page
91
ISSN
1754-2383
Deposit Date
May 2019
Embargo Period
2024-07-08
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Recommended Citation
Chatting, Matthew
(2018)
"A Comparison of Exact and Heuristic Algorithms to Solve the Travelling Salesman Problem,"
The Plymouth Student Scientist: Vol. 11:
Iss.
2, Article 4.
DOI: https://doi.org/10.24382/rvjy-vx76
Available at:
https://pearl.plymouth.ac.uk/tpss/vol11/iss2/4
