한국의 81,998개 술집을 모두 돌아보는 최단 도보 경로는 178일
(math.uwaterloo.ca)- 워털루대 윌리엄 쿡 교수가 외판원 문제(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년 출판된 응용 사례 책
저는 2024년 3월에 대전에 위치한 KAIST에서 TSP 강의를 하기로 예정되어 있었고, 대전 TSP 투어를 위한 지역 데이터 세트를 찾고 있었습니다. 2023년 12월에 엄상일 박사가 "경찰청에서 만든 전국 술집 데이터 세트가 필요하신가요? 최신 파일은 1,000원이며 90,680개의 항목이 있습니다."라고 이메일을 보내왔습니다. 와. 1,000원이 1달러보다 작은지 먼저 확인한 후(환율이 반대로 되지 않았는지 확인한 것이 좋았습니다), "고맙습니다!"라고 답장했습니다.
영문 페이지는 https://www.math.uwaterloo.ca/tsp/korea/index.html 입니다.
투어는 확실히 비현실적이긴 합니다. 육지에서 제주도나 울릉도로 이동할 때 배로 이동하는 해로를 고려하는 것은 아닌 걸로 보입니다. 이 그림을 보시면 됩니다: https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png
방문에 드는 예상 시간 계산을 정확히 하는 것이 목적이 아니라 TSP를 현실의 데이터로 풀어냈다는 것에 의미를 두어야겠죠.
저는 2024년 3월에 대전에 위치한 KAIST에서 TSP 강의를 하기로 예정되어 있었고, 대전 TSP 투어를 위한 지역 데이터 세트를 찾고 있었습니다.
아마 한국에 강연을 하기로 했기 때문에 관련 정보를 찾고 있었다고 생각됩낟.