KR100833490B1

KR100833490B1 - 궤적 정보를 이용한 최적 경로 탐색 방법 및 장치 및 궤적정보를 이용한 교통 정보 제공 방법

Info

Publication number: KR100833490B1
Application number: KR1020060036354A
Authority: KR
Inventors: 민경욱; 김주완; 박종현
Original assignee: 한국전자통신연구원
Priority date: 2005-12-08
Filing date: 2006-04-21
Publication date: 2008-05-29
Anticipated expiration: 2026-04-21
Also published as: KR20070061041A

Abstract

이동 객체의 과거 궤적 정보를 이용하여 최적 거리를 산출하기 위한 방법 및 장치, 및 과거 궤적 정보를 이용하여 교통 정보를 제공하기 위한 방법이 개시된다. 본 발명에 의한 최적 경로 탐색 방법은 출발지 및 목적지를 수신하는 단계; 출발지로부터 목적지까지의 정적 경로(static route)들을 탐색하는 정적 경로 탐색 단계, 정적 경로들에 상응하는 궤적 정보를 독출하는 궤적 정보 독출 단계, 및 궤적 정보를 기반으로 정적 경로들 중에서 최적 경로를 탐색하는 최적 경로 탐색 단계를 포함한다. 궤적 정보는, 이동 객체(moving object)가 도로망의 소정 노드를 통과할 때 이동 객체의 네비게이션 장치로부터 소정 통신망을 통하여 궤적 정보 서버로 제공되며, 궤적 정보 독출 단계는, 하나 이상의 노드를 포함하는 세그먼트에 대하여, 세그먼트 내의 최초 노드의 위치, 최초 노드를 통과한 속도, 최초 노드를 통과한 시각, 세그먼트 내의 최후 노드의 위치, 최후 노드를 통과한 속도, 및 최후 노드를 통과한 시각 중 적어도 하나를 독출하는 단계를 포함하는 것을 특징으로 한다. 본 발명에 의하여, 고가의 교통 정보 수집 장치를 이용하지 않고서도 도로망 세그먼트에 대한 교통 정보를 용이하게 수집하여 제공할 수 있으며, 도로망 세그먼트의 동적 정보를 용이하게 수집함은 물론, 수집된 과거 궤적 정보를 이용함으로써 최적 거리를 탐색할 수 있다.

Description

궤적 정보를 이용한 최적 경로 탐색 방법 및 장치 및 궤적 정보를 이용한 교통 정보 제공 방법{Method and apparatus for searching for optimal route using trajectory information and method for providing traffic information using the trajectory information}

도 1은 종래 기술에 의한 경로 탐색 방법의 문제점을 설명하기 위한 도면이다.

도 2a는 종래 기술에 의한 정적 경로 탐색 장치를 나타내는 블록도이다.

도 2b는 종래 기술에 의한 종래 기술에 의한 정적 경로 탐색 결과를 예시하는 도면이다.

도 3은 본 발명의 일 측면에 의한 최적 경로 탐색 장치를 나타내는 블록도이다.

도 4는 본 발명의 다른 측면에 의한 최적 경로 탐색 방법을 나타내는 흐름도이다.

도 5는 본 발명에 의한 최적 경로 탐색 장치 및 방법에서 이용되는 궤적 정보를 예시하는 도면이다.

도 6은 본 발명의 일 측면에 의한 최적 경로 탐색 장치에 포함되는 궤적 정보 제공부의 동작을 설명하기 위한 도면이다.

도 7은 도 6에 도시된 궤적 정보 제공부에서 제공하는 궤적 정보를 예시하는 도면이다.

도 8은 궤적 정보를 실제 도로망에 매칭하는 과정을 예시하는 도면이다.

도 9는 본 발명의 일 측면에 의한 최적 경로 탐색 장치에 적용되는 최적 경로 결정 인자를 예시하는 도면이다.

도 10은 최적 경로 분석부에서 정적 경로와 궤적 정보를 비교 분석하여 최적 경로를 산출하는 과정을 설명하기 위한 도면이다.

도 11은 본 발명의 또다른 측면에 의한 교통 정보 제공 방법을 설명하기 위한 도면이다.

도 12는 본 발명의 또다른 측면에 의한 교통 정보 제공 방법을 나타내는 흐름도이다.

본 발명은 다수 개의 노드들을 포함하는 도로망에서 최적 경로를 탐색하기 위한 방법 및 장치에 관한 것으로서, 특히 이동 객체(moving object)의 과거 궤적 정보를 저장 관리하는 이동 객체 데이터베이스의 정보를 이용하여 최적 경로를 산출하는 방법 및 장치와 이러한 궤적 정보를 이용하여 교통 정보를 제공하는 방법에 관한 것이다.

인공 위성을 이용하여 사람 및 차량 등의 주행을 위한 정보를 제공하는 항법 시스템은 흔히 네비게이션 시스템(Navigation System)이라고 불리며, 통신 기술의 발달에 힘입어 급속도로 보급되고 있다. 네비게이션 시스템은, 이용자가 출발지, 목적지, 경유지 등을 설정하면 출발지에서 경유지점들을 거쳐 목적지까지의 경로를 지도 상에 표시하고 운전자가 목적지까지 도달하기 위한 부가 정보를 알려준다. 네비게이션 시스템이 보급됨으로써, 사용자는 초행길도 당황하지 않고 찾아갈 수 있으며, 경로를 찾지 못함으로써 발생되는 불필요한 연료의 낭비도 방지할 수 있다.

또한, 이러한 네비게이션 시스템은, 지도 데이터 중 노드 및 링크로 구성된 도로망 정보를 이용하여 경로를 탐색하고, 탐색된 경로의 거리와 링크의 가중치를 고려하여 사용자가 선택한 바에 따라 다양한 경로를 제공한다. 링크의 가중치에는 고속도로의 통행료나 상대적으로 혼잡한 경로를 고려하기 위한 가중치가 포함된다. 사용자는 출발지 및 목적지까지의 여러 가지 경로 중에서 최단 경로, 최저 비용 경로, 국도를 이용한 경로, 및 최적 경로 등 자신이 원하는 옵션을 부여하여 자신의 목적에 상응하는 경로를 전체 경로로서 선택한다.

종래 기술에 의한 경로 산출하는 방법은 기본적으로 도로망 데이터를 이용한다. 도로망 데이터는 라인세그먼트와 노드로 구성이 되어 있으며, 연결정보를 가지고 있다. 노드란 도로망의 특정 지점을 의미하며, 세그먼트란 두 개 이상의 노드를 연결하는 지로(branch)를 나타낸다. 또한 각 도로 세그먼트는 최대 속도, 최소 속도, 차선, 거리 등의 속성 정보를 포함하고 있다. 종래 기술에 의한 경로 산출 방법에 따르면, 이러한 도로 세그먼트의 연결 정보 및 속성 정보를 이용하여 최 단 경로를 산출한다.

도 1에 도시된 바와 같이 S->E로의 진행 결과가 S->J->E 이고, 총 거리는 7km, 예상 소요 시간은 7분 임을 알 수 있다. 하지만, 실제 상황에서는 차량의 속도는 커브(curve)구간과 교차로(junction)구간에서는 감속되기 때문에 도로 세그먼트의 최고 속도 및 거리를 이용하여 예상 소요시간을 추출하는 것은 신뢰성이 떨어진다. 즉, 정적인 도로망의 정보만으로는 최적의 경로를 탐색하기 힘들다.

도 2a는 종래 기술에 의한 정적 경로 탐색 장치를 나타내는 블록도이다. 정적 경로 결정부(210)는 도로망 데이터베이스 관리 서버(DBMS, DataBase Management Server)에 경로를 질의한다. 그러면, 도로망 데이터베이스 관리 서버(DBMS)는 데이터베이스(DB)에 경로를 문의한다. 데이터베이스(DB)는 도시된 바와 같이, 각 세그먼트의 거리, 속력 등을 포함한다.

도 2b에 도시된 경로의 정적 정보는 데이터베이스(DB)로부터 도로망 데이터베이스 관리 서버(DBMS)로 전달되고, 도로망 데이터베이스 관리 서버(DBMS)는 정적 경로 결정부에 정적 정보를 송신한다.

그런데, 이러한 방법은 정적인 세그먼트의 속성 정보를 이용하여 산출하기 현실 상황에 잘 맞지가 않다. 그 이유는, 도로의 상황은 항시 수시로 변경되기 때 문이다. 예를 들면, 출퇴근 시간에는 일반적으로 도로가 많이 정체되어 최대 속도를 낼 수가 없기 때문에 도로 세그먼트의 정적인 속성 정보만을 이용하여 최단 경로를 추출한 정보는 정확하고 신뢰 있는 정보가 아니다.

이러한 문제점을 해결하기 위하여, 실시간 교통 정보를 포함하여 정적 경로를 제공하는 방법이 고안되었다. 즉, 교통정보는 실시간 교통정보와 과거 누적된 교통정보로 구분이 되며, 이들 교통 정보는 도로망에 설치된 교통 정보 수집 장치(카메라, 센서 등)를 이용하여 수집 및 제공된다. 과거에 누적된 교통정보를 이용함으로써 특정 도로의 특정 시간에 차량의 평균 속도 정보를 제공할 수가 있다. 이러한 방법을 이용하면 전술한 방법에 비하여 과거 누적된 교통정보에 기반하여 경로 산출을 할 수 있으므로 보다 신뢰 있는 경로정보를 제공할 수가 있다. 그 이유는 과거 누적된 교통 정보를 분석하여 특정 시간대의 차량의 평균 속도를 계산할 수가 있기 때문이다.

하지만, 교통 정보를 수집하기 위한 장치는 고가의 장비이고, 모든 도로에 설치되지 못하기 때문에 최적 경로 산출에 정보를 활용하는데 한계가 있다.

그러므로, 고가의 시스템 구축 비용을 들이지 않고서도 과거 누적된 교통 정보를 적극적으로 수집하고 활용함으로써 교통 정보 수집 장치가 없는 지역에 대해서 이동 객체 데이터베이스의 과거 차량의 이동 궤적 정보를 이용하여 도로 구간별 특정시간대의 평균 속도를 산출할 수 있는 방법이 절실히 요구된다.

본 발명의 목적은 고가의 교통 정보 수집 장치를 이용하지 않고서도 도로망 세그먼트에 대한 교통 정보를 용이하게 수집하여 제공할 수 있는 교통 정보 제공 방법을 제공하는 것이다.

또한, 본 발명의 목적은 고가의 교통 정보 수집 장치를 이용하지 않고서도 도로망 세그먼트의 동적 정보를 용이하게 수집함은 물론, 수집된 과거 궤적 정보를 이용함으로써 최적 거리를 탐색할 수 있는 방법 및 장치를 제공하는 것이다.

상기와 같은 목적들을 달성하기 위한 본 발명의 일면은, 다수 개의 노드를 포함하는 도로망에서 최적 경로를 탐색하는 방법으로서, 출발지 및 목적지를 수신하는 단계; 출발지로부터 목적지까지의 정적 경로(static route)들을 탐색하는 정적 경로 탐색 단계; 정적 경로들에 상응하는 궤적 정보를 독출하는 궤적 정보 독출 단계; 및 궤적 정보를 기반으로 정적 경로들 중에서 최적 경로를 탐색하는 최적 경로 탐색 단계를 포함하는 최적 경로 탐색 방법에 관한 것이다. 궤적 정보는, 이동 객체(moving object)가 도로망의 소정 노드를 통과할 때 이동 객체의 네비게이션 장치로부터 소정 통신망을 통하여 궤적 정보 서버로 제공되는 것을 특징으로 한다. 본 발명에 의한 궤적 정보 독출 단계는, 하나 이상의 노드를 포함하는 세그먼트에 대하여, 세그먼트 내의 최초 노드의 위치, 최초 노드를 통과한 속도, 최초 노드를 통과한 시각, 세그먼트 내의 최후 노드의 위치, 최후 노드를 통과한 속도, 및 최후 노드를 통과한 시각 중 적어도 하나를 독출하는 단계를 포함하는 것을 특징으로 한다. 또한, 본 발명에 의한 최적 경로 탐색 단계는, 소정의 최적 경로 결정 인자를 선택하는 단계; 최적 경로 결정 인자에 상응하는 가중치를 정적 경로들에 적용하는 적용 단계; 및 가중치가 적용된 정적 경로들 중에서 최적 경로를 결정하는 단계를 포함하는 것을 특징으로 한다. 바람직하게는, 최적 경로 결정 인자는 거리, 요일, 시각, 및 통과 시간 중 적어도 하나를 포함하는 것을 특징으로 한다. 뿐만 아니라, 본 발명에 의한 적용 단계는, 정적 경로들 중에서 출발 시각과 근사한 시간대에 해당하는 정적 경로들을 최적 경로 후보들로서 선택하는 단계 및 선택된 최적 경로 후보들에 가중치를 적용하는 단계를 포함하는 것을 특징으로 한다.

상기와 같은 목적들을 달성하기 위한 본 발명의 다른 면은, 다수 개의 노드를 포함하는 도로망의 교통 정보를 제공하는 방법으로서, 이동체가 도로망의 소정 노드를 통과할 때, 이동 객체의 네비게이션 장치가 소정 통신망을 통하여 궤적 정보 서버로 궤적 정보를 송신하는 궤적 정보 송신 단계; 궤적 정보를 수신하고, 수신된 궤적 정보에 기반하여 교통 정보를 생성하는 교통 정보 생성 단계; 생성된 교통 정보에 대한 요청에 응답하여 교통 정보를 제공하는 교통 정보 제공 단계를 포함하는 궤적 정보를 이용한 교통 정보 제공 방법에 관한 것이다. 본 발명의 다른 면에 의한 교통 정보 생성 단계는, 궤적 정보에 기반하여 세그먼트를 통과한 차량의 평균 속도를 연산하는 단계 및 연산된 평균 속도를 시간 및 요일을 기준으로 분류하여 저장하는 단계를 포함하는 것을 특징으로 한다. 또한, 교통 정보 생성 단계는 세그먼트 내의 교통 정보 카메라로부터 수집된 정보를 더 이용하여 평균 속도를 연산하는 단계를 더 포함하는 것을 특징으로 한다.

상기와 같은 목적들을 달성하기 위한 본 발명의 또다른 면은, 다수 개의 노드를 포함하는 도로망에서 최적 경로를 탐색하는 장치로서, 출발지 및 목적지를 수 신하기 위한 입력부; 출발지로부터 목적지까지의 정적 경로들을 제공하기 위한 정적 경로 제공부; 정적 경로들에 상응하는 궤적 정보를 제공하기 위한 궤적 정보 제공부; 및 궤적 정보를 기반으로 정적 경로들 중에서 최적 경로를 탐색하는 최적 경로 분석부를 포함하는 최적 경로 탐색 장치에 관한 것이다. 본 발명에 의한 최적 경로 분석부는, 소정의 최적 경로 결정 인자를 선택하고, 최적 경로 결정 인자에 상응하는 가중치를 정적 경로들에 적용하며, 가중치가 적용된 정적 경로들 중에서 최적 경로를 결정하는 것을 특징으로 한다. 또한, 본 발명에 의한 최적 경로 분석부는, 정적 경로들 중에서 출발 시각과 근사한 시간대에 해당하는 정적 경로들을 최적 경로 후보들로서 선택하고, 선택된 최적 경로 후보들에 가중치를 적용하는 것을 특징으로 한다.

본 발명에 의하여 도로망의 각 세그먼트의 동적 정보를 용이하게 수집함은 물론, 수집된 동적 정보를 이용하여 최적 경로를 산출할 수 있다.

본 발명과 본 발명의 동작상의 이점 및 본 발명의 실시에 의하여 달성되는 목적을 충분히 이해하기 위해서는 본 발명의 바람직한 실시예를 예시하는 첨부 도면 및 첨부 도면에 기재된 내용을 참조하여야만 한다.

이하, 첨부한 도면을 참조하여 본 발명의 바람직한 실시예를 설명함으로서, 본 발명을 상세히 설명한다. 각 도면에 대하여, 동일한 참조부호는 동일한 부재임을 나타낸다.

본 발명에 따른 최적 경로 탐색 장치(300)는 다른 어플리케이션(310) 및 네비게이션 장치(320)와 상호작용하며, 최적 경로 분석부(350), 정적 경로 제공부(360), 궤적 정보 제공부(370)를 포함한다. 또한, 본 발명에 따른 최적 경로 탐색 장치는 교통 정보 처리부(400)와 상호 작용할 수 있으며, 교통 정보 처리부(400)는 교통 정보 제공부(460) 및 교통 정보 추출부(450)를 포함한다. 교통 정보 처리부(400)는 다른 어플리케이션(410) 및 카메라(420)로부터 교통 정보를 수신할 수 있다.

각 이동 객체에는 서버(미도시)로 자신의 위치를 전송할 수 있는 네비게이션 장치(320)가 장착된다. 궤적 정보 제공부(370)는 이동 객체로부터 수신된 위치 정보를 저장 및 관리한다.

어플리케이션(310)에서 미들웨어 서버로 시작점과 끝점에 대한 최적 경로 요청이 있을 경우 정적 경로 제공부(360)는 정적 경로 정보를 산출하여 최적 경로 분석부(350)로 제공한다. 또한, 궤적 정보 제공부(370)는 특정 시작점과 끝점을 지나간 이동 객체의 과거 궤적 정보를 추출하여 최적 경로 분석부(350)로 제공한다. 그러면, 최적 경로 분석부(350)는 정적 경로 제공부(360) 및 궤적 정보 제공부(370)로부터 수신된 정보를 분석하여 최적 경로를 산출하게 된다. 이때 최적 경로 분석부(350)는 최적 경로 결정 인자를 적용하여 최적 경로를 결정한다. 최적 경로 결정 인자에 대해서는 본 명세서의 해당 부분에서 상세히 후술된다.

교통 정보 처리부(400)는 교통정보 수집 카메라(420)가 설치되어 있는 도로 구간에서는 과거 특정 시점의 평균 속도를 계산하게 되지만, 카메라가 설치되어 있 지 않은 도로 구간에 대해서는 궤적 정보 제공부(370)로부터 수신한 과거 궤적 정보를 이용하여 구간별, 특정 시간에 대한 평균 속도를 연산하여 교통 정보를 생성하고, 생성된 교통 정보를 제공한다.

궤적 정보 제공부(370)에 이동 객체의 과거 궤적 정보를 제공하기 위해서, 네비게이션 장치(320)는 서버(미도시)로 주기적 또는 비주기적으로 위치를 전송한다. 네비게이션 장치(320)에서 서버로 이동 객체의 위치를 보고함에 있어서, 주기적인 방법이 아닌, 도로 구간에 진입시 최초 획득한 GPS 위치정보를 서버로 전송하는 방법을 이용할 수 있다. 이와 같이 주요 노드를 통과할 때마다 궤적 정보를 제공함으로써 네비게이션 장치(320) 및 서버 간의 불필요한 통신 부하를 절감할 수 있다. 하지만, 본 발명은 이에 한정되는 것은 아니며, 동일 세그먼트 내에서 주기적으로 여러 번 위치를 전송할 수도 있다. 서버로 전송하는 궤적 정보에 대해서는 도 5를 이용하여 상세히 후술된다.

네비게이션 장치(320) 및 서버 간의 통신은 위성 통신망, CDMA 통신망, GSM 통신망, 무선 근거리 통신망, 및 와이브로 통신망과 같은 무선 통신 기법을 이용하여 이루어질 수 있다. WiBro(Wireless Broadband Internet)란 휴대형 단말기를 이용하여 정지 및 이동 중에 고속의 전송 속도로 인터넷에 접속하여 다양한 정보 및 콘텐츠를 이용하도록 하는 초고속 인터넷 서비스를 의미한다. 와이브로는 2.3GHz 주파수 대역을 이용하여 셀 반경 1Km이내, 이동시 최소 60Km/H 이상에서도 끊김 없는 무선 인터넷 서비스를 보장하며, 와이브로 서비스를 이용함으로써, 사용자는 주행 중에서도 지도 데이터를 용이하게 갱신할 수 있는 장점을 가진다.

우선, 출발지 및 목적지가 수신되고(S410), 수신된 출발지 및 목적지 간의 정적 경로가 탐색된다(S420). 정적 경로는 종래 기술에 의한 모든 알고리즘을 이용하여 탐색될 수 있는 것은 물론이다.

그러면, 정적 경로들에 상응하는 궤적 정보가 존재하는지 판단한다(S430). 즉, 탐색된 정적 경로 중에서 최적 경로를 선택하기 위하여 과거 궤적 정보를 이용하기 위하여 탐색된 정적 경로 내에 궤적 정보가 포함되는지 여부를 판단한다. 궤적 정보가 존재한다면 궤적 정보를 독출한다(S440).

궤적 정보는, 세그먼트 내의 최초 노드의 위치, 최초 노드를 통과한 속도, 최초 노드를 통과한 시각, 세그먼트 내의 최후 노드의 위치, 최후 노드를 통과한 속도, 및 최후 노드를 통과한 시각 등을 포함할 수 있다. 이러한 궤적 정보를 이용하여 특정 세그먼트의 시간대별 요일별 평균 속도를 용이하게 연산할 수 있다.

그러면, 최적 경로 결정 인자가 선택된다(S450). 최적 경로 결정 인자는 과거 궤적 정보 중에서 특히 중요한 궤적 정보에 가중치를 부여하기 위하여 이용된다. 최적 경로 결정 인자가 선택되면, 선택된 최적 경로 결정 인자를 적용하여 정적 경로들 중에서 최적 경로를 탐색한다(S460). 더 상세히 설명하면, 최적 경로는 최적 경로 결정 인자에 상응하는 가중치를 정적 경로들에 적용하고, 가중치가 적용 된 정적 경로들 중에서 최적 경로를 결정하는 과정을 통하여 수행된다. 이 경우 최적 경로 결정 인자는 정적 경로들 중에서 출발 시각과 근사한 시간대에 해당하는 정적 경로들을 최적 경로 후보들로서 선택하고, 선택된 최적 경로 후보들에 가중치를 적용함으로써 수행될 수 있다. 최적 경로 후보들을 선택하는 이유는, 정적 경로들에 사용자가 현재 진행하고자 하는 시간에 상응하는 궤적 정보만을 적용하는 것이 연산량을 절감시킬 수 있기 때문이다.

도 4에 도시된 바와 같이, 본 발명에 의한 최적 경로 탐색 방법에서는 도로망의 정적 상태에 대한 정적 경로에 해당 도로망의 과거 궤적 정보를 이용한 가중치를 부여함으로써, 사용자에게 더 신뢰성 있는 최적 경로를 제공할 수 있다.

도 5에 도시된 바와 같이, 네비게이션 장치(도 3의 320 참조)는 특정 노드들(510, 520, 550, 560)을 통과할 때 해당 노드의 식별자(570), 시작 및 종료 노드들의 위치(Position X, Position Y), 시작 및 종료 노드들에서는 속력(Velocity X, Velocity Y), 해당 노드, 및 통과 시간(Time), 및 세그먼트 식별자(SegmentID)를 서버로 전송하는 것이 바람직하다. 도 5에 도시된 실시예에서, 세그먼트 1은 노드 520으로부터 노드 550 까지의 세그먼트이며, 세그먼트 2는 노드 550으로부터 노드 560까지의 세그먼트를 나타낸다.

서버는 도 5에 도시된 바와 같은 궤적 정보를 수신하고, 수신된 정보를 이용하여 해당 세그먼트를 통과하는 특정 시간대별 평균 속도를 연산하여 해당 세그먼 트에 대한 동적 정보를 생성할 수 있다.

궤적 정보 제공부(610)에 궤적 정보 요청이 수신되면, 궤적 정보 제공부(610)는 동적 객체 데이터베이스 관리 서버(630)에 궤적 정보를 질의한다. 그러면, 동적 객체 데이터베이스 관리 서버(630)는 동적 객체 데이터베이스(MODB, Moving Object DataBase)(650)에 궤적 정보를 질의하여 수신한다. 수신된 궤적 정보는 다시 동적 객체 데이터베이스 관리 서버(630)로부터 궤적 정보 제공부(610)로 전달되며, 궤적 정보 제공부(610)는 수신한 궤적 정보를 버퍼링하고, 버퍼링한 궤적 정보를 궤적 결과로서 제공한다. 도 6에서, 시작 노드(START) 및 끝 노드(END) 사이에 세 개의 궤적들(T1, T2, T3)이 존재하며, 현재 이동 객체(MO, Moving Object)는 제3 궤적(T3) 상에서 이동중이라는 것을 알 수 있다. 각 궤적들(T1, T2, T3)에 해당하는 궤적 정보는 표에 예시되며, 동적 객체 데이터베이스 관리 서버(630)에서 저장 및 관리하는 이동 객체의 과거 궤적 정보는 도 6에서 각 이동 객체(MO)에 상응하는 리스트로 구성된다. 즉, 이동 객체 데이터베이스(DB)(650)는 각 이동 객체의 과거의 위치 정보, 속도 정보, 시간 정보, 및 세그먼트 식별자를 포함하며, 하나의 이동 객체에 대한 항목이 하나의 궤적 정보를 구성한다. 이동 객체 데이터베이스(DB)(650)에 저장되는 궤적 정보는 도 7을 이용하여 상세히 후술된다.

도 7에서 제1 궤적(T1)의 거리는 35km이며, 출발 시간은 13:00이고, 종료 시간은 13:50이므로 통과하는데 50분이 소요되었음을 알 수 있다. 마찬가지 방법으로, 제2 및 제3 궤적(T2, T3)에 대해서도 각 궤적의 거리, 출발 시간, 종료 시간, 및 통과 소요 시간을 알 수 있다. 그러면, 도 7에 도시된 궤적 정보로부터, 13시 경에 제1 궤적(T1)을 통과하는 평균 속도는 35/(50/60)=42km/h 이며, 10시 40분 경에 제2 궤적(T2)을 통과하는 평균 속도는 45.8km/h 이고, 10시 40분 경에 제3 궤적(T3)을 통과하는 평균 속도는 60km/h 라는 것을 용이하게 알아낼 수 있다. 이렇게 연산된 동적 정보가 최적 경로 분석부(도 3의 350 참조)에 제공되어 최적 경로를 결정하는데 이용된다.

도 6에 도시된 이동 객체 데이터베이스(DB)(650)에 저장되는 과거 궤적 정보는 단지 이동 객체 각각의 항목의 리스트로 구성된다. 이때, 이동 객체의 위치 정보를 연결한 선은 유클리디언 거리이기 때문에 실제 도로망에 대한 경로 정보를 산출할 수가 없다. 유클리디언 거리는 도 8에서 점선으로 표시되며 실제 도로망에서의 경로는 도 8에서 실선으로 표시된다. 그러므로, 궤적 정보를 실제 도로망에 상응하도록 매칭시키는 과정이 필요하다. 도 8에 도시된 바와 같이, 점선으로 표시된 유클리디언 거리는 네 개의 세그먼트들(S1, S2, S3, S4) 각각으로 매칭되어 실제 도로망 상태에 상응하게 된다. 이 과정에서 궤적 정보를 구성하는 이동 객체의 세그먼트 식별자(도 5의 SegmentID 참조)를 이용하여 실제 도로 구간을 추출할 수 있다.

최적 경로 분석부(도 3의 350)는 정적 경로 제공부(360)에서 제공하는 정적 경로 정보와 궤적 정보 제공부(370)에서 제공하는 과거 궤적 정보를 이용하여 최적 경로를 탐색한다. 이 과정에서 최적 경로 결정 인자(ORDF: Optimal Route Determination Factor)가 이용된다.

최적 경로 결정 인자(ORDF)는 여러 가지 요소를 포함할 수 있으며, 도 9와 같이 예를 들어 거리, 소요시간, 통과 시간, 특징적 시간, 특징 요일, 및 속력 등의 항목을 포함할 수 있다. 그러면, 최적 경로 분석부(350)는 정적 경로에 최적 경로 결정 인자(ORDF)에 상응하는 가중치(w_d, w_t, w_f, w_w, w_s)를 적용하여 최종적으로 최적 경로를 결정한다. 각 가중치들의 합은 1이 되는 것이 바람직하다.

예를 들어, 통과 시간에 가장 높은 가중치(w_t)를 부여한다면, 다른 인자보다 통과 시간이 양호한 경로를 최적 경로로 결정하게 된다. 그런데, 동일한 시간대라도 평일 및 휴일에 대한 최적 경로는 상이할 수밖에 없다. 그러므로, 휴일 등의 특징적 요일에 더 높은 가중치(ww)를 부여함으로써, 요일에 가장 높은 비중을 두어 최적 경로를 선택할 수 있다.

도 10의 (a) 내지 (d)는 정적 경로 제공부(도 3의 360)로부터 제공된 정적 경로 및 궤적 정보 제공부(도 3의 370)로부터 제공된 궤적 정보를 이용하여 최적 경로를 산출함에 있어서, 최적 경로 결정 인자(ORDF)로서 거리, 통과 시간, 및 도착 시간을 이용하여 최적 경로 분석을 하는 경우를 예시하는 도면이다. 만약, 도착 시간에 가장 높은 가중치를 할당한 경우에는 (a) 및 (b)에 도시된 궤적 정보가 더 정확한 경로 정보를 제공할 수 있다. 즉, (a)를 참조하면, 정적 경로 정보만을 이용할 경우 A 내지 B 노드 간의 30km 경로는 30분 안에 통과할 수 있는 것으로 보이지만, (b)에서 알 수 있는 바와 같이, 과거 궤적정보의 경험상 10:00정도에는 30분이 아닌 45분 정도가 실제 소요됨을 알 수 있다. 그러므로, 10시 10분 경의 최단 통과 시간을 얻기 위해서는 최단 거리인 (a)에 도시된 경로가 아니라 (c)에 도시된 경로를 최적 경로로서 선택해야 한다는 것을 알 수 있다.

도 10에 도시된 바와 같이, 본 발명에 의한 최적 경로 탐색 방법에 따르면, 도로망의 정적 경로만을 이용하는 것이 아니라, 여러 경로의 과거 궤적 정보를 동적으로 이용함으로써, 시간대별 최적 경로를 용이하게 제공할 수 있다.

교통정보 제공 시스템에서는 교통정보 수집 카메라가 있는 도로 구간에 대한 과거 특정 시간별 평균 속도 정보를 제공한다. 도 11에 도시된 바와 같이, 세그먼트들(S1, S2)에 포함되는 특정 시간 간격(Time Interval: [Ti, Tj])에 대한 차량의 평균 속도(average speed) 정보가 이동 객체 데이터베이스(DB)(730)에 저장 및 관 리된다.

전술된 바와 같이, 교통 정보 수집 카메라가 존재하지 않는 구간에 대해서는 이동 객체 DBMS(740)에 과거 궤적 질의를 수행함으로써 위와 같은 구간별, 특정 시간대에 해당하는 평균 속도를 추출할 수 있다. 그러면 추출된 교통 정보는 교통 정보 추출부(750)로 전송되어 교통 정보 제공부(760)로 전달된다. 교통 정보 추출부(750)로부터 추출된 교통 정보는 교통 정보 데이터베이스(DB)(790)에 저장된다.

도 11에 도시된 바와 같이, 본 발명에 의한 교통 정보 제공 방법에서는 교통 정보 수집 카메라가 존재하지 않는 구간에 대해서도, 특정 세그먼트의 과거 궤적 정보를 이용함으로써 정밀하게 교통 정보를 추출할 수 있다.

우선 도로망으로부터 특정 교통 정보가 필요한 세그먼트가 추출된다(S910). 그러면, 해당 세그먼트 내에 교통 정보 수집 카메라가 존재하는지 여부가 판단된다(S920). 교통 정보 수집 카메라가 존재하는 세그먼트에 대해서는 기존에 교통 정보 수집 카메라에 의하여 수집된 교통 정보가 독출된다(S960). 만일, 해당 세그먼트에 교통 정보 수집 카메라가 존재하지 않는다면, 데이터베이스(DB)에 과거 궤적 정보를 질의한다(S930).

그러면, 이동 객체 데이터베이스(DB)로부터 해당 세그먼트의 과거 궤적 정보를 수신하고, 수신된 궤적 정보로부터 시간별 평균 속도를 추출한다(S940). 추출된 교통 정보는 교통 정보 데이터베이스(DB)에 제공된다(S950).

전술된 바와 같이, 궤적 정보는 이동 객체가 도로망의 소정 노드를 통과할 때, 이동 객체의 네비게이션 장치에 의하여 무선 통신망을 통하여 궤적 정보 서버로 송신된 것이다. 그러면, 수신된 궤적 정보에 기반하여 교통 정보가 생성되기 때문에, 교통 정보 수집 카메라가 존재하지 않는 세그먼트에 대해서도 정밀하고 용이하게 교통 정보를 수집할 수 있다. 수신된 궤적 정보로부터 교통 정보를 생성하는 과정은, 해당 세그먼트 별 평균 속도를 연산하고, 연산된 평균 속도를 시간 및 요일을 기준으로 분류하여 저장함으로써 수행될 수 있음은 전술된 바와 같다. 본 발명은 도면에 도시된 실시예를 참고로 설명되었으나 이는 예시적인 것에 불과하며, 본 기술 분야의 통상의 지식을 가진 자라면 이로부터 다양한 변형 및 균등한 타 실시예가 가능하다는 점을 이해할 것이다. 예를 들면, 본 발명에 의한 교통 정보 수집 방법에서는 교통 정보 수집 카메라가 존재하는 세그먼트에 대해서는 교통 정보 수집 카메라에 의하여 독출된 교통 정보를 수신하여 이용하는 것으로 도시되었으나, 본 발명은 이에 한정되는 것이 아니다. 따라서, 교통 정보 수집 카메라가 존재하는 세그먼트에 대해서도 궤적 정보를 이용하여 교통 정보를 생성할 수 있음은 물론이다.

따라서, 본 발명의 진정한 기술적 보호 범위는 첨부된 등록청구범위의 기술적 사상에 의해 정해져야 할 것이다.

본 발명에 의하여, 고가의 교통 정보 수집 장치를 이용하지 않고서도 도로망 세그먼트에 대한 교통 정보를 용이하게 수집하여 제공할 수 있으며, 도로망 세그먼 트의 동적 정보를 용이하게 수집함은 물론, 수집된 과거 궤적 정보를 이용함으로써 최적 거리를 탐색할 수 있다.

또한, 본 발명에 의하여, 정적인 도로망 데이터를 이용하여 비현실적인 경로 정보를 산출하는 것이 아니라, 이동 객체의 위치 정보를 저장 관리하여, 과거 이동 궤적 정보인 경험 정보를 추출하여 보다 현실성 있고, 보다 정확한 최적 경로를 산출할 수 있다. 그러므로, 본 발명은 현재 산업계에 널리 쓰이고 있는 네비게이션, 물류 차량 관리 시스템 등에 직접 활용될 수 있으며, 과거 누적된 정보인 구간별 평균 속도 정보를 제공할 수 있는 교통정보 제공 시스템에서 제공하지 못하는 특정 지역에 대해서, 이동객체 데이터베이스의 과거 궤적정보를 추출함으로써, 구간별, 시간별 평균 속도 정보를 추출할 수 있다. 본 발명을 이용함으로써 교통정보 방송 및 다양한 응용에서 활용 가능한 교통정보 제공 시스템의 정확성이 향상될 수 있다.

Claims

다수 개의 노드들을 포함하는 도로망에서 최적 경로를 탐색하는 방법에 있어서,

출발지 및 목적지를 수신하는 단계;

상기 출발지로부터 상기 목적지까지의 정적 경로(static route)들을 탐색하는 정적 경로 탐색 단계;

상기 정적 경로들에 따라 상기 출발지에서 상기 목적지로 이동했던 이동객체의 궤적 정보를 독출하는 궤적 정보 독출 단계; 및

상기 궤적 정보를 기반으로 상기 정적 경로들 중에서 최적 경로를 탐색하는 최적 경로 탐색 단계를 포함하며, 상기 궤적 정보는,

상기 이동 객체(moving object)가 상기 도로망의 노드를 통과할 때 상기 이동 객체의 네비게이션 장치로부터 무선 통신망을 통하여 전송받아 저장된 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 방법.
제1항에 있어서, 상기 궤적 정보 독출 단계는, 적어도 하나 이상의 노드를 포함하는 세그먼트에 대하여,

상기 세그먼트 내의 최초 노드의 위치, 상기 최초 노드를 통과한 속도, 상기 최초 노드를 통과한 시각, 상기 세그먼트 내의 최후 노드의 위치, 상기 최후 노드를 통과한 속도, 및 상기 최후 노드를 통과한 시각을 독출하는 단계를 포함하는 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 방법.
제2항에 있어서, 상기 최적 경로 탐색 단계는,

상기 독출된 궤적 정보 중에서 선택된 최적 경로 결정 인자에 상응하는 가중치를 상기 정적 경로들에 적용하는 적용 단계; 및

상기 가중치가 적용된 정적 경로들 중에서 최적 경로를 결정하는 단계를 포함하는 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 방법.
제3항에 있어서, 상기 최적 경로 결정 인자는,

거리, 요일, 시각, 및 통과 시간 중 적어도 하나를 포함하는 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 방법.
제3항에 있어서, 상기 적용 단계는,

상기 정적 경로들 중에서 출발 시각과 근사한 시간대에 해당하는 정적 경로들을 최적 경로 후보들로서 선택하는 단계 및

상기 선택된 최적 경로 후보들에 상기 가중치를 적용하는 단계를 포함하는 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 방법.
제1항에 있어서, 상기 무선 통신망은,

위성 통신망, CDMA 통신망, GSM 통신망, 무선 근거리 통신망, 및 와이브로 통신망 중 하나인 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 방법.
삭제
삭제
삭제
삭제
삭제
다수 개의 노드를 포함하는 도로망에서 최적 경로를 탐색하는 장치에 있어서,

출발지 및 목적지를 수신하기 위한 입력부;

상기 출발지로부터 상기 목적지까지의 정적 경로들을 제공하기 위한 정적 경로 제공부;

상기 정적 경로들에 따라 상기 출발지에서 상기 목적지로 이동했던 이동 객체의 궤적 정보를 제공하기 위한 궤적 정보 제공부; 및

상기 궤적 정보를 기반으로 상기 정적 경로들 중에서 최적 경로를 탐색하는 최적 경로 분석부를 포함하며, 상기 궤적 정보는,

상기 이동 객체(moving object)가 상기 도로망의 노드를 통과할 때 상기 이동 객체의 네비게이션 장치로부터 무선 통신망을 통하여 전송받아 저장된 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 장치.
제12항에 있어서, 상기 궤적 정보 제공부는, 적어도 하나 이상의 노드를 포함하는 세그먼트에 대하여,

상기 세그먼트 내의 최초 노드의 위치, 상기 최초 노드를 통과한 속도, 상기 최초 노드를 통과한 시각, 상기 세그먼트 내의 최후 노드의 위치, 상기 최후 노드를 통과한 속도, 및 상기 최후 노드를 통과한 시각을 제공하는 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 장치.
제13항에 있어서, 상기 최적 경로 분석부는,

상기 제공된 궤적 정보 중에서 선택된 최적 경로 결정 인자에 상응하는 가중치를 상기 정적 경로들에 적용하며,

상기 가중치가 적용된 정적 경로들 중에서 상기 최적 경로를 결정하는 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 장치.
제14항에 있어서, 상기 최적 경로 결정 인자는,

거리, 요일, 시각, 및 통과 시간 중 적어도 하나를 포함하는 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 장치.
제14항에 있어서, 상기 최적 경로 분석부는,

상기 정적 경로들 중에서 출발 시각과 근사한 시간대에 해당하는 정적 경로들을 최적 경로 후보들로서 선택하고,

상기 선택된 최적 경로 후보들에 상기 가중치를 적용하는 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 장치.
제12항에 있어서, 상기 무선 통신망은,

위성 통신망, CDMA 통신망, GSM 통신망, 무선 근거리 통신망, 및 와이브로 통신망 중 하나인 것을 특징으로 하는 궤적 정보를 이용한 최적 경로 탐색 장치.