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

  • compliance audit

    A compliance audit is a comprehensive review of an organization's adherence to regulatory guidelines.

  • regulatory compliance

    Regulatory compliance is an organization's adherence to laws, regulations, guidelines and specifications relevant to its business...

  • Whistleblower Protection Act

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

SearchSecurity

  • brute force attack

    Brute force (also known as brute force cracking) is a trial and error method used by application programs to decode encrypted ...

  • spyware

    Spyware is software that is installed on a computing device without the user's knowledge. Spyware can be difficult to detect; ...

  • ATM black box attack

    An ATM black box attack, also referred to as jackpotting, is a type of banking-system crime in which the perpetrators bore holes ...

SearchHealthIT

SearchDisasterRecovery

  • business continuity and disaster recovery (BCDR)

    Business continuity and disaster recovery (BCDR) are closely related practices that describe an organization's preparation for ...

  • warm site

    A warm site is a type of facility an organization uses to recover its technology infrastructure when its primary data center goes...

  • disaster recovery (DR) test

    A disaster recovery test (DR test) is the examination of each step in a disaster recovery plan as outlined in an organization's ...

SearchStorage

  • enterprise storage

    Enterprise storage is a centralized repository for business information that provides common data management, protection and data...

  • disk array

    A disk array, also called a storage array, is a data storage system used for block-based storage, file-based storage or object ...

  • optical storage

    Optical storage is any storage type in which data is written and read with a laser. Typically, data is written to optical media, ...

Close