OSRM을 사용하여 단일 소스 최단 경로를 계산하는 방법은 무엇입니까?

Question

최근 라우팅 라이브러리 OSRM을 가지고 놀았습니다. 최단 경로 문제를 해결하는 데 매우 효율적으로 보인다. 그러나, 그것으로 단일 소스 최단 경로를 계산하는 방법을 보지 못했습니다. 보다 정확하게, 고정 된 출발점이 주어지면, 주어진 거리 한계 내에서 도달 할 수있는 모든 위치에 대한 최단 거리 (예를 들어, 30 분 이내에 도달 가능)를 계산한다.

OSRM은 내부적으로 축소 계층 구조를 사용합니다. 내 이해에서,이 기술은 실제 데이터에서 두 위치 사이의 거리를 계산할 때 Dijkstra의 알고리즘보다 훨씬 우수합니다. 그러나, 내 문제에 대한 Dijkstra의 알고리즘을 잘 맞는 것, 그렇지?

OSRM은 단일 소스 최단 경로 문제 (거리 제한 포함)를 계산하는 API를 제공합니까? 이 유형의 문제에 더 적합한 다른 무료 라우팅 라이브러리가 있습니까? OpenStreetMap 데이터를 잘 지원하는 것이 좋습니다.

Answer 1

OSRM은 "일대일 라우팅"을 위해 수축 계층 구조 (CH)를 사용합니다. CH가 작동하도록하려면 적응 형 양방향 알고리즘 (A *, Dijkstra, ...)이 필요하므로 단일 소스 사례가 더 어렵습니다. 하지만 하나에서 여러 알고리즘은 상대방이 원하는 목적지를 미리 알면 상대적으로 간단합니다.

조회 테이블을 사용하는 "비 목표 지향, 양방향 검색"솔루션을 원한다면 "Fast Detour Computation for Ride Sharing"또는 here 종이를 살펴보십시오.

기타 무료 라우팅 라이브러리?

내 자바 GraphHopper 프로젝트를 제안

)

하지만 물론 더있다 : http://wiki.openstreetmap.org/wiki/Routing