The traveling salesman problem (TSP) asks for a tour that visits every specified city and returns to its starting point while minimizing a chosen cost, such as travel time, distance, or price. The decision is the order of visits: a permutation of the cities. A fast route need not be the shortest route if travel times differ from distances. section 2.1.1 section 1.4.3
Direction matters. In symmetric TSP, travel costs are the same both ways, so the cities and connections form an undirected graph. In asymmetric TSP, a return trip may cost differently or a connection may exist in only one direction. Traffic patterns and one-way streets make the asymmetric case practical, not merely theoretical. section 2.1.1 section 1.4.3
Why not check every tour?
For 13 cities, fixing the starting city still leaves 12! = 479,001,600 possible visit orders in the asymmetric case. Exhaustively checking them is a poor real-time plan. Dynamic programming can reduce the work; approximate search methods offer another practical route when the search space is too large. section 2.1.1 section 1.4.3
To turn a routing task into a TSP instance:
- Choose the stops, the starting location, and the cost to minimize. For a delivery truck, that might be total road distance over a round trip. section 5.6
- Build inter-stop costs. One truck example uses GPS coordinates, an OSMnx road graph, and NetworkX shortest paths; a 20-city example instead builds a distance matrix from coordinates. section 5.6 section 8.6
- Represent a candidate as a city order, sum its consecutive leg costs, and include the return leg. Keep the search feasible: a permutation visits each city once, while a repair operator can rotate a tour to a designated start. section 8.6 section 9.6
The solver can change without changing the underlying routing question. Simulated annealing improved an initial 593.88 km route among 18 Greater Toronto Area stores to a 227.17 km route. A separate 20-US-city implementation uses a genetic algorithm with permutation sampling, order crossover, inversion mutation, and start-city repair. These are found routes, not demonstrations that no shorter tour exists. section 5.6 section 8.6
problem = TravelingSalesman(cities,distance_matrix) #1
algorithm = GA(
pop_size=20,
sampling=PermutationRandomSampling(),
mutation=InversionMutation(),
crossover=OrderCrossover(),
repair=StartFromZeroRepair(),
eliminate_duplicates=True
) #2
termination = DefaultSingleObjectiveTermination(period=300, n_max_gen=np.inf) #3
res = minimize(
problem,
algorithm,
termination,
seed=1,
verbose=False
) #4
Inspect how permutation sampling, crossover, mutation, and repair are configured together in a genetic-algorithm TSP solver. section 8.6
Other approaches need different representations. A particle-swarm example sorts a particle’s values to obtain a city order, then scores the tour. A graph-learning pipeline predicts promising nodes or edges and uses graph search to assemble a feasible candidate; its worked application uses a pretrained model rather than training one from scratch. Compare routes using the same stops and cost definition before drawing conclusions about solvers. section 9.6 section 11.7
