•  
  •  
 

The Plymouth Student Scientist

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

URI

http://hdl.handle.net/10026.1/14184

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

license.txt (5 kB)

Share

COinS