Traveling Salesman problem
The Traveling Salesman problem is a combinatorial optimization problem that seeks a minimum-cost tour visiting each specified location exactly once and returning to the starting location.
Optimization Algorithms: AI techniques for design, planning, and control problems
The traveling salesman problem is the optimization problem of finding a minimum-time tour that visits every specified city, potentially with asymmetric travel times between cities.
- How it is used
- Uses city and delivery routing to motivate combinatorial optimization and compare search approaches.
- How deep it goes
- Develops route representations, cost evaluation, and solver workflows, including feasibility repair and a graph-learning pipeline.
- Examples
- Uses 13 Greater Toronto Area cities, 18 delivery stops, and a 20-city US tour.
- What you can do after
- Apply it via pymoo or simulated annealing to search for routes and experiment with solver settings.
Evolutionary Deep Learning: Genetic algorithms and neural networks
The traveling salesman problem is the optimization problem of finding a route that visits each destination while minimizing total travel distance, typically with a return to the start.
- How it is used
- Uses the TSP as an NP-hard optimization task for demonstrating genetic algorithms.
- How deep it goes
- Works through route encoding, visualization, distance fitness, population setup, and evolutionary runs without deriving a linear-time solution.
- Examples
- Uses a random map, an initial plotted route, a 22-destination evolved solution, and operator-comparison visualizations.
- What you can do after
- Apply it via DEAP to encode, evaluate, evolve, and visualize candidate routes for a TSP instance.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
The Traveling Salesman problem asks for a minimum-cost cycle that visits every city exactly once and returns to the starting city.
- How it is used
- Frames route optimization as a classic graph problem and a practical application for shipping, distribution, and other routing scenarios.
- How deep it goes
- Develops a complete brute-force Swift solver with backtracking, cycle closure, distance evaluation, and a concrete five-city result, but not scalable alternatives.
- Examples
- Uses a Vermont distance matrix, recursive permutations, closed tours, and a 318-mile route as worked artifacts.
- What you can do after
- Build a brute-force Swift solver that enumerates tours and returns the shortest cycle and its distance.
Advanced Algorithms and Data Structures
The travelling salesman problem asks for the shortest route that visits each specified location exactly once and returns to the starting location.
- How it is used
- Frames route planning as a graph optimization problem and motivates simulated annealing and genetic algorithms for large instances.
- How deep it goes
- Explains graph representation, permutation encoding, cost evaluation, search difficulty, and heuristic alternatives, without developing an exact polynomial-time algorithm.
- Examples
- Uses delivery routes, a six-city complete graph, city-map tours, and applications in transport, logistics, manufacturing, and sequencing.
- What you can do after
- Apply it via simulated annealing or genetic algorithms to represent, evaluate, and search large route-planning instances.
Read how Advanced Algorithms and Data Structures explains Traveling Salesman problem →
Inside AI
The traveling salesman problem is an optimization problem that seeks the best route visiting each location exactly once and returning to the starting location.
- How it is used
- Uses route planning as a practical case for showing why genetic algorithms search beyond conventional exhaustive programs.
- How deep it goes
- Explains route representation, fitness evaluation, selection, and crossover, but does not provide implementation details.
- Examples
- Uses city tours and route-count comparisons, including a twenty-location example with an astronomical number of possible routes.
- What you can do after
- Evaluate/understand why genetic search can replace exhaustive route comparison when possible solutions grow dramatically.
Sutskever's List
The traveling salesman problem asks for a minimum-length route that visits each specified location and returns to the starting location.
- How it is used
- Tests whether a Ptr-Net can learn and generalize route-optimization strategies.
- How deep it goes
- Defines the route constraint and complexity, then reports model results without deriving optimization algorithms.
- Examples
- Uses city routes and compares heuristic and Ptr-Net results across problem sizes.
- What you can do after
- Understand how a Ptr-Net learns routes from optimal small instances and performs on larger ones.
Read how Sutskever's List explains Traveling Salesman problem →
Also covered in
- Algorithms Every Programmer Should KnowIn early access (MEAP)
- How Large Language Models Work
- Grokking Algorithms, Second Edition
- Grokking AI Algorithms, Second Edition
What to know first
- distanceA distance function assigns a numerical measure of separation or dissimilarity to pairs of points or objects in a defined space.
- dynamic programmingDynamic programming is an algorithmic technique that solves problems by decomposing them into overlapping subproblems and storing or reusing their solutions.
- graphA graph is a mathematical structure consisting of vertices and edges that connect pairs of vertices to represent relationships or connections.
- optimizationOptimization is the systematic selection or modification of values, configurations, or implementations to improve a defined objective, often subject to constraints.
Related concepts
- genetic algorithmaddressed by · A genetic algorithm is an evolutionary optimization method that improves a population of candidate solutions through fitness-based selection and variation, often including recombination and mutation.
- Christofides algorithmaddressed by · A polynomial-time approximation algorithm for the metric traveling salesman problem with a worst-case tour length no greater than 1.5 times optimal.
- np-complete problemkind of · An NP-complete problem is a decision problem in NP to which every problem in NP can be reduced in polynomial time.
- simulated annealingaddressed by · Simulated annealing is a stochastic optimization method that gradually reduces the probability of accepting worse solutions to escape local optima.
- ant colony optimizationaddressed by · Ant colony optimization is a population-based probabilistic optimization technique in which artificial agents use simulated pheromone trails to guide the search for good solutions.
Questions about Traveling Salesman problem
What is Traveling Salesman problem?
The Traveling Salesman problem is a combinatorial optimization problem that seeks a minimum-cost tour visiting each specified location exactly once and returning to the starting location.
Which Manning books explain Traveling Salesman problem?
Optimization Algorithms: AI techniques for design, planning, and control problems, Evolutionary Deep Learning: Genetic algorithms and neural networks, Classic Computer Science Problems in Swift: Essential techniques for practicing programmers, Advanced Algorithms and Data Structures, Inside AI and Sutskever's List.
What should I know before learning Traveling Salesman problem?
Manning books that teach Traveling Salesman problem usually introduce distance, dynamic programming, graph and optimization first.
What is Traveling Salesman problem a kind of?
Traveling Salesman problem is a kind of np-complete problem. An NP-complete problem is a decision problem in NP to which every problem in NP can be reduced in polynomial time.
What is Traveling Salesman problem also called?
Traveling Salesman problem is also called TSP or traveling salesperson problem.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.





