ā Back to Optimizer
Traveling Salesman Problem (TSP) Algorithms
The Traveling Salesman Problem asks: "Given a list of cities and the distances between them, what is the shortest
possible route that visits each city exactly once and returns to the starting point?" This is an NP-hard problem,
meaning there's no known efficient algorithm to find the perfect solution for large numbers of cities. Below are
the algorithms implemented in the Route Optimizer, ranging from fast heuristics to guaranteed optimal solutions.
A greedy approach that always visits the closest unvisited point next.
Initialize current_city = random_start_city
Mark current_city as visited
While unvisited cities exist:
Find nearest unvisited city to current_city
Move to nearest city
Mark it as visited
Return to start
ā Pros
Extremely fast; easy to implement; good for huge datasets.
ā Cons
Short-sighted (greedy); path often crosses itself; usually ~25% longer than optimal.
Implementation Note: We use this as the baseline initialization for 2-Opt and Simulated Annealing to speed up convergence. For N > 2000, we time-slice execution to prevent UI freezing.
Builds a tour by inserting the unvisited point that adds the minimal distance to the current tour.
Start with a sub-tour of 3 cities (triangle)
While unvisited cities exist:
Select unvisited city k
Find edge (i, j) in tour minimizing cost:
dist(i, k) + dist(k, j) - dist(i, j)
Insert k between i and j
ā Pros
Creates 'round' natural shapes; handles convex hull arrangements well.
ā Cons
Slower than Nearest Neighbor per step; effective complexity often closer to O(NĀ³) in naive implementations.
Implementation Note: This implementation is heavy (O(NĀ³) behavior due to search). If the timeout is reached, we force-append remaining unvisited points to ensure a valid tour is returned rather than crashing.
Optimization step. Takes an existing route and iteratively swaps edges to untangle crossing paths.
path = initial_path
Repeat until no improvement:
For every pair of edges (A-B) and (C-D):
If dist(A-C) + dist(B-D) < dist(A-B) + dist(C-D):
Swap edges (reverse segment B...C)
improvement = true
ā Pros
Removes visible edge crossings; industry standard for 'good enough' routes.
ā Cons
Can get stuck in 'Local Minima' (good but not best); requires an initial path.
Implementation Note: We initialize this with a Nearest Neighbor tour, not a random one. Starting with NN drastically reduces the time needed to reach a clean solution.
Builds a Minimum Spanning Tree (Prim's Algorithm) and traverses it (DFS) to form a cycle.
1. Compute MST of the graph (Prim's Algo)
2. Perform Preorder Walk (DFS) on MST
3. Record nodes in order of first visit
4. Connect last node to start
ā Pros
Guaranteed to be within 2x of the optimal solution (2-approximation).
ā Cons
Does not optimize for shape; ignores 'return trip' cost; usually worse than 2-Opt in practice.
Implementation Note: We use Prim's algorithm. For 15k+ points, building the full adjacency matrix is memory intensive, so we use an implicit graph approach with time-slicing.
Probabilistic meta-heuristic. Sometimes accepts worse moves to escape local traps, cooling down over time.
current = initial_solution
best = current
temp = high_temp
While temp > min_temp:
neighbor = slightly_modify(current)
delta = cost(neighbor) - cost(current)
If delta < 0 OR random() < exp(-delta / temp):
current = neighbor
temp = temp * cooling_rate
ā Pros
Can find global optima where 2-Opt gets stuck; very robust.
ā Cons
Slow; results vary per run; requires parameter tuning (temperature, cooling rate).
Implementation Note: Initialized with Nearest Neighbor to start from a decent shape. Cooling rate is set to 0.995. We use a simple 'swap two cities' mutation strategy.
Evolutionary approach. Uses a population of routes, selecting the best to 'breed' and mutate.
Population = [NearestNeighborResult, ...RandomPaths]
For generation in 1..MAX_GEN:
Select fittest parents (Elitism)
Breed offspring (Crossover)
Mutate offspring (Random Swaps)
Replace population with new gen
Return best individual
ā Pros
Excellent for very large problems; works well with time limits.
ā Cons
Memory intensive; requires many generations to converge if seeded randomly.
Implementation Note: CRITICAL: We seed the initial population with the Nearest Neighbor result. Without this, the GA starts from chaos (4M+ distance) and cannot converge to a recognizable shape within the time limit.
Tries every single possible permutation of the route to find the mathematically perfect one.
Generate all permutations (N!)
For each p in permutations:
d = calculate_distance(p)
if d < min_dist:
min_dist = d
best_path = p
ā Pros
Guaranteed optimal solution (100% perfect).
ā Cons
Impossible for N > 15 (computation time explodes exponentially).
Implementation Note: Strictly capped at 10 cities (3.6 million permutations) to prevent browser crashes.