Traveling Salesman Problem (TSP) using the 2-opt algorithm (Japan's prefectoral capital) 都道府県庁所在地の巡回セールスマン

tsp.py

import random

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

capitals = {
    'Hokkaido': (43.0646, 141.3468),
    'Aomori': (40.8246, 140.7406),
    'Iwate': (39.7036, 141.1527),
    'Miyagi': (38.2688, 140.8721),
    'Akita': (39.7186, 140.1023),
    'Yamagata': (38.2404, 140.3636),
    'Fukushima': (37.7499, 140.4675),
    'Ibaraki': (36.3418, 140.4468),
    'Tochigi': (36.5658, 139.8836),
    'Gunma': (36.3912, 139.0609),
    'Saitama': (35.8617, 139.6455),
    'Chiba': (35.6047, 140.1233),
    'Tokyo': (35.6895, 139.6917),
    'Kanagawa': (35.4478, 139.6425),
    'Niigata': (37.9161, 139.0364),
    'Toyama': (36.6953, 137.2137),
    'Ishikawa': (36.5947, 136.6256),
    'Fukui': (36.0652, 136.2214),
    'Yamanashi': (35.6642, 138.5689),
    'Nagano': (36.2384, 138.5400),
    'Gifu': (35.4233, 136.7606),
    'Shizuoka': (34.9769, 138.3831),
    'Aichi': (35.1802, 136.9066),
    'Mie': (34.7303, 136.5086),
    'Shiga': (35.0044, 135.8683),
    'Kyoto': (35.0116, 135.7681),
    'Osaka': (34.6937, 135.5023),
    'Hyogo': (34.6913, 135.1830),
    'Nara': (34.6851, 135.8048),
    'Wakayama': (34.2260, 135.1675),
    'Tottori': (35.5031, 134.2372),
    'Shimane': (35.4723, 133.0505),
    'Okayama': (34.6551, 133.9190),
    'Hiroshima': (34.3853, 132.4553),
    'Yamaguchi': (34.1785, 131.4738),
    'Tokushima': (34.0704, 134.5547),
    'Kagawa': (34.3401, 134.0438),
    'Ehime': (33.8416, 132.7656),
    'Kochi': (33.5597, 133.5311),
    'Fukuoka': (33.5903, 130.4017),
    'Saga': (33.2494, 130.2988),
    'Nagasaki': (32.7503, 129.8779),
    'Kumamoto': (32.8032, 130.7079),
    'Oita': (33.2382, 131.6126),
    'Miyazaki': (31.9111, 131.4239),
    'Kagoshima': (31.5968, 130.5579),
    'Okinawa': (26.2124, 127.6809)
}



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)