Show simple item record

dc.contributor.authorChatting, M.
dc.date.accessioned2019-05-22T08:58:06Z
dc.date.available2019-05-22T08:58:06Z
dc.date.issued2018
dc.identifier.citation

Chatting, M. (2018) 'A Comparison of Exact and Heuristic Algorithms to Solve the Travelling Salesman Problem', The Plymouth Student Scientist, 11(2), p. 53-91.

en_US
dc.identifier.issn1754-2383
dc.identifier.urihttp://hdl.handle.net/10026.1/14184
dc.description.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.

en_US
dc.language.isoenen_US
dc.publisherUniversity of Plymouth
dc.rightsAttribution 3.0 United States*
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/us/*
dc.subjectTravelling Salesman Problemen_US
dc.subjectalgorithmsen_US
dc.subjectheuristic algorithmsen_US
dc.subjectefficiencyen_US
dc.titleA Comparison of Exact and Heuristic Algorithms to Solve the Travelling Salesman Problemen_US
dc.typeArticle
plymouth.journalThe Plymouth Student Scientist


Files in this item

Thumbnail
Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution 3.0 United States
Except where otherwise noted, this item's license is described as Attribution 3.0 United States

All items in PEARL are protected by copyright law.
Author manuscripts deposited to comply with open access mandates are made available in accordance with publisher policies. Please cite only the published version using the details provided on the item record or document. In the absence of an open licence (e.g. Creative Commons), permissions for further reuse of content should be sought from the publisher or author.
Theme by 
@mire NV