Given a matrix and route, function improves route using 2-opt heuristic: reverses segments, reduce total travel distance.

# Traveling Salesman Problem - 2-Opt Heuristic # Description: Given a distance matrix and an initial route, this function improves the route using the 2-opt heuristic by reversing segments to reduce the total travel distance. # Traveling Salesman Problem (TSP) - 2-Opt Heuristic Optimization def calculate_route_distance(route, distance_matrix): """ Calculate the total distance of a route, including return to the starting city. Args: route (list of int): Ordered list of city indices distance_matrix (list of list of float): Matrix of distances between cities Returns: float: Total route distance """ total_distance = 0 route_length = len(route) # Sum distances between consecutive cities for i in range(route_length - 1): total_distance += distance_matrix[route[i]][route[i + 1]] # Add distance from last city back to first city (complete the tour) total_distance += distance_matrix[route[-1]][route[0]] return total_distance def tsp_2opt(initial_route, distance_matrix, max_iterations=100): """ Optimize a TSP route using the 2-opt heuristic algorithm. The 2-opt algorithm improves a route by: 1. Selecting two edges in the current route 2. Removing these edges 3. Reconnecting the route in a different way 4. Keeping the change if it reduces total route distance Args: initial_route (list of int): Starting route of city indices distance_matrix (list of list of float): Distances between cities max_iterations (int, optional): Maximum number of optimization iterations Returns: tuple: (optimized_route, total_distance) Time Complexity: O(n^3), where n is the number of cities Space Complexity: O(n) """ # Validate inputs if not initial_route or len(initial_route) < 3: return initial_route, calculate_route_distance(initial_route, distance_matrix) # Current best solution best_route = initial_route.copy() best_distance = calculate_route_distance(best_route, distance_matrix) # Track improvement flag improved = True iterations = 0 # Continue until no improvement or max iterations reached while improved and iterations < max_iterations: improved = False # Try all possible 2-opt swaps for i in range(1, len(best_route) - 1): for j in range(i + 1, len(best_route)): # Create a new route by reversing the segment between i and j new_route = ( best_route[:i] + # Cities before swap point best_route[i:j+1][::-1] + # Reversed segment best_route[j+1:] # Cities after swap point ) # Calculate new route distance new_distance = calculate_route_distance(new_route, distance_matrix) # Update if improved if new_distance < best_distance: best_route = new_route best_distance = new_distance improved = True break # Exit outer loop if improvement found if improved: break iterations += 1 return best_route, best_distance # Demonstration function def demonstrate_tsp_2opt(): """ Demonstrate the 2-opt TSP optimization with sample distance matrix. """ # Example distance matrix (symmetric) distance_matrix = [ [0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0] ] # Initial route initial_route = [0, 1, 2, 3] print("Initial Route:") print(f"Route: {initial_route}") print(f"Distance: {calculate_route_distance(initial_route, distance_matrix)}") # Optimize route optimized_route, optimized_distance = tsp_2opt(initial_route, distance_matrix) print("\nOptimized Route:") print(f"Route: {optimized_route}") print(f"Distance: {optimized_distance}")

Mar 28, 2025 - 04:49

Given a matrix and route, function improves route using 2-opt heuristic: reverses segments, reduce total travel distance.

# Traveling Salesman Problem - 2-Opt Heuristic
# Description: Given a distance matrix and an initial route, this function improves the route using the 2-opt heuristic by reversing segments to reduce the total travel distance.

# Traveling Salesman Problem (TSP) - 2-Opt Heuristic Optimization
def calculate_route_distance(route, distance_matrix):
    """
    Calculate the total distance of a route, including return to the starting city.

    Args:
        route (list of int): Ordered list of city indices
        distance_matrix (list of list of float): Matrix of distances between cities

    Returns:
        float: Total route distance
    """
    total_distance = 0
    route_length = len(route)

    # Sum distances between consecutive cities
    for i in range(route_length - 1):
        total_distance += distance_matrix[route[i]][route[i + 1]]

    # Add distance from last city back to first city (complete the tour)
    total_distance += distance_matrix[route[-1]][route[0]]

    return total_distance

def tsp_2opt(initial_route, distance_matrix, max_iterations=100):
    """
    Optimize a TSP route using the 2-opt heuristic algorithm.

    The 2-opt algorithm improves a route by:
    1. Selecting two edges in the current route
    2. Removing these edges
    3. Reconnecting the route in a different way
    4. Keeping the change if it reduces total route distance

    Args:
        initial_route (list of int): Starting route of city indices
        distance_matrix (list of list of float): Distances between cities
        max_iterations (int, optional): Maximum number of optimization iterations

    Returns:
        tuple: (optimized_route, total_distance)

    Time Complexity: O(n^3), where n is the number of cities
    Space Complexity: O(n)
    """
    # Validate inputs
    if not initial_route or len(initial_route) < 3:
        return initial_route, calculate_route_distance(initial_route, distance_matrix)

    # Current best solution
    best_route = initial_route.copy()
    best_distance = calculate_route_distance(best_route, distance_matrix)

    # Track improvement flag
    improved = True
    iterations = 0

    # Continue until no improvement or max iterations reached
    while improved and iterations < max_iterations:
        improved = False

        # Try all possible 2-opt swaps
        for i in range(1, len(best_route) - 1):
            for j in range(i + 1, len(best_route)):
                # Create a new route by reversing the segment between i and j
                new_route = (
                    best_route[:i] +  # Cities before swap point
                    best_route[i:j+1][::-1] +  # Reversed segment
                    best_route[j+1:]  # Cities after swap point
                )

                # Calculate new route distance
                new_distance = calculate_route_distance(new_route, distance_matrix)

                # Update if improved
                if new_distance < best_distance:
                    best_route = new_route
                    best_distance = new_distance
                    improved = True
                    break

            # Exit outer loop if improvement found
            if improved:
                break

        iterations += 1

    return best_route, best_distance

# Demonstration function
def demonstrate_tsp_2opt():
    """
    Demonstrate the 2-opt TSP optimization with sample distance matrix.
    """
    # Example distance matrix (symmetric)
    distance_matrix = [
        [0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]
    ]

    # Initial route
    initial_route = [0, 1, 2, 3]

    print("Initial Route:")
    print(f"Route: {initial_route}")
    print(f"Distance: {calculate_route_distance(initial_route, distance_matrix)}")

    # Optimize route
    optimized_route, optimized_distance = tsp_2opt(initial_route, distance_matrix)

    print("\nOptimized Route:")
    print(f"Route: {optimized_route}")
    print(f"Distance: {optimized_distance}")