우리는 또한 한국 산 383개를 보고 대전의 술집 2141개를 방문하는 최적의 도보 여행을 계산했습니다. 이 두 개의 작은 인스턴스는 KAIST에서 진행된 TSP 토크를 위해 만들어졌습니다.

PeakVisor 웹사이트를 사용하여 500m가 넘는 383개의 한국 산봉우리 목록을 얻었습니다. 정상에서 정상까지의 도보 시간은 다시 OSRM 경로 소프트웨어를 사용하여 얻었습니다. 최적의 투어에 대한 총 하이킹 시간은 5,434,221초(약 65일)로 측정되었습니다. 이 문제는 M1 Mac Studio에서 0.88초 만에 해결되었습니다.

아래 이미지를 클릭하면 산악 투어의 대화형 지도를 볼 수 있습니다. 지도의 왼쪽 상단 모서리에 한국 지역을 확대하는 버튼이 있는 메뉴가 있습니다. 지도의 오른쪽 상단 모서리에는 그림을 수정하기 위한 작은 메뉴가 있고, 오른쪽 하단 모서리에는 확대 또는 축소 버튼이 있습니다. 위치 마커를 클릭하면 산 정상을 확대하거나 투어에서 인접한 정거장으로 이동할 수 있는 메뉴가 표시됩니다.

아래 왼쪽 이미지를 클릭하면 피크 투 피크 투어의 아름답고 거친 구간을 고해상도로 볼 수 있습니다. 오른쪽 이미지는 Grayscale 지도 보기에서 같은 구간을 보여줍니다.

원래 우리는 산 정상 챌린지를 비대칭 TSP(ATSP)의 한 예로 만들 계획이었습니다. 여기서 정상 A에서 정상 B까지 하이킹하는 데 걸리는 시간은 정상 B에서 정상 A까지 걸어가는 데 걸리는 시간과 같지 않을 수 있습니다. 하지만 OSRM 라우터는 이동 시간을 계산할 때 오르막/내리막을 구분하지 않습니다. 예를 들어, 해안에서 트레일을 따라 제주도의 한라산 정상(1947m)까지 하이킹하는 데 걸리는 시간은 한국에서 가장 높은 지점인 한라산에서 해안까지 걸어가는 데 걸리는 시간과 같습니다.

따라서 OSRM 여행 시간을 고려하면 봉우리 사이를 어느 방향으로 하이킹하든 상관없습니다. ATSP의 예를 보려면 일본의 미치노에키 도로변 역을 방문하는 운전 투어를 살펴보세요.

korea81998 데이터 세트에는 대전에 있는 2141개 바의 위치가 포함되어 있습니다. 우리는 총 러닝 타임 M1 Mac Studio에서 66.75초로 이 대전 TSP에 대한 최적의 투어를 ​​계산했습니다. 투어의 도보 시간은 209,055초(약 58시간)로 측정되었습니다.

아래 그림은 대전 투어의 대화형 지도의 스크린샷입니다. 이미지를 클릭하면 지도를 볼 수 있습니다.

산 정상과 대전 인스턴스에 대한 데이터 세트에 대한 링크는 다음 표에 나와 있습니다. Lat-Lng 세트는 각 정류장의 (위도-경도) 위치를 제공합니다. TSP 세트는 TSPLIB 형식으로 도보 시간 표를 제공합니다. Tour 항목은 최적의 투어에 정류장이 나타나는 순서를 나열합니다. 이러한 파일도 TSPLIB 형식입니다.

데이터 세트	위도-경도	TSP	관광
산봉우리	korea383.xy	korea383.tsp	korea383.tour
대전 바	dj2142.xy	dj2141.tsp.gz	dj2141.tour

지점 간 이동 시간과 경로 폴리곤은 OSRM과 OpenStreetMap 데이터를 사용하여 생성되었습니다.

투어 지도 도면은 모바일 친화적인 대화형 지도를 위한 오픈 소스 JavaScript 라이브러리인 Leaflet을 사용하여 제작되었으며, OpenStreetMap, Stadia Maps 및 ArcGIS에서 만든 지도 타일을 활용했습니다.

하이커, 워커, 대전 스카이라인의 그림은 대전 관광 페이지에서 가져왔습니다.

한국 산봉우리의 위치는 PeakVisor 웹사이트에서 얻었습니다.

대전 지역 술집의 위치는 경찰청이 관리하는 데이터베이스에서 얻었습니다.