Overview
The Traveling Salesperson Problem (TSP) is an optimization problem defined on a set of cities and travel costs between pairs of cities. The objective is to find a minimum-cost Hamiltonian cycle: a closed tour that visits each city exactly once before returning to the starting city. In the symmetric version, the cost from city A to city B equals the cost from city B to city A. In the asymmetric version, travel costs may differ by direction.
Key concepts
name: Core idea; description: The central focus of traveling salesperson problem (tsp) is the capability described here: The Traveling Salesperson Problem asks for the least-cost tour that visits every required city exactly once and returns to the starting city. It is a fundamental combinatorial optimization problem used to study computational difficulty, exact search, approximation, and heuristic methods.; name: Problem context; description: Traveling Salesperson Problem (TSP) is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using traveling salesperson problem (tsp), check its assumptions, input requirements, expected output, and resource constraints.
Types
name: Symmetric TSP; description: Travel cost from city i to city j is equal to travel cost from city j to city i.; name: Asymmetric TSP; description: Travel costs can differ depending on the direction of travel.; name: Metric TSP; description: Travel costs satisfy the triangle inequality, meaning direct travel is no more expensive than traveling through an intermediate location.; name: Euclidean TSP; description: Cities are represented by points in Euclidean space, and travel costs are based on geometric distance.
Mathematical model
objective: Minimize the total cost of a Hamiltonian cycle.; costExpression: Total tour cost = sum of the travel costs of consecutive cities, including the final return to the starting city.; decisionVersion: Does there exist a tour whose total cost is at most K?
Complexity
optimizationVersion: NP-hard.; decisionVersion: NP-complete.; explanation: The decision version asks whether a tour with cost at most K exists. A proposed tour can be checked in polynomial time, while the decision problem is NP-complete.
Example
scenario: A delivery company must visit four cities and return to its warehouse.; cities: A; B; sampleTour: A; B; explanation: The cost of the sample tour is calculated by adding the costs of A to B, B to D, D to C, and C to A. Other valid tours can be evaluated to identify the least expensive one.
Applications
Delivery route planning.; Warehouse picking and logistics.; Circuit-board drilling paths.; Manufacturing and machine scheduling.; DNA sequencing and scientific data analysis.; Robotics and movement planning.