KR101022148B1

KR101022148B1 - 네비게이션 시스템, 경로 탐색 서버, 경로 탐색 방법 및 프로그램이 기록된 기록 매체

Info

Publication number: KR101022148B1
Application number: KR1020067026364A
Authority: KR
Inventors: 케이스케 오니시; 신 키쿠치; 켄이치 아이하라
Original assignee: 가부시키가이샤 나비타이무쟈판
Priority date: 2005-04-20
Filing date: 2005-04-27
Publication date: 2011-03-17
Anticipated expiration: 2025-04-27
Also published as: EP1876418A1; US20060241857A1; EP1876418B1; CN1969170A; KR20080007417A; EP1876418A4; JP2006300735A; JP3987073B2; TW200638022A; US8798918B2; TWI277723B; CN1969170B; WO2006114894A1

Abstract

목적 지점 또는 출발 지점이 복수 존재하는 경우에 1 회의 경로 탐색 처리로 최적 경로를 탐색할 수 있도록 하는 네비게이션 시스템을 제공한다. 네비게이션 시스템(10)은 흥미 대상 장소의 속성 정보를 보유한 POI 속성 정보 데이터베이스(40)와, 네트워크 데이터 편집 수단(38)과, 가상 노드 설정 수단(39)을 구비하고, 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스(40)를 참조하여 출발지 및/또는 목적지에 복수의 POI가 존재하는지를 판별하고, 복수의 POI가 존재하는 경우에는 가상 노드 설정 수단(39)과 복수의 POI의 노드 각각의 링크 코스트가 동등한 값을 가지는 링크로 접속되는 가상 노드를 설정하고, 네트워크 데이터 편집 수단(38)이 탐색용 네트워크 데이터에 가상 노드를 추가하고, 경로 탐색 수단(33)은 해당 가상 노드가 추가된 탐색용 네트워크 데이터(35)를 사용하여 경로 탐색을 행한다.

Description

네비게이션 시스템, 경로 탐색 서버, 경로 탐색 방법 및 프로그램이 기록된 기록 매체{NAVIGATION SYSTEM, ROUTE SEARCH SERVER, ROUTE SEARCH METHOD, PROGRAM AND COMPUTER READABLE MEDIUM HAVING PROGRAM}

본 발명은 출발지에서부터 목적지까지의 최적 경로를 탐색하여 안내하는 네비게이션 시스템, 경로 탐색 서버, 경로 탐색 방법 및 프로그램에 관한 것이며, 특히 목적 지점 또는 출발 지점이 복수 존재하는 경우에 1 회의 경로 탐색 처리로 최적 경로를 탐색할 수 있도록 한 네비게이션 시스템, 경로 탐색 서버, 경로 탐색 방법 및 프로그램에 관한 것이다.

목적 지점, 출발 지점이 복수 존재하는 경로 탐색이란, 예를 들면, 테마파크나 이벤트 회장, 교통 기관의 역 등, 복수의 출입구가 존재하는 경로 탐색이나, 현재 위치나 목적지로부터 가까운 범위에 있는 편의점이나 주유소 등의 흥미 대상 장소(POI:Point of Interest)까지의 경로를 탐색하고 싶은 경우 등이다.

종래부터, 지도 데이터, 도로 데이터를 사용하여 원하는 출발지에서부터 목적지까지의 경로를 탐색하여 이용자를 안내하는 네비게이션 장치, 네비게이션 시스템이 알려져 있다.

이와 같은 네비게이션 장치, 네비게이션 시스템으로서는 자동차에 탑재하여 운전자에게 경로를 안내하는 카 네비게이션 장치, 휴대 전화를 네비게이션 단말로 서 이용하여 경로 탐색 서버에 경로 탐색 요구를 전송하고, 그 결을 수신하여 경로 안내를 받는 통신형의 네비게이션 시스템 등이 실용화되고 있다.

특히, 통신형의 네비게이션 시스템은 휴대 전화 등의 휴대 단말을 네비게이션 단말로서 이용한 시스템으로서, 보행자용의 네비게이션 시스템으로서도 사용되는 것이다. 보행자용의 네비게이션 시스템으로서는 교통 기관을 포함한 경로 안내 기능을 부가하는 것이 바람직하고, 도로 네트워크 데이터를 사용한 자동차나 도보 경로의 탐색과 안내에 더하여, 경로 탐색 서버에 교통 기관의 노선이나 운행 시각 데이터를 교통 네트워크 데이터로서 축적하고 있다.

이와 같은 보행자용의 네비게이션 시스템은 원하는 출발역으로부터 원하는 목적역까지의 경로(승차 후보 열차)를, 도보 경로의 탐색과 안내에 더하여 안내하는 기능을 가진다. 또, 도보 경로의 경로 탐색을 수반하지 않고 정보 배신(配信, distribute) 서버로부터 교통 기관의 노선이나 시각표, 승차 가능한 열차 등의 정보의 배신을 받아서 표시하는 교통안내 시스템도 존재한다.

또, 항공기, 열차, 전철, 버스 등의 교통 수단을 사용하여 출발지에서부터 목적지까지의 경로를 탐색하여 안내하는 경로 탐색 시스템도 알려져 있다. 이와 같은 경로 탐색 시스템은 일반적으로는 사용자가 지정하는 출발 일시, 출발지, 목적지, 도착 시각 등의 경로 탐색 조건에 근거하여 경로 탐색을 행한다.

즉, 각 교통 기관의 노선 데이터나 운행 시각 데이터를 데이터베이스화한 교통 네트워크 데이터를 참조하고, 환승을 포함하여 출발지와 목적지를 연결하는 이용 가능한 각 교통 수단을 경로로서 순차적으로 취하여, 경로 탐색 조건에 합치하 는 안내 경로(열차 등의 교통 수단)의 후보를 하나 또는 복수 제시한다. 경로 탐색 조건으로서는 다시, 소요 시간, 환승 회수, 운임 등의 조건을 지정할 수 있도록 되어 있는 것이 일반적이다.

상기와 같은 도로 네트워크의 데이터를 사용하여 경로 탐색하여 얻은 출발지에서부터 목적지까지의 경로 중, 경로의 누계 코스트(거리 또는 시간)가 최소로 되는 경로가 최적인 안내 경로로서 결정되고, 안내 경로 데이터가 작성된다. 안내 경로 데이터에는 최적 경로의 데이터 외에 지도 데이터, 가이던스(guidance) 데이터가 포함되며, 안내 경로 데이터는 필요에 따라 안내 데이터 기억 수단으로부터 판독되어 표시 수단에 표시된다.

일반적으로는 네비게이션 장치가 가지는 GPS 수신기를 사용하여 측위한 네비게이션 장치의 현재 위치를 포함하는 일정한 축척, 일정한 범위의 지도에, 안내 경로와, 네비게이션 장치의 현재 위치를 나타내는 마크를 겹쳐서 이 현재 위치 마크가 표시 화면의 중심이 되도록 표시한다.

GPS 수신기를 사용하여 측위한 위치 정보에는 오차가 포함되기 때문에 현재 위치가 안내 경로로부터 벗어나 있는 경우에는 현재 위치를 안내 경로상에 보정하는 루트 매칭 처리나 지도상의 가장 가까운 도로 위에 보정하는 맵 매칭 처리가 행해진다.

또, 안내 경로 데이터에 교차점 등의 가이던스 포인트가 설정되고, 그 가이던스 포인트에 있어서의 가이던스로서 음성 가이드(예를 들면,「이 앞, 300m 교차점입니다. 좌회전해 주세요」 등의 음성 메시지)의 데이터가 부가되어 있는 경우는 스피커를 통하여 음성 메시지를 재생 출력하여 사용자를 가이드 한다.

이와 같은 네비게이션 시스템, 경로 탐색 방법은 예를 들면, 하기와 같은 특허 문헌 1(일본 특개 2000-258184호 공보)에「교통 네트워크 경로 탐색 방법 및 장치」로서 본 출원인에 의해 개시되어 있다.

이 경로 탐색 네비게이션 시스템은 출발 지점으로부터 목적 지점까지의 경로를, 지점을 노드, 지점 사이를 링크로 하여 도로 네트워크, 교통 네트워크의 데이터로서 표현하고, 컴퓨터를 사용하여 라벨 확정법에 의해 최단 코스트 조건하에서 도보 구간, 교통 기관 이용 구간을 탐색하는 것이다.

이 경로 탐색 방법에 있어서는 출발 지점 및 목적 지점으로부터 이용하는 교통 기관의 역까지의 경로로서, 출발 지점 및 목적 지점으로부터 이용하는 교통 기관의 역까지의 직선 거리를 위도 경도 정보를 사용하여 구하고, 이 직선 거리를 변수로 하여 평균 코스트를 산출한다.

그리고, 상기 평균 코스트가 지정한 코스트의 범위내에 포함되는 모든 이용 교통 기관의 역을 구하여 보행 경로를 결정하고, 구해진 보행 경로를 교통 기관의 교통 네트워크 경로에 편입하여 종합 교통 네트워크를 표현하고, 컴퓨터를 사용하여 라벨 확정법에 의해 구하는 코스트 조건하에서 탐색한다.

도보와 교통 기관을 이용하는 경로 탐색의 경우, 역에 출입구가 복수 존재하는 경우가 있다. 복수의 출입구를 고려하여, 출발지로부터 가장 가까운 역의 각 출입구까지의 도보 경로, 또는 가장 가까운 역의 각 출입구에서부터 목적지까지의 도보 경로 중에서 거리가 최단으로 되는 경로를 탐색하는 경로 탐색 방법도 알려져 있다. 예를 들면, 하기와 같은 특허 문헌 2(일본 특개 2003-182578호 공보)에 「최적 경로 탐색 장치, 최적 경로 탐색 방법」으로서 본 출원인에 의해 개시되어 있다.

이 최적 경로 탐색 장치는 출발지, 목적지, 출발 예정일시의 탐색 조건이 지정되어서 탐색이 지시되면, 최적 경로 탐색부는 도로 데이터와 교통 기관의 시각표 데이터를 사용하여, 출발지 근처의 하나 또는 복수의 출발역 후보와 목적지 근처의 하나 또는 복수의 목적역 후보를 정한다. 그리고, 각 출발역 후보와 각 목적역 후보의 편성 가운데서, 도보와 교통 기관의 편성에 의해, 지정 탐색 조건에 따라 출발지에서부터 목적지까지 최단 시간으로 이동할 수 있는 최적인 경로를 탐색하도록 구성되어 있다. 출발역 후보나 목적역 후보가 복수의 출입구를 가질 때, 출발지 부근의 근처의 하나의 출입구를 출발역 후보나 목적역 후보의 역 위치로 하여, 최적 경로를 탐색하도록 구성되어 있다.

도 9 및 도 10은 상기 특허 문헌 2에 개시된 최적 경로 탐색 장치에 있어서의 종래의 경로 탐색의 개념을 나타내는 설명도이며, 도 9는 출발지(START)로부터 가장 가까운 역과 그 출입구까지의 경로 탐색의 개념, 도 10은 가장 가까운 역과 그 출입구로부터 목적지(GOAL)까지의 종래의 경로 탐색의 개념을 나타내는 설명도이다.

교통 기관을 이용하는 경로 탐색에 의해 출발지에서부터 목적지까지의 전철 경로, 가장 가까운 역이 탐색되면, 최적 경로 탐색 장치는 다음에 도 9에 나타내는 바와 같이 출발지(START)로부터서 가장 가까운 역 ST1과 ST2와 그 출입구 A1 ~ A4, A5, A6마다 각 출입구까지의 최단의 도보 경로 RT1 ~ RT4, RT5, RT6을 차례로 탐색한다. 따라서 도보 경로의 탐색회수는 출입구의 수에 상당하는 회수로 된다.

다음에, 도 10에 나타내는 바와 같이 목적지측의 각 가장 가까운 역 ST3, ST4와 그 출입구 B1, B2, B3, B4로부터 목적지(GOAL)까지의 최단의 도보 경로 RP1, RP2, RF1, RF2를 차례로 탐색한다. 따라서 도보 경로의 탐색회수는 출입구의 수에 상당하는 회수로 된다. 또한 도 9, 도 10에 있어서, L1 ~ L4는 전철노선을 나타내며, RO은 출발지(START)로부터 가장 가까운 역 ST1과 ST2를 추출하는 범위, 목적지(GOAL)측의 가장 가까운 역 ST3, ST4를 추출하는 범위를 나타내는 반경 거리이다.

또, 네비게이션 시스템에 있어서는 특정한 목적지, 출발지를 경로 탐색 조건으로 하여 경로 탐색 서버에 경로 탐색을 요구하는 경우 외에, 특정한 장소를 목적으로 하지 않고, 어떤 조건에 맞는 장소에 도달하는 경로의 탐색 요구를 행하는 경우가 있다. 예를 들면, 어느 시설을 목적지로 하여 차로 이동하는 경우에, 아무래도 차를 주차할 필요가 있으므로, 시설 주변의 주차장이 실질적인 목적지로 되는 경우가 있다. 이 경우, 주변의 주차장이면 어디라도 되기 때문에, 어쨌든 주차장을 목적지로 하고자 하는 희망이 있다.

이와 같은 경로 탐색을 가능하게 한 네비게이션 시스템도 제안되어 있다. 예를 들면, 하기와 같은 특허 문헌 3(일본 특개 2003-057057)에「주차장 정보 검색 방법, 주차장 정보 검색 시스템 및 프로그램」으로서 개시되고 있다. 이 주차장 정보 검색 시스템은 단말 장치로부터의 경로 탐색 조건에 근거하여 네트워크 네비게 이션 센터가 경로 탐색할 때, 네트워크 네비게이션 센터가 목적지 주변의 복수의 주차장을 검색하고, 각 주차장까지의 최단 경로를 탐색한 다음, 가장 가까운 경로로 되는 주차장을 안내하도록 구성한 것이다.

또, 특정한 테마파크나 박람회 회장 등의 특정 에어리어에의 경로를 탐색 요구하는 경우도 있다. 도 11은 이와 같은 특정 에어리어의 지도를 나타내는 도면이다. 도 11에 나타내는 바와 같이 이벤트 회장인 특정 에어리어에는 3개의 출입구 G1 ~ G3이 설치되어 있다. 이와 같은 경우, 사용자는 특정 에어리어의 복수의 출입구를 인식하고 있지 않고, 해당 에어리어 전체를 목적지로 인식하며, 그 출입구 가운데 출발지로부터 가장 가까운 출입구까지의 경로 안내를 요구하는 것이 일반적이다.

이와 같은 경로 탐색에 있어서도, 종래의 경로 탐색 서버에 있어서는 상기 특허 문헌 3에 개시된 주차장 정보 검색 방법과 같이, 탐색 요구된 특정 에어리어 출입구 G 1 ~ G3을 추출하고, 출발지로부터 각 출입구 G1 ~ G3까지의 경로 탐색을 개별적으로 반복하여 최단의 출입구를 안내하고, 또는 거리의 가까운 순에 몇 가지의 추천경로를 안내하고 있었다.

특허 문헌 1 : 일본 특개 2000-258184호 공보(도 4)

특허 문헌 2 : 일본 특개 2003-182578호 공보(도 9, 도 10)

특허 문헌 3 : 일본 특개 2003-057057호 공보(도 3, 도 6, 단락 [0089], [0090])

네비게이션 시스템에 있어서, 상술한 바와 같은 주차장을 포함하는 안내를 희망하는 경우나, 가장 가까운 역의 복수 있는 출입구 중 가장 도보 경로가 짧은 출입구의 안내를 희망하는 경우가 있다. 이와 같은 경로 탐색에 있어서, 상기 특허 문헌 3에 개시된 네비게이션 시스템과 같이, 네트워크 네비게이션 센타(경로 탐색 서버)측에서, 목적지 주변의 주차장을 추출하여 각 주차장까지의 경로를 탐색하는 구성에 의하면 이하와 같은 순서로 된다.

즉, 출발지로부터 경로 탐색 서버가 추출한 각 주차장까지의 경로 탐색을 반복하여 각각의 주차장에의 최단 경로를 탐색하고, 각각의 주차장에의 최단 경로가 탐색되면, 경로 탐색 서버는 출발지로부터 가장 가까운 주차장에의 경로 또는 출발지로부터 가까운 순으로 복수의 경로를 안내 경로로서 단말 장치에 배신한다.

도 12는 출발지(START)로부터 목적지 부근의 가장 가까운 POI까지의 경로를 탐색하는 종래의 경로 탐색의 개념을 나타내는 모식도이다. 도 12에 있어서, 종래의 경로 탐색 방법에서는 목적지 근방이 있는 에어리어(AR) 내의 흥미 대상 장소 POI, 예를 들면, 흥미 대상 장소가 주차장인 경우, 주차장 G1 ~ G5를 추출한다. 그리고 경로 탐색 서버는 출발지(START)로부터 주차장 G1에의 최적 경로를 탐색한다. 도면 중, 출발지(START)로부터의 화살표는 경로 탐색의 방향을 개념적으로 나타내는 것이다.

다음에, 경로 탐색 서버는 출발지(START)로부터 주차장 G2에의 최적 경로를 탐하고, 동일하게 하여 출발지(START)로부터 주차장 G3, 주차장 G4, 주차장 G5에의 최적 경로를 탐색한다. 즉, 이 경우 경로 탐색 서버는 주차장 G1 ~ G5의 각각에 대해 5회의 경로 탐색을 행한다. 그 결과 얻어진 출발지(START)로부터 가장 가까운 주차장과 그 곳까지의 경로, 또는 출발지(START)로부터 주차장까지의 거리가 가까운 순으로 2 내지 3의 경로 후보를 단말 장치에 제공한다.

즉, 특허 문헌 3에 개시된 네비게이션 시스템에서는 경로 탐색 서버가 각 주차장에의 경로 탐색을 추출한 주차장의 수만큼 반복함으로써, 경로 탐색 서버에 있어서의 탐색 처리의 부하가 과대하게 된다고 하는 문제점이 있었다.

통신형의 네비게이션 시스템에 있어서는 경로 탐색 서버에의 안내요구는 각 단말 장치로부터 랜덤하게 행해지기 때문에, 안내 요구가 일시에 집중하고, 경로 탐색 서버에 경로 탐색 처리의 부하가 집중하면 서버가 다운하거나, 단말 장치측의 대기시간이 증대하거나 하는 문제가 발생한다고 하는 문제점이 있었다.

출발지로부터 도보로 가장 가까운 역으로 가는 경우에도, 역의 입구가 복수 있으면, 상술한 주차장의 경우와 동일하게, 경로 탐색 서버측에서 역의 입구의 수만큼 목적지를 설정하여 경로 탐색을 반복하고, 가장 가까운 입구를 구하도록 하고 있었기 때문에, 상술과 같은 문제점이 있었다.

이와 같은 경로 탐색 요구로서는 다양한 경우가 있으며, 상술한 역 출입구나 주차장을 탐색 조건으로 하는 경우 외에도, 예를 들면, 복수의 입출구장을 가지는 테마파크나 만국 박람회 회장에의 액세스, 목적지 주변의 편의점이나 주유소, 또는 레스토랑이나 호텔 등, 사용자가 흥미 대상으로 하는 장소 POI에의 액세스를 위한 경로 탐색 요구 등이다.

본원의 발명자는 상기의 문제점을 해소하기 위하여 여러 가지 검토를 거듭한 결과, 복수의 POI가 위치하는 노드로부터 링크 코스트(link cost) 0의 링크로 접속 되는 가상 노드(위도ㆍ경도의 위치 정보를 갖지 않음)를 탐색용 네트워크 데이터에 추가하고, 해당 가상 노드까지의 경로를 1 회의 경로 탐색으로 탐색하면, 출발 지점으로부터 가장 가까운 경로로 도달할 수 있는 경로를 안내할 수 있는 점에 상도(想到)하고, 본 발명을 완성하기에 이른 것이다.

즉, 본 발명은 상기의 문제점을 해소하는 것을 과제로 하고, 목적 지점 또는 출발 지점이 복수 존재하는 경우에 1 회의 경로 탐색 처리로 최적 경로를 탐색할 수 있도록 한 네비게이션 시스템, 경로 탐색 서버, 경로 탐색 방법 및 프로그램을 제공하는 것을 목적으로 한다.

상기 과제를 해결하기 위해, 본원의 청구의 범위 제 1 항에 관한 발명은 탐색용 네트워크 데이터를 사용하여 출발 노드에서부터 목적 노드까지의 경로를 탐색하는 네비게이션 시스템에 있어서, 상기 네비게이션 시스템은 흥미 대상 장소의 속성 정보를 축적한 POI 속성 정보 데이터베이스와 네트워크 데이터 편집 수단과, 가상 노드 설정 수단을 구비하고, 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스를 참조하여 출발지 및/또는 목적지에 복수의 POI가 존재하는지의 여부를 판별하고, 복수의 POI가 존재하는 경우에는 상기 가상 노드 설정 수단이 상기 복수의 POI의 노드의 각각과 링크 코스트가 동등한 값을 가지는 링크로 접속되는 가상 노드를 설정하고, 상기 네트워크 데이터 편집 수단이 상기 탐색용 네트워크 데이터에 상기 가상 노드를 추가하고, 경로 탐색 수단은 해당 가상 노드가 추가된 탐색용 네트워크 데이터를 사용하여 경로 탐색을 행하는 것을 특징으로 한다.

또, 본원의 청구의 범위 제 2 항에 관한 발명은 청구의 범위 제 1 항의 발명에 관한 네비게이션 시스템에 있어서, 상기 POI에서부터 가상 노드까지의 링크 코스트는 값이 0 인 것을 특징으로 한다.

또, 본원의 청구의 범위 제 3 항에 관한 발명은 청구의 범위 제 1 항 또는 청구의 범위 제 2 항의 발명에 관한 네비게이션 시스템에 있어서, 상기 네비게이션 시스템은 경로 탐색 조건을 송신하는 네비게이션 단말 장치와, 네트워크를 통하여 상기 네비게이션 단말 장치와 접속되는 경로 탐색 서버를 구비하여 구성되는 것을 특징으로 한다.

본원의 청구의 범위 제 4 항에 관한 발명은 네트워크를 통하여 경로 탐색 조건을 송신하는 네비게이션 단말 장치와 접속되는 경로 탐색 서버에 있어서, 상기 경로 탐색 서버는 흥미 대상 장소의 속성 정보를 축적한 POI 속성 정보 데이터베이스와, 네트워크 데이터 편집 수단과 가상 노드 설정 수단을 구비하고, 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스를 참조하여 출발지 및/또는 목적지에 복수의 POI가 존재하는지를 판별하고, 복수의 POI가 존재하는 경우에는 상기 가상 노드 설정 수단이 상기 복수의 POI의 각각의 노드와 링크 코스트가 동등한 값을 가지는 링크로 접속되는 가상 노드를 설정하고, 상기 네트워크 데이터 편집 수단이 상기 탐색용 네트워크 데이터에 상기 가상 노드를 추가하고, 경로 탐색 수단은 해당 가상 노드가 추가된 탐색용 네트워크 데이터를 사용하여 경로 탐색을 행하는 것을 특징으로 한다.

또, 본원의 청구의 범위 제 5 항에 관한 발명은 청구의 범위 제 4 항의 발명에 관한 경로 탐색 서버에 있어서, 상기 POI에서부터 가상 노드까지의 링크 코스트는 값이 0 인 것을 특징으로 한다.

본원의 청구의 범위 제 6 항에 관한 발명은 탐색용 네트워크 데이터를 사용하여 출발 노드에서부터 목적 노드까지의 경로를 탐색하는 경로 탐색 방법에 있어서, 상기 네비게이션 시스템은 흥미 대상 장소의 속성 정보를 축적한 POI 속성 정보 데이터베이스와, 네트워크 데이터 편집 수단과 가상 노드 설정 수단을 구비하고, 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스를 참조하여 출발지 및/또는 목적지에 복수의 POI가 존재하는지를 판별하는 단계와, 복수의 POI가 존재하는 경우에는 상기 가상 노드 설정 수단이 상기 복수의 POI의 각각의 노드와 링크 코스트가 동등한 값을 가지는 링크로 접속되는 가상 노드를 설정하는 단계와, 상기 네트워크 데이터 편집 수단이 상기 탐색용 네트워크 데이터에 상기 가상 노드를 추가하고, 경로 탐색 수단은 해당 가상 노드가 추가된 탐색용 네트워크 데이터를 사용하여 경로 탐색을 행하는 단계를 포함하는 것을 특징으로 한다.

또, 본원의 청구의 범위 제 7 항에 관한 발명은 청구의 범위 제 6 항의 발명에 관한 경로 탐색 방법에 있어서, 상기 POI에서부터 가상 노드까지의 링크 코스트의 값을 0 으로 하는 단계를 포함하는 것을 특징으로 한다.

본원의 청구의 범위 제 8 항에 관한 발명은 경로 탐색 조건을 송신하는 네비게이션 단말 장치와, 네트워크를 통하여 상기 네비게이션 단말 장치와 접속되는 경로 탐색 서버를 구비하여 구성된 네비게이션 시스템에 있어서의 경로 탐색 방법에 있어서, 상기 경로 탐색 서버는 흥미 대상 장소의 속성 정보를 축적한 POI 속성 정보 데이터베이스와 네트워크 데이터 편집 수단과, 가상 노드 설정 수단을 구비하고, 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스를 참조하고 출발지 및/또는 목적지에 복수의 POI가 존재하는지를 판별하는 단계와, 복수의 POI가 존재하는 경우에는 상기 가상 노드 설정 수단이 상기 복수의 POI의 각각의 노드와 링크 코스트가 동등한 값을 가지는 링크로 접속되는 가상 노드를 설정하는 단계와, 상기 네트워크 데이터 편집 수단이 상기 탐색용 네트워크 데이터에 상기 가상 노드를 추가하고, 경로 탐색 수단은 해당 가상 노드가 추가된 탐색용 네트워크 데이터를 사용하여 경로 탐색을 행하는 단계를 포함하는 것을 특징으로 한다.

또, 본원의 청구의 범위 제 9 항에 관한 발명은 청구의 범위 제 8 항의 발명에 관한 경로 탐색 방법에 있어서, POI에서부터 가상 노드까지의 링크 코스트의 값을 0 으로 하는 단계를 포함하는 것을 특징으로 한다.

본원의 청구의 범위 제 10 항에 관한 발명은 경로 탐색 조건을 송신하는 네비게이션 단말 장치와, 네트워크를 통하여 상기 네비게이션 단말 장치와 접속되는 경로 탐색 서버에 있어서, 흥미 대상 장소의 속성 정보를 축적한 POI 속성 정보 데이터베이스와 네트워크 데이터 편집 수단과, 가상 노드 설정 수단을 구비한 경로 탐색 서버를 구성하는 컴퓨터에, 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스를 참조하고 출발지 및/또는 목적지에 복수의 POI가 존재하는지를 판별하는 처리를 실행시키고, 복수의 POI가 존재하는 경우에는 상기 가상 노드 설정 수단이 상기 복수의 POI의 각각의 노드와 링크 코스트가 동등한 값을 가지는 링크로 접속되는 가상 노드를 설정하는 처리를 실행시키고, 상기 네트워크 데이터 편집 수단이 상기 탐색용 네트워크 데이터에 상기 가상 노드를 추가하고, 경로 탐색 수단은 해당 가상 노드가 추가된 탐색용 네트워크 데이터를 사용하여 경로 탐색을 행하는 처리를 실행시키는 것을 특징으로 하는 프로그램이다.

또, 본원의 청구의 범위 제 11 항에 관한 발명은 청구의 범위 제 10 항의 발명에 관한 프로그램에 있어서, POI에서부터 가상 노드까지의 링크 코스트의 값을 0 으로 하는 처리를 실행시키는 것을 특징으로 한다.

청구의 범위 제 1 항에 관한 발명에 있어서는 네비게이션 시스템은 흥미 대상 장소의 속성 정보를 축적한 POI 속성 정보 데이터베이스와, 네트워크 데이터 편집 수단과 가상 노드 설정 수단을 구비하고, 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스를 참조하여 출발지 및/또는 목적지에 복수의 POI가 존재하는지를 판별한다.

그리고 복수의 POI가 존재하는 경우에는 상기 가상 노드 설정 수단이 상기 복수의 POI의 각각의 노드와 링크 코스트가 동등한 값을 가지는 링크로 접속되는 가상 노드를 설정하고, 네트워크 데이터 편집 수단이 상기 탐색용 네트워크 데이터에 상기 가상 노드를 추가하고, 경로 탐색 수단은 해당 가상 노드가 추가된 탐색용 네트워크 데이터를 사용하여 경로 탐색을 행한다.

가상 노드 PN으로부터 각 주차장 G1 ~ G5를 연결하는 링크의 링크 코스트는 실제의 거리에 의하지 않고 모두「O」이기 때문에, 가상 노드 PN과 각 POI의 거리는 가상적으로 동일한 거리이다. 따라서, 특정한 POI를 경유하는 경로가 최단 거리이면, 그 경로가 출발지(STAR T)로부터 각 POI까지의 경로 중에서 최단의 경로인 것으로 되고, 1 회의 경로 탐색으로 복수의 POI 중 가장 가까운 POI와 그 곳까지의 경로를 제공할 수 있게 된다.

청구의 범위 제 2 항에 관한 발명에 있어서는 청구의 범위 제 1 항의 발명에 관한 네비게이션 시스템에 있어서, POI에서부터 가상 노드까지의 링크 코스트는 값이 0 이다. 따라서, 경로 탐색에 있어서 주변에의 탐색의 확산을 일으키는 일 없이, 효율적인 경로 탐색을 행할 수 있게 된다.

청구의 범위 제 3 항에 걸리는 발명에 있어서는 청구의 범위 제 1 항 또는 청구의 범위 제 2 항의 발명에 관한 네비게이션 시스템에 있어서, 네비게이션 시스템은 경로 탐색 조건을 송신하는 네비게이션 단말 장치와, 네트워크를 통하여 상기 네비게이션 단말 장치와 접속되는 경로 탐색 서버를 구비하여 구성된다. 따라서, 통신형의 네비게이션 시스템을 제공할 수 있게 되며, 또, 경로 탐색 서버는 1 회의 경로 탐색으로 복수의 POI 중 가장 가까운 POI와 그곳까지의 경로를 제공할 수 있게 된다.

청구의 범위 제 4 항, 청구의 범위 제 5 항에 관한 발명에 있어서는 각각 청구의 범위 제 1 항, 청구의 범위 제 2 항에 관한 발명의 네비게이션 시스템을 구성하는 경로 탐색 서버를 제공할 수 있게 되며, 경로 탐색 서버는 1 회의 경로 탐색으로 복수의 POI 중 가장 가까운 POI와 그곳까지의 경로를 제공할 수 있게 된다.

청구의 범위 제 6 항, 청구의 범위 제 7 항에 관한 발명에 있어서는 각각 청구의 범위 제 1 항, 청구의 범위 제 2 항에 관한 발명의 네비게이션 시스템에 있어서의 경로 탐색 방법을 제공할 수 있고, 1 회의 경로 탐색으로 복수의 POI 중 가장 가까운 POI와 그곳까지의 경로를 제공할 수 있게 된다.

청구의 범위 제 8 항, 청구의 범위 제 9 항에 관한 발명에 있어서는 각각 청구의 범위 제 4 항, 청구의 범위 제 5 항에 관한 발명의 경로 탐색 서버에 있어서의 경로 탐색 방법을 제공할 수 있게 되고, 경로 탐색 서버는 1 회의 경로 탐색으로 복수의 POI 중 가장 근접한 POI와 그곳까지의 경로를 제공할 수 있게 된다.

청구의 범위 제 10 항, 청구의 범위 제 11 항에 관한 발명에 있어서는 각각 청구의 범위 제 4 항, 청구의 범위 제 5 항에 관한 발명의 경로 탐색 서버를 실현하기 위한 프로그램을 제공할 수 있고, 경로 탐색 서버는 1 회의 경로 탐색으로 복수의 POI 중 가장 가까운 POI와 그곳까지의 경로를 제공할 수 있게 된다.

도 1은 출발지(START)로부터 목적지 부근의 어떤 에어리어(AR)에 존재하는 복수의 흥미 대상 장소 POI G1 ~ G5 중에서 가장 가까운 POI까지의 경로를 탐색하는 본 발명의 경로 탐색의 개념을 나타내는 모식도.

도 2는 본 발명의 실시예에 관한 네비게이션 시스템의 구성을 나타내는 블록도.

도 3은 흥미 대상 장소 등의 POI 속성 정보를 축적한 데이터베이스에 있어서의 데이터 구성을 나타내는 도면.

도 4는 도로 네트워크의 데이터의 개념을 나타내는 모식도.

도 5는 교통 네트워크의 데이터의 개념을 나타내는 모식도.

도 6은 출발지측의 역에 복수의 출입구가 존재하는 경우의 경로 탐색의 개념 을 설명하기 위한 설명도.

도 7은 출발지측, 목적지측의 쌍방에 복수의 출입구나 POI가 존재하는 경우의 경로 탐색의 개념을 설명하기 위한 설명도.

도 8은 본 발명의 네비게이션 시스템의 경로 탐색 순서를 나타내는 플로차트.

도 9는 출발지로부터 복수의 출입구를 가지는 가장 가까운 역에의 경로를 탐색하는 종래의 경로 탐색 방법의 개념을 설명하기 위한 설명도.

도 10은 복수의 출입구를 가지는 가장 가까운 역으로부터 목적지에의 경로를 탐색하는 종래의 경로 탐색 방법의 개념을 설명하기 위한 설명도.

도 11은 테마파크 등 복수의 출입구를 가지는 특정의 에어리어에의 경로 탐색의 개념을 설명하기 위한 설명도.

도 12는 복수의 목적 지점에의 경로를 탐색하는 종래의 경로 탐색 방법을 설명하기 위한 설명도.

<부호의 설명>

10 ㆍㆍㆍㆍ네비게이션 시스템

11, 12 ㆍㆍ네트워크

20 ㆍㆍㆍㆍ네비게이션 단말 장치

21 ㆍㆍㆍㆍ제어 수단

22 ㆍㆍㆍㆍ통신 수단

23 ㆍㆍㆍㆍ측위 수단

24 ㆍㆍㆍㆍ표시 수단

25 ㆍㆍㆍㆍ안내 경로 데이터 기억 수단

26 ㆍㆍㆍㆍ배신 요구 편집 수단

27 ㆍㆍㆍㆍ조작ㆍ입력 수단

30 ㆍㆍㆍㆍ경로 탐색 서버

31 ㆍㆍㆍㆍ제어 수단

32 ㆍㆍㆍㆍ경로 안내 수단

33 ㆍㆍㆍㆍ경로 탐색 수단

34 ㆍㆍㆍㆍ통신 수단

35 ㆍㆍㆍㆍ탐색용 네트워크 데이터

36 ㆍㆍㆍㆍ도로 네트워크 데이터

37 ㆍㆍㆍㆍ교통 네트워크 데이터

38 ㆍㆍㆍㆍ네트워크 데이터 편집 수단

39 ㆍㆍㆍㆍ가상 노드 설정 수단

40 ㆍㆍㆍㆍPOI 속성 정보 DB(데이터베이스)

50 ㆍㆍㆍㆍPOI 정보 제공 서버

이하, 본 발명의 구체적인 예를 실시예 및 도면을 사용하여 상세하게 설명한다. 도 1은 출발지(START)로부터 목적지(GOAL) 부근의 어떤 에어리어(AR)에 존재하는 복수의 흥미 대상 장소 POI G1 ~ G5 중에서 가장 가까운 POI까지의 경로를 탐색 하는 본 발명의 경로 탐색의 개념을 나타내는 모식도이다.

〔실시예〕

또한, 이하의 본 발명의 실시예의 설명에 있어서는 흥미 대상 장소, 복수의 출입구를 가지는 역 등, 복수 지점이 존재하는 출발 지점이나 목적 지점을 포함하여 흥미 대상 장소 POI로 총칭하나, 역의 출입구인 것이나 특정한 테마파크 등의 출입구인 것을 명확하게 나타내는 경우에는 출입구로 칭하는 일도 있다.

도 1에 있어서, 목적지 부근의 주차장 G1 ~ G5를 추출하면, 경로 탐색 서버는 각 주차장 G1 ~ G5의 노드 위치로부터 링크 코스트가「O」의 값을 지닌 링크로 접속되는 가상 노드 PN을 설정한다. 이 가상 노드 PN는 경로 탐색을 위해 임시로 경로 탐색 네트워크에 접속되는 것이며, 링크 코스트 누계의 연산에 사용될 뿐이므로, 경로 탐색 네트워크의 노드와 같이 위도, 경도로 이루어지는 위치 정보를 가질 필요는 없다. 또, 가상 노드는 경로 탐색상 필요할 뿐이므로 표시할 필요도 없다. 따라서 가상 노드에 위치 정보의 값을 설정하는 처리는 일절 필요가 없다.

가상 노드 PN이 설정되면, 경로 탐색 서버는 출발지(START)로부터 가상 노드 PN까지의 최적 경로 GR을 탐색한다. 이 경로 탐색에 있어서, 가상 노드 PN으로부터 각 주차장 G1 ~ G5를 연결하는 링크의 링크 코스트는 실제의 거리에 의하지 않고 모두「O」이기 때문에, 가상 노드 PN와 각 주차장 G1 ~ G5의 거리는 가상적으로 동등한 거리이다.

따라서, 주차장 G3을 경유하는 경로가 최단 거리라면, 그 경로가 출발지(START)로부터 각 주차장 G1 ~ G5까지의 경로중에서 최단의 경로인 것으로 되며, 1 회의 경로 탐색으로 복수의 주차장 G1 ~ G5 중 가장 가까운 주차장과 그곳까지의 경로를 네비게이션 단말 장치(20)에 제공할 수 있게 된다.

여기서, 각 주차장 G1 ~ G5로부터 가상 노드 PN에의 링크의 링크 코스트는 논리적으로는 각각의 값이 동일하면 되고 반드시 값이「0」일 필요는 없다. 그렇지만, 링크 코스트가「O」이외의 값인 경우에는 경로 탐색시에 다이크스트라(dijkstra)법에 있어서의 확산이 그 값의 몫만큼 주변으로 나아갈 가능성이 있고, 경로 탐색의 처리시간이 증대하는 경우가 있다.

이 점, 링크 코스트의 값이「0」이면, 가상 노드 PN에 탐색이 도달한 시점에서 경로 탐색 처리가 종료한다. 즉, 가상 노드 PN의 링크 코스트의 값이「0」이면 효율적인 경로 탐색 처리를 행할 수 있다.

도 2는 본 발명의 실시예에 관한 네비게이션 시스템의 구성을 나타내는 블록도이다. 본 발명의 실시예에 관한 네비게이션 시스템(10)은 도 2의 블록도에 나타내는 바와 같이 인터넷 등의 네트워크(11)를 통하여 통신하는 네비게이션 단말 장치(20)와, 경로 탐색 서버(30)를 구비하여 구성되어 있다.

네비게이션 단말 장치(20)는 경로 탐색 서버(30)에 출발지와 목적지 등의 경로 탐색 조건을 설정하여 경로 탐색 요구를 송신하고, 경로 탐색 서버(30)는 경로 탐색 조건에 따라 도로 네트워크 데이터, 교통 네트워크 데이터로부터 이루어지는 탐색용 네트워크 데이터를 참조하여 최적 경로를 탐색하고, 그 최적 경로를 안내 경로 데이터에 편집하여 네비게이션 단말 장치(20)에 배신한다.

경로 탐색 서버(30)는 보행자 네비게이션 시스템이나 카 네비게이션 시스템 에 있어서의 경로 탐색을 위한 지도 데이터를 포함하는 도로 네트워크 데이터(36)와 교통 기관을 이용하는 경로 구간을 탐색하기 위한 교통 네트워크 데이터(37)를 축적한 탐색용 네트워크 데이터(35)(데이터베이스)와, POI 속성 정보를 축적한 POI 속성 정보 DB(데이터베이스)(40)를 구비하고 있다.

POI 속성 정보 DB(40)에 축적된 POI 속성 정보는 도 3에 나타내는 바와, 흥미 대상 장소 POI마다 그 위치 좌표(위도ㆍ경도)와, 속성 정보가 축적된 것이며, 속성 정보에는 해당 POI에 이르는 링크의 단점(端点)의 노드 수와 각 노드의 위치 정보가 축적되고, 또 각 POI의 종별이 축적되어 있다.

예를 들면, POI의 A는 테마파크 A 이며, 해당 테마파크에 접속되는 링크, 즉 출입구 링크는 3개이며, 그 3개의 링크 단점 노드의 위치가 축적되어 있다. 만국 박람회 등의 이벤트 회장, 테마파크, 교통 기관의 각 역의 출입구도 동일하다. 이들 POI와 그 속성 정보는 경로 탐색 서버(30)가 네트워크(12)를 통하여 POI 정보 제공 서버(50)로부터 수집할 수 있다(도 2 참조).

네비게이션 단말 장치(20)가 특정한 테마파크나 이벤트 회장을 목적지로 하는 경로 탐색 요구를 행한 경우, 경로 탐색 서버(30)는 POI 속성 정보(DB(40))를 참조하여 해당 테마파크를 이벤트 회장의 출입구가 다수 있는지의 여부를 판단한다. 교통 기관을 이용한 경로 탐색에 있어서, 목적지 또는 출발지의 가장 가까운 역이 탐색된 경우, 해당 가장 가까운 역까지의 도보 경로 구간을 탐색할 때에도 동일하게 POI 속성 정보(DB(40))를 참조하여 가장 가까운 역에 복수의 출입구가 있는지의 여부를 판단한다. 복수의 출입구를 가지는 경우, 경로 탐색 서버(30)는 상술 한 가상 노드를 설정하여 경로 탐색을 행한다.

또, 주차장, 주유소, 편의점, 호텔 등의 POI에 대해서는 그 종별 정보가 속성 정보로서 기록되어 있다. 경로 탐색 조건으로서 네비게이션 단말 장치(20)로부터 목적지나 출발지 부근의 특정한 POI, 예를 들면 주유소 중에서 가장 가까운 주유소까지의 경로 탐색 요구가 있었던 경우에, 경로 탐색 서버(30)는 POI 속성 정보(DB(40))를 참조하여 목적지나 출발지 부근의 해당 POI를 추출한다. 그리고, 경로 탐색 서버(30)는 추출된 POI를 복수의 목적지로서 상술한 가상 노드를 설정하여 경로 탐색을 행한다.

가상 노드 설정 수단(39)(도 2 참조)은 복수의 POI를 경로 탐색하는 경우, 또는 복수의 출입구를 가지는 목적지나 출발지를 포함하는 경로 탐색을 행하는 경우, 도 1에 있어서 설명한 바와 같이, 추출된 각 POI 또는 출입구로부터의 노드로부터 링크 코스트「O」로 접속되는 가상 노드 PN을 설정하는 것이다. 네트워크 데이터 편집 수단(38)은 가상 노드 설정 수단(39)이 설정한 가상 노드 PN을 탐색용 네트워크 데이터(35)의 데이터에 일시적으로 추가하는 처리를 행하는 것이다.

그리고, 경로 탐색 수단(33)은 네트워크 데이터 편집 수단(38)에 의해 탐색용 네트워크 데이터(35)에 추가된 가상 노드 PN을 목적지 또는 출발지로 하는 경로 탐색을 행한다. 네비게이션 단말 장치(20)로부터의 경로 탐색 조건이 특정한 출발지에서부터 목적지까지의 경로 탐색을 요구하는 통상의 경우에는 가상 노드 PN이 추가되어 있지 않은 탐색용 네트워크 데이터(35)를 사용하여 경로 탐색하는 것은 말할 것도 없다.

경로 안내 수단(32)은 경로 탐색 수단(33)이 탐색한 최적 경로 또는 복수의 추천 안내 경로의 데이터를 편집하여 네비게이션 단말 장치(20)에 배신하기 위한 것이며, 통신 수단(34)은 네비게이션 단말 장치(20)로부터의 각종 요구를 수신하고, 또는 네비게이션 단말 장치(20)에 각종 정보를 배신하기 위한 것이다.

보행자 네비게이션 시스템이나 카 네비게이션 시스템에 있어서의 경로 탐색을 위한 도로 네트워크 데이터(36)는 이하와 같이 구성되어 있다. 예를 들면, 도로가 도 4에 나타내는 바와 같이 도로 A, B, C로 이루어지는 경우, 도로 A, B, C의 단점, 교차점, 굴곡점 등을 노드로 하고, 각 노드 사이를 연결하는 도로를 유향성(有向性)의 링크로 나타내고 노드 데이터(노드의 위도ㆍ경도), 링크 데이터(링크 번호)와 각 링크의 링크 코스트(링크의 거리 또는 링크를 주행하는데 필요한 소요 시간)를 데이터로 한 링크 코스트 데이터에 의해 구성된다.

즉, 도 4에 있어서 0표, ◎표가 노드를 나타내며, ◎표는 도로의 교차점을 나타내고 있다. 각 노드 사이를 연결하는 유향성의 링크를 화살표 선(실선, 점선, 2점 쇄선)으로 나타내고 있다. 링크는 도로의 오름, 내림 각각의 방향을 향한 링크가 존재하나, 도 4에서는 도시를 간략화하기 위해 화살표의 방향의 링크만을 도시하고 있다.

이와 같은 도로 네트워크의 데이터를 경로 탐색용의 데이터베이스로서 경로 탐색을 행하는 경우, 출발지의 노드로부터 목적지의 노드까지 연결된 링크를 취하여 그 링크 코스트를 누적하고, 누적 링크 코스트의 최소로 되는 경로를 탐색하여 안내한다. 즉, 도 4에 있어서 출발지를 노드 AX, 목적지를 노드 CY로 하여 경로 탐 색을 행하는 경우, 노드 AX로부터 도로 A를 주행하여 2 번째의 교차점에서 우회전하여 도로 C에 들어가 노드 CY에 으르는 링크를 차례로 취하여 링크 코스트를 누적하고, 링크 코스트의 누적치가 최소로 되는 경로를 탐색하여 안내한다.

도 4에서는 노드 AX로부터 노드 CY에 이르는 다른 경로는 도시되어 있지 않으나, 실제로는 그러한 경로가 그 밖에도 존재하기 때문에, 노드 AX로부터 노드 CY에 이르는 가능한 경로를 동일하게 하여 탐색하고, 그들의 경로 중 링크 코스트가 최소로 되는 경로를 최적 경로로서 결정하는 것이다. 이 방법은 예를 들면 다이크스트라법으로 불리는 주지된 방법에 의해 행해진다.

이에 대하여, 교통 기관의 경로 탐색을 위한 교통 네트워크 데이터(37)는 이하와 같이 구성되어 있다. 예를 들면, 도 5에 나타내는 바와 같이 교통 노선 A, B, C로 이루어지는 경우, 각 교통 노선 A, B, C에 설치된 각 역(항공기의 노선에 있어서는 각 공항)을 노드로 하고, 각 노드 사이를 연결하는 구간을 유향성의 링크로 나타내며, 노드 데이터(위도ㆍ경도), 링크 데이터(링크 번호)를 네트워크 데이터로 하고 있다. 도 5에 있어서, O표, ◎표가 노드를 나타내고, ◎표는 교통 노선의 환승점(환승역 등)을 나타내며, 각 노드 사이를 연결하는 유향성의 링크를 화살표 선(실선, 점선, 2점 쇄선)으로 나타내고 있다. 링크는 교통 노선의 오름, 내림 각각의 방향을 향한 링크가 존재하나, 도 5에서는 도시를 간략화하기 위해 화살표 방향의 링크만을 도시하고 있다.

그러나, 교통 네트워크는 도로 네트워크와 비교하여 링크 코스트가 기본적으로 상이하다. 즉, 도로 네트워크에서는 링크 코스트는 고정적, 정적인 것이었으나, 교통 네트워크에서는 도 5에 나타내는 바와 같이 교통 노선을 운행하는 열차나 항공기(이하 개개의 열차나 항공기 등의 각 경로를 교통 수단이라 칭함)가 복수 있다. 각 교통 수단마다 있는 노드를 출발하는 시각과 다음의 노드에 도착하는 시각이 정해져 있고(시각표 데이터, 운행 데이터로 규정됨), 또한 개개의 경로가 반드시 인접하는 노드에 링크하지 않는 경우가 있다. 예를 들면, 급행과 각 역 정차의 열차와 동일한 경우이다. 이와 같은 경우에는 같은 교통 노선상에 다른 복수의 링크가 존재하게 되며, 또 노드 사이의 소요 시간이 교통 수단에 의해 다른 경우도 있다.

도 5에 예시하는 교통 네트워크에 있어서는 교통 노선 A의 같은 링크에 복수의 교통 수단(경로) Aa ~ Acㆍㆍㆍ, 교통 노선 C에 복수의 교통 수단(경로) Ca ~ Ccㆍㆍㆍ가 존재하게 된다. 따라서, 교통 기관의 운행 네트워크는 단순한 도로 네트워크와 다르며, 노드, 링크, 링크 코스트의 각 데이터는 교통 수단(개개의 항공기나 열차 등의 경로)의 총수에 비례한 데이터량이 된다. 이 때문에 교통 네트워크의 데이터는 도로 네트워크의 데이터량에 비해 방대한 데이터량으로 된다. 따라서, 그에 따라 경로 탐색에 요하는 시간도 많은 시간이 필요하게 된다.

이와 같은 교통 네트워크 데이터를 이용하여, 어떤 출발지로부터 어떤 목적지까지의 경로를 탐색하기 위해서는 출발지에서부터 목적지까지 도달할 때에 사용(승차)할 수 있는 모든 교통 수단을 탐색하여 탐색 조건에 합치하는 교통 수단을 특정할 필요가 있다.

예를 들면, 도 5에 있어서 출발지를 교통 노선 A의 노드 AX로 하여 어떤 특 정한 출발시각을 지정하고, 교통 노선 C의 노드 CY를 목적지로 하는 경로 탐색을 행하는 경우, 교통 노선 A 상을 운행하는 교통 수단 Aa ~ Ac ㆍㆍㆍ중 출발시각 이후의 모든 교통 수단을 차례로 출발시의 경로로서 선택한다. 그리고 교통 노선 C에의 환승 노드에의 도착 시각에 근거하여, 교통 노선 C 상을 운행하는 각 교통 수단 Ca ~ Cc ㆍㆍㆍ중, 환승 노드에 있어서 승차 가능한 시각 이후의 교통 수단의 모든 편성을 탐색하여 각 경로의 소요 시간이나 환승 회수 등을 누계하여 안내하게 된다.

한편, 네비게이션 단말 장치(20)는 제어 수단(21), 통신 수단(22), 측위 수단(23), 표시 수단(24), 안내 경로 데이터 기억 수단(25), 배신 요구 편집 수단(26), 조작ㆍ입력 수단(27)을 구비하여 구성되어 있다. 측위 수단(23)은 GPS 수신기를 구비하여 GPS 위성 신호를 수신, 처리하여 네비게이션 단말 장치(20)의 현재 위치(위도ㆍ경도)를 측위한다.

통신 수단(22)은 라디오 커뮤니케이션 유닛을 포함하고, 경로 탐색 서버(30)와 통신하기 위한 것이다. 조작ㆍ입력 수단(27)은 키, 다이얼 등으로 이루어지며, 네비게이션 단말 장치(20)를 조작하기 위한 입력, 출발지, 목적지 등의 입력 기능으로서 사용된다. 표시 수단(24)은 액정 표시 패널 등으로 이루어지며, 경로 탐색 서버(30)로부터 배신된 안내 경로 데이터의 안내 경로, 지도의 표시에 사용되는 것이다. 또, 표시 수단(24)은 메뉴 화면을 표시하여 네비게이션 단말 장치(20)를 조작하기 위한 입력 수단으로서도 기능한다. 배신 요구 편집 수단(26)은 조작ㆍ입력 수단(27)을 사용하여 입력된 출발지, 목적지, 또는 측위 수단(23)으로 측위한 네비 게이션 단말 장치(20)의 현재 위치를 출발지로 하고, 이들의 정보에 근거하여 경로 탐색 서버(30)에 송신하는 경로 탐색 요구를 작성하는 것이다.

안내 경로 데이터 기억 수단(25)은 경로 탐색 서버(30)로부터 배신된 경로 탐색 결과인 안내 경로 데이터, 지도 데이터, 가이던스 등을 기억하는 것이며, 이들의 데이터는 필요에 따라 안내 경로 데이터 기억 수단(25)으로부터 판독되고, 표시 수단(24)에 표시된다. 일반적으로는 측위 수단(23)으로 측위한 네비게이션 단말 장치(20)의 현재 위치를 포함하는 일정한 축척, 일정한 범위의 지도에, 안내 경로와 네비게이션 단말 장치(20)의 현재 위치를 나타내는 마크를 겹쳐서 이 현재 위치 마크가 표시 화면의 중심이 되도록 표시한다.

측위 수단(23)에 의해 GPS 위성 신호를 수신하여 측위한 현재 위치 정보(위도ㆍ경도의 정보)에는 오차가 포함되기 때문에, 현재 위치가 안내 경로로부터 벗어나 있는 경우에는 현재 위치를 안내 경로상에 보정하는 루트 매칭 처리가 행해진다. 또, 경로 탐색 서버(30)로부터 배신되는 안내 경로 데이터에 음성 가이드(예를 들면,「이 앞, 300m 교차점입니다. 좌회전해 주세요」 등의 음성 메시지)의 데이터가 부가되고 있는 경우는 스피커를 통하여 음성 메시지를 재생 출력하여 사용자를 가이드 한다.

다음에, 이상 설명한 본 발명의 실시예에 관한 네비게이션 시스템(10)에 있어서의 경로 탐색 방법에 대해 설명한다. 목적지측에 복수의 출입구 또는 POI가 존재하는 경우의 본 발명에 의한 경로 탐색의 개념에 대해서는 도 1을 참하여 설명한 바와 같다. 동일한 경로 탐색이 출발지측에 있어서도 가능하다. 도 6은 목적 지(GOAL)에 대하여 출발지측의 역 ST1에 복수 출입구 A1 ~ A5가 존재하는 경우를 나타내는 도면이다.

출발지의 가장 가까운 역 ST1이 탐색되면, 경로 탐색 서버는 역 ST1의 POI 속성 정보(DB(40))를 참조하여, 출입구가 복수 있는지를 판별한다. 도 6에 나타내는 바와 같이 역 ST1에 복수의 출입구 A1 ~ A5가 있는 경우, 출입구 A1 ~ A5의 노드 위치로부터 링크 코스트가 「O」의 값을 가지는 링크로 접속되는 가상 노드 PN을 설정한다. 이 가상 노드 PN는 경로 탐색을 위해서 임시로 경로 탐색 네트워크에 접속되는 것이며, 위도, 경도로 이루어지는 위치 정보를 가질 필요는 없다.

가상 노드 PN이 설정되면, 경로 탐색 서버는 가상 노드 PN으로부터 목적지(GOAL)까지의 최적 경로 GR을 탐색한다. 이 경로 탐색에 있어서, 가상 노드 PN으로부터 각 출입구 A1 ~ A5를 연결하는 링크의 링크 코스트는 실제의 거리에 의하지 않고 모두「O」이기 때문에, 가상 노드 PN와 출입구 A1 ~ A5의 거리는 가상적으로 등거리이다.

따라서, 출입구 A3을 경유하는 경로 RT1이 최단 거리라면, 그 경로가 출발지측의 출입구 A1 ~ A5의 경로 중에서 최단의 경로인 것으로 된다. 따라서 1 회의 경로 탐색으로 복수의 출입구 A1 ~ A5 중 목적지(GOAL)까지의 가장 가까운 출입구와 목적지(GOAL)까지의 경로를 네비게이션 단말 장치(20)에 제공할 수 있게 된다.

동일하게 하여, 출발지측, 목적지측 모두 복수의 출입구나 POI를 가지는 경우의 경로 탐색도 가능하다. 도 7은 이와 같은 경로 탐색의 개념을 설명하기 위한 설명도이다. 도 7은 네비게이션 단말 장치(20)로부터의 경로 탐색 요구에 있어서, 출발지측의 가장 가까운 역 등의 POI에 복수의 출입구 A1 ~ A5가 존재하고, 목적지측의 테마파크 등의 POI에 복수의 출입구 G1 ~ G5가 존재하고 있는 경우를 나타내고 있다.

이와 같은 경로 탐색 요구가 네비게이션 단말 장치(20)로부터 경로 탐색 서버(30)에 요구되면, 경로 탐색 서버(30)는 우선, 출발지측, 목적지측의 각각에 복수의 출입구가 존재하는지, POI 속성 정보(DB(40))를 참조하여 판단한다. 복수의 출입구가 존재하는 경우, 각 출입구 A1 ~ A5, G1 ~ G5를 추출한다. 다음에, 가상 노드 설정 수단(39)은 출발지측의 출입구 A1 ~ A5의 각각으로부터 링크 코스트「O」의 링크로 접속되는 가상 노드 PN1를 설정하고, 목적지측의 출입구 G1 ~ G5의 각각으로부터 링크 코스트「O」의 링크로 접속되는 가상 노드 PN2를 설정한다.

이어서, 경로 탐색 서버(30)에 있어서 네트워크 데이터 편집 수단(38)이 가상 노드 PN1, PN2를 탐색용 네트워크 데이터(35)에 일시적으로 추가한다.도 7에 있어서, 점선이 탐색용의 네트워크를 모식적으로 나타내며 가상 노드 PN1, PN2가 추가된다. 경로 탐색 수단(33)은 이 탐색용 네트워크 데이터(35)를 사용하여 가상 노드 PN1로부터 가상 노드 PN2에 이르는 최적 경로를 탐색한다.

이 탐색은 다이크스트라법 등, 일반적인 경로 탐색에 있어서 사용되는 방법으로 행할 수 있다. 즉, 실제로 경로 탐색을 행하는 범위는 실제의 탐색용 네트워크 상으로 되나, 가상 노드 PN1(출발지측)와 가상 노드 PN2(목적지측)를 둠으로써, 이 사이에서 구해진 최적 경로는 출발지와 목적지도 동시에 특정하고 있는 점에 특징이 있다.

가상 노드 PN1과 각 출입구 A1 ~ A5의 사이의 링크 코스트는 모두「O」에서 동등하며, 가상 노드 PN2와 각 출입구 G1 ~ G5의 사이의 링크 코스트는 모두「O」에서 동등하므로, 경로 탐색의 결과, 가상 노드 PN1로부터 가상 노드 PN2에 이르는 최단 경로 RT1를 얻을 수 있고, 이 최단 경로 RT1이 경유하는 출발지측의 출입구 A5와 목적지측의 출입구 G1이 각각 출발지측, 목적지측의 최적인 출입구가 된다.

또한, 도 7의 경우, 출발지측은 출발지로부터 일정한 범위내의 교통 기관의 역이기 때문에, 경로 RT1는 교통 기관의 노선 경로가 중심이 된다. 또, 목적지측의 테마파크의 출입구 G1의 가장 가까운 역을 포함하는 안내 경로가 탐색되고, 가장 가까운 역으로부터 출입구 G1까지는 도보 경로가 탐색되어 종합적인 안내 경로 RT1이 탐색된다. 출발지로부터 출발지측의 가장 가까운 역 출입구, 이 경우는 A5의 사이의 경로는 도보 구간으로서 경로 탐색된다.

이상, 설명한 본 발명의 네비게이션 시스템의 경로 탐색 순서에 대해, 도 8에 나타내는 플로차트를 참조하여 설명한다. 단계 S10의 처리에 있어서 경로 탐색 서버(30)는 네비게이션 단말 장치(20)로부터 경로 탐색 조건을 수신한다.

경로 탐색 서버(30)는 경로 탐색 조건을 수신하면, 먼저 단계 S11의 처리에 있어서 출발지측의 조건을 조사하고, 단계 S12의 처리에 있어서 POI 속성 정보 DB(40)를 참조하고, 출발지측에 복수의 POI가 존재하는지를 판단한다. 출발지측에 복수의 POI가 존재하지 않으면 단계 S14의 처리에 나아가 출발지를 출발지 노드로서 결정한다.

단계 S12의 처리에 있어서, 출발지측에 복수의 POI가 존재하는 경우는 가상 노드 설정 수단(39)이 복수의 POI의 각각의 노드로부터 링크 코스트 「O」의 링크로 접속되는 가상 노드(출발지측)를 설정하여 단계 S15의 처리로 나아간다. 단계 S15의 처리에 있어서는 경로 탐색 서버(30)는 목적지측의 조건을 조사하여 단계 S16의 처리에 있어서 POI 속성 정보 DB(40)를 참조하고, 목적지측에 복수의 POI가 존재하는지 판단한다. 목적지측에 복수의 POI가 존재하지 않으면 단계 S17의 처리로 나아가 목적지를 목적지 노드로서 결정한다.

단계 S16의 처리에 있어서, 목적지측에 복수의 POI가 존재하는 경우는 단계 S18의 처리에 있어서 가상 노드 설정 수단(39)이 복수의 POI의 각각의 노드로부터 링크 코스트「O」의 링크로 접속되는 가상 노드(목적지측)를 설정하여 단계 S19의 처리로 나아간다. 단계 S19의 처리에 있어서, 네트워크 데이터 편집 수단(38)은 가상 노드 설정 수단(39)이 설정한 출발지측의 가상 노드와 목적지측의 가상 노드를 탐색용 네트워크 데이터에 일시적으로 추가하고, 경로 탐색 수단(33)은 가상 노드가 추가된 탐색용 네트워크 데이터를 사용하여 출발지측의 가상 노드로부터 목적지측의 가상 노드까지의 최적 경로를 탐색한다.

또한, 출발지측 또는 목적지측에 복수의 POI가 존재하지 않고, 단계 S14 또는 단계 S17의 처리에 있어서, 출발지 또는 목적지가 출발지 노드 또는 목적지 노드로서 결정되어 있는 경우, 단계 S19의 처리에 있어서의 노드는 가상 노드가 아니며 출발지 노드 또는 목적지 노드가 사용되는 것은 당연하다.

단계 S19의 처리에 있어서 경로 탐색 수단(33)에 의해 최적 경로가 탐색되면 경로 탐색 서버(30)는 탐색한 안내 경로의 데이터를 단계 S20의 처리에 있어서 네 비게이션 단말 장치(20)에 배신하여 처리를 종료한다. 안내 경로의 데이터를 수신한 네비게이션 단말 장치(20)는 안내 경로의 데이터를 안내 경로 데이터 기억 수단(25)에 일시 기억하고, 표시 수단(24)에 지도, 안내 경로 등을 표시한다.

또한, 상기의 실시예에 있어서는 복수의 출입구를 가지는 테마파크에 대하여, POI 속성 정보 DB(40)를 참조하여 가상 노드를 설정하는 구성을 설명하였으나, POI 속성 정보 DB(40)에 가상 노드의 데이터를 축적해 두고, 가상 노드 설정 수단(39)이 POI 속성 정보 DB(40)로부터 가상 노드의 데이터를 취득하는 구성으로 할 수도 있다.

이상 설명한 본 발명에 관한 경로 탐색 방법은 복수 목적지 또는 복수 출발지가 상정되는 각종 탐색에 이용할 수 있다. 카 네비게이션으로 주유소를 찾는 경우, 보행자 네비게이션으로 편의점을 찾는 경우 등에 유효하다. 탐색 자체는 종래의 알고리즘을 사용할 수 있기 때문에, 카 네비게이션 등의 스탠드-얼론(stand-alone)의 장치라도 프로그램을 큰 폭으로 수정하는 일 없이 실시가 가능하다.

Claims

탐색용 네트워크 데이터의 데이터베이스를 이용하여 출발 노드에서부터 목적 노드까지의 경로를 탐색하는 네비게이션 시스템에 있어서,

상기 네비게이션 시스템은 흥미 대상 장소(이하, "POI"라 함)의 속성 정보를 축적한 POI 속성 정보 데이터베이스와, 네트워크 데이터 편집 수단과, 가상 노드 설정 수단을 구비하고,

상기 네비게이션 시스템이 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스를 참조하여 출발지 및/또는 목적지에 복수의 POI가 존재하는지를 판별하고,

복수의 POI가 존재하는 경우에는 상기 가상 노드 설정 수단이 상기 복수의 POI의 노드의 각각과 링크 코스트(link cost)가 동일한 값을 가지는 링크로 접속되는 가상 노드를 설정하고,

상기 네트워크 데이터 편집 수단이 상기 탐색용 네트워크 데이터의 데이터 베이스에 상기 가상 노드를 추가하고, 경로 탐색 수단은 해당 가상 노드가 추가된 탐색용 네트워크 데이터를 이용하여 경로 탐색을 행하는 것을 특징으로 하는 네비게이션 시스템.
제1항에 있어서,

상기 POI에서부터 가상 노드까지의 링크 코스트는 값이 0 인 것을 특징으로 하는 네비게이션 시스템.
제1항 또는 제2항에 있어서,

상기 네비게이션 시스템은 경로 탐색 조건을 송신하는 네비게이션 단말 장치와,

네트워크를 통하여 상기 네비게이션 단말 장치와 접속되는 경로 탐색 서버를 구비하여 구성되는 것을 특징으로 하는 네비게이션 시스템.
네트워크를 통하여 경로 탐색 조건을 송신하는 네비게이션 단말 장치와 접속되는 경로 탐색 서버로서,

상기 경로 탐색 서버는 흥미 대상 장소(이하, "POI"라 함)의 속성 정보를 축적한 POI 속성 정보 데이터베이스와, 네트워크 데이터 편집 수단과, 가상 노드 설정 수단을 구비하고,

상기 경로 탐색 서버가 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스를 참조하여 출발지 및/또는 목적지에 복수의 POI가 존재하는지를 판별하고,

복수의 POI가 존재하는 경우에는 상기 가상 노드 설정 수단이 상기 복수의 POI 각각의 노드와 링크 코스트가 동등한 값을 가지는 링크로 접속되는 가상 노드를 설정하고,

상기 네트워크 데이터 편집 수단이 탐색용 네트워크 데이터의 데이터베이스에 상기 가상 노드를 추가하고, 경로 탐색 수단은 해당 가상 노드가 추가된 탐색용 네트워크 데이터를 이용하여 경로 탐색을 행하는 것을 특징으로 하는 경로 탐색 서버.
제4항에 있어서,

상기 POI에서부터 가상 노드까지의 링크 코스트는 값이 0 인 것을 특징으로 하는 경로 탐색 서버.
탐색용 네트워크 데이터를 이용하여 출발 노드에서부터 목적 노드까지의 경로를 탐색하는 경로 탐색 방법에 있어서,

네비게이션 시스템은 흥미 대상 장소(이하, "POI"라 함)의 속성 정보를 축적한 POI 속성 정보 데이터베이스와, 네트워크 데이터 편집 수단과, 가상 노드 설정 수단을 구비하고,

상기 네비게이션 시스템이 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스를 참조하여 출발지 및/또는 목적지에 복수의 POI가 존재하는지를 판별하는 단계와,

복수의 POI가 존재하는 경우에는 상기 가상 노드 설정 수단이 상기 복수의 POI의 각각의 노드와 링크 코스트가 동일한 값을 가지는 링크로 접속되는 가상 노드를 설정하는 단계와,

상기 네트워크 데이터 편집 수단이 탐색용 네트워크 데이터의 데이터베이스에 상기 가상 노드를 추가하고, 경로 탐색 수단은 해당 가상 노드가 추가된 탐색용 네트워크 데이터를 이용하여 경로 탐색을 행하는 단계를 포함하는 것을 특징으로 하는 경로 탐색 방법.
제6항에 있어서,

상기 POI에서부터 가상 노드까지의 링크 코스트의 값을 0 으로 하는 단계를 포함하는 것을 특징으로 하는 경로 탐색 방법.
경로 탐색 조건을 송신하는 네비게이션 단말 장치와, 네트워크를 통하여 상기 네비게이션 단말 장치와 접속되는 경로 탐색 서버를 구비하여 구성된 네비게이션 시스템에 있어서의 경로 탐색 방법으로서,

상기 경로 탐색 서버는 흥미 대상 장소(이하, "POI"라 함)의 속성 정보를 축적한 POI 속성 정보 데이터베이스와, 네트워크 데이터 편집 수단과, 가상 노드 설정 수단을 구비하고,

상기 경로 탐색 서버가 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스를 참조하여 출발지 및/또는 목적지에 복수의 POI가 존재하는지를 판별하는 단계와,

복수의 POI가 존재하는 경우에는 상기 가상 노드 설정 수단이 상기 복수의 POI의 각각의 노드와 링크 코스트가 동일한 값을 가지는 링크로 접속되는 가상 노드를 설정하는 단계와,

상기 네트워크 데이터 편집 수단이 탐색용 네트워크 데이터의 데이터베이스에 상기 가상 노드를 추가하고, 경로 탐색 수단은 해당 가상 노드가 추가된 탐색용 네트워크 데이터를 이용하여 경로 탐색을 행하는 단계를 포함하는 것을 특징으로 하는 경로 탐색 방법.
제8항에 있어서,

상기 POI에서부터 가상 노드까지의 링크 코스트의 값을 0 으로 하는 단계를 포함하는 것을 특징으로 하는 경로 탐색 방법.
프로그램이 기록된 기록매체로서, 상기 프로그램은 경로 탐색 조건을 송신하는 네비게이션 단말 장치와 네트워크를 통하여 접속되는 컴퓨터를 흥미 대상 장소(이하, "POI"라 함)의 속성 정보를 축적한 POI 속성 데이터베이스와, 네트워크 데이터 편집 수단과, 가상 노드 설정 수단을 구비한 경로 탐색 서버로서 기능을 시키고,

상기 경로 탐색 서버는 출발지 및/또는 목적지에 근거하여 POI 속성 정보 데이터베이스를 참조하여 출발지 및/또는 목적지에 복수의 POI가 존재하는지를 판별하는 처리를 실행하고,

복수의 POI가 존재하는 경우에는 상기 가상 노드 설정 수단이 상기 복수의 POI의 각각의 노드와 링크 코스트가 동일한 값을 가지는 링크로 접속되는 가상 노드를 설정하는 처리를 실행하고,

상기 네트워크 데이터 편집 수단이 탐색용 네트워크 데이터의 데이터베이스에 상기 가상 노드를 추가하고, 경로 탐색 수단은 해당 가상 노드가 추가된 탐색용 네트워크 데이터를 이용하여 경로 탐색을 행하는 처리를 실행하는 것을 특징으로 하는 프로그램이 기록된 기록 매체.
제10항에 있어서,

상기 경로 탐색 서버를 구성하는 컴퓨터에 상기 POI에서부터 가상 노드까지의 링크 코스트의 값을 0 으로 하는 처리를 실행시키는 것을 특징으로 하는 프로그램이 기록된 기록 매체.