✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-236

Traveling Salesperson Problem (TSP)

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.

Explanation

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.

Example or application

Scenario

A delivery company must visit four cities and return to its warehouse.

Cities

  • A

  • B

  • C

  • D

Sample Tour

  • A

  • B

  • D

  • C

  • A

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.

Definition

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.

Problem Components

ComponentDescription

Cities

The locations that must be visited.

Travel Costs

Distances, times, financial costs, or other weights associated with moving between cities.

Tour

A complete cycle visiting every city once and returning to the start.

Objective Function

The sum of the travel costs along the selected tour.

Constraints

Every city must appear exactly once in the tour, apart from the repeated starting city at the end.

Mathematical Model

Objective

Minimize the total cost of a Hamiltonian cycle.

Cost Expression

Total tour cost = sum of the travel costs of consecutive cities, including the final return to the starting city.

Decision Version

Does there exist a tour whose total cost is at most K?

Types

NameDescription

Symmetric TSP

Travel cost from city i to city j is equal to travel cost from city j to city i.

Asymmetric TSP

Travel costs can differ depending on the direction of travel.

Metric TSP

Travel costs satisfy the triangle inequality, meaning direct travel is no more expensive than traveling through an intermediate location.

Euclidean TSP

Cities are represented by points in Euclidean space, and travel costs are based on geometric distance.

Basic Approaches

NameDescriptionComplexityLimitation

Brute Force

Enumerates possible tours and selects the least expensive one.

Approximately O(n!) candidate tours before accounting for evaluation costs.

Becomes impractical as the number of cities increases.

Dynamic Programming

Uses subsets of visited cities and the current endpoint to avoid repeating certain calculations.

The Held-Karp algorithm runs in O(n² × 2ⁿ) time and O(n × 2ⁿ) space.

Exponential complexity still limits the practical input size.

Branch and Bound

Explores partial tours while using lower bounds to discard branches that cannot improve the best known solution.

Worst-case exponential.

Performance depends heavily on the quality of bounds and the input structure.

Approximation Algorithms

Find tours with a provable relationship to the optimal cost under specified assumptions, such as metric distances.

Depends on the selected algorithm.

The result may not be exactly optimal.

Heuristics

Use practical strategies such as nearest neighbor, local search, or simulated annealing to find good tours.

Depends on the heuristic and stopping conditions.

Usually provides no general guarantee of optimality.

Complexity

Optimization Version

NP-hard.

Decision Version

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.

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.

Limitations

  • The number of possible tours grows factorially.

  • Exact algorithms become expensive for large instances.

  • Real transportation problems may include time windows, vehicle capacities, multiple vehicles, and changing traffic conditions that require richer models.

  • Heuristic solutions may be good but not globally optimal.

Related Topics

  • INFO-CS-ADS-233

  • INFO-CS-ADS-234

  • INFO-CS-ADS-235

  • INFO-CS-ADS-237

  • INFO-CS-ADS-246

Practice Questions

QuestionAnswer

What is the main objective of TSP?

Find a minimum-cost tour that visits every city exactly once and returns to the starting city.

What is the difference between symmetric and asymmetric TSP?

Symmetric TSP has equal costs in both directions, while asymmetric TSP may have different directional costs.

What is the time complexity of the Held-Karp dynamic programming algorithm?

O(n² × 2ⁿ) time.

Why is TSP important in computer science?

It is a central NP-hard optimization problem with applications in routing, logistics, manufacturing, and research.

Key Concepts

NameDescription

Core idea

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.

Problem context

Traveling Salesperson Problem (TSP) is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using traveling salesperson problem (tsp), check its assumptions, input requirements, expected output, and resource constraints.

Learning Objectives

  • Explain the central idea and purpose of traveling salesperson problem (tsp).

  • Identify the assumptions, inputs, and conditions relevant to traveling salesperson problem (tsp).

  • Evaluate an application of traveling salesperson problem (tsp) for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Advanced Algorithm Theory and Applications

Suggest a correction or source · More in Algorithms & Data Structures