TSP Algorithms

Solve Traveling Salesman Problem variants for optimal routing in warehouse operations.

Installation

pip install numpy scipy networkx python-tsp

Quick Start

import numpy as np
from python_tsp.heuristics import solve_tsp_simulated_annealing

# Distance matrix between locations
distance_matrix = np.array([
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
])

# Solve TSP
permutation, distance = solve_tsp_simulated_annealing(distance_matrix)
print(f"Route: {permutation}, Distance: {distance}")

TSP Algorithms

Nearest Neighbor Heuristic

def nearest_neighbor_tsp(distance_matrix, start=0):
    """Greedy nearest neighbor algorithm for TSP."""
    n = len(distance_matrix)
    visited = [False] * n
    route = [start]
    visited[start] = True
    total_distance = 0

    current = start
    for _ in range(n - 1):
        nearest = None
        min_dist = float('inf')

        for j in range(n):
            if not visited[j] and distance_matrix[current][j] < min_dist:
                nearest = j
                min_dist = distance_matrix[current][j]

        route.append(nearest)
        visited[nearest] = True
        total_distance += min_dist
        current = nearest

    # Return to start
    total_distance += distance_matrix[current][start]
    route.append(start)

    return route, total_distance

2-Opt Improvement

def two_opt(route, distance_matrix):
    """Improve route using 2-opt swaps."""
    improved = True
    best_route = route[:]

    while improved:
        improved = False
        for i in range(1, len(route) - 2):
            for j in range(i + 1, len(route) - 1):
                # Calculate change in distance
                d1 = distance_matrix[best_route[i-1]][best_route[i]]
                d2 = distance_matrix[best_route[j]][best_route[j+1]]
                d3 = distance_matrix[best_route[i-1]][best_route[j]]
                d4 = distance_matrix[best_route[i]][best_route[j+1]]

                if d3 + d4 < d1 + d2:
                    # Reverse segment between i and j
                    best_route[i:j+1] = reversed(best_route[i:j+1])
                    improved = True

    return best_route, calculate_route_distance(best_route, distance_matrix)

def calculate_route_distance(route, distance_matrix):
    """Calculate total distance of a route."""
    return sum(distance_matrix[route[i]][route[i+1]]
               for i in range(len(route) - 1))

Or-Opt Improvement

def or_opt(route, distance_matrix):
    """Improve route by relocating segments of 1-3 nodes."""
    best_route = route[:]
    best_distance = calculate_route_distance(best_route, distance_matrix)
    improved = True

    while improved:
        improved = False
        for segment_size in [1, 2, 3]:
            for i in range(1, len(route) - segment_size - 1):
                segment = best_route[i:i + segment_size]

                for j in range(1, len(route) - 1):
                    if j >= i and j <= i + segment_size:
                        continue

                    # Try moving segment to position j
                    new_route = (
                        best_route[:i] +
                        best_route[i + segment_size:j] +
                        segment +
                        best_route[j:]
                    )
                    new_distance = calculate_route_distance(new_route, distance_matrix)

                    if new_distance < best_distance:
                        best_route = new_route
                        best_distance = new_distance
                        improved = True

    return best_route, best_distance

Christofides Algorithm (For Metric TSP)

import networkx as nx

def christofides_tsp(distance_matrix):
    """Christofides algorithm with 1.5 approximation guarantee."""
    n = len(distance_matrix)
    G = nx.Graph()

    # Create complete graph
    for i in range(n):
        for j in range(i + 1, n):
            G.add_edge(i, j, weight=distance_matrix[i][j])

    # Find minimum spanning tree
    mst = nx.minimum_spanning_tree(G)

    # Find odd-degree vertices
    odd_vertices = [v for v in mst.nodes() if mst.degree(v) % 2 == 1]

    # Find minimum weight perfect matching on odd vertices
    subgraph = G.subgraph(odd_vertices)
    matching = nx.min_weight_matching(subgraph)

    # Combine MST and matching
    multigraph = nx.MultiGraph(mst)
    for u, v in matching:
        multigraph.add_edge(u, v, weight=distance_matrix[u][v])

    # Find Eulerian circuit
    euler_circuit = list(nx.eulerian_circuit(multigraph))

    # Convert to Hamiltonian path (skip repeated vertices)
    visited = set()
    path = []
    for u, v in euler_circuit:
        if u not in visited:
            path.append(u)
            visited.add(u)
    path.append(path[0])  # Return to start

    return path, calculate_route_distance(path, distance_matrix)

Distance Matrix Creation

def create_distance_matrix(locations):
    """Create distance matrix from (x, y) coordinates."""
    n = len(locations)
    matrix = np.zeros((n, n))

    for i in range(n):
        for j in range(n):
            if i != j:
                dx = locations[i][0] - locations[j][0]
                dy = locations[i][1] - locations[j][1]
                matrix[i][j] = np.sqrt(dx**2 + dy**2)

    return matrix

def create_manhattan_distance_matrix(locations):
    """Create Manhattan distance matrix for grid-based warehouses."""
    n = len(locations)
    matrix = np.zeros((n, n))

    for i in range(n):
        for j in range(n):
            matrix[i][j] = abs(locations[i][0] - locations[j][0]) + \
                          abs(locations[i][1] - locations[j][1])

    return matrix