Google 지도를 통한 최적의 지도 경로

StackOverflow https://stackoverflow.com/questions/337607

  •  22-07-2019
  •  | 
  •  

문제

Google Maps API를 사용하여 일련의 경유지(즉, 여행하는 외판원 문제에 대한 "충분한" 솔루션)가 제공되는 "최적화된" 경로를 반환하는 방법이 있습니까? 아니면 항상 다음과 같은 경로를 반환합니까? 지정된 순서대로 포인트가 있나요?

도움이 되었습니까?

해결책

그것은 항상 그들에게 순서대로 제공합니다.

따라서 한 번에 하나씩 각 지점 사이의 거리 (또는 시간)를 찾은 다음 여행 판매원 문제를 직접 해결해야한다고 생각합니다. 어쩌면 Google지도에서 해당 기능을 추가하도록 설득 할 수 있습니다. "충분히 충분한"솔루션을 구성하는 것은 당신이하고있는 일과 얼마나 빨리 필요한지에 달려 있다고 생각합니다.

다른 팁

Google Maps API DirectionsRequest에는 원하는 작업을 수행하는 OptimizeWaypoints라는 옵션이 있습니다.하지만 최대 8개의 웨이포인트만 처리할 수 있습니다.

또는 Google Maps API와 함께 최적(최대 15개 위치) 또는 최적에 매우 가까운(최대 100개 위치) 경로를 얻을 수 있는 오픈 소스(MIT 라이센스) 라이브러리가 있습니다.

보다 http://code.google.com/p/google-maps-tsp-solver/

도서관이 실제로 작동하는 모습을 볼 수 있습니다. www.optimap.net

일반적인 TSP 문제에서, 가정은 두 지점 사이에서 직접 이동할 수 있다고 가정합니다. 표면 도로의 경우 이것은 결코 그렇지 않습니다. Google이 두 지점 사이의 경로를 계산하면 휴리스틱 스패닝 트리 최적화를 수행하며 일반적으로 최적의 경로에 상당히 가까운 경로가 나옵니다.

TSP 경로를 계산하려면 먼저 Google에 그래프의 모든 노드 사이의 쌍별 거리를 계산하도록 요청해야합니다. 나는 이것이 n*(n-1) / 2 calcs가 필요하다고 생각합니다. 그런 다음 그 거리를 잡고 TSP 최적화를 수행 할 수 있습니다.

OpenStreetMaps.org가 있습니다 Java Webstart 원하는대로 할 수있는 응용 프로그램. 물론 계산은 클라이언트 측면을 실행하고 있습니다. 이 프로젝트는 오픈 소스이며 볼만한 가치가있을 수 있습니다.

위치 또는 최적의 운전 경로간에 최적의 직선 경로를 찾으려고합니까? 포인트를 주문하려면 GPS 좌표를받을 수 있다면 매우 쉬운 문제가됩니다.

방금 발견되었습니다 http://gebweb.net/optimap/ 멋지고 쉬워 보입니다. Google지도를 사용하는 온라인 버전.

Google은 여행 판매원 문제에 대한 준비된 솔루션을 보유하고 있습니다.여기에서 찾을 수 있는 것은 OR-Tools(Google의 운영 연구 도구)입니다. https://developers.google.com/optimization/routing/tsp

기본적으로 해야 할 일은 2가지입니다.

또한 다음 사항에 유의할 수 있습니다.

고전적인 여행 세일즈맨에 대한 해결책을 찾는 것 외에도 문제, OR-Tools는보다 일반적인 유형의 메소드를 제공합니다. 다음을 포함한 TSP:

  • 비대칭 비용 문제 - 기존 TSP는 대칭적입니다.점 A에서 점 B까지의 거리는 점 B에서 점까지의 거리와 같습니다. 포인트 A.그러나 A 지점에서 B 지점으로 품목을 배송하는 비용입니다 B 지점에서 A 지점으로 배송하는 비용과 같지 않을 수 있습니다.OR-Tools는 비용이 비대칭인 문제도 처리할 수 있습니다.

  • 노드 방문으로 이익이 발생하는 상금 수집 TSP

  • 시간 창이 있는 TSP

추가 링크:

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top