korea81998 Data

korea81998 TSP 인스턴스는 대한민국의 81,998개 바 사이의 초 단위로 측정된 도보 시간으로 구성되어 있습니다. 우리는 일반적인 TSP 언어와 일치하도록 도보 시간을 "거리"라고 부를 것입니다. korea81998의 거리는 대칭적입니다. 즉, 모든 쌍의 상점 A와 B에 대해 A에서 B까지의 거리는 B에서 A로 돌아오는 거리와 같습니다.

X-Y 좌표

TSP의 예를 구축하는 첫 번째 단계는 방문할 지점의 위치를 수집하는 것입니다. korea81998의 경우, TSP 챌린지에 사용할 수 있는 매우 훌륭하고 방대한 데이터 세트를 사용할 수 있어서 운이 좋았습니다. 이는 한국 대전에 있는 기초과학연구원(IBS) 이산수학그룹의 엄상일 박사 덕분입니다. 엄상일은 이산수학 연구를 위한 세계 최고의 센터 중 한 곳의 수석 연구 위원입니다.

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

2024년 초에 저는 엄상일 박사가 제공한 데이터 세트에서 대전의 2,104개 바 목록을 추출했습니다. 관심이 있으시다면 제가 대전 술집 경로를 소개한 KAIST 강연회 영상을 보실 수 있습니다. 또한 더 많은 투어 페이지에도 설명되어 있습니다.

KAIST 강의 당시, 저는 한국 전체의 TSP를 풀려고 시도하는 것을 고려조차 하지 않았습니다. 그것은 우리가 2021년에 발견한 네덜란드 투어보다 훨씬 더 컸고, 그 사례는 97년의 컴퓨터 시간이 필요했습니다(우리 Linux 서버의 단일 프로세서 코어에서 실행하는 경우). 하지만 2024년 가을에 Keld Helsgaun과 저는 LKH와 Concorde 컴퓨터 코드를 결합하여 TSP의 대규모 인스턴스를 해결하는 방법에 대한 진전을 이루었고, 그래서 2024년 12월에 다시 한국 사례를 살펴보았습니다.

전체 데이터 세트에는 한국의 90,680개 바에 대한 정보가 포함되어 있습니다. 하지만 일부 항목은 동일한 위도-경도 좌표를 갖는 것으로 나열되어 있습니다. 이는 아마도 같은 건물의 다른 층에 있는 장소 때문일 수 있습니다. 엘리베이터나 계단에서 소요된 시간을 측정할 쉬운 방법이 없어서, 우리는 그러한 공동 위치 지점의 각 클러스터에서 단 하나의 예만 가져왔습니다. 그 결과 81,998개의 개별 지점이 수집되었습니다.

81,998개 지역의 위도-경도 좌표는 korea81998.xy 파일에 있습니다.

거리 테이블

우리는 바 위치 사이의 지점 간 도보 시간을 얻기 위해 오픈 소스 라우팅 머신(OSRM)을 채택했습니다. OSRM을 실행하기 위한 유용한 지침 세트는 Project-OSRM GitHub 페이지에서 찾을 수 있습니다. korea81998 거리 표를 작성할 때 다음과 같은 조정을 했습니다.

우리는 "간선" 도로에서의 보행을 허용하기 위해 수정된 프로필을 사용했습니다.
우리는 전처리를 위해 대체 Construction Hierarchies(CH) 설정을 채택했습니다. 우리의 큰 예제에서 이것은 기본 Multi-Level Dijkstra(MLD) 설정보다 훨씬 빨랐습니다.
--max-table-size 인수를 사용하여 전체 행렬의 행을 처리하고, 이 값을 기본값인 10000 대신 90000으로 설정했습니다.

TSPLIB 형식의 전체 데이터 세트는 22GByte 파일입니다. 이것은 우리 대학 서버에 저장하기에는 너무 큽니다. 하지만 korea81998에 대한 실험을 수행하고 싶으시다면 bico@uwaterloo.ca로 편지를 보내주시면 파일을 일시적으로 공공 장소에 보관하도록 하겠습니다.