[OSRM] Chat GPT와 함께하는 TSP

import json
import numpy as np

def tsp_greedy(distance_matrix):
    """
    Greedy TSP Algorithm
    :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

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

# Run the greedy TSP algorithm
optimal_route = tsp_greedy(distance_matrix)

# Print the results
print("Optimal Route:", optimal_route)

# 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)
)
# Add distance to return to the starting point
total_distance += distance_matrix[optimal_route[-1]][optimal_route[0]]

print("Total Distance:", total_distance)

TSP, Traveling Salesman Problem 은 짧은 지식으로나마 얘기 해본다면 영업사원이 여러 도시 혹은 지역을 한번 씩만 거쳐서 다시 집으로 돌아 올 수 있는 최적의 거리 계산이라고 할 수있을 것입니다.

물론, 여기에 여러가지 이야기들을 붙일 수도 있고 정의가 틀렸다고 할 수 있지만 뭐 저 나름의 생각이라고 치죠

질문은 다음과 같이 했습니다.

대한민국 서울 지역에 대한 pdf 파일을 이용해서 OSRM routd 서버를 구성하고, front end 를 Nodejs http-server를 웹서버로 클라이언트 leaflet 을 이용하여 경로 탐색 시스템을 구성 했습니다. 여기서 서울 지역을 랜덤하게 500 개 지점을 정한 후 TSP 알고리즘을 만들어 스케줄화 하고 싶습니다. 어떤 식의 구성이 가능하며, 데모 버전은 어떤 구성으로 시스템화 할 수 있는 지에 대해서 알려주세요

 

여기에 교수님의 답변 중심으로 이야기를 진행해보기로 했습니다. 코드는 그대로 가져다 쓰기로 합니다.

 

랜덤 지점 생성 - rnd_gener_seoul.py

import random
import json

# 서울 지역 대략적인 경계 좌표
LAT_RANGE = (37.4500, 37.7000)
LNG_RANGE = (126.8000, 127.1000)

def generate_random_points(num_points=500):
    points = [{"id": i, "lat": random.uniform(*LAT_RANGE), "lng": random.uniform(*LNG_RANGE)} for i in range(num_points)]
    return points

# 파일로 저장
with open("random_points.json", "w") as f:
    json.dump(generate_random_points(), f)

이런 느낌이네요..

 

거리 행렬 생성 - distance_mat.py

import requests
import json

OSRM_URL = "http://localhost:5000/table/v1/driving/"
with open("random_points.json", "r") as f:
    points = json.load(f)

coords = ";".join([f"{p['lng']},{p['lat']}" for p in points])
response = requests.get(f"{OSRM_URL}{coords}?annotations=distance")
distance_matrix = response.json()["distances"]

# 저장
with open("distance_matrix.json", "w") as f:
    json.dump(distance_matrix, f)

위 스크립트를 실행하기 전에 설치 해야 할 것들을 먼저 설치해야 합니다.

pacman -S mingw-w64-clang-x86_64-python-pip

python -m pip install requests

OSRM 백엔드 서버를 실행 합니다.

오류가 나네요

 

거리 행렬 생성 - distance_mat_fix.py

여기서, GET 방식만 지원한다고 하는 기본의 OSRM 의 경우 다음과 같이 코드를 다시 구성 할 수가 있다고 하네요

import requests
import json

OSRM_URL = "http://localhost:5000/table/v1/driving/"
MAX_POINTS = 100  # OSRM 요청 시 한 번에 처리 가능한 최대 지점 수 (권장값)

def split_points(points, batch_size):
    for i in range(0, len(points), batch_size):
        yield points[i:i + batch_size]

with open("random_points.json", "r") as f:
    points = json.load(f)

coords = [f"{p['lng']},{p['lat']}" for p in points]
distance_matrix = []

for batch in split_points(coords, MAX_POINTS):
    batch_coords = ";".join(batch)
    response = requests.get(f"{OSRM_URL}{batch_coords}?annotations=distance")
    if response.status_code == 200:
        distance_matrix.extend(response.json()["distances"])
    else:
        print("Error:", response.text)

# 저장
with open("distance_matrix.json", "w") as f:
    json.dump(distance_matrix, f)

이런 느낌이겠네요..

 

계속 진행해 보기로 합니다.

TSP 알고리즘 수행 - tsp_greedy.py

여기서는 greedy 하게 최단 경로만으로 계산되는 형태 이네요...

import numpy as np
import json

def tsp_greedy(distance_matrix):
    num_points = len(distance_matrix)
    visited = [False] * num_points
    route = [0]
    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

with open("distance_matrix.json", "r") as f:
    distance_matrix = json.load(f)
optimal_route = tsp_greedy(distance_matrix)
print("Optimal Route:", optimal_route)

 

numpy 가 필요하네요...아니나 다를

$ python tsp_greedy.py
Traceback (most recent call last):
  File "C:/DEV/GIS/OSRM/TSP/tsp_greedy.py", line 1, in <module>
    import numpy as np
ModuleNotFoundError: No module named 'numpy'

pacman -S mingw-w64-clang-x86_64-python-numpy

 

위코드에 오류가 있어서 오류 난다니까 고쳐 준 코드를 실행해도 문제가 발생해서 다시 물었더니, distance_matrix  생성이 잘 못 되었다고 합니다.

여하튼 여기까지는 오류로 끝나네요...