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

SearchCompliance

  • Whistleblower Protection Act

    The Whistleblower Protection Act of 1989 is a law that protects federal government employees in the United States from ...

  • smart contract

    A smart contract, also known as a cryptocontract, is a computer program that directly controls the transfer of digital currencies...

  • risk map (risk heat map)

    A risk map, also known as a risk heat map, is a data visualization tool for communicating specific risks an organization faces. A...

SearchSecurity

  • certificate authority (CA)

    A certificate authority (CA) is a trusted entity that issues digital certificates, which are data files used to cryptographically...

  • hacktivism

    Hacktivism is the act of hacking, or breaking into a computer system, for a politically or socially motivated purpose.

  • advanced persistent threat (APT)

    An advanced persistent threat (APT) is a prolonged and targeted cyberattack in which an intruder gains access to a network and ...

SearchHealthIT

  • Cerner Corp.

    Cerner Corp. is a public company in North Kansas City, Mo., that provides various health information technologies, ranging from ...

  • clinical decision support system (CDSS)

    A clinical decision support system (CDSS) is an application that analyzes data to help healthcare providers make decisions and ...

  • Health IT (health information technology)

    Health IT (health information technology) is the area of IT involving the design, development, creation, use and maintenance of ...

SearchDisasterRecovery

  • tabletop exercise (TTX)

    A tabletop exercise (TTX) is a disaster preparedness activity that takes participants through the process of dealing with a ...

  • risk mitigation

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

  • ransomware recovery

    Ransomware recovery is the process of resuming options following a cyberattack that demands payment in exchange for unlocking ...

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.

  • file system

    In a computer, a file system -- sometimes written filesystem -- is the way in which files are named and where they are placed ...

  • storage virtualization

    Storage virtualization is the pooling of physical storage from multiple storage devices into what appears to be a single storage ...

Close