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

> Clean Markdown view of GeekNews topic #20484. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=20484](https://news.hada.io/topic?id=20484)
- GeekNews Markdown: [https://news.hada.io/topic/20484.md](https://news.hada.io/topic/20484.md)
- Type: news
- Author: [xguru](https://news.hada.io/@xguru)
- Published: 2025-04-23T09:31:02+09:00
- Updated: 2025-04-23T09:31:02+09:00
- Original source: [math.uwaterloo.ca](https://www.math.uwaterloo.ca/tsp/korea/sk_index.html)
- Points: 23
- Comments: 10

## Summary

워털루대 윌리엄 쿡 교수는 **외판원 문제(TSP)** 를 한국의 **81,998개 술집**을 방문하는 최단 경로로 계산한 세계 최초 사례를 발표했습니다. 이 경로는 **오픈소스 라우팅 머신(OSRM)** 을 사용하여 약 33억 쌍의 도보 시간을 계산하고, **수학적으로 최적임을 증명**했습니다. 계산된 최적 경로는 쉬지 않고 걸었을 때 **총 15,386,177초**, 즉 **178일 1시간 56분 17초**가 소요되며, 이는 **세계 최대 규모의 도로 기반 TSP 해결 사례**입니다. 이 프로젝트는 **LKH**와 **Concorde** 도구를 사용하여 **절단 평면 방법**을 적용해 해결하였습니다.

## Topic Body

- 워털루대 윌리엄 쿡 교수가 외판원 문제(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](https://project-osrm.org/)** 으로 계산  
- 수학적으로 이 경로보다 더 짧은 경로는 **존재하지 않음**  
- 이 문제는 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) 알고리듬](http://webhotel4.ruc.dk/~keld/research/LKH/)** 과 **[Concorde TSP Solver - 절단 평면 방법](https://www.math.uwaterloo.ca/tsp/concorde.html)** 이 결합되어 사용됨  
  
### 절단 평면 방법 개념 요약  
  
- 선형 계획법을 기반으로 함  
- 도로 사용 여부 대신 **연결 정도를 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](https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/)**: 무료 학술 연구용 제공에 감사  
- 지도는 **Leaflet**, **OpenStreetMap**, **Carto**, **Stadia Maps**를 이용해 제작  
- **엄상일 박사**가 한국 경찰청 데이터 기반 술집 위치 데이터 제공  
- 도보 시간 계산은 **[OSRM](https://project-osrm.org/)** 을 활용  
  
### 다른 나라의 TSP 프로젝트 사례  
  
- **일본**: 편의점 40,426개  
- **영국**: 술집 49,687개  
- **미국**: 역사적 장소 49,603개  
- **네덜란드**: 기념물 57,912개  
  
### 추가 학습 자료  
  
- [In Pursuit of the Traveling Salesman](http://press.princeton.edu/titles/9531.html): TSP의 역사와 응용  
- [Traveling Salesman Problem](http://press.princeton.edu/titles/8451.html): 절단면법 적용 연구  
- [The Golden Ticket](http://press.princeton.edu/titles/9937.html): P vs. NP 문제 소개  
- [Opt Art](https://press.princeton.edu/books/hardcover/9780691164069/opt-art): TSP를 이용한 예술적 이미지 생성  
- [Approximation Algorithms](https://www.or.uni-bonn.de/tspbook/tsp_book.html): TSP 근사 알고리듬에 관한 최신 연구  
- [Computational Solutions for TSP Applications](https://link.springer.com/book/10.1007/3-540-48661-5): 1994년 출판된 응용 사례 책

## Comments



### Comment 37694

- Author: ep6tri
- Created: 2025-04-24T02:39:18+09:00
- Points: 1

영문 페이지는 https://www.math.uwaterloo.ca/tsp/korea/index.html 입니다.  
투어는 확실히 비현실적이긴 합니다. 육지에서 제주도나 울릉도로 이동할 때 배로 이동하는 해로를 고려하는 것은 아닌 걸로 보입니다. 이 그림을 보시면 됩니다: https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png  
  
방문에 드는 예상 시간 계산을 정확히 하는 것이 목적이 아니라 TSP를 현실의 데이터로 풀어냈다는 것에 의미를 두어야겠죠.

### Comment 37639

- Author: skshin
- Created: 2025-04-23T15:28:13+09:00
- Points: 1

섬과의 이동은 어떻게? 도보로?

### Comment 37650

- Author: halfenif
- Created: 2025-04-23T16:59:19+09:00
- Points: 1
- Parent comment: 37639
- Depth: 1

walking and ferry라고 나오는 것을 보니. 배타고 가나 봅니다.

### Comment 37635

- Author: woalsdnd
- Created: 2025-04-23T14:02:27+09:00
- Points: 1

실시간으로 생기고 폐업하는 경우는 어떻게 하면 좋을까요?

### Comment 37598

- Author: majorika
- Created: 2025-04-23T12:05:58+09:00
- Points: 4

> 저는 2024년 3월에 대전에 위치한 KAIST에서 TSP 강의를 하기로 예정되어 있었고, 대전 TSP 투어를 위한 지역 데이터 세트를 찾고 있었습니다. 2023년 12월에 엄상일 박사가 "경찰청에서 만든 전국 술집 데이터 세트가 필요하신가요? 최신 파일은 1,000원이며 90,680개의 항목이 있습니다."라고 이메일을 보내왔습니다. 와. 1,000원이 1달러보다 작은지 먼저 확인한 후(환율이 반대로 되지 않았는지 확인한 것이 좋았습니다), "고맙습니다!"라고 답장했습니다.  
  
https://www.math.uwaterloo.ca/tsp/korea/sk_data.html

### Comment 37619

- Author: kimjoin2
- Created: 2025-04-23T13:06:06+09:00
- Points: 1
- Parent comment: 37598
- Depth: 1

와우 이런 배경이 있었군요. 정리 & 공유 감사합니다

### Comment 37573

- Author: kimjoin2
- Created: 2025-04-23T10:18:17+09:00
- Points: 1

한국을 대상으로 선정한 이유도 궁금하내요 👀

### Comment 37910

- Author: firea32
- Created: 2025-04-28T11:35:49+09:00
- Points: 1
- Parent comment: 37573
- Depth: 1

1000원에 양질의 데이터를 얻을 수 있다는 점도 한몫했을겁니다 :)

### Comment 37651

- Author: halfenif
- Created: 2025-04-23T17:00:43+09:00
- Points: 1
- Parent comment: 37573
- Depth: 1

> 저는 2024년 3월에 대전에 위치한 KAIST에서 TSP 강의를 하기로 예정되어 있었고, 대전 TSP 투어를 위한 지역 데이터 세트를 찾고 있었습니다.   
  
아마 한국에 강연을 하기로 했기 때문에 관련 정보를 찾고 있었다고 생각됩낟.

### Comment 37571

- Author: bbulbum
- Created: 2025-04-23T09:50:01+09:00
- Points: 1

한국에 술집이 많아서 주제로 잡은건가..