지도 제공 업체 (예 : Google 또는 Yahoo!지도)는 길 찾기를 어떻게 제안합니까?
내 말은, 아마도 거리를 포함하여 어떤 형태로든 실제 데이터를 가지고있을 것입니다. 물론 주행 속도, 보도의 존재 여부, 기차 시간표 등과 같은 것들도 있지만 데이터가 더 간단한 형식이라고 가정하십시오. 거리를 반영하는 가장자리 가중치 임의의 한 지점에서 다른 지점으로 방향을 신속하게 계산할 수 있기를 원합니다. 때때로이 지점들은 (한 도시 내에서) 서로 가까이있을 때도 있고 멀리 떨어져있을 수도 있습니다 (국가 간).
그래프가 엄청 나서 Dijkstra의 알고리즘과 같은 그래프 알고리즘은 작동하지 않습니다. 운 좋게도 A *와 같은 휴리스틱 알고리즘이 작동 할 것입니다. 그러나 우리의 데이터는 매우 체계적이며 어떤 종류의 계층 적 접근 방식이 효과가 있습니까? (예를 들어, 특정 “키”지점 사이의 미리 계산 된 방향과 일부 로컬 방향을 저장합니다. 그러면 두 개의 원거리 지점의 방향에는 주요 지점에 대한 로컬 방향, 다른 주요 지점에 대한 전역 방향 및 로컬이 포함됩니다. 다시 지시하십시오.)
실제로 어떤 알고리즘이 사용됩니까?
추신. 이 질문은 온라인 매핑 방향에서 기발한 부분을 찾아 동기를 부여했습니다. 삼각형 부등식과 달리 Google지도는 XZ 가 XYZ 에서와 같이 중간 지점을 사용하는 것보다 시간이 오래 걸리고 더 먼 것으로 생각합니다 . 그러나 도보 방향이 다른 매개 변수에도 최적화되어 있습니까?
PPS. 여기에 삼각형 불평등에 대한 또 다른 위반이 있습니다 .XZ 대 XYZ 와 같은 계층 적 접근 방식을 사용한다고 제안 합니다. 전자는 약간 방해가 되더라도 유명한 Boulevard de Sebastopol을 사용하는 것 같습니다.
편집 :이 예제 중 어느 것도 더 이상 작동하지 않는 것 같지만 원래 게시물 당시에는 두 가지 모두 작동했습니다.
답변
라우팅 알고리즘에 대한 작업을 포함하여 18 개월 동안지도 회사에서 근무한 사람으로 말하면 Dijkstra 는 몇 가지 수정 작업을 수행합니다.
- 소스에서 대상까지 Dijkstra를 한 번 수행하는 대신 각 끝에서 시작하여 중간에서 만날 때까지 양쪽을 확장하십시오. 이것은 작업의 대략 절반을 제거합니다 (2 * pi * (r / 2) ^ 2 vs pi * r ^ 2).
- 출발지와 목적지 사이의 모든 도시의 뒷골목을 탐색하지 않으려면 몇 가지 맵 데이터 계층을 가질 수 있습니다. 고속도로 만 포함하는 ‘고속도로’레이어, 2 차 거리 만 포함하는 ‘보조’레이어 등. 그런 다음 더 세부적인 레이어의 작은 섹션 만 탐색하고 필요에 따라 확장합니다. 분명히이 설명은 많은 세부 사항을 생략하지만 아이디어를 얻습니다.
이러한 라인을 따라 수정하면 매우 합리적인 시간 내에 국가 간 라우팅을 수행 할 수도 있습니다.
답변
이 질문은 지난 몇 년간 활발한 연구 분야였습니다. 주요 아이디어는 그래프 에서 사전 처리 를 한 번 수행 하여 모든 후속 쿼리 속도 를 높이는 것 입니다. 이 추가 정보를 사용하면 여정을 매우 빠르게 계산할 수 있습니다. 여전히 Dijkstra의 알고리즘 은 모든 최적화의 기초입니다.
거미류 는 계층 적 정보를 기반으로 양방향 검색 및 엣지 프 루닝의 사용법을 설명했습니다. 이러한 속도 향상 기법은 꽤 잘 작동하지만 최신 알고리즘은 이러한 기법보다 훨씬 뛰어납니다. 현재 알고리즘을 사용하면 대륙 도로 네트워크에서 1 밀리 초 보다 훨씬 짧은 시간에 최단 경로를 계산할 수 있습니다 . Dijkstra의 수정되지 않은 알고리즘의 빠른 구현에는 약 10 초가 필요합니다 .
공학 빠른 경로 계획 알고리즘 기사 는 해당 분야의 연구 진행 상황에 대한 개요를 제공합니다. 자세한 내용은 해당 논문의 참조를 참조하십시오.
가장 빠른 알려진 알고리즘은 데이터에서 도로의 계층 상태 (예 : 고속도로 또는 지방 도로)에 대한 정보를 사용하지 않습니다. 대신, 전처리 단계에서 경로 계획을 가속화하도록 최적화 된 자체 계층 구조를 계산합니다. 그런 다음이 사전 계산을 사용하여 검색을 정리할 수 있습니다. Dijkstra 알고리즘에서 출발지와 목적지에서 멀리 떨어진 느린 도로는 고려할 필요가 없습니다. 이점은 매우 우수한 성능입니다 과 결과에 대한 정확성 보장입니다.
첫 번째로 최적화 된 경로 계획 알고리즘은 정적 도로 네트워크 만 처리했습니다. 즉, 그래프의 가장자리에 고정 비용 값이 있음을 의미합니다. 교통 체증이나 차량 의존 제한과 같은 동적 정보를 고려하기 때문에 실제로는 그렇지 않습니다. 최신 알고리즘도 이러한 문제를 해결할 수 있지만 여전히 해결해야 할 문제가 있으며 연구가 진행 중입니다.
TSP 솔루션을 계산하기 위해 가장 짧은 경로 거리가 필요한 경우 소스와 대상 사이의 모든 거리를 포함하는 행렬에 관심이있을 것입니다. 이를 위해 고속도로 계층을 사용하여 다 대다 최단 경로 계산을 고려할 수 있습니다. 최근 2 년간 새로운 접근 방식으로 개선되었습니다.
답변
삼각형 부등식 위반을 해결하는 것만으로도 그들이 최적화하는 추가 요소가 상식적입니다. 혼돈 과 파괴로 이어질 수 있기 때문에 가장 짧거나 빠른 경로를 원하지는 않습니다. . 트럭 친화적 인 주요 경로를 선호하고 모든 위성 항법 운전자가 해당 경로를 전송하도록하려면, 삼각형 부등식을 빨리 버립니다 [1].
Y가 X와 Z 사이의 좁은 주거 거리 인 경우 사용자가 XYZ를 명시 적으로 요청하는 경우 Y를 통해 바로 가기 만 사용하려고 할 수 있습니다. 그들이 XZ를 요구한다면, 조금 더 길고 더 오래 걸리더라도 주요 도로를 고수해야합니다. Braess의 역설 과 비슷 합니다. 모든 사람이 가장 짧고 빠른 경로를 사용하려고하면 정체가 발생하여 더 이상 가장 빠른 경로가 아닙니다. 여기에서 그래프 이론에서 게임 이론으로 넘어갑니다.
[1] 실제로, 일방 통행 도로를 허용하고 대칭 요구 사항을 잃으면 생성 된 거리가 수학적 의미에서 거리 함수가되기를 희망합니다. 삼각형의 불평등을 잃는 것도 상처에 소금을 문지르는 것입니다.
답변
정확성을 비교하고 입증 한 세계에서 가장 빠른 라우팅 알고리즘은 다음과 같습니다.
http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf
주제에 대한 Google 기술 강연은 다음과 같습니다.
http://www.youtube.com/watch?v=-0ErpE8tQbw
다음은 schultes가 논의한 고속도로 계층 구조 알고리즘의 구현입니다 (현재 베를린에서만 인터페이스를 작성 중이며 모바일 버전도 개발 중입니다).
답변
이전에 Google, Microsoft 또는 Yahoo Maps에서 작업 한 적이 없으므로 작동 방식을 말할 수 없습니다.
그러나 나는 에너지 회사를위한 맞춤형 공급망 최적화 시스템을 설계했으며, 여기에는 트럭에 대한 일정 및 라우팅 응용 프로그램이 포함되었습니다. 그러나 라우팅에 대한 우리의 기준은 건설 또는 교통 속도 저하 또는 차선 폐쇄 위치보다 훨씬 비즈니스에 따라 다릅니다.
우리는 트럭을 예약하고 경로를 정하기 위해 ACO (Ant Colony Optimization)라는 기술을 사용했습니다. 이 기술은 이동 판매원 문제에 적용되어 라우팅 문제를 해결 한 AI 기술입니다. ACO의 트릭은 알려진 라우팅 사실을 기반으로 오류 계산을 작성하여 그래프 해결 모델이 종료시기를 알 수 있도록하는 것입니다 (오류가 충분히 작은 경우).
Google ACO 또는 TSP에서이 기술에 대한 자세한 정보를 찾을 수 있습니다. 나는 이것을 위해 오픈 소스 AI 도구를 사용하지 않았으므로 제안 할 수는 없습니다 (SWARM이 꽤 포괄적이라고 들었지만).
답변
그래프가 엄청 나서 Dijkstra의 알고리즘과 같은 그래프 알고리즘은 작동하지 않습니다.
Dijkstra는 일반적으로 완전한 그래프를 보는 것이 아니라 매우 작은 부분 집합 (그래프를 더 잘 상호 연결할수록이 부분 집합이 더 작음)을 볼 것이기 때문에이 주장이 반드시 필요한 것은 아닙니다.
Dijkstra는 실제로 잘 작동하는 그래프에서 다소 성능이 좋을 수 있습니다. 반면에 신중하게 매개 변수를 지정하면 A *는 항상 좋은 성능을 발휘합니다. 데이터에서 어떻게 수행되는지 이미 시도 했습니까?
즉, 나는 또한 다른 사람들의 경험에 대해 듣고 싶어합니다. 물론 Google지도 검색과 같은 두드러진 예가 특히 흥미 롭습니다. 가장 가까운 이웃 휴리스틱과 같은 것을 상상할 수 있습니다.
답변
정적 도로 네트워크에 대한 쿼리 시간의 관점에서 현재의 최신 상태는 Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . 이 분야에 대한 훌륭하고 서면으로 작성된 설문 조사는 최근 Microsoft 기술 보고서 http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf 로 게시되었습니다 .
짧은 버전은 …
허브 라벨링 알고리즘은 정적 도로 네트워크에 가장 빠른 쿼리를 제공하지만 실행하는 데 많은 양의 램 (18GiB)이 필요합니다.
전송 노드 라우팅은 약간 느리지 만 약 2GiB의 메모리 만 필요하며 전처리 시간이 더 빠릅니다.
수축 계층은 빠른 사전 처리 시간, 낮은 공간 요구 사항 (0.4 GiB) 및 빠른 쿼리 시간간에 훌륭한 균형을 유지합니다.
어느 알고리즘도 완전히 지배하지는 않습니다 …
Peter Sanders의 Google 기술 강연은 흥미로울 것입니다
https://www.youtube.com/watch?v=-0ErpE8tQbw
앤드류 골드버그의 이야기
https://www.youtube.com/watch?v=WPrkc78XLhw
KIT의 Peter Sanders 리서치 그룹 웹 사이트에서 수축 계층 구조의 오픈 소스 구현을 사용할 수 있습니다. http://algo2.iti.kit.edu/english/routeplanning.php
CRP 알고리즘의 사용법에 대해 Microsoft가 작성한 쉽게 액세스 할 수있는 블로그 게시물 … http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/
