[OSRM] Chat GPT와 함께하는 TSP - 2

저번 글에서 실패한 내용을 다시 해 봅시다. 일단 슈퍼맨 같은 세일즈맨이 하루에 500 곳 영업이 가능하다고 치고...

 

[OSRM] Chat GPT와 함께하는 TSP

 

매트릭스를 만들어 내는 코드를 다음과 같이 작성해 주었습니다. - 1_full_distance_matrix_seoul.py

import requests
import json
import time

# OSRM URL
OSRM_URL = "http://localhost:5000/table/v1/driving/"
MAX_BATCH_SIZE = 20  # 배치 크기 20으로 설정
TIMEOUT = 30  # 30초 타임아웃 설정

def fetch_distance_matrix(points):
    """
    Generate a full distance matrix by batching OSRM requests.
    :param points: List of coordinates (longitude, latitude)
    :return: 500x500 distance matrix
    """
    num_points = len(points)
    matrix = [[0] * num_points for _ in range(num_points)]  # Initialize a matrix of zeros
    cnt = 0  # Initialize cnt to track batch requests

    # Loop through the matrix in batches for rows (i) and columns (j)
    for i in range(0, num_points, MAX_BATCH_SIZE):  # Loop for rows (i)
        for j in range(0, num_points, MAX_BATCH_SIZE):  # Loop for columns (j)
            # Define batch points for the current section
            batch_points = points[i:i + MAX_BATCH_SIZE]
            batch_targets = points[j:j + MAX_BATCH_SIZE]
            
            # Construct coordinates for the OSRM request
            coords = ";".join(f"{p[0]},{p[1]}" for p in batch_points + batch_targets)
            try:
                # Request distances between the batch points with a timeout to prevent hanging
                response = requests.get(f"{OSRM_URL}{coords}?annotations=distance", timeout=TIMEOUT)
                
                # Raise an exception for unsuccessful responses
                response.raise_for_status()

                # Parse the distances and fill the matrix
                distances = response.json()["distances"]
                cnt += 1  # Increase cnt by 1 for each batch request
                print(f"Processing batch {cnt}: i={i} j={j}")  # Show cnt for each batch

                for m, row in enumerate(distances):
                    for n, value in enumerate(row):
                        # Ensure the indices are within bounds
                        if i + m < num_points and j + n < num_points:
                            matrix[i + m][j + n] = value

                # Adding delay to avoid overwhelming the server
                time.sleep(1)  # 1 second delay between requests
                
                # Close the response explicitly to release network resources
                response.close()

            except requests.exceptions.RequestException as e:
                print(f"Error fetching data for batch {i}-{j}: {e}")
                break  # Break out of the loop on error to avoid infinite retries

    return matrix

# Example coordinates (500 random points in Seoul)
coordinates = [
    [126.9780 + (i % 5) * 0.01, 37.5665 + (i // 5) * 0.01] for i in range(500)
]

# Generate the distance matrix
full_distance_matrix = fetch_distance_matrix(coordinates)

# Save the result
with open("full_distance_matrix.json", "w") as f:
    json.dump(full_distance_matrix, f)

print("500x500 distance matrix successfully generated and saved.")

 

TSP 알고리즘 수행 -  2_greedy_tsp_seoul.py

import json
import numpy as np

# Load the distance matrix from the file
with open("full_distance_matrix.json", "r") as file:
    distance_matrix = json.load(file)

def tsp_greedy(distance_matrix):
    """
    Greedy Algorithm for solving the Traveling Salesman Problem (TSP).
    :param distance_matrix: 2D list or numpy array of distances
    :return: List of visited node indices in order
    """
    num_points = len(distance_matrix)
    visited = [False] * num_points
    route = [0]  # Start from the first node
    visited[0] = True

    for _ in range(1, num_points):
        last = route[-1]
        next_city = np.argmin([
            distance_matrix[last][j] if not visited[j] else float('inf')
            for j in range(num_points)
        ])
        visited[next_city] = True
        route.append(next_city)

    return route

# Run the Greedy TSP Algorithm
optimal_route = tsp_greedy(distance_matrix)

# Calculate the total distance of the route
total_distance = sum(
    distance_matrix[optimal_route[i]][optimal_route[i + 1]]
    for i in range(len(optimal_route) - 1)
)
total_distance += distance_matrix[optimal_route[-1]][optimal_route[0]]  # Return to start

print(f"Optimal route: {optimal_route}")
print(f"Total distance: {total_distance}")

# Convert numpy int64 values to native Python int before dumping to JSON
optimal_route = [int(i) for i in optimal_route]

# Optionally, save the optimal route to a file
with open("optimal_route.json", "w") as f:
    json.dump(optimal_route, f)

print("Optimal route saved to optimal_route.json")

 

만들어진 파일을 표시하기 위해서 geojson 형태로 변환하기 - 3_to_geojson_seoul.py

import json
import numpy as np

# Load the distance matrix from the file
with open("full_distance_matrix.json", "r") as file:
    distance_matrix = json.load(file)

def tsp_greedy(distance_matrix):
    """
    Greedy Algorithm for solving the Traveling Salesman Problem (TSP).
    :param distance_matrix: 2D list or numpy array of distances
    :return: List of visited node indices in order
    """
    num_points = len(distance_matrix)
    visited = [False] * num_points
    route = [0]  # Start from the first node
    visited[0] = True

    for _ in range(1, num_points):
        last = route[-1]
        next_city = np.argmin([
            distance_matrix[last][j] if not visited[j] else float('inf')
            for j in range(num_points)
        ])
        visited[next_city] = True
        route.append(next_city)

    return route

# Run the Greedy TSP Algorithm to get the optimal route
optimal_route = tsp_greedy(distance_matrix)

# Calculate the total distance of the route
total_distance = sum(
    distance_matrix[optimal_route[i]][optimal_route[i + 1]]
    for i in range(len(optimal_route) - 1)
)
total_distance += distance_matrix[optimal_route[-1]][optimal_route[0]]  # Return to start

print(f"Optimal route: {optimal_route}")
print(f"Total distance: {total_distance}")

# Convert optimal_route to native Python int before dumping to JSON
optimal_route = [int(i) for i in optimal_route]

# Optionally, save the optimal route to a file
with open("optimal_route.json", "w") as f:
    json.dump(optimal_route, f)

print("Optimal route saved to optimal_route.json")

# Now we generate the GeoJSON for the optimal route
coordinates = [
    [126.9780 + (i % 5) * 0.01, 37.5665 + (i // 5) * 0.01] for i in range(500)
]  # Example coordinates for Seoul

# Create GeoJSON data
geojson_data = {
    "type": "FeatureCollection",
    "features": [
        {
            "type": "Feature",
            "geometry": {
                "type": "LineString",
                "coordinates": [coordinates[i] for i in optimal_route]
            },
            "properties": {"name": "Optimal Route"}
        }
    ]
}

# Save GeoJSON to file
with open("optimal_route.geojson", "w") as geojson_file:
    json.dump(geojson_data, geojson_file)

print("GeoJSON for optimal route saved.")

 

이 파일을 통해 수행된 결과를 확인 할 수 있는 파일 - 4_tsp_view_seoul.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Optimal TSP Route</title>
    <link rel="stylesheet" href="https://unpkg.com/leaflet@1.9.4/dist/leaflet.css" />
    <style>
        #map {
            width: 100%;
            height: 600px;
        }
    </style>
</head>
<body>
    <h1>Optimal TSP Route Visualization</h1>
    <div id="map"></div>

    <script src="https://unpkg.com/leaflet@1.9.4/dist/leaflet.js"></script>
    <script>
        // Initialize the map centered on Seoul (adjust the coordinates as needed)
        const map = L.map('map').setView([37.5665, 126.9780], 12); // Latitude, Longitude of Seoul
        
        // Use OpenStreetMap tile layer
        L.tileLayer('https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
            attribution: '&copy; <a href="https://www.openstreetmap.org/copyright">OpenStreetMap</a> contributors'
        }).addTo(map);

        // Load the GeoJSON file (optimal_route.geojson)
        fetch('optimal_route.geojson')
            .then(response => response.json())
            .then(data => {
                // Add the GeoJSON to the map
                L.geoJSON(data, {
                    style: {
                        color: "blue",
                        weight: 4,
                        opacity: 0.7
                    }
                }).addTo(map);
            })
            .catch(error => console.error("Error loading GeoJSON: ", error));
    </script>
</body>
</html>

 

서버 시작

 

결과물 확인

마지막으로 결과물을 확인 합니다.

 

뭔가 잘 못 되었네요...ㅋㅋㅋ

이상.