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 TSP as a routing objective and a test case for search, optimization, and graph-learning methods.
- How deep it goes
- Defines tour structure and search-space growth, then works through solver implementations; does not establish that their found tours are optimal.
- Examples
- Uses a 13-city counting example, an 18-store delivery route, and 20-city US tours.
- What you can do after
- Apply it via optalgotools simulated annealing or pymoo genetic algorithms to seek and score round-trip routes.
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 →
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.
- 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.
- 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.
- 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.
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.