Traveling Salesman Problem

This notebook demonstrates solving the Traveling Salesman Problem (TSP) using simulated annealing. The TSP is a classic optimization problem where the goal is to find the shortest possible route that visits each city exactly once and returns to the origin city.

from collections.abc import Sequence
from random import uniform
from itertools import permutations
from time import time

from altbacken.external.neighbourhood.permutation import PermutationNeighbourhood
from altbacken.external.annealing import SimpleSimulatedAnnealing

type Graph = dict[int, dict[int, float]]

def random_graph(n: int, min_dist: float = 1.0, max_dist: float = 100.0) -> Graph:
    return {
        i: {
            j: uniform(min_dist, max_dist) for j in range(i + 1, n)
        }
        for i in range(n-1)
    }

def distance_between(graph: Graph, start: int, end: int) -> float:
    start, end = min(start, end), max(start, end)
    return graph[start][end]

GRAPH_SIZE: int = 8
graph: Graph = random_graph(GRAPH_SIZE)
initial_solution = list(range(GRAPH_SIZE))

def travel_cost(solution: Sequence[int]) -> float:
    current: int = solution[0]
    start: int = solution[0]
    cost: float = 0.0
    for node in solution[1:]:
        cost += distance_between(graph, current, node)
        current = node
    cost += distance_between(graph, current, start)
    return cost

annealing: SimpleSimulatedAnnealing = SimpleSimulatedAnnealing(
    travel_cost,
    PermutationNeighbourhood(),
    10000.0
)

sa_start: float = time()
best_match, best_value = annealing.simulate(initial_solution)
print("SA took:", time() - sa_start, "seconds.")

print("Best match (SA):", best_match)
print("Best value (SA):", best_value)

SA took: 0.003637552261352539 seconds.
Best match (SA): (1, 6, 5, 7, 4, 0, 3, 2)
Best value (SA): 125.91510850173273

naive_start: float = time()
optimal_path = min(permutations(list(range(GRAPH_SIZE)), GRAPH_SIZE), key=travel_cost)
print("Naive took:", time() - naive_start, "seconds.")
print("Optimal path:", optimal_path)
print("Optimal cost:", travel_cost(optimal_path))

Naive took: 0.04398012161254883 seconds.
Optimal path: (1, 6, 5, 7, 4, 0, 3, 2)
Optimal cost: 125.91510850173273

print("Relative derivation of SA solution:", (best_value / travel_cost(optimal_path))-1)

Relative derivation of SA solution: 0.0