[OSRM] Chat GPT와 함께하는 TSP - 마무리

이제 TSP에 대해서 잘 알아보기로 했습니다. 이제 전체적으로 어떤 방법으로 이런 이야기를 진행해 왔는 지 돌아보고

하나씩 순서대로 따라가보는 것으로 마무리 하는 것으로 하겠습니다.

 

1. OSRM - 경로 탐색 엔진

 

Project OSRM

 

Open Source Routing Machine 이란 오픈 소스를 빌드 하는 것부터 시작 했습니다. 왜냐하면 경로를 탐색해야 얼마나 이를 정리 해야 할 지가 나오기 때문에 경로 탐색 할 수 있는 엔진이 필요 했었고, OSRM 을 이 엔진으로 선정했습니다.

오픈소스 생태계에서 오픈스트리트 맵을 이용해서 경로 탐색을 할 수 있다는 것이 큰 이득이 아닐까 합니다.

 

2. vroom - TSP 엔진

이제 경로 탐색 엔진을 구성 했으니, 실제 이 경로 탐색 엔진을 이용해서 TSP 를 구현 해 줄 시스템이 필요 합니다. 여기서는 그냥 쌩(?)으로 구현해 보았으나, 이는 궁금증만 더 증폭 시킬 수 있는 노릇입니다.

따라서, 오픈소스로 OSRM과 호환 될 수 있는 엔진이 필요 했습니다.

 

VROOM - Vehicle Routing Open-source Optimization Machine

 

3. TSP 를 위한 데이터

이 알고리즘에 들어가는 입력 데이터를 말합니다. 이는 생성해야만 하는 데, 여러가지 소스를 이용해서 구할 수도 있을 것입니다. 요즘은 오픈 API 가 활성화 되어 있는 곳이 많아서 거기서 얻어도 되지만 Chat GPT 교수님께 여쭤 보았습니다.

강동구 어딘가를 한번 물어 보았습니다.

{
  "vehicles": [
    {
      "id": 1,
      "start": [127.123289, 37.538416],  // 천호동 중심
      "end": [127.123289, 37.538416]    // 천호동 중심
    }
  ],
  "jobs": [
    { "id": 1, "location": [127.123289, 37.538416] },  // 천호동
    { "id": 2, "location": [127.129153, 37.551052] },  // 암사동
    { "id": 3, "location": [127.137241, 37.528131] },  // 둔촌동
    { "id": 4, "location": [127.143545, 37.548152] },  // 명일동
    { "id": 5, "location": [127.140395, 37.538827] },  // 길동
    { "id": 6, "location": [127.127874, 37.537267] },  // 성내동
    { "id": 7, "location": [127.156823, 37.561231] },  // 고덕동
    { "id": 8, "location": [127.166023, 37.556111] },  // 상일동
    { "id": 9, "location": [127.176654, 37.565231] },  // 강일동
    { "id": 10, "location": [127.120500, 37.540000] },  // 기타 동 (예시)
    { "id": 11, "location": [127.130000, 37.550000] },
    { "id": 12, "location": [127.135000, 37.545000] },
    { "id": 13, "location": [127.140000, 37.535000] },
    { "id": 14, "location": [127.150000, 37.525000] },
    { "id": 15, "location": [127.160000, 37.555000] },
    { "id": 16, "location": [127.170000, 37.565000] },
    { "id": 17, "location": [127.123500, 37.540500] },
    { "id": 18, "location": [127.127500, 37.537500] },
    { "id": 19, "location": [127.129500, 37.550500] },
    { "id": 20, "location": [127.133500, 37.543500] },
    { "id": 21, "location": [127.138500, 37.548500] },
    { "id": 22, "location": [127.143500, 37.553500] },
    { "id": 23, "location": [127.148500, 37.558500] },
    { "id": 24, "location": [127.153500, 37.563500] },
    { "id": 25, "location": [127.158500, 37.568500] },
    { "id": 26, "location": [127.163500, 37.573500] },
    { "id": 27, "location": [127.168500, 37.578500] },
    { "id": 28, "location": [127.123789, 37.539789] },
    { "id": 29, "location": [127.130789, 37.540789] },
    { "id": 30, "location": [127.140789, 37.545789] },
    { "id": 31, "location": [127.150789, 37.550789] },
    { "id": 32, "location": [127.160789, 37.555789] },
    { "id": 33, "location": [127.123345, 37.541234] },
    { "id": 34, "location": [127.129234, 37.546123] },
    { "id": 35, "location": [127.135234, 37.551234] },
    { "id": 36, "location": [127.145234, 37.556234] },
    { "id": 37, "location": [127.155234, 37.561234] },
    { "id": 38, "location": [127.165234, 37.566234] },
    { "id": 39, "location": [127.123678, 37.540678] },
    { "id": 40, "location": [127.129678, 37.545678] },
    { "id": 41, "location": [127.135678, 37.550678] },
    { "id": 42, "location": [127.145678, 37.555678] },
    { "id": 43, "location": [127.155678, 37.560678] },
    { "id": 44, "location": [127.165678, 37.565678] },
    { "id": 45, "location": [127.123890, 37.540890] },
    { "id": 46, "location": [127.129890, 37.545890] },
    { "id": 47, "location": [127.135890, 37.550890] },
    { "id": 48, "location": [127.145890, 37.555890] },
    { "id": 49, "location": [127.155890, 37.560890] },
    { "id": 50, "location": [127.165890, 37.565890] }
  ]
}

 

4. TSP 수행

다음 명령어로 TSP 를 수행 해 줍니다. 최신 버전을 빌드 했더니 예전 버전과 옵션이 차이가 좀 있네요

vroom.exe -i C:\DEV\GIS\OSRM_exec\osrm_data\tsp\input_gangdong.json -o C:\DEV\GIS\OSRM_exec\osrm_data\tsp\output_gangdong.json -a "localhost" -p 5000

다 수행하면 output_gangdong.json 파일이 만들어 집니다.

5. Nodejs 설치

일단 위의 결과를 확인하기 위해서 ' 6. TSP 수행 결과 확인하기' 을 진행하면 되는 데, 보안 상의 문제로 인해서 웹서버를 실제 구동해야만 합니다. 따라서 Nodejs에서 제공하는 http server 를 설치하여 구동 하기로 합니다.

 

6. TSP 수행 결과 확인하기

수행 결과를 오픈스트리트 맵 상에 표출하기 위해서 다음 코드가 필요 합니다.

<!DOCTYPE html>
<html>
<head>
  <title>VROOM Output Map</title>
  <!--
  <link rel="stylesheet" href="https://unpkg.com/leaflet@1.9.4/dist/leaflet.css" />
  !-->
  <link rel="stylesheet" href="leaflet.css" />
  <style>
    #map {
      height: 100vh;
    }
  </style>
</head>
<body>
  <div id="map"></div>
  <!--
  <script src="https://unpkg.com/leaflet@1.9.4/dist/leaflet.js"></script>
  !-->
  <script src="leaflet.js"></script>
  <script src="output.json" type="application/json"></script>
  <script>
    // 지도 초기화
    const map = L.map('map').setView([37.566535, 126.977969], 10); // 서울 중심 좌표

    // OpenStreetMap 타일 추가
    L.tileLayer('https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
      maxZoom: 19
    }).addTo(map);

    // VROOM Output.json 불러오기
    fetch("output.json")
      .then(response => response.json())
      .then(data => {
        // Marker 및 경로 시각화
        data.routes.forEach(route => {
          // 각 경로의 경로선
          const coordinates = route.steps.map(step => [step.location[1], step.location[0]]);
          const polyline = L.polyline(coordinates, { color: 'blue' }).addTo(map);

          // 각 경로의 시작 및 끝 위치
          L.marker(coordinates[0], { title: `Start - Route ${route.vehicle}` }).addTo(map);
          L.marker(coordinates[coordinates.length - 1], { title: `End - Route ${route.vehicle}` }).addTo(map);

          // 방문 지점 마커
          route.steps.forEach((step, index) => {
            L.marker([step.location[1], step.location[0]], {
              title: `Step ${index + 1}: Job ${step.id}`
            }).addTo(map);
          });
        });

        // 지도 경계 조정
        const allCoordinates = data.routes.flatMap(route =>
          route.steps.map(step => [step.location[1], step.location[0]])
        );
        const bounds = L.latLngBounds(allCoordinates);
        map.fitBounds(bounds);
      })
      .catch(err => console.error("Error loading output.json:", err));
  </script>
</body>
</html>

결과를 확인 해 봅니다

http://localhost:8080/tsp_viewer.html

 

7. TSP 의 실제 경로 탐색 수행

사실 위의 모습은 실제 우리 세계에서 올바른 모습은 아닐 것입니다. 그냥 선만 이어놓은 것에 불과 하니까요. 따라서 어느 정도 경로가 어떻게 이어 졌는 지에 대해서 확인 해 볼 필요가 있겠죠.

nodejs 를 설치 하였기 때문에, 이에 관련 된 모듈을 설치하여 경로 탐색 엔진에 요청해서 실제 경로를 불러와야 할 것입니다. 다음 모듈을 설치해 줍니다.

npm npm install axios

그런 다음 위의 input.json을 활용하여 경로탐색 엔진으로 요청하는 코드가 다음과 같이 필요 합니다.

const axios = require('axios');
const fs = require('fs');

// OSRM 서버 URL
const osrmUrl = 'http://localhost:5000/route/v1/driving';

// VROOM output.json 경로
const outputJsonPath = 'output.json'; // 실제 경로로 변경
const routeJsonPath = 'route.json'; // 저장할 경로 설정

// OSRM 경로 요청 함수
async function getRouteFromOSRM(coords) {
  const url = `${osrmUrl}/${coords.join(';')}?overview=full&geometries=geojson`;
  try {
    const response = await axios.get(url);
    if (!response.data || !response.data.routes || response.data.routes.length === 0) {
      console.error('OSRM 응답 데이터가 비어 있습니다.');
      return null;
    }
    return response.data.routes[0]; // 첫 번째 경로 반환
  } catch (error) {
    console.error('OSRM 요청 실패:', error.message);
    return null;
  }
}

// VROOM output.json 처리 및 route.json 저장
async function processVroomOutput() {
  try {
    const data = JSON.parse(fs.readFileSync(outputJsonPath, 'utf8'));

    if (!data.routes || data.routes.length === 0) {
      console.error('VROOM output에 경로 정보가 없습니다.');
      return;
    }

    const steps = data.routes[0].steps; // 첫 번째 경로의 steps 가져오기
    const sequence = steps.map(step => step.location); // 좌표 추출

    console.log('경로 계산 및 저장을 시작합니다...');
    const routeData = [];

    for (let i = 0; i < sequence.length - 1; i++) {
      const coords = [sequence[i], sequence[i + 1]].map(loc => loc.join(','));
      const route = await getRouteFromOSRM(coords);
      if (route) {
        routeData.push({
          from: sequence[i],
          to: sequence[i + 1],
          distance: route.legs[0].distance,
          duration: route.legs[0].duration,
          geometry: route.geometry
        });
      }
    }

    // route.json 파일로 저장
    fs.writeFileSync(routeJsonPath, JSON.stringify(routeData, null, 2));
    console.log(`경로 데이터가 ${routeJsonPath}에 저장되었습니다.`);
  } catch (error) {
    console.error('Error processing VROOM output:', error.message);
  }
}

// 실행
processVroomOutput();

 

그런 다음 다음과 같이 실행해 줍시다.

node tsp_route_out.js

C:\DEV\GIS\OSRM_exec\TSP>node tsp_route_out.js
경로 계산 및 저장을 시작합니다...
경로 데이터가 route.json에 저장되었습니다.

 

결과를 확인 해 봅시다.

 

여기까지가 기본적으로 만들어본 TSP 알고리즘의 구현 시스템이었습니다. 최소한 내가 아는 한...

이상.