한국 술집 81,998곳을 모두 도는 최단 도보 경로

 (math.uwaterloo.ca)
2P by GN⁺ | ★ favorite | 댓글 2개
  • 한국 전역의 술집 81,998곳을 모두 걸어서 방문하는 외판원 문제(TSP)가 풀렸고, OSRM 기준으로 더 짧은 순서는 없다는 최적성 증명까지 확보됨
  • 경로 계산은 Open Source Routing Machine(OSRM)으로 만든 3,361,795,003개 지점 간 도보 이동 시간 표를 바탕으로 함
  • 전체 왕복 시간은 15,386,177초, 즉 178일 1시간 56분 17초이며 방문 순서를 바꿔도 OSRM 추정 시간상 1초도 줄일 수 없음
  • 이번 결과는 2021년 2월 네덜란드 57,912개 지점 사례를 넘어, 증명 가능한 최적해가 나온 가장 큰 도로망 기반 TSP 사례가 됨
  • 계산은 2024년 12월부터 2025년 3월까지 Roskilde University와 University of Waterloo에서 수행됐으며, LKH와 Concorde, 절단평면법이 핵심 도구로 쓰임

81,998개 술집 순회 경로의 계산 결과

  • 한국의 81,998개 술집을 모두 걸어서 방문하는 외판원 문제(TSP)가 풀림
  • 문제 구성에는 Open Source Routing Machine이 사용됨
    • 각 술집 위치 쌍마다 하나의 도보 이동 시간이 계산됨
    • 전체 표에는 3,361,795,003개의 지점 간 이동 시간이 포함됨
  • 계산 결과는 하나의 순회 경로와 함께, OSRM 이동 시간 기준으로 이 경로가 최단 가능 경로라는 증명을 포함함
  • 전체 왕복 도보 시간은 15,386,177초임
    • 178일 1시간 56분 17초에 해당함
    • OSRM 추정 도보 시간 기준으로 방문 순서를 바꿔도 1초도 절약할 수 없음

가장 큰 도로망 TSP 최적해 사례

지도와 시각화

  • korea81998 순회 경로는 인터랙티브 지도로 제공됨
  • 지도 왼쪽 메뉴에서 7개 지역 중 하나를 선택해 볼 수 있음
  • 오른쪽 위 메뉴에서는 색상 거리 지도 또는 거리 이름이 없는 회색조 지도를 선택할 수 있음
  • 정류점 마커와 경로 간선은 각각 표시하거나 둘 다 표시할 수 있음
  • 인터랙티브 지도를 보기 어려우면 고해상도 이미지로 경로 스냅샷을 확인할 수 있음
  • 도시 지역의 확대 뷰는 Cities 페이지에 있음

최적성 증명 방식

  • TSP를 풀 때 가능한 모든 순회를 하나씩 확인해야 한다는 방식은 이런 대규모 사례에 적용되기 어려움
  • korea81998 사례의 가능한 순회 수는 대략 2 뒤에 367,308개의 0이 붙는 수에 해당함
  • 실제 계산은 두 도구를 결합함
    • LKH: 매우 좋은 TSP 해를 계산하는 코드
    • Concorde: 절단평면법(cutting-plane method) 으로 품질 보증을 만드는 코드
  • 절단평면법은 선형계획법을 사용해 도로 선택을 바로 0 또는 1로 확정하지 않고, 도시 쌍을 잇는 도로에 분수 값을 할당하는 방식으로 작동함
    • 각 도시에서 들어오고 나가는 도로에 할당된 분수 합이 각각 1이 되도록 시작함
    • 이후 도로 분수 합에 관한 제약을 단계적으로 추가함
    • 선형계획법이 각 도로에 대한 최선의 결정을 찾아 최단 가능 경로로 이어짐
  • 관련 설명 영상으로 Optimal Tours와 KAIST에서 2024년 3월 진행된 Amazon Deliveries, Pub Walks, and Astro Tours가 있음

P vs NP와 최적화 연구 맥락

  • TSP와 연결된 P와 NP 복잡도 계급 논의는 Lance Fortnow의 Fifty Years of P vs. NP and the Possibility of the Impossible에서 다뤄짐
  • 대형 TSP 사례는 범용 최적화 방법을 개발하고 시험하는 수단으로 사용됨
  • 수학적 최적화와 운영연구는 제한된 자원을 더 효율적으로 쓰기 위한 도구를 만드는 응용수학 분야로 소개됨
  • 관련 학회로 American Mathematical Society, Mathematical Association of America, Mathematical Optimization Society, INFORMS, SIAM이 언급됨

연구진과 데이터 출처

  • 연구진은 William Cook, Daniel Espinoza, Marcos Goycoolea, Keld Helsgaun으로 구성됨
  • 계산 중 생긴 많은 수의 선형계획 모델은 IBM CPLEX Optimizer로 풀림
  • 지도 그림은 Leaflet 오픈소스 JavaScript 라이브러리로 만들어짐
  • 한국 술집 위치는 Institute for Basic Science(IBS) Discrete Mathematics Group의 Dr. Sang-il Oum이 확보함
    • 위치 데이터는 한국 경찰청이 유지하는 데이터베이스에서 다운로드됨
  • 지점 간 도보 이동 시간 표는 OSRM으로 생성됨

다른 도로 여행 TSP 사례와 읽을거리

  • 다른 도로 여행 사례
    • 일본 40,426개 konbini
    • 영국 49,687개 pub
    • 미국 49,603개 historic places
    • 네덜란드 57,912개 monuments
  • 추가 읽을거리
    • In Pursuit of the Traveling Salesman: TSP의 역사, 응용, 해법 기법 소개
    • Traveling Salesman Problem: TSP를 위한 절단평면법의 계산 연구
    • The Golden Ticket: P vs NP 문제와 파급 효과 입문
    • Opt Art: TSP를 사용해 하나의 선으로 이미지를 만드는 사례
    • Approximation Algorithms for the TSP: TSP 근사 알고리듬 이론 연구
    • Computational Solutions for TSP Applications: TSP 응용을 다룬 1994년 책이며 무료 다운로드 가능

함께 보면 좋은 글 β

xguru   [-]

한국의 81,998개 술집을 모두 돌아보는 최단 도보 경로는 178일 글을 해커뉴스에 긱뉴스 계정으로 올렸는데요.
투표를 많이받아서 6시간동안 탑을 차지하더니 인기 글이 되어서 다시 GN+로 수입(?)되었네요.

해당 글이 영문도 같이 있어서 그렇게 해본건데, 종종 영문 포함 글들은 해커뉴스쪽으로 올려보려고 합니다.

답변달기
GN⁺   [-]
Hacker News 의견들

  • 이게 인상적이라면 같은 저자들이 낸 13억 3천만 개 별 외판원 문제 해도 볼 만함
    Gaia DR2 (1,331,906,450 Stars): https://www.math.uwaterloo.ca/tsp/star/gaia2.html
    “이 순회 경로는 가능한 최단 경로 길이의 최대 1.0038배”

    • 다만 이건 별들의 상대 운동은 다루지 않는 것 같음. 이동하는 동안 거리 자체가 바뀌니 문제가 더 어려워지는 것 아닌가? 아니면 내가 천문학을 잘못 이해한 건가?
    • 아쉽게도 https://www.math.uwaterloo.ca/tsp/star/star10m_tour.html의 대화형 뷰어에서 쓰던 Three.js 버전을 고정하지 않았음
      그 결과 2022년 5월부터 깨져 있었음: https://github.com/mrdoob/three.js/releases/tag/r141
      HTML 파일을 내려받아 링크를 버전 고정된 것으로 바꾸니 뷰어는 여전히 잘 작동함

  • 단순한 Bell Labs식 확률적 알고리즘만 쓰면 결과가 얼마나 더 나빠질까?
    고전적인 외판원 문제 접근은 임의의 경로로 모든 노드를 잇고, 경로를 두 군데 잘라 세 조각을 만든 뒤, 그 세 조각을 가능한 여섯 방식으로 재배열해 가장 짧은 것을 유지하는 식임
    2~3단계를 한동안 개선이 없을 때까지 반복함. 최적이 보장되지는 않지만, 현실 문제 대부분에서는 최적해를 찾거나 그에 매우 가까워짐

    • 순회 경로 자체는 휴리스틱 해법으로 빠르게 찾았고(https://www.math.uwaterloo.ca/tsp/korea/computation.html), 여기서의 성과와 계산량은 그 경로가 하한임을 증명하는 데 있었던 것으로 이해함
      그러니 휴리스틱 해법은 꽤 잘 작동한 셈임 :) 다만 설명한 휴리스틱 알고리즘과 얼마나 가까웠을지는 모르겠음. 무작위 선택만으로는 수렴이 너무 오래 걸릴 테니, 아마 훨씬 더 고도화된 방식일 것 같음
    • https://www.youtube.com/watch?v=tChnXG6ulyE
      저자의 발표임
    • 기억하기로 이들이 쓴 것은 아마 단순화한 LKH 휴리스틱이었음
      각 반복마다 약간의 무작위화를 적용하고, 각 위치에서 시작해 경로를 2..n곳 자른 뒤 가장 최적인 방식으로 다시 연결함. 새 순회 경로가 최고 기록이면 저장하는 식이고, n은 4나 5 정도의 작은 수였던 듯함

  • 총거리를 언급하지 않는 게 이상함. 이들이 푸는 대상이 지점 간 이동 시간이라는 건 이해하지만, 실제 이동 거리가 얼마였는지도 흥미로웠을 것임
    적어도 칼로리 소모량 계산에는 쓸 수 있고, 최단거리 경로에서 얼마나 벗어났는지도 볼 수 있음

    • 제대로 된 경로 계산도 비용이 많이 듦. 도로에서 A* 같은 걸 돌릴 수는 있지만, 그러면 폐쇄 도로, 일방통행, 고도 변화 등을 반영하지 못함
      제대로 된 경로 API를 쓰면 거의 확실히 비용이 감당하기 어려울 것임

  • 오하이오 정도 크기의 나라에 술집이 거의 8만 2천 곳 있다는 생각만으로도 압도됨

    • 술 판매 허가를 받은 모든 식당 데이터셋을 구한 것 같음. 아니면 적어도 그런 식당들의 꽤 괜찮은 부분집합을 메뉴 등으로 필터링한 듯함
      내가 사는 곳 근처 점 몇 개를 확인해 보니 전부 치킨집이었음. 여기서는 정말 치맥을 좋아함 :)
    • 미국인들은 항상 거대한 도시를 텅 빈 주와 비교함
    • 폭이 20마일쯤 되는 NYC에도 술을 파는 장소가 11,000곳 있음
    • 그 나라는 인구가 5,200만 명이라 오하이오의 약 5배임
    • 몇 군데 확인해 보니 식당이 많이 포함돼 있음
      https://www.math.uwaterloo.ca/tsp/korea/data/korea81998.xy.t...

  • 이렇게 어렵지만 훨씬 더 어렵지는 않은 데이터셋을 찾아낸 게 인상적임. 이전 외판원 문제 최고 기록인 네덜란드를 넘기면서도 계산이 끝나지 않는 상태는 피해야 하니 미묘한 균형임

    • 터무니없으면서도 실제로 풀 수 있는 문제를 고른 계획성은 인정해야 함
    • “computations” 페이지[1]의 표를 보면 네덜란드 계산은 97 CPU년과 실제 경과 6개월이 들었고, 한국 술집 문제는 44 CPU년과 실제 경과 3개월이 들었음. 두 문제가 같은 하드웨어에서 풀렸는지는 모르겠음
      [1] https://www.math.uwaterloo.ca/tsp/korea/computation.html
    • 문제가 되는 술집들을 데이터셋에서 하나씩 제외하다가 해가 나오는 데이터셋을 찾은 게 아니라는 걸 우리가 알고 있나?

  • 60년대 아일랜드 군대에서 묻곤 했다는 질문이 떠오름. 아버지가 들려준 이야기임
    “Bachelor's Walk에서 Collins Barracks까지 술집을 지나치지 않고 어떻게 가나?” 사람들이 몇 시간, 며칠씩 답을 찾았는데, 최종 답은 “모든 술집에 들어간다”였음

  • 그러면 NP가 다시 P 같은 건가. 학교에서는 13이 최대라고 배웠고, 80년대에 대수학 교수 중 한 명은 그걸 15로 올렸음. 그다음 20, 그다음 20,000이 나왔고, 이건 증명까지 포함한 80k임. World TSP 페이지를 보면 기록은 1m이었음
    http://webhotel4.ruc.dk/~keld/research/LKH/
    현재 증명된 최적해 중 가장 큰 것은 3,178,031개짜리임
    덧붙이면 이건 plain C가 아니라 CUDA로 해야 함

    • GPU에서 최적화 알고리즘을 돌리는 연구는 엄청 많음. 현재 형태의 분기 한정법과 절단 평면법은 CUDA로 구현해도 이점이 없음
      GPU 구현이 가능한 새 알고리즘으로 PDLP가 있지만 아직 초기 단계임. 더 보려면 https://blogs.nvidia.com/blog/cuopt-open-source/ 참고
    • 유클리드 외판원 문제는 어려운 사례를 인코딩하는 데 많은 데이터가 필요함
      N=15는 60년대에도 이미 풀린 것으로 여겨졌고, N=20은 큰 사례로 여겨진 적이 없음. 특히 유클리드 외판원 문제에서는 더더욱 아님
      누가 13이 최대라고 말할 수 있었는지 모르겠음. 필요한 건 메모리 슬롯 10만 개와 비교 100만 번 정도인데, 꽤 오래전부터 사소한 수준이었음
    • “80k with proof”라면 증명을 올려야 함

  • 코로나 때 웹 기반 CityStrides(https://citystrides.com/) 추적기로 내가 사는 도시의 모든 길을 걸어보는 걸 목표로 삼았음
    걸은 거리를 추적하고 도시의 몇 퍼센트를 걸었는지 알려줌. 내 경로를 커버리지에 맞춰 최적화해 주지는 않았지만, 중복 없이 최대한 많은 거리를 지나도록 산책 계획을 짜는 게 재미있는 머리 쓰기였음
    자동화 도구도 재미있겠지만, 손으로 하는 것 자체가 여정의 일부였음
    CityStrides 사이트를 둘러보면 사람들이 걸은 전체 기록인 LifeMaps를 볼 수 있음. 정말 엄청난 양을 걸은 사람들도 있음. 예를 들어 이 사용자의 프랑스 파리 커버리지를 보면 됨
    https://citystrides.com/users/15259/map#48.85741101618777,2....

  • 아뿔싸, 새 술집 몇 곳이 생겼고 몇 곳은 닫은 것 같음. 이제 재계산할 시간임

  • 분기 한정법은 내게 “교과서에 나오는” 알고리즘임. 선형계획법 풀이기를 블랙박스로 본다면 근본적으로 매우 단순하지만, 믿을 수 없을 정도로 유용함

답변달기