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)

Networking
  • Network as a Service (NaaS)

    Network as a service, or NaaS, is a business model for delivering enterprise WAN services virtually on a subscription basis.

  • network configuration management (NCM)

    Network configuration management is the process of organizing and maintaining information about all of the components in a ...

  • presentation layer

    The presentation layer resides at Layer 6 of the Open Systems Interconnection (OSI) communications model and ensures that ...

Security
  • backdoor (computing)

    A backdoor attack is a means to access a computer system or encrypted data that bypasses the system's customary security ...

  • Heartbleed

    Heartbleed was a vulnerability in some implementations of OpenSSL, an open source cryptographic library.

  • What is risk management and why is it important?

    Risk management is the process of identifying, assessing and controlling threats to an organization's capital and earnings.

CIO
HRSoftware
  • team collaboration

    Team collaboration is a communication and project management approach that emphasizes teamwork, innovative thinking and equal ...

  • employee self-service (ESS)

    Employee self-service (ESS) is a widely used human resources technology that enables employees to perform many job-related ...

  • learning experience platform (LXP)

    A learning experience platform (LXP) is an AI-driven peer learning experience platform delivered using software as a service (...

Customer Experience
  • headless commerce (headless e-commerce)

    Headless commerce, also called headless e-commerce, is a platform architecture that decouples the front end of an e-commerce ...

  • chief customer officer (CCO)

    A chief customer officer, or customer experience officer, is responsible for customer research, communicating with company ...

  • relationship marketing

    Relationship marketing is a facet of customer relationship management (CRM) that focuses on customer loyalty and long-term ...

Close