한국의 81,998개 술집을 모두 돌아보는 최단 도보 경로는 178일

• 워털루대 윌리엄 쿡 교수가 외판원 문제(TSP)를 한국의 81,998개 술집을 방문하는 최단 경로에 대해 계산한 세계 최초 사례
• 오픈소스 라우팅 머신(OSRM) 을 이용하여 약 33억 쌍의 도보 시간을 계산하고, 수학적으로 최적임을 증명
• 계산 결과는 쉬지 않고 걸었을 때 총 15,386,177초, 즉 178일 1시간 56분 17초가 걸림
• TSP 최적화에는 LKH와 Concorde 도구가 사용되었으며, 절단 평면 방법이 적용됨
• 이전까지 최다 방문 경로였던 네덜란드 57,912개 경로를 넘어서는 세계 최대 규모의 도로 기반 TSP 해결 사례임

한국의 모든 술집을 걷는 외판원 문제(Traveling Salesman Problem)

• 한국에 있는 81,998개 술집을 모두 방문하고 다시 돌아오는 가장 짧은 경로를 계산함
• 세계 최초로 이처럼 많은 장소를 포함한 TSP 문제를 최적으로 해결
• 술집 간 총 3,361,795,003쌍에 대한 도보 시간을 OSRM - Open Source Routing Machine 으로 계산
• 수학적으로 이 경로보다 더 짧은 경로는 존재하지 않음
• 이 문제는 TSP 문제 중 방문지점 수 기준으로 역대 최대 규모임

최단 경로 소요 시간

• 계산된 최적 경로를 따라 쉬지 않고 걸으면 총 15,386,177초가 소요됨
• 이는 178일 1시간 56분 17초에 해당함
• 실제로는 걷는 동안 쉬거나 마시게 되어 정확히 끝내기는 어려움
• OSRM 기반 도보 시간으로 단 1초도 더 줄일 수 없는 최적 경로

TSP 역사적 맥락과 기록 경신

• 이전 최대 기록은 네덜란드 57,912개 지점 자전거 경로였음
• 이번 korea81998 경로는 그보다 큰 규모의 TSP 문제 해결 사례
• 계산은 2024년 12월부터 2025년 3월까지 로스킬데 대학교와 워털루 대학교에서 수행
• 자세한 계산 내용은 별도 계산 페이지에서 확인 가능

경로 시각화 방법

• 경로는 인터랙티브 지도로 확인 가능하며, 7개 지역별로 나누어 탐색 가능
• 다양한 시각화 모드(컬러 거리 지도, 회색조 등) 제공
• 경로의 일부 고해상도 이미지를 별도로 제공하고 있음
• 도시별 클로즈업 보기는 도시 페이지에서 제공됨

TSP 해결 전략과 오해

• 일부 미디어에서는 "22개 도시만으로도 1000년"이 걸린다고 보도하나 이는 모든 경로를 무작위로 시도하는 경우를 의미
• 실제로는 고급 최적화 기법을 통해 많은 지점도 해결 가능
• korea81998의 경우 가능한 경로 수는 2 뒤에 0이 367,308개 붙는 수에 달함
• 해결에는 LKH(Lin-Kernighan Heuristic) 알고리듬 과 Concorde TSP Solver - 절단 평면 방법 이 결합되어 사용됨

절단 평면 방법 개념 요약

• 선형 계획법을 기반으로 함
• 도로 사용 여부 대신 연결 정도를 0~1 사이 수치로 표현
• 단계별 제약조건을 추가하여 가장 짧은 경로를 찾아냄
• 자세한 설명은 Scientific American과 YouTube 강연에서 확인 가능

P 대 NP 문제

• TSP 문제는 NP-완전 문제로, P와 NP 문제의 대표적 예시
• 관련된 흥미로운 논의는 Lance Fortnow 교수의 논문에서 소개됨
• 이 문제는 컴퓨터 과학의 가장 유명한 미해결 문제 중 하나

수학적 최적화의 의미

• 이 프로젝트는 범용 최적화 방법의 실험이자 발전을 위한 기반
• 산업, 상업, 의학, 환경 분야에서의 응용 가능성 높음
• 수학적 모델링은 유한한 자원을 효과적으로 사용하기 위한 중요한 도구임

연구진 소개

• William Cook: 캐나다 워털루 대학교
• Daniel Espinoza: 칠레 Alicanto Labs
• Marcos Goycoolea: 칠레 Adolfo Ibáñez 대학교
• Keld Helsgaun: 덴마크 로스킬데 대학교

감사의 말

• IBM CPLEX Optimizer: 무료 학술 연구용 제공에 감사
• 지도는 Leaflet, OpenStreetMap, Carto, Stadia Maps를 이용해 제작
• 엄상일 박사가 한국 경찰청 데이터 기반 술집 위치 데이터 제공
• 도보 시간 계산은 OSRM 을 활용

다른 나라의 TSP 프로젝트 사례

• 일본: 편의점 40,426개
• 영국: 술집 49,687개
• 미국: 역사적 장소 49,603개
• 네덜란드: 기념물 57,912개

추가 학습 자료

• In Pursuit of the Traveling Salesman: TSP의 역사와 응용
• Traveling Salesman Problem: 절단면법 적용 연구
• The Golden Ticket: P vs. NP 문제 소개
• Opt Art: TSP를 이용한 예술적 이미지 생성
• Approximation Algorithms: TSP 근사 알고리듬에 관한 최신 연구
• Computational Solutions for TSP Applications: 1994년 출판된 응용 사례 책