Browse Definitions :
Definition

traveling salesman problem (TSP)

Contributor(s): Matthew Haughn

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 March 2018

Continue Reading About traveling salesman problem (TSP)

Start the conversation

Send me notifications when other members comment.

Please create a username to comment.

-ADS BY GOOGLE

File Extensions and File Formats

Powered by:

SearchCompliance

SearchSecurity

  • GPS jamming

    GPS jamming is the process of using a frequency transmitting device to block or interfere with radio communications.

  • time-based one-time password (TOTP)

    A time-based one-time password (TOTP) is a temporary code, generated by an algorithm, for use in authenticating access to ...

  • Security Operations Center (SOC)

    A security operations center (SOC) is a command center facility for a team of IT professionals with expertise in information ...

SearchHealthIT

SearchDisasterRecovery

  • disaster recovery team

    A disaster recovery team is a group of individuals focused on planning, implementing, maintaining, auditing and testing an ...

  • cloud insurance

    Cloud insurance is any type of financial or data protection obtained by a cloud service provider. 

  • business continuity software

    Business continuity software is an application or suite designed to make business continuity planning/business continuity ...

SearchStorage

  • SSD (solid-state drive)

    An SSD (solid-state drive) is a type of nonvolatile storage media that stores persistent data on solid-state flash memory.

  • NAND flash memory

    NAND flash memory is a type of nonvolatile storage technology that does not require power to retain data.

  • storage class memory (SCM)

    Storage class memory (SCM) is a type of NAND flash that includes a power source to ensure that data won't be lost due to a system...

Close