동일한 실행에서 계산 된 다른 최단 경로를 고려하여 최단 경로를 동적으로 계산하는 방법은 무엇입니까?
내 주제는 건설 라인 파기 비용을 최소화하는 것입니다. 소스 지점에서 시작하여 해당 라인에 연결해야하는 여러 세대가 있습니다. 내 계획은 각 소스-> 집의 최단 경로를 계산 한 다음 겹치는 선을 잘라내는 것이 었습니다.
아래 예에서 나는 집 1-4에서가는 동부 거리에 경로를 가질 것입니다. 예를 들어, 집 4의 선은 소스 지점 (빨간색)까지가 아니라 집 3에만 도달합니다. 나는 집 1에서 3까지의 최단 경로로 최단 경로를 잘라냅니다. 그러나 집 5의 경우 최단 경로는 서쪽 도로 였을 것이므로 다른 최단 경로와 교차하지 않습니다. 그러나 실제로 4 번 집에서 연결하는 것이 더 비용 효율적이었을 것입니다. PostGIS 및 pgrouting을 사용하여 알고리즘에이 고려 사항을 어떻게 포함시킬 수 있습니까?
답변
steiner-tree의 근사치를 만들어 보겠습니다.
- 소스는 1 & 10 모서리입니다.
- 주택은 2,3,4,5,6,7,8,9,11,12,13입니다 (샘플 데이터 14, 15, 16 및 17의 정보에서 나머지 그래프와 연결이 끊어졌습니다. 노드를 고려하기 전에 연결해야 함)
- 시각적으로 모든 길이가 동일하게 보이기 때문에 가장자리가 가장자리의 ID 번호에 가중치를 부여하도록합니다.
단계 :
- sources (1,10)에 가장 가까운 집 (2,3,4,5,6,7,8,9,11,12,13)은
2(가장자리 1 사용)입니다. - sources (1,10,2)에 가장 가까운 집 (3,4,5,6,7,8,9,11,12,13)은
3(가장자리 2 사용)입니다. - sources (1,10,2,3)에 가장 가까운 집 (4,5,6,7,8,9,11,12,13)은
4(가장자리 3 사용) - sources (1,10,2,3,4)에 가장 가까운 집 (5,6,7,8,9,11,12,13)은
5(가장자리 4 사용)입니다. - sources (1,10,2,3,4,5)에 가장 가까운 집 (6,7,8,9,11,12,13)은
6(가장자리 5 사용)입니다. - sources (1,10,2,3,4,5,6)에 가장 가까운 집 (7,8,9,11,12,13)은
8(가장자리 7 사용) - sources (1,10,2,3,4,5,6,8)에 가장 가까운 집 (7,9,11,12,13)은
7(가장자리 6 사용) - sources (1,10,2,3,4,5,6,8,7)에 가장 가까운 집 (9,11,12,13)은
9(가장자리 9 사용) - sources (1,10,2,3,4,5,6,8,7,9)에 가장 가까운 집 (11,12,13)은
11(가장자리 11 사용) 따라서이 지점까지의 결과 그래프는 가장자리입니다 (2,3,4,5,6,7,8,9,11) - 기타
이 기능 pgr_dijkstraNear은 pgRouting의 개발 버전 (3.2.0-dev)에 있습니다. 이를 사용하려면 develop저장소 브랜치를 컴파일하고 빌드해야 합니다.
문서 : 해당 개발 브랜치의 최신 문서를 게시 할 시간이 없습니다. 가능한 한 빨리 여기에 다른 의견으로 게시하겠습니다.
그 동안 여기에서 처리되지 않은 문서 파일을 읽을 수 있습니다. https://github.com/pgRouting/pgrouting/blob/develop/doc/dijkstra/pgr_dijkstraNear.rst
해당 파일에 언급 된 예는 다음과 같습니다. https://github.com/pgRouting/pgrouting/blob/develop/docqueries/dijkstra/doc-pgr_dijkstraNear.result
찾고있는 스테이 너 트리입니다. 여기에 설명되어 있습니다. https://blog.routeware.dk/2018/05/29/steiner-tree/ 나는 그것이 pgrouting의 일부라고 생각하지 않습니다.
오픈 소스 솔루션을 찾고 있다면 pgRouting의 "최소 스패닝 트리"기능을 사용할 수 있습니다. 몇 가지 옵션이 있습니다.https://docs.pgrouting.org/dev/en/spanningTree-family.html