초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

이동 컴퓨팅(Mobile Computing)의 상업적인 응용분야로서, 지능형 교통정보시스템(ITS)에서의 첨단 여행자 정보시스템(ATIS)이 있다. ATIS에서 가장 중요한 이동 컴퓨팅 태스크는 현재 위치에서 목적지까지의 최단 경로를 계산하는 일이다. 본 논문에서는 최단 경로 재 계산 문제에 대해서 연구하였다. 이 문제는 전자 수치 지도(topological digital road map)상의 간선(edge) 비용이 동적인 교통 상태에 따라 빈번하게 갱신되고 있는 ATIS의 동적 경로 안내 시스템(URGS)에서 발생한다. 지금까지 제안된 방법들은 처음부터 최단 경로를 재계산하거나, 또는 단지 비용의 변화가 일어난 간건 상에 있는 양 끝 노드 사이에 대해서 최단 경로를 재계산할 뿐이다. 본 논문에서는 앞서 계산된 최단 경로에 대한 정보를 이용하는 효율적인 적응형 슬라이딩 윈도우 기반의 근접 최단 경로 재 계산 방법을 제안한다.

이동 컴퓨팅(Mobile Computing)의 상업적인 응용분야로서, 지능형 교통정보시스템(ITS)에서의 첨단 여행자 정보시스템(ATIS)이 있다. ATIS에서 가장 중요한 이동 컴퓨팅 태스크는 현재 위치에서 목적지까지의 최단 경로를 계산하는 일이다. 본 논문에서는 최단 경로 재 계산 문제에 대해서 연구하였다. 이 문제는 전자 수치 지도(topological digital road map)상의 간선(edge) 비용이 동적인 교통 상태에 따라 빈번하게 갱신되고 있는 ATIS의 동적 경로 안내 시스템(URGS)에서 발생한다. 지금까지 제안된 방법들은 처음부터 최단 경로를 재계산하거나, 또는 단지 비용의 변화가 일어난 간건 상에 있는 양 끝 노드 사이에 대해서 최단 경로를 재계산할 뿐이다. 본 논문에서는 앞서 계산된 최단 경로에 대한 정보를 이용하는 효율적인 적응형 슬라이딩 윈도우 기반의 근접 최단 경로 재 계산 방법을 제안한다.

AI 본문요약

엑셀 다운로드 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 본 논문에서는 2장에서 언급한 세 가지 특성을 이용하는 동적 윈도우 기반의 근접 춰단 경로 재계산 방법을 제안한다.
• 본 논문에서는 앞서 계산된 최단 경로의 정보를 이용하는 효율적인 적옹형 슬라이딩 윈도우 기반의 근접 최단 경로 재계 산 방법을 제안한다. 이 방법은 지도상의 임의의 두 정점 사이에 대한 최적의 최단 경로를 보 중하지는 않지만, 최적에 상당히 가까운 경로를 제공한다.
• 본 논문에서는 앞서 계산된 최단 경로정보를 이용하는 효율적인 적웅형 슬라이딩 윈도우 기반의 근접 최단 경로 채 계산방법을 제안하였다. 제안한 방법은 면밀한 실험을 통한 최단 경로상의 갱신 영향의 분석에 그 근거를 두고 있다.
• 본 논문에서는 최단 경로 재계산 문제에 대해서 연구하였다. 이 문제는 전자 수치 지도상의 간선 비용이 동적인 교통 상태에 따라 빈번하게 갱신되고 있눈 ATIS의 동적 경로 안내 시스 템(DRGS)에서 발생한다.

가설 설정

• 2. 는 세 경로, SP（s, w）, SP（u, v）, SR叫 d）들을 연결한 것이다. 즉-, N_SRs,d）= SAs,GI|SR“j）||SRsd）
• 그림 6은 제안한 방법의 기본 개념올 보여준다. 여기서, 출발 지 s에서 목적지 d까지의 최단 경로상에 간선 （月,q）의 비용이 갱신되었다고 가정한다. 2장에서의 특성 1로부터, 최단 경로상의 어떤 노드 s와 u에 대해서, s에서 /까지 그리고 d에서 u까 지의 두 간선（예를 들어, 노드 수열）이 s에서 d까지 재계산된 최단 경로에서 재사용될 것이다.
• 이 방법은 지도상의 임의의 두 정점 사이에 대한 최적의 최단 경로를 보 중하지는 않지만, 최적에 상당히 가까운 경로를 제공한다. 제안한 방법의 기본적인 가정은 실제 교통상황에서 경로 재계산에 드는 매우 큰 시간 비용을 감안할 때, 운전자들은 최적으로 재계산된 최단 경로보다 신 속히 계산되는 대략적인 최단 경로를 얻고자 한다는 것이다.

제안 방법

• 각 격자 그래프에 대해서, 5개의 노드 쌍에 대한 5개의 최단 경로를 계산하고, 각 최단 경로의 5%, 10%, ... , 90%, 95%에 해당되는 위치의 간선 비용을 갱신하였다. 그리고, 각 해당 위치의 간선 비용 갱신에 대하여 PRPU3）을 계산하였다.
• 본 논문에서는 실험을 위해 171=50 X 50개의 노드, I目 =4、x50x 49개의 방향 간선과 각각 20%, 40%, 80%, 160%, 240%, 320%의 간선 비용의 다양성（variations of edge costs）에 대옹하는 6개의 간■등한 분포 [100,12이, [100,14이, [100,18이, [100,26이, [100,340], [100,42이에 기반하여 간선 비용을 생성한 총 6x100개의 격자 그래프 G（U,E,L）률 생성하였다（각 간선 비용의 다 양성에 대해 100개씩 생성）. 그다음, 출발지와 목적지로서 5개의 노드 쌍 즉, 二l림 2와 같이 0=15, 30, 45도를 이루며 마 주보는 3개의 노드 쌍, 수직으로 마주 보는 1개의 노드 쌍3 =90）, 수평으로 마주 보는 1개의 노드 쌍 3=0）을 선택하였다.
• 제안한 방법에서 사실상 가장 중요한 작업은 살제 최단 경로에 최대로 근접하기 위한 적당한 윈도우 크기（최단 경로를 새롭게 계산해야 하는 구간 즉, 노드 u에서 노도。까지의 구간） 를 동적으로 결정하는데 있다. 먼저 제안한 방법은 윈도우를 찾는데 있어, 최단 경로상의 각 노드들에 대한/h가佰勿크기를 이용한다. 忻切을 노드 p에서의 frontierSet 크기라고 하자.
• 본 논문에서는 실험을 위해 171=50 X 50개의 노드, I目 =4、x50x 49개의 방향 간선과 각각 20%, 40%, 80%, 160%, 240%, 320%의 간선 비용의 다양성（variations of edge costs）에 대옹하는 6개의 간■등한 분포 [100,12이, [100,14이, [100,18이, [100,26이, [100,340], [100,42이에 기반하여 간선 비용을 생성한 총 6x100개의 격자 그래프 G（U,E,L）률 생성하였다（각 간선 비용의 다 양성에 대해 100개씩 생성）. 그다음, 출발지와 목적지로서 5개의 노드 쌍 즉, 二l림 2와 같이 0=15, 30, 45도를 이루며 마 주보는 3개의 노드 쌍, 수직으로 마주 보는 1개의 노드 쌍3 =90）, 수평으로 마주 보는 1개의 노드 쌍 3=0）을 선택하였다.
• 예를 들어, 출발지와 목적지 사이의 각도가 이고 간선 비용의 다양성이 20%이라면, 윈도 우를 크게 결정하기 위해 비율 以를 크게 해야 한다. 비율 a/b의 효율적인 결정 방법은 아직 연구 중이며, 제안한 방법의 효율성을 확인하기 위해 일단 임의의 값을 주어 실험하였다. 다음에서 노드 〃롤 찾는 보다 자세한 알고리즘올 보인다;

이론/모형

• 1. 노드 u에서 u까지의 최단 경로 SR虬〃）만을 A' 또는 OTO 알고리즘을 이용하여 계산한다.

성능/효과

• 2. 간선 비용 분포가 20%에서 320%까지 증가함에 따牛 PRP〈x,y）도 역시 증가한다.
• 3. 각 간선 비용 분포에 대해서, 그것의 PRP（x,y）는 최단 경로의 양 끝 노드에서 최대이고 중간 위치의 노드로 갈수록 감소하기 시작하여, 중간 노드에서 최소가 된다.
• 위 사실은 양 끝 노드에서부터 중간 노드에 가까울수록, 양 끝 노드에 비해서 선택할 수 있는 최단 경로（대안 경로）가 많아진다는 사실을 암시한다. 대안 경로의 증가는 최단 경로와 대안 경로 간의 중복 도가 낮아진다는 것을 의미하며, 결과적으로 PRP（x,y）의 값은 낮아진다.
• 2절에서 논의한다. 만으이 벡터들에 대한 정보를 이용한다면 제안한 방법의 목표인 근접 최단 경로를 효율적으로 산출할 수였다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기