Browse Definitions :
Definition

traveling salesman problem (TSP)

The traveling salesman problem (TSP) is an algorithmic problem tasked with finding the shortest route between a set of points and locations that must be visited. In the problem statement, the points are the cities a salesperson might visit. The salesman‘s goal is to keep both the travel costs and the distance traveled as low as possible.

Focused on optimization, TSP is often used in computer science to find the most efficient route for data to travel between various nodes. Applications include identifying network or hardware optimization methods.  It was first described by Irish mathematician W.R. Hamilton and British mathematician Thomas Kirkman in the 1800s through the creation of a game that was solvable by finding a Hamilton cycle, which is a non-overlapping path between all nodes.

TSP has been studied for decades and several solutions have been theorized. The simplest solution is to try all possibilities, but this is also the most time consuming and expensive method. Many solutions use heuristics, which provides probability outcomes. However, the results are approximate and not always optimal. Other solutions include branch and bound, Monte Carlo and Las Vegas algorithms.

Rather than focus on finding the most effective route, TSP is often concerned with finding the cheapest solution. In TSPs, the large amount of variables creates a challenge when finding the shortest route, which makes approximate, fast and cheap solutions all the more attractive.

 

This was last updated in June 2020

Continue Reading About traveling salesman problem (TSP)

SearchCompliance
  • ISO 31000 Risk Management

    The ISO 31000 Risk Management framework is an international standard that provides businesses with guidelines and principles for ...

  • pure risk

    Pure risk refers to risks that are beyond human control and result in a loss or no loss with no possibility of financial gain.

  • risk reporting

    Risk reporting is a method of identifying risks tied to or potentially impacting an organization's business processes.

SearchSecurity
  • Pretty Good Privacy (PGP)

    Pretty Good Privacy or PGP was a popular program used to encrypt and decrypt email over the internet, as well as authenticate ...

  • email security

    Email security is the process of ensuring the availability, integrity and authenticity of email communications by protecting ...

  • Blowfish

    Blowfish is a variable-length, symmetric, 64-bit block cipher.

SearchHealthIT
SearchDisasterRecovery
  • What is risk mitigation?

    Risk mitigation is a strategy to prepare for and lessen the effects of threats faced by a business.

  • fault-tolerant

    Fault-tolerant technology is a capability of a computer system, electronic system or network to deliver uninterrupted service, ...

  • synchronous replication

    Synchronous replication is the process of copying data over a storage area network, local area network or wide area network so ...

SearchStorage
  • direct access

    In computer storage, direct access is the process of reading and writing data on a storage device by going directly to where the ...

  • kibi, mebi, gibi, tebi, pebi and exbi

    Kibi, mebi, gibi, tebi, pebi and exbi are binary prefix multipliers that, in 1998, were approved as a standard by the ...

  • holographic storage (holostorage)

    Holographic storage is computer storage that uses laser beams to store computer-generated data in three dimensions.

Close