트랜짓 노드 라우팅

응용 수학에서 트랜짓 노드 라우팅은 장거리 이동과 관련된 하위 네트워크에 공통 액세스 노드들 사이의 연결을 미리 계산하여 최단 경로 라우팅 속도를 높이는 데 사용될 수 있다.^[1]

2007년에^[1] 프레임워크로서의 트랜짓 노드 라우팅이 확립되었고 그리드, 고속도로 계층^[2] 구조 및 수축 계층을 이용한 접근방식과 같은 많은 구체적인 구현이 몇 년 후에 표면화되었다.^[3]트랜짓 노드 라우팅은 그래프에서 중요한 노드 사이의 쌍방향 거리를 사전 처리해야 하는 정적 접근방식이다(아래에서 해당 노드 선택 방법 참조).동적 접근법은 발표되지 않았다.^[4]

직감

장거리 여행은 보통 도시 도로 대신 고속도로와 같은 도로망의 일부를 따라 운전하는 것을 포함한다.이 서브 네트워크는 희박하게 분산된 액세스 노드를 통해서만 입력할 수 있다.서로 비교했을 때, 동일한 위치에서 출발하는 여러 장거리 노선은 항상 시작 위치와 가까운 동일한 소량의 액세스 노드를 사용하여 이 네트워크에 진입한다.같은 방법으로, 유사한 대상 위치는 항상 그것들에 가까운 동일한 액세스 노드를 사용하여 도달한다.이 직관은 장거리 여행에만 적합하다.단거리를 이동할 때는 대상의 가장 빠른 경로가 로컬 도로만을 사용하기 때문에 그러한 액세스 노드는 절대 사용되지 않을 수 있다.

그러한 접속 노드의 수는 도로망의 전체 노드 수에 비해 작기 때문에, 그러한 노드들을 서로 연결하는 모든 최단 경로를 미리 계산하여 저장할 수 있다.따라서 최단 경로를 계산할 때는 시작 위치와 대상 위치에 가까운 노드에 접근하는 경로만 계산하면 된다.

일반 프레임워크

1. 트랜짓 노드 라우팅은 로드 네트워크의 모든$$ 노드 $V{\displaystyle }$ ${\$$displaystyle T\subseteq V}$의 하위 집합으로$$ 전송 노드 $T{\displaystyle }$t ${\displaystyle V}${\$displaystyle V}$을(를) 선택하는 것으로 시작한다.
2. For every node ${\displaystyle v\in V}$ dedicated sets of forward access nodes ${\displaystyle {\overrightarrow {A}}(v)\subseteq T}$ and backward access nodes ${\displaystyle {\overleftarrow {A}}(v)\subseteq T}$ are chosen from all transit nodes.
3. 이제 전송 노드 $D{\displaystyle {}_{}}$ ${\displaystyle T_{}}$ ${\$ 사이의 쌍방향 거리와$$ $노드{\displaystyle }$ v ${\displaystyle v}$ 및 해당$$ 액세스 노드 ${\displaystyle d_{}}$ $A{\displaystyle {}_{}}$ ${\$ 사이의 거리를 계산하여 저장한다$$.
4. A distance between two nodes can now be calculated as ${\displaystyle d(s,t)=\min _{u\in {\overrightarrow {A}}(s),v\in {\overleftarrow {A}}(t)}d_{A}(s,u)+D_{T}(u,v)+d_{A}(v,t)}$

위치 필터

근접 출발 지점과 대상 위치 사이의 짧은 경로에는 어떤 중계 노드가 필요하지 않을 수 있다.이 경우, 위의 프레임워크는 적어도 하나의 중계 노드를 방문하도록 경로를 강제하기 때문에 부정확한 거리로 이어진다.

이런 종류의 문제를 방지하기 위해, 위치 필터를 사용할 수 있다.지정된 시작 및 대상 위치에 대해, 위치 필터는 트랜짓 노드 라우팅을 적용해야 하는지 또는 폴백 루틴을 사용해야 하는지(로컬 쿼리)를 결정한다.

구체적인 예

트랜짓 노드 라우팅은 알고리즘이 아니라 단지 경로 계획 속도를 높이기 위한 프레임워크일 뿐이다.일반적인 프레임워크는 이를 구현하기 위해 답해야 할 몇 가지 질문을 열어둔다.

• 트랜짓 노드 선택 방법
• 액세스 노드 선택 방법
• 어떤 위치 필터를 사용해야 하는가?
• 로컬 쿼리를 어떻게 처리해야 하는가?

이 프레임워크의 다음 예시 구현은 오버레이 그리드의^[2] 셀에 있는 노드 그룹화 및 수축 계층에 기초한 보다 정교한 구현과 같은 다른 기본 방법을 사용하여 이러한 질문에 대답한다.^[3]

그리드를 이용한 기하학적 접근법

그리드 기반 접근방식에서 모든 노드의 경계 사각형은 사각 셀로 균등하게 세분된다.

액세스 노드 선택 방법

$각{\displaystyle }$ 셀 $C{\displaystyle }$ ${\displaystyle C}$에 대해$,$ 5x5 셀의$$ 내부 $영역{\displaystyle }$ I ${\displaystyle I}$과 C ${\displaystyle$ C} 주위에 있는 9x9 $셀$의 외부 $영역{\displaystyle }$ O ${\displaystyle$ O$}$를 보면 액세스 노드 집합을 찾을 수 있다$.$ 교차 노드($C{\displaystyle }$ ${\\displaystyty C$ $\).$$displaystyle I}$ or ${\displaystyle O}$), the access nodes for ${\displaystyle C}$ are those nodes of ${\displaystyle I}$ that are part of a shortest path from some node in ${\displaystyle C}$ to a node in ${\displaystyle O}$. As access nodes for an arbitrary node ${\displaystyle v\in C}$ all accC ${\displaystyle C}$의 에센스 노드가 선택됨$$(오른쪽 영상의 빨간색 점).

트랜짓 노드 선택 방법

전송 노드 집합은 모든 액세스 노드 집합의 조합이다.

어떤 위치 필터를 사용해야 하는가?

접근 노드를 선택하는 방법은 소스와 대상이 4개 이상의 그리드 셀과 떨어져 있는 경우, 트랜짓 노드를 최단 경로로 통과해야 하며, 위에서 설명한 대로 거리를 계산할 수 있다는 것을 의미한다.만약 그들이 더 가까이 누우면, 그 거리를 얻기 위해 예비 알고리즘을 사용한다.

로컬 쿼리를 어떻게 처리해야 하는가?

로컬 쿼리는 시작과 대상이 이미 서로 가깝게 놓여 있는 경우에만 필요하므로 Dijkstra의 알고리즘이나 그 확장 같은 모든 적절한 최단 경로 알고리즘을 선택할 수 있다.

공간 요구 사항

각 노드와 해당 접속 노드 사이의 사전 계산된 거리뿐만 아니라 중계 노드 사이의 쌍방향 거리도 거리 표에 저장해야 한다.

위에서 설명한 그리드 기반 구현에서, 이는 도로 그래프의 각 노드에 필요한 16바이트의 저장 공간을 산출한다.미국 도로망의 전체 그래프는 23,947,347개의 노드를 가지고 있다.^[5]따라서 거리 표를 저장하려면 약 383MB의 저장 공간이 필요할 것이다.

수축 계층 사용

트랜짓 노드 선택 방법

정의에 의해 수축 계층은 중요한 노드(즉, 많은 최단 경로의 일부인 노드)를 계층의 상단으로 이동시킨다.따라서 일련의 전송 노드를 수축 계층의 $k$ ${\displaystyle k}$ 최고 노드로 선택할 수 있다.

액세스 노드 선택 방법

$노드{\displaystyle }$ $v{\displaystyle }$ ${\displaystyle v$$}$에서 시작하는 수축 계층의 위쪽 검색을 실행하면 노드 v ${\displaystyle$v}의 전방 액세스 노드를 찾을 수 있으며$$$,$ 위쪽 검색 중에는 이전에 발견된 전송 노드가 남아 있는 가장자리가 완화되지 않는다.검색에 더 이상 위쪽 노드가 남아 있지 않을 때, 해결된 전송 노드는 $v{\displaystyle }$ ${\displaystyle v}$의 액세스 노드$.$ 역방향 액세스 노드는 유사하게 찾을 수 있다.

어떤 위치 필터를 사용해야 하는가?

계층에서 최단 상향 경로의 가장 높은 노드가 전송 노드 집합의 일부가 아닌 경우 쿼리는 로컬이었다.이는 경로의 위쪽 부분(시작 노드에서 시작됨)이나 경로의 아래쪽 부분(대상 노드에서 종료됨)은 트랜짓 노드를 포함할 수 없으며 양쪽 경로에 공통 노드가 있어야 함을 의미한다.액세스 노드를 계산하는 동안, 전송 노드를 포함하지 않고 각 노드의 검색 공간(열대 상단으로 방문한 모든 노드)을 저장할 수 있다.쿼리를 수행할 때 시작 노드와 대상 노드에 대한 검색 공간은 교차점에 대해 점검된다.위 경로와 아래 경로가 트랜짓 노드에서 일치해야 하므로 이러한 공간이 분리되면 트랜짓 노드 라우팅을 사용할 수 있다.그렇지 않으면 중계 노드가 없는 최단 경로가 있을 수 있다.

로컬 쿼리를 어떻게 처리해야 하는가?

로컬 쿼리는 수축 계층의 정규 쿼리 알고리즘을 사용한다.

참고 항목

• 최단 경로 문제
• 허브 레이블
• 양방향 검색

참조