2-opt tsp

tsp.gif

tsp.py

import random

import matplotlib.animation as animation
import matplotlib.pyplot as plt

capitals = {
    'AL': (32.3777, -86.3006),  # Montgomery, Alabama
    'AK': (58.3019, -134.4197),  # Juneau, Alaska
    'AZ': (33.4484, -112.0740),  # Phoenix, Arizona
    'AR': (34.7465, -92.2896),  # Little Rock, Arkansas
    'CA': (38.5767, -121.4934),  # Sacramento, California
    'CO': (39.7392, -104.9903),  # Denver, Colorado
    'CT': (41.7670, -72.6770),  # Hartford, Connecticut
    'DE': (39.1619, -75.5267),  # Dover, Delaware
    'FL': (30.4383, -84.2807),  # Tallahassee, Florida
    'GA': (33.7490, -84.3880),  # Atlanta, Georgia
    'HI': (21.3074, -157.8574),  # Honolulu, Hawaii
    'ID': (43.6166, -116.2008),  # Boise, Idaho
    'IL': (39.7984, -89.6548),  # Springfield, Illinois
    'IN': (39.7684, -86.1581),  # Indianapolis, Indiana
    'IA': (41.6005, -93.6091),  # Des Moines, Iowa
    'KS': (39.0481, -95.6778),  # Topeka, Kansas
    'KY': (38.1867, -84.8753),  # Frankfort, Kentucky
    'LA': (30.4583, -91.1403),  # Baton Rouge, Louisiana
    'ME': (44.3078, -69.7824),  # Augusta, Maine
    'MD': (38.9786, -76.4911),  # Annapolis, Maryland
    'MA': (42.3582, -71.0637),  # Boston, Massachusetts
    'MI': (42.7336, -84.5555),  # Lansing, Michigan
    'MN': (44.9551, -93.1022),  # Saint Paul, Minnesota
    'MS': (32.2988, -90.1848),  # Jackson, Mississippi
    'MO': (38.5767, -92.1735),  # Jefferson City, Missouri
    'MT': (46.5958, -112.0270),  # Helena, Montana
    'NE': (40.8090, -96.6789),  # Lincoln, Nebraska
    'NV': (39.1608, -119.7539),  # Carson City, Nevada
    'NH': (43.2067, -71.5381),  # Concord, New Hampshire
    'NJ': (40.2206, -74.7597),  # Trenton, New Jersey
    'NM': (35.6672, -105.9644),  # Santa Fe, New Mexico
    'NY': (42.6526, -73.756),  # Albany, New York
    'NC': (35.7804, -78.6391),  # Raleigh, North Carolina
    'ND': (46.8083, -100.7837),  # Bismarck, North Dakota
    'OH': (39.9612, -82.9988),  # Columbus, Ohio
    'OK': (35.4822, -97.5350),  # Oklahoma City, Oklahoma
    'OR': (44.9429, -123.0351),  # Salem, Oregon
    'PA': (40.2697, -76.8756),  # Harrisburg, Pennsylvania
    'RI': (41.8230, -71.4189),  # Providence, Rhode Island
    'SC': (34.0007, -81.0348),  # Columbia, South Carolina
    'SD': (44.3680, -100.3364),  # Pierre, South Dakota
    'TN': (36.1627, -86.7816),  # Nashville, Tennessee
    'TX': (30.2672, -97.7431),  # Austin, Texas
    'UT': (40.7608, -111.8910),  # Salt Lake City, Utah
    'VT': (44.2601, -72.5754),  # Montpelier, Vermont
    'VA': (37.5407, -77.4360),  # Richmond, Virginia
    'WA': (47.0425, -122.8931),  # Olympia, Washington
    'WV': (38.3498, -81.6326),  # Charleston, West Virginia
    'WI': (43.0747, -89.3843),  # Madison, Wisconsin
    'WY': (41.1456, -104.8020)  # Cheyenne, Wyoming
}

def tsp(cities: list[tuple[float, float]]) -> tuple[list[int], float]:
    """
    Solve the Traveling Salesman Problem (TSP) using the 2-opt algorithm.

    Args:
        cities: A list of tuples representing the (x, y) coordinates of each city.

    Returns:
        A tuple containing the optimal path that visits all cities exactly once, represented as a list of city indices,
        and the length of the optimal path.
    """
    n = len(cities)
    path = list(range(n))
    random.shuffle(path)  # Initialize path randomly

    def get_path_length(path: list[int]) -> float:
        """Calculate the length of a given path."""
        return sum(distance(cities[path[i]], cities[path[i+1]]) for i in range(-1, n-1))

    def distance(city1: tuple[float, float], city2: tuple[float, float]) -> float:
        """Calculate the Euclidean distance between two cities."""
        return ((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2) ** 0.5

    # Iterate until no further improvements can be made
    improvement = True
    path_history = [path]
    while improvement:
        improvement = False
        for i in range(n - 1):
            for j in range(i + 1, n):
                # Reverse the path between city i and j and check if the resulting path is shorter
                new_path = path[:i] + path[i:j+1][::-1] + path[j+1:]
                new_length = get_path_length(new_path)
                if new_length < get_path_length(path):
                    path = new_path
                    path_history.append(new_path)
                    improvement = True
                    break
            if improvement:
                break

    return path_history, get_path_length(path)


def plot_tsp_path(cities: list[tuple[float, float]], list_path: list[list[int]], capitals: dict[str, tuple[float, float]]) -> None:
    """
    Plot the cities in USA and the path generated by the TSP solver using Matplotlib.

    Args:
        cities: A list of tuples representing the (latitude, longitude) coordinates of each city.
        list_path: A list of lists of city indices representing the optimal paths to be rendered one by one.
        capitals: A dictionary mapping state codes to the (latitude, longitude) coordinates of their respective capital cities.
    """
    fig, ax = plt.subplots()

    # Extract the latitude and longitude coordinates of each city
    latitudes = [city[0] for city in cities]
    longitudes = [city[1] for city in cities]

    def animate(i):
        path = list_path[i]
        ax.clear()

        # Create a scatter plot of the cities and add labels for each city using the corresponding state capital
        for j in range(len(cities)):
            x, y = longitudes[j], latitudes[j]
            label = list(capitals.keys())[list(capitals.values()).index((y, x))]
            ax.scatter(x, y, label=label)

            # Add a label for the city using the corresponding state capital
            ax.annotate(
                label,  # Text of the label
                xy=(x, y),  # Position of the city dot
                xytext=(x + 0.2, y + 0.2),  # Position of the label relative to the city dot
                fontsize=8,  # Font size of the label
                color='black',  # Color of the label
                ha='left',  # Horizontal alignment of the label
                va='center'  # Vertical alignment of the label
            )

        # Plot the optimal path as a red line
        for j in range(len(path) - 1):
            start = path[j]
            end = path[j + 1]
            x_start, y_start = longitudes[start], latitudes[start]
            x_end, y_end = longitudes[end], latitudes[end]
            ax.plot([x_start, x_end], [y_start, y_end], color='red')

        # Plot the final edge connecting the last and first cities
        x_start, y_start = longitudes[path[-1]], latitudes[path[-1]]
        x_end, y_end = longitudes[path[0]], latitudes[path[0]]
        ax.plot([x_start, x_end], [y_start, y_end], color='red')

        # Set the x and y limits of the plot to encompass all cities with same scale
        max_range = max(max(longitudes) - min(longitudes), max(latitudes) - min(latitudes))
        ax.set_xlim(min(longitudes) - 0.1 * max_range, max(longitudes) + 0.1 * max_range)
        ax.set_ylim(min(latitudes) - 0.1 * max_range, max(latitudes) + 0.1 * max_range)

        # Add axis labels and legend
        ax.set_xlabel('Longitude')
        ax.set_ylabel('Latitude')
    
    # Create an animation using the `animate` function and save it as a GIF
    ani = animation.FuncAnimation(fig, animate, frames=len(list_path), interval=50, repeat=True)
    ani.save('tsp.gif')

# Example usage
cities = list(capitals.values())
path_history, length = tsp(cities)
print("Optimal path:", path_history[-1])
print("Optimal length:", length)
plot_tsp_path(cities, path_history, capitals)