KR20160122434A

KR20160122434A - System and method for searching route

Info

Publication number: KR20160122434A
Application number: KR1020150052273A
Authority: KR
Inventors: 허성범
Original assignee: 주식회사 맵퍼스
Priority date: 2015-04-14
Filing date: 2015-04-14
Publication date: 2016-10-24

Abstract

경로 탐색 시스템은 경로 탐색을 위한 복수의 교통 허브들을 생성하는 교통 허브 생성부, 교통 정보를 이용하여 교통 허브들을 간의 최단 교통 허브 경로들을 탐색하는 교통 허브 경로 탐색부, 및 최단 교통 허브 경로들을 이용하여 출발지로부터 목적지까지의 최단 경로를 탐색하는 최단 경로 탐색부를 포함한다.The route search system includes a traffic hub generating unit for generating a plurality of traffic hubs for searching for a route, a traffic hub path searching unit searching for the shortest traffic hub paths between traffic hubs using traffic information, And a shortest path search unit for searching for the shortest path from the source to the destination.

Description

{SYSTEM AND METHOD FOR SEARCHING ROUTE}

본 발명은 경로 탐색 시스템에 관한 것으로, 보다 상세하게는 교통 허브를 이용한 경로 탐색 시스템 및 경로 탐색 방법에 관한 것이다.The present invention relates to a route search system, and more particularly, to a route search system and a route search method using a transportation hub.

경로 탐색 시스템은 GPS(Global Positioning System)와 같은 GNSS (Global Navigation Satellite System)를 이용하여 현재 위치에서 사용자가 지정한 임의의 목적지까지의 길을 탐색한다.The route search system searches for a route from a current location to an arbitrary destination specified by a user using a Global Navigation Satellite System (GNSS) such as Global Positioning System (GPS).

일반적으로, 경로 탐색 시스템은 GPS 위성을 통해서 수신 받은 차량의 위치 정보를 기반으로 현재 위치를 파악한 후, 사용자가 현재 위치를 식별할 수 있도록 차량의 위치를 지도와 함께 단말기에 표시한다. 또한, 경로 탐색 시스템은 출발지로부터 목적지까지의 경로를 탐색할 수 있으므로, 경로 탐색 시스템은 사용자가 목적지를 쉽게 찾을 수 있도록 안내할 수 있다.Generally, the route search system grasps the current location based on the location information of the vehicle received through the GPS satellite, and displays the location of the vehicle along with the map on the terminal so that the user can identify the current location. Also, since the route search system can search the route from the departure point to the destination, the route search system can guide the user to find the destination easily.

경로 탐색 시스템은 단말기의 부하를 줄이기 위해 단말기와 분리되어 별도의 서버에서 구현될 수 있다. 예를 들어, 서버에서 경로를 탐색하고, 탐색된 경로 정보를 단말기로 전송한다. 단말기는 서버로부터 수신된 경로 정보를 이용하여 경로를 안내할 수 있다.The path search system may be implemented in a separate server separate from the terminal to reduce the load on the terminal. For example, the server searches for a path and transmits the discovered path information to the terminal. The terminal can guide the route using the route information received from the server.

또한, 경로 탐색 시스템은 교통 정보를 활용하여 경로를 탐색함으로써 사용자에게 소요 시간이 적은 경로를 제공할 수 있다. 경로 탐색 시스템은 사용자가 목적지를 설정하면 출발지에서 목적지까지의 예상 도착 시간을 안내하거나, 교통 정보에 따른 우회 경로를 제안하는 등 사용자에게 다양한 부가 정보를 제공한다. In addition, the route search system can provide a route requiring less time to the user by searching the route using the traffic information. The route search system provides various additional information to the user, such as guiding the estimated arrival time from the origin to the destination when the user sets a destination, or suggesting a bypass route based on the traffic information.

TPEG(Transport Protocol Expert Group) 등과 같이 교통 정보를 반영하는 경로 검색 시스템은 교통 정보를 주기적으로 갱신하기 위하여 설정에 따라 5~10분 주기로 경로에 대한 재탬색을 실시한다. 경로 검색 시스템의 재탐색 동작은 현재 위치와 목적지간 교통 정보를 취합하여 가공하는 작업이 반복적으로 실시되므로, 시스템 리소스 낭비 및 탐색 시간이 길어지는 문제점이 있다. 이러한, 경로 검색 시스템의 부하는 장거리 경로에 대한 탐색 시 더 심하게 발생한다.A route retrieval system that reflects traffic information such as TPEG (Transport Protocol Expert Group) carries out a redesign of the route in a period of 5 to 10 minutes according to the setting in order to periodically update the traffic information. In the re-search operation of the route search system, the work of collecting the traffic information between the current location and the destination is repeatedly performed, which results in a waste of system resources and a long search time. This load on the path search system occurs more heavily when searching for long distance paths.

본 발명의 일 목적은 효율적으로 경로를 탐색할 수 있는 경로 검색 시스템을 제공하는 것이다.An object of the present invention is to provide a route search system capable of efficiently searching for a route.

본 발명의 다른 목적은 효율적으로 경로를 탐색할 수 있는 경로 검색 방법을 제공하는 것이다.Another object of the present invention is to provide a route search method capable of efficiently searching a route.

다만, 본 발명의 목적은 상기 목적들로 한정되는 것이 아니며, 본 발명의 사상 및 영역으로부터 벗어나지 않는 범위에서 다양하게 확장될 수 있을 것이다.It should be understood, however, that the present invention is not limited to the above-described embodiments, and may be variously modified without departing from the spirit and scope of the present invention.

본 발명의 일 목적을 달성하기 위하여, 본 발명의 실시예들에 따른 서버 부하 및 탐색 시간을 줄일 수 있는 경로 검색 시스템은 경로 탐색을 위한 복수의 교통 허브들을 생성하는 교통 허브 생성부, 교통 정보를 이용하여 교통 허브 간선들을 통해 상기 교통 허브들을 연결하는 교통 허브 경로들 중 최단 소요 시간에 상응하는 최단 교통 허브 경로들을 탐색하는 교통 허브 경로 탐색부, 및 상기 최단 교통 허브 경로들을 이용하여 출발지로부터 목적지까지의 최단 경로를 탐색하는 최단 경로 탐색부를 포함할 수 있다.According to an aspect of the present invention, there is provided a route search system capable of reducing server load and search time according to embodiments of the present invention includes a traffic hub generating unit for generating a plurality of traffic hubs for route search, A traffic hub path search unit for searching for the shortest traffic hub paths corresponding to the shortest required time among the transportation hub paths connecting the transportation hubs through the transportation hub trunks by using the shortest transportation hub paths, And a shortest path search unit for searching for a shortest path.

일 실시예에 의하면, 상기 최단 경로 탐색부는 상기 교통 정보를 이용하여 상기 출발지로부터 상기 교통 허브들까지의 소요 시간들 중 최단 소요 시간에 상응하는 출발지 교통 허브 및 상기 목적지로부터 상기 교통 허브들까지의 소요 시간들 중 최단 소요 시간에 상응하는 목적지 교통 허브를 선택할 수 있다. 그리고 상기 출발지로부터 상기 제1 교통 허브를 연결하는 제1 경로 및 상기 목적지로부터 상기 제2 교통 허브를 연결하는 제2 경로를 탐색할 수 있다.According to an embodiment of the present invention, the shortest path search unit uses the traffic information to provide a source transport hub corresponding to the shortest time required from the start point to the transportation hubs, and a route from the destination to the transport hubs The destination transportation hub corresponding to the shortest time among the times can be selected. And a first path connecting the first transportation hub and a second path connecting the second transportation hub from the destination may be searched.

일 실시예에 의하면, 상기 교통 허브 경로 탐색부는 상기 출발지 교통 허브로부터 상기 목적지 교통 허브를 연결하는 탐색 교통 허브 경로를 탐색할 수 있고 상기 최단 경로 탐색부는 상기 제1 경로, 상기 탐색 교통 허브 경로, 및 상기 제2 경로를 연결함으로써 상기 출발지로부터 상기 목적지까지의 상기 최단 경로를 탐색할 수 있다.According to an embodiment, the traffic hub path search unit may search for a search traffic hub path connecting the destination traffic hub from the source traffic hub, and the shortest path search unit may search for the first path, the search traffic hub path, The shortest path from the source to the destination can be searched by connecting the second route.

일 실시예에 의하면, 상기 경로 탐색 시스템은 상기 최단 교통 허브 경로들이 저장되는 교통 허브 경로 저장부를 더 포함하고, 상기 교통 허브 경로 탐색부는 상기 최단 교통 허브 경로들을 상기 교통 허브 경로 저장부에 저장할 수 있다.According to an embodiment of the present invention, the path search system may further include a transportation hub path storage unit in which the shortest transportation hub paths are stored, and the transportation hub path search unit may store the shortest transportation hub paths in the transportation hub path storage unit .

일 실시예에 의하면, 상기 교통 허브 경로 탐색부는 기 지정된 주기 마다 상기 최단 교통 허브 경로들을 갱신할 수 있다.According to an embodiment, the traffic hub path search unit may update the shortest traffic hub paths every predetermined period.

일 실시예에 의하면 상기 교통 허브 생성부는 기 지정된 주기마다 상기 교통 허브들을 갱신할 수 있다.According to an embodiment, the traffic hub generating unit may update the traffic hubs at predetermined intervals.

일 실시예에 의하면, 상기 교통 정보가 누적하여 저장되는 교통 정보 저장부를 더 포함하고, 상기 교통 허브 생성부는 상기 교통 정보 저장부에 저장된 상기 교통 정보에 기초하여 상기 교통 허브들을 생성할 수 있다.According to an embodiment of the present invention, the traffic hub generating unit may generate the traffic hubs based on the traffic information stored in the traffic information storage unit.

본 발명의 다른 목적을 달성하기 위하여, 발명의 실시예들에 따른 경로 검색 방법은 경로 탐색을 위한 복수의 교통 허브들을 생성하는 단계, 교통 정보를 이용하여 출발지로부터 상기 교통 허브들까지의 소요 시간들 중 최단 소요 시간에 상응하는 출발지 교통 허브 및 목적지로부터 상기 교통 허브들까지의 소요 시간들 중 최단 소요 시간에 상응하는 목적지 교통 허브를 선택하는 단계, 상기 교통 정보를 이용하여 상기 교통 허브 간선들을 통해 상기 출발지 교통 허브로부터 상기 목적지 교통 허브를 연결하는 교통 허브 경로들 중 최단 소요 시간에 상응하는 탐색 교통 허브 경로를 탐색하는 단계, 및 상기 탐색 교통 허브 경로를 이용하여 상기 출발지로부터 상기 목적지까지 최단 경로를 탐색하는 단계를 포함할 수 있다.According to another aspect of the present invention, there is provided a route search method comprising: generating a plurality of traffic hubs for route search; Selecting a destination transportation hub corresponding to a shortest required time and a destination transportation hub corresponding to a shortest required time from the destination to the transportation hubs, The method comprising the steps of: searching for a search transport hub path corresponding to the shortest time required among the transport hub paths connecting the destination transport hub from the source transport hub; and searching for a shortest path from the source to the destination using the search transport hub path .

일 실시예에 의하면, 상기 최단 경로를 탐색하는 단계는 상기 출발지로부터 상기 출발지 교통 허브를 연결하는 제1 경로를 탐색하고, 상기 목적지로부터 상기 목적지 교통 허브를 연결하는 제2 경로를 탐색하는 단계 및 상기 제1 경로, 상기 탐색 교통 허브 경로, 및 상기 제2 경로를 연결함으로써, 상기 출발지로부터 상기 목적지까지 상기 최단 경로를 탐색하는 단계를 포함할 수 있다.According to one embodiment, the searching for the shortest path may include searching a first path connecting the departure location transportation hub from the departure location, searching a second route connecting the destination transportation hub from the destination, And searching for the shortest path from the source to the destination by concatenating the first path, the search transportation hub path, and the second path.

일 실시예에 의하면, 상기 교통 허브들은 기 지정된 주기마다 갱신될 수 있다.According to one embodiment, the transport hubs may be updated every predetermined period.

본 발명의 실시예들에 따른 경로 탐색 시스템은 교통 허브 경로들을 이용하여 출발지로부터 목적지까지의 최단 경로를 탐색함으로써 경로 탐색 속도를 향상시킬 수 있다.The path search system according to the embodiments of the present invention can improve the path search speed by searching for the shortest path from the source to the destination using the traffic hub paths.

나아가, 상기 경로 탐색 시스템은 최단 교통 허브 경로들을 교통 허브 경로 저장부에 저장함으로써 경로 탐색 요청마다 교통 허브 경로를 반복적으로 탐색할 필요가 없으므로 서버 리소스를 효율적으로 사용할 수 있다.Furthermore, since the path search system stores the shortest traffic hub paths in the traffic hub path storage unit, it is unnecessary to search the traffic hub path repeatedly for each path search request, so that server resources can be efficiently used.

다만, 본 발명의 효과는 상기 효과들로 한정되는 것이 아니며, 본 발명의 사상 및 영역으로부터 벗어나지 않는 범위에서 다양하게 확장될 수 있을 것이다.However, the effects of the present invention are not limited to the above effects, and may be variously extended without departing from the spirit and scope of the present invention.

도 1은 본 발명의 일 실시예에 따른 경로 탐색 시스템을 나타내는 블록도이다.
도 2a 내지 도2d는 도 1의 경로 탐색 시스템에서 출발지로부터 목적지까지의 최단 경로를 탐색하는 일 예를 나타내는 도면들이다.
도 3은 교통 정보가 갱신됨에 따라 도 2의 최단 경로가 변경되는 일 예를 나타내는 도면이다.
도 4는 본 발명의 다른 실시예에 따른 경로 탐색 시스템을 나타내는 블록도이다.
도 5는 본 발명의 실시예들에 따른 경로 탐색 방법을 나타내는 순서도이다.1 is a block diagram showing a route search system according to an embodiment of the present invention.
2A to 2D are diagrams illustrating an example of searching for a shortest path from a source to a destination in the route search system of FIG.
3 is a diagram showing an example in which the shortest path of FIG. 2 is changed as the traffic information is updated.
4 is a block diagram illustrating a path search system according to another embodiment of the present invention.
5 is a flowchart illustrating a path search method according to embodiments of the present invention.

본문에 개시되어 있는 본 발명의 실시예들에 대해서, 특정한 구조적 내지 기능적 설명들은 단지 본 발명의 실시예를 설명하기 위한 목적으로 예시된 것으로, 본 발명의 실시예들은 다양한 형태로 실시될 수 있으며 본문에 설명된 실시예들에 한정되는 것으로 해석되어서는 아니 된다.For the embodiments of the invention disclosed herein, specific structural and functional descriptions are set forth for the purpose of describing an embodiment of the invention only, and it is to be understood that the embodiments of the invention may be practiced in various forms, The present invention should not be construed as limited to the embodiments described in Figs.

본 발명은 다양한 변경을 가할 수 있고 여러 가지 형태를 가질 수 있는바, 특정 실시예들을 도면에 예시하고 본문에 상세하게 설명하고자 한다. 그러나 이는 본 발명을 특정한 개시 형태에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다.The present invention is capable of various modifications and various forms, and specific embodiments are illustrated in the drawings and described in detail in the text. It is to be understood, however, that the invention is not intended to be limited to the particular forms disclosed, but on the contrary, is intended to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention.

제1, 제2 등의 용어는 다양한 구성 요소들을 설명하는데 사용될 수 있지만, 상기 구성요소들은 상기 용어들에 의해 한정되어서는 안 된다. 상기 용어들은 하나의 구성요소를 다른 구성 요소로부터 구별하는 목적으로 사용될 수 있다. 예를 들어, 본 발명의 권리 범위로부터 이탈되지 않은 채 제1 구성 요소는 제2 구성 요소로 명명될 수 있고, 유사하게 제 2 구성 요소도 제1 구성 요소로 명명될 수 있다.The terms first, second, etc. may be used to describe various components, but the components should not be limited by the terms. The terms may be used for the purpose of distinguishing one component from another. For example, without departing from the scope of the present invention, the first component may be referred to as a second component, and similarly, the second component may also be referred to as a first component.

본 출원에서 사용한 용어는 단지 특정한 실시예를 설명하기 위해 사용된 것으로, 본 발명을 한정하려는 의도가 아니다. 단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 출원에서, "포함하다" 또는 "가지다" 등의 용어는 설시된 특징, 숫자, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것이 존재함을 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.The terminology used in this application is used only to describe a specific embodiment and is not intended to limit the invention. The singular expressions include plural expressions unless the context clearly dictates otherwise. In the present application, the terms "comprise", "having", and the like are intended to specify the presence of stated features, integers, steps, operations, elements, components, or combinations thereof, , Steps, operations, components, parts, or combinations thereof, as a matter of principle.

또한, 본문에 기재된 "~부" 등의 용어는 적어도 하나의 기능이나 동작을 처리하는 단위를 의미하며, 이는 하드웨어나 소프트웨어 또는 하드웨어 및 소프트웨어의 결합으로 구현될 수 있다.Also, the terms "to" and the like in the present description mean a unit for processing at least one function or operation, and may be implemented by hardware, software, or a combination of hardware and software.

다르게 정의되지 않는 한, 기술적이거나 과학적인 용어를 포함해서 여기서 사용되는 모든 용어들은 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에 의해 일반적으로 이해되는 것과 동일한 의미이다. 일반적으로 사용되는 사전에 정의되어 있는 것과 같은 용어들은 관련 기술의 문맥상 가지는 의미와 일치하는 의미인 것으로 해석되어야 하며, 본 출원에서 명백하게 정의하지 않는 한, 이상적이거나 과도하게 형식적인 의미로 해석되지 않는다.Unless otherwise defined, all terms used herein, including technical or scientific terms, have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. Terms such as those defined in commonly used dictionaries should be construed as meaning consistent with meaning in the context of the relevant art and are not to be construed as ideal or overly formal in meaning unless expressly defined in the present application .

이하, 첨부한 도면들을 참조하여, 본 발명의 실시예들을 보다 상세하게 설명하고자 한다. 도면상의 동일한 구성 요소에 대해서는 동일하거나 유사한 참조 부호를 사용한다.Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings. The same or similar reference numerals are used for the same components in the drawings.

도 1은 본 발명의 일 실시예에 따른 경로 탐색 시스템을 나타내는 블록도이다.1 is a block diagram showing a route search system according to an embodiment of the present invention.

도 1을 참조하면, 경로 탐색 시스템(100A)은 교통 허브 생성부(110), 교통 허브 경로 탐색부(120), 교통 허브 경로 저장부(130) 및 최단 경로 탐색부(140)를 포함할 수 있다.Referring to FIG. 1, the route search system 100A may include a traffic hub generating unit 110, a traffic hub path searching unit 120, a traffic hub path storing unit 130, and a shortest path searching unit 140 have.

교통 허브 생성부(110)는 경로 탐색을 위한 복수의 교통 허브들을 생성할 수 있다. 예를 들면, 교통 허브 생성부(110)는 교통량이 많은 교차로, 고속도로 톨게이트 등의 위치에 교통 허브들을 생성할 수 있다. 또한, 교통 허브 생성부(110)는 시간, 요일, 날짜 등 다양한 조건에 따라 다른 위치에 교통 허브를 생성할 수 있다.The traffic hub generating unit 110 may generate a plurality of traffic hubs for path search. For example, the traffic hub generating unit 110 may generate traffic hubs at locations such as intersections, highway tolls, and the like having high traffic. In addition, the transportation hub generating unit 110 may generate a transportation hub at a different location according to various conditions such as time, day of the week, and date.

일 실시예에서, 교통 허브 생성부(110)는 기 지정된 주기마다 교통 허브들을 갱신할 수 있다. 구간 소요 시간, 구간 속도, 통행 제한 도로 등을 포함하는 교통 정보는 날씨, 교통 사고와 같은 우연한 사건에 의해서 급변할 수 있다. 기 지정된 주기마다 교통 허브가 갱신되는 경우, 주기적으로 갱신된 교통 정보를 반영한 교통 허브가 생성될 수 있다. 예를 들어, 한 시간 주기로 교통 허브 생성부(110)가 교통 허브를 생성하는 경우, 한 시간 사이에 발생한 교통 사고 또는 통행 제한 도로 등 교통 정보가 반영된 교통 허브들이 생성될 수 있다.In one embodiment, the traffic hub generator 110 may update the traffic hubs at predetermined intervals. Traffic information including the time required for the section, the section speed, and the traffic restriction road can be changed rapidly due to an incident such as a weather or a traffic accident. If the traffic hub is updated every predetermined period, a traffic hub that reflects periodically updated traffic information can be generated. For example, when the traffic hub generating unit 110 generates a traffic hub in a period of one time, traffic hubs in which traffic information such as traffic accidents or traffic restriction roads generated during one hour are reflected may be generated.

교통 허브 경로 탐색부(120)는 교통 정보를 이용하여 교통 허브 간선들을 통해 상기 교통 허브들을 연결하는 교통 허브 경로들 중 최단 소요 시간에 상응하는 최단 교통 허브 경로들을 탐색할 수 있다. 여기서, 최단 교통 허브 경로는 교통 허브 간선들을 경유하여 2개의 교통 허브들을 연결하는 다양한 경로들(즉, 교통 허브 경로들) 중 최단 소요 시간에 상응하는 경로를 의미한다. 교통 허브 간선은 인접한 2개의 교통 허브들을 연결하는 경로를 의미한다. 예를 들어, 교통 허브 탐색부(120)는 교통 허브 간선들을 통과하여 제1 교통 허브로부터 제2 교통 허브에 도달하는 다양한 경로들 중에서 최단 소요 시간에 상응하는 최단 교통 허브 경로를 탐색할 수 있다. 최단 교통 허브 경로는 Dijkstra 알고리즘, Bellman-Ford 알고리즘, Floyd-Warshall 알고리즘 등과 같은 최단 경로 알고리즘을 이용하여 도출될 수 있다.The transportation hub route search unit 120 may search for the shortest transportation hub routes corresponding to the shortest required time among the transportation hub routes connecting the transportation hubs through the transportation hub trunks using the traffic information. Here, the shortest traffic hub path means a path corresponding to the shortest required time among various paths connecting the two transportation hubs via the transportation hub trunks (i.e., transportation hub paths). The transport hub trunk refers to a path connecting two adjacent transportation hubs. For example, the traffic hub searching unit 120 may search for the shortest traffic hub path corresponding to the shortest time among the various paths from the first traffic hub to the second traffic hub through the traffic hub trunks. The shortest transport hub path can be derived using shortest path algorithms such as the Dijkstra algorithm, the Bellman-Ford algorithm, the Floyd-Warshall algorithm, and so on.

일 실시예에서, 교통 허브 경로 탐색부(120)는 출발지 교통 허브로부터 목적지 교통 허브를 연결하는 탐색 교통 허브 경로를 탐색할 수 있다. 출발지 교통 허브는 출발지로부터 교통 허브들까지의 소요 시간들 중 최단 소요 시간에 상응하는 교통 허브일 수 있다. 목적지 교통 허브는 목적지로부터 교통 허브들까지의 소요 시간들 중 최단 소요 시간에 상응하는 교통 허브일 수 있다.In one embodiment, the traffic hub path search unit 120 may search for a search traffic hub path connecting the destination traffic hub from the source traffic hub. The departure point transportation hub may be a transportation hub corresponding to the shortest time required from the departure point to the transportation hubs. The destination transportation hub may be a transportation hub corresponding to the shortest time required from the destination to the transportation hubs.

일 실시예에서, 교통 허브 경로 탐색부(120)는 최단 교통 허브 경로들을 교통 허브 경로 저장부(130)에 저장할 수 있다. 교통 허브 경로 저장부(130)는 데이터베이스 관리 시스템(database management system) 등의 스토리지 시스템일 수 있다. 교통 허브 경로 탐색부(120)는 탐색 교통 허브 경로를 탐색할 때, 교통 허브 경로 저장부(130)에 저장된 최단 교통 허브 경로들을 이용함으로써 탐색 교통 허브 경로를 탐색할 때마다 최단 교통 허브 경로를 탐색하는 과정을 반복해서 수행할 필요가 없어질 수 있다. 즉, 교통 허브 경로 탐색부(120)는 교통 허브 경로 저장부(130)에 저장된 최단 교통 허브 경로들을 이용하여 탐색 교통 허브 경로를 도출할 수 있으므로, 경로 탐색의 효율을 높일 수 있다.In one embodiment, the transportation hub path search unit 120 may store the shortest transportation hub paths in the transportation hub path storage unit 130. [ The transportation hub route storage unit 130 may be a storage system such as a database management system. The traffic hub path search unit 120 searches for the shortest traffic hub path every time the search traffic hub path is searched by using the shortest traffic hub paths stored in the traffic hub path storage unit 130 when searching for the search traffic hub path. It may be unnecessary to perform the process repeatedly. That is, the traffic hub path search unit 120 can derive the search traffic hub path using the shortest traffic hub paths stored in the traffic hub path storage unit 130, thereby improving the efficiency of path search.

일 실시예에서, 교통 허브 경로 탐색부(120)는 기 지정된 주기마다 최단 교통 허브 경로들을 갱신할 수 있다. 교통 허브 경로 탐색부(120)는 갱신된 최단 교통 허브 경로들을 기 지정된 주기마다 갱신함으로써, 최단 교통 허브 경로에 주기적으로 교통 정보를 반영하고, 교통 정보가 반영된 탐색 교통 허브 경로를 탐색할 수 있다. 나아가, 최단 경로 탐색부(140)는 갱신된 탐색 교통 허브 경로를 이용하여 출발지로부터 목적지까지의 최단 경로를 탐색할 수 있다. 결과적으로, 최단 경로 탐색부(140)은 기 지정된 주기마다 갱신된 최단 교통 허브 경로들 및 탐색 교통 허브 경로에 기초하여 출발지로부터 목적지까지의 최단 경로를 탐색할 수 있다.In one embodiment, the traffic hub path search unit 120 may update the shortest traffic hub paths every predetermined period. The transportation hub route search unit 120 may update the updated shortest transportation hub routes at predetermined intervals so as to periodically reflect the traffic information in the shortest transportation hub route and search for the navigation transportation hub route reflecting the traffic information. Furthermore, the shortest path search unit 140 can search for the shortest path from the source to the destination using the updated search transport hub path. As a result, the shortest path searching unit 140 can search for the shortest path from the origin to the destination based on the shortest transportation hub paths and the search transportation hub path updated every predetermined period.

최단 경로 탐색부(140)는 최단 교통 허브 경로들을 이용하여 출발지로부터 목적지까지의 최단 경로를 탐색할 수 있다. 일 실시예에서, 최단 경로 탐색부(140)는 교통 정보를 이용하여 출발지로부터 교통 허브들까지의 소요 시간들 중 최단 소요 시간에 상응하는 출발지 교통 허브 및 목적지로부터 교통 허브들까지의 소요 시간들 중 최단 소요 시간에 상응하는 목적지 교통 허브를 선택하고, 출발지로부터 출발지 교통 허브를 연결하는 제1 경로 및 목적지로부터 목적지 교통 허브를 연결하는 제2 경로를 탐색할 수 있다. 즉, 최단 경로 탐색부(140)는 출발지로부터 교통 허브까지 최단 시간에 도달할 수 있는 제1 경로 및 교통 허브로부터 목적지까지 최단 시간에 도달할 수 있는 제2 경로를 탐색할 수 있다. 따라서, 최단 경로 탐색부(140)는 제1 경로, 탐색 교통 허브 경로, 및 제2 경로를 연결함으로써 출발지로부터 목적지까지의 최단 경로를 탐색할 수 있다.The shortest path search unit 140 can search for the shortest path from the source to the destination using the shortest transportation hub paths. In one embodiment, the shortest path search unit 140 uses the traffic information to calculate the time required from the source transportation hub corresponding to the shortest required time to the transportation hubs from the destination and the transportation hubs It is possible to select a destination transportation hub corresponding to the shortest required time and search a first route connecting the departure location transportation hub and a second route connecting the destination transportation hub from the destination. That is, the shortest path search unit 140 can search the first path that can reach the shortest time from the source to the transportation hub, and the second path that can reach the shortest time from the transportation hub to the destination. Therefore, the shortest path searching unit 140 can search the shortest path from the source to the destination by connecting the first path, the search traffic hub path, and the second path.

단말기(200)는 경로 탐색 요청부(210) 및 표시부(220)를 포함할 수 있다.The terminal 200 may include a route search request unit 210 and a display unit 220.

경로 탐색 요청부(210)는 출발지 및 목적지에 대한 정보를 포함하는 경로 탐색 요청 신호를 경로 탐색 시스템(100A)의 최단 경로 탐색부(140)로 전송할 수 있다. 경로 탐색 시스템(100A)은 경로 탐색 요청 신호를 수신함으로써 출발지로부터 목적지까지 연결하는 최단 경로를 탐색할 수 있다. 경로 탐색 시스템(100A)은 탐색된 최단 경로를 단말기(200)에 표시하기 위한 형태로 변환하고, 변환된 정보를 단말기(200)로 전송할 수 있다. 단말기(200)는 탐색된 최단 경로에 대한 정보를 수신하고, 단말기(200)의 표시부(220)는 출발지로부터 목적지까지 연결하는 최단 경로를 지도에 표시하고 안내 음성을 출력할 수 있다.The route search request unit 210 may transmit a route search request signal including information on a source and a destination to the shortest route search unit 140 of the route search system 100A. The path search system 100A can search for the shortest path connecting from the origin to the destination by receiving the path search request signal. The path search system 100A may convert the shortest path detected to a form for display on the terminal 200 and transmit the converted information to the terminal 200. [ The terminal 200 receives the information about the shortest route searched and the display unit 220 of the terminal 200 displays the shortest route connecting from the source to the destination on a map and outputs a guidance voice.

예를 들어, 단말기(200)는 서울 시청이 출발지로 설정되고 목적지는 대전역으로 설정된 경로 탐색 요청 신호를 경로 탐색 시스템(100A)으로 전송할 수 있다. 경로 탐색 요청 신호를 수신한 경로 탐색 시스템(100A)은 교통 정보에 따라 출발지 교통 허브는 남산 제1 호 터널로, 목적지 교통 허브는 대동역으로 선택할 수 있다. 나아가, 경로 탐색 시스템(100A)은 서울역으로부터 남산 제1 호 터널까지 도달할 수 있는 경로 중에서 최단 소요 시간에 상응 하는 제1 경로 및 대동역으로부터 대전역까지 도달할 수 있는 경로 중에서 최단 소요 시간에 상응하는 제2 경로를 탐색할 수 있다. 교통 허브 경로 탐색부(120)는 최단 교통 허브 경로를 이용하여 남산 제1 호 터널로부터 대동역까지 도달할 수 있는 탐색 교통 허브를 탐색할 수 있다. 탐색 교통 허브 경로가 결정 되면, 경로 탐색 시스템(100A)은 제1 경로, 제2 경로, 및 탐색 교통 허브 경로를 연결하는 최단 경로를 탐색할 수 있다. 추가적으로, 경로 탐색 시스템(100A)은 탐색된 최단 경로에 대한 정보를 단말기(200)에 표시하기 위한 형태로 변환할 수 있다. 경로 탐색 시스템 (100A)은 탐색된 서울 시청에서부터 대전역까지 도달할 수 있는 최단 경로에 대한 정보를 단말기(200)로 전송할 수 있다. 단말기(200)는 탐색된 최단 경로에 대한 정보를 수신하고, 단말기(200)의 표시부(220)에서는 서울 시청에서부터 대전역까지 도달할 수 있는 최단 경로를 지도에 표시하고 안내 음성을 출력할 수 있다. 최단 경로를 탐색하는 과정에 대해서는 도 2a 내지 도 2d를 참조하여 자세히 설명하기로 한다.For example, the terminal 200 may transmit a route search request signal to the route search system 100A, which is set as a departure location of Seoul City Hall and whose destination is a charging station. The route search system 100A that has received the route search request signal can select the Namsan No. 1 tunnel as the source transport hub and the destination transport hub as the destination transport hub according to the traffic information. Furthermore, the route search system 100A is equivalent to the shortest travel time among the routes that can reach the Namsan No. 1 tunnel from the Seoul station to the first route corresponding to the shortest travel time, It is possible to search the second path. The transportation hub route search unit 120 can search for a navigation transportation hub that can reach from the Namsan No. 1 tunnel to the east station using the shortest transportation hub route. Once the search traffic hub path is determined, the path search system 100A can search for the shortest path connecting the first path, the second path, and the search traffic hub path. In addition, the path search system 100A may convert the information about the shortest path detected to a form for display on the terminal 200. [ The path search system 100A can transmit information on the shortest path from the searched Seoul City Hall to the Daejeon station to the terminal 200. [ The terminal 200 receives the information on the shortest route searched for and displays the shortest route from the city hall to the Daejeon station on the map and outputs the guide voice in the display unit 220 of the terminal 200 . The process of searching for the shortest path will be described in detail with reference to FIGS. 2A to 2D.

따라서, 경로 탐색 시스템(100A)은 탐색 교통 허브 경로 탐색 시 미리 저장된 최단 교통 허브 경로를 이용하여 탐색을 할 수 있다. 경로 탐색 시스템(100A)은 출발지로부터 출발지 교통 허브까지 연결하는 제1 경로 및 도착지로부터 도착지 교통 허브까지 연결하는 제2 경로를 탐색하고, 제1 경로, 탐색 교통 허브 경로, 및 제2 경로를 연결하여 최단 경로를 도출될 수 있다. 경로 탐색 시스템(100A)은 미리 저장된 탐색 교통 허브 경로를 이용하여 도출할 수 있으므로, 경로 탐색 시스템(100A)의 부하를 줄이고 최단 경로가 빠르게 탐색될 수 있다.Accordingly, the path search system 100A can perform the search using the pre-stored shortest transportation hub path in the search traffic hub path search. The route search system 100A searches for a first route connecting from a departure place to a departure location transportation hub and a second route connecting from a destination to a destination transportation hub, and connects the first route, the search transportation hub route, A shortest path can be derived. Since the path search system 100A can be derived using a previously stored search transportation hub path, the load of the path search system 100A can be reduced and the shortest path can be quickly searched.

또한, 경로 탐색 시스템(100A)은 복수의 단말기(200)로부터 복수의 경로 탐색 요청들을 수신하는 경우, 반복되는 경로 탐색 동작을 줄일 수 있다. 즉, 복수의 단말기(200)로부터 복수의 경로 탐색 요청들을 수신하는 경우, 미리 저장된 탐색 교통 허브 경로를 이용할 수 있으므로 경로 탐색 요청 횟수만큼 전구간에 걸친 경로 탐색을 수행할 필요가 없다. 결과적으로, 경로 탐색 시스템(100A)의 리소스를 효율적으로 사용할 수 있고 경로 탐색 시스템(100A)의 과부하 문제가 방지될 수 있다.In addition, the path search system 100A can reduce a repeated path search operation when receiving a plurality of path search requests from a plurality of terminals 200. [ In other words, when a plurality of route search requests are received from a plurality of terminals 200, it is not necessary to perform a route search all the way by the number of route search requests since it can use a stored search transportation hub route. As a result, the resources of the path search system 100A can be efficiently used and the overload problem of the path search system 100A can be prevented.

도 2a 내지 도2d는 도 1의 경로 탐색 시스템에서 출발지로부터 목적지까지의 최단 경로를 탐색하는 일 예를 나타내는 도면들이다.2A to 2D are diagrams illustrating an example of searching for a shortest path from a source to a destination in the route search system of FIG.

도 2a 내지 도2d를 참조하면, 경로 탐색 시스템은 최단 교통 허브 경로들을 이용하여 출발지(S)로부터 목적지(D)까지의 최단 경로를 탐색할 수 있다. 제1 교통 허브(H1) 내지 제7 교통 허브(H7)를 생성할 수 있다. 예를 들면, 교통 허브 생성부는 교통량이 많은 교차로, 고속도로 톨게이트 등의 위치에 교통 허브들을 생성할 수 있다. 또한, 교통 허브 생성부는 시간, 요일, 날짜 등 다양한 조건에 따라 다른 위치에 교통 허브를 생성할 수 있다. 단말기로부터 경로 탐색 요청 신호를 수신할 때마다, 최단 경로 탐색부는 출발지 교통 허브 및 목적지 교통 허브를 선택할 수 있다. 출발지 교통 허브는 출발지(S)로부터 최단 시간에 도달할 수 있는 교통 허브로서 제1 교통 허브(H1)가 선택될 수 있다. 목적지 교통 허브는 목적지로(D)부터 최단 시간에 도달할 수 있는 교통 허브로서 제6 교통 허브(H6) 및 제7 교통 허브(H7)가 선택될 수 있다. 출발지 교통 허브 또는 목적지 교통 허브는 하나 이상의 교통 허브가 선택될 수 있다. 교통 허브 경로 탐색부는 교통 정보에 포함된 구간 소요 시간 및 교통 허브 생성부로부터 수신한 교통 허브들에 대한 정보를 이용하여 교통 허브들 간의 최단 교통 허브 경로들을 탐색할 수 있다. Referring to Figs. 2A to 2D, the path search system can search for the shortest path from the source S to the destination D using the shortest transportation hub paths. The first to fourth transport hubs H1 to H7 may be generated. For example, the traffic hub generating unit can generate traffic hubs at locations such as intersections, highway tolls, and the like having high traffic. Also, the transportation hub generating unit may generate the transportation hub at different positions according to various conditions such as time, day of the week, and date. Each time the route search request signal is received from the terminal, the shortest path search unit can select the source transport hub and the destination transport hub. The first transportation hub H1 may be selected as a transportation hub from which the departure location transportation hub can reach the shortest time from the departure place S. [ The sixth transportation hub H6 and the seventh transportation hub H7 can be selected as the transportation hub that can reach the destination transportation hub from the destination D in the shortest time. One or more transport hubs may be selected as a source transport hub or a destination transport hub. The transportation hub route search unit can search for the shortest transportation hub routes among the transportation hubs by using the required travel time included in the traffic information and the information about the transportation hubs received from the transportation hub generating unit.

도 2b에 도시된 바와 같이, 교통 허브 경로 탐색부는 출발지 교통 허브로부터 목적지 교통 허브를 연결하는 탐색 교통 허브 경로를 탐색할 수 있다. 교통 허브 경로 탐색부는 최단 교통 허브 경로들을 이용하여 출발지 교통 허브로부터 목적지 교통 허브를 연결하고, 교통 허브들을 통과하는 교통 허브 경로들 중 최단 소요 시간에 상응하는 경로를 탐색 교통 허브 경로로 탐색할 수 있다.As shown in FIG. 2B, the traffic hub path search unit can search for a search traffic hub path connecting the destination traffic hub from the source traffic hub. The transportation hub route search unit may connect the destination transportation hub from the source transportation hub using the shortest transportation hub routes and search the route corresponding to the shortest required time among the transportation hub routes passing through the transportation hub to the navigation transportation hub route .

예를 들면, 교통 허브 경로 탐색부는 출발지 교통 허브인 제1 교통 허브(H1)으로부터 목적지 교통 허브인 제6 교통 허브(H6) 또는 제7 교통 허브(H7)을 연결하는 탐색 교통 허브 경로를 탐색할 수 있다. 제1 교통 허브(H1)로부터 교통 허브를 통과하여 제6 교통 허브(H6) 또는 제7 교통 허브(H7)를 연결할 수 있는 다양한 교통 허브 경로가 존재할 수 있다. 즉, 제1 교통 허브(H1) 및 제6 교통 허브(H6)를 연결하는 제1 교통 허브 경로, 제1 교통 허브(H1), 제4 교통 허브(H4), 및 제6 교통 허브(H6)을 연결하는 제2 교통 허브 경로, 제1 교통 허브(H1), 제4 교통 허브(H4), 및 제7 교통 허브(H7)을 연결하는 제3 교통 허브 경로 등이 존재할 수 있다. 이 중, 탐색 교통 허브 경로는 최단 소요 시간에 상응하는 제1 교통 허브(H1) 및 제6 교통 허브(H6)를 연결하는 제1 교통 허브 경로로 선택될 수 있다.For example, the transportation hub path search unit searches for a navigation transportation hub path connecting the sixth transportation hub H6 or the seventh transportation hub H7, which is the destination transportation hub, from the first transportation hub H1, which is the transportation hub . There may be various transportation hub paths from the first transportation hub H1 through the transportation hub to connect the sixth transportation hub H6 or the seventh transportation hub H7. A first transport hub H1, a fourth transport hub H4 and a sixth transport hub H6 for connecting the first and second transport hubs H1 and H6. A third transportation hub path connecting the first transportation hub H1, the fourth transportation hub H4, and the seventh transportation hub H7 may be present. The search transportation hub path may be selected as a first transportation hub path connecting the first and sixth transportation hubs H1 and H6 corresponding to the shortest required time.

일 실시예에서, 교통 허브 탐색부는 최단 교통 허브 경로를 탐색할 수 있다. 구체적으로, 교통 허브 탐색부는 2개의 교통 허브들을 선택하고, 2개의 교통 허브들을 연결하는 최단 교통 허브 경로를 탐색할 수 있다. 예를 들어, 교통 허브 탐색부는 제3 교통 허브(H3)와 제7 교통 허브(H7) 사이의 최단 교통 허브 경로로서, 제3 교통 허브(H3), 제1 교통 허브(H1), 제4 교통 허브(H4), 및 제7 교통 허브(H7)를 연결하는 최단 교통 허브 경로를 탐색할 수 있다. 최단 교통 허브 경로는 Dijkstra 알고리즘, Bellman-Ford 알고리즘, Floyd-Warshall 알고리즘 등과 같은 최단 경로 알고리즘을 이용하여 도출될 수 있다.In one embodiment, the traffic hub searcher may search for the shortest traffic hub path. Specifically, the traffic hub search unit selects two traffic hubs and searches for the shortest traffic hub path connecting the two traffic hubs. For example, the transportation hub search unit is the shortest transportation hub path between the third transportation hub H3 and the seventh transportation hub H7. The third transportation hub H3, the first transportation hub H1, The hub H4, and the seventh transport hub H7. The shortest transport hub path can be derived using shortest path algorithms such as the Dijkstra algorithm, the Bellman-Ford algorithm, the Floyd-Warshall algorithm, and so on.

일 실시예에서 교통 허브 탐색부는 모든 교통 허브 쌍에 대한 교통 허브 경로를 탐색하고, 교통 허브 경로 저장부에 탐색된 최단 교통 허브 경로들을 저장할 수 있다. 교통 허브 경로 탐색부는 탐색 교통 허브 경로를 탐색할 때, 교통 허브 경로 저장부에 저장된 최단 교통 허브 경로들을 이용함으로써 탐색 교통 허브 경로를 탐색할 때마다 최단 교통 허브 경로를 탐색하는 과정을 반복해서 수행할 필요가 없어질 수 있다. 예를 들어, 교통 허브 탐색부는 제3 교통 허브(H3)와 제7 교통 허브(H7) 사이의 최단 교통 허브 경로로서, 제3 교통 허브(H3), 제1 교통 허브(H1), 제4 교통 허브(H4), 및 제7 교통 허브(H7)를 연결하는 최단 교통 허브 경로를 교통 허브 경로 저장부에 저장할 수 있다. 또한 교통 허브 탐색부는 제3 교통 허브로부터 제7 교통 허브까지의 탐색 교통 허브를 탐색 시 저장된 경로를 사용할 수 있다.In one embodiment, the traffic hub search unit may search for traffic hub paths for all traffic hub pairs, and may store the shortest traffic hub paths searched in the traffic hub path storage unit. The transportation hub route search unit repeatedly searches for the shortest transportation hub route whenever searching for the navigation transportation hub route by using the shortest transportation hub routes stored in the transportation hub route storage unit when searching for the navigation transportation hub route The need can be eliminated. For example, the transportation hub search unit is the shortest transportation hub path between the third transportation hub H3 and the seventh transportation hub H7. The third transportation hub H3, the first transportation hub H1, The hub H4, and the seventh transport hub H7 may be stored in the transport hub route storage unit. Also, the traffic hub search unit can use the stored path when searching for the search transportation hub from the third traffic hub to the seventh traffic hub.

도 2c에 도시된 바와 같이, 최단 경로 탐색부는 출발지(S)로부터 교통 허브까지 최단 시간에 도달할 수 있는 제1 경로 및 교통 허브로부터 목적지(D)까지 최단 시간에 도달할 수 있는 제2 경로를 탐색할 수 있다. 만약 복수의 교통 허브가 출발지 교통 허브 또는 목적지 교통 허브로 선택되었다면 탐색 교통 허브 경로에 포함된 허브를 제1 경로 또는 제2 경로 탐색하는 기준으로 정한다. As shown in FIG. 2C, the shortest path search unit includes a first path that can reach the shortest time from the source S to the transportation hub, and a second path that can reach the shortest time from the transportation hub to the destination D Can be searched. If a plurality of transport hubs are selected as a source transport hub or a destination transport hub, the hub included in the search transport hub route is set as a reference for searching the first route or the second route.

예를 들면, 최단 경로 탐색부는 출발지(S)로부터 출발지 교통 허브(H1)을 연결하는 제1 경로 및 교통 허브(H6)로부터 목적지(D)를 연결하는 제2 경로를 탐색할 수 있다. 만약 복수의 교통 허브가 출발지 교통 허브 또는 목적지 교통 허브로 선택되었다면 탐색 교통 허브 경로에 포함된 제1 교통 허브(H1) 및 제6 교통 허브(H6)를 각각 제1 경로 및 제2 경로 탐색하는 기준으로 정한다. 즉, 도 2c에서 제6 교통 허브(H6) 및 제7 교통 허브(H7)는 둘 다 목적지 교통 허브이지만 탐색 교통 허브 경로에 포함된 제6 교통 허브(H6)를 기준으로 최단 경로 탐색부는 제2 경로를 탐색한다.For example, the shortest path search unit can search a first path connecting the departure location H1 from the source S and a second route connecting the destination D from the transportation hub H6. If a plurality of transport hubs are selected as a source transport hub or a destination transport hub, a first transport hub H1 and a sixth transport hub H6 included in the search transport hub route are respectively referred to as a first route search route and a second route search route . In other words, in FIG. 2C, the sixth and seventh transport hubs H6 and H7 are both the destination transport hubs, but the shortest route search unit is based on the sixth transport hub H6 included in the search transport hub route, Search the path.

도 2d에 도시된 바와 같이, 최단 경로 탐색부은 제1 경로, 제2 경로 및 교통 허브 경로 탐색부가 탐색한 탐색 교통 허브를 연결하여 출발지(S)로부터 목적지(D)에 도달 할 수 있는 최단 경로를 탐색할 수 있다.As shown in FIG. 2D, the shortest path search unit includes a first path, a second path, and a shortest path that can reach the destination (D) from the source S by connecting the search transport hubs Can be searched.

예를 들면, 최단 경로 탐색부는 도 2d에서 출발지(S)와 제1 교통 허브(H1), 제6 교통 허브(H6), 및 목적지(D)를 연결한 경로를 출발지(S)로부터 목적지(D)까지 도달 할 수 있는 최단 경로로서 탐색할 수 있다. For example, the shortest path search unit may route the route connecting the source S, the first transport hub H1, the sixth transport hub H6, and the destination D from the source S to the destination D ) As the shortest path that can reach.

단말기의 경로 탐색 요청부의 요청에 의해 경로 탐색이 진행될 수 있고, 경로 탐색 시스템은 탐색된 경로를 전송할 수 있다. 단말기는 탐색된 경로 데이터를 수신 하고, 단말기의 표시부에서는 탐색된 경로 데이터에 기초하여 지도와 화살표 등을 이용하여 경로를 표시하고 음성으로 경로 안내를 할 수 있다.A path search can be performed at the request of the path search request unit of the terminal, and the path search system can transmit the searched path. The terminal receives the retrieved route data, and the display unit of the terminal displays the route using the map and the arrow based on the retrieved route data, and can guide the route by voice.

전국의 도로망에 허브를 구축하고 본 발명의 실시예에 따른 경로 탐색 시스템을 사용한다면 경로 탐색 요청 시 출발지로부터 가까운 허브까지의 경로 및 허브로부터 목적지까지의 경로만 종래 기술을 이용하여 탐색하고 허브 사이는 저장된 최단 교통 허브 경로를 사용하여 경로 탐색을 하기 때문에 경로 탐색 요청 시 전구간에 걸친 구간 소요 시간을 계산하는 과정이 생략되어 경로 탐색 시간이 줄어들 수 있다. 또한 여러 대의 단말기의 경로 탐색 요청 시 반복되는 탐색 작업을 줄일 수 있다.If a hub is built in a nationwide road network and a route search system according to an embodiment of the present invention is used, only a route from a departure place to a nearby hub and a route from a hub to a destination in a route search request are searched using a conventional technique, Since the route search is performed using the stored shortest transportation hub route, the route search time can be shortened by omitting the process of calculating the time required for the entire route in the route search request. In addition, it is possible to reduce the number of search operations that are repeated when a plurality of terminals request a route search.

즉, 출발지로부터 목적지까지 전구간에 걸쳐서 구간 소요 시간을 계산하여 경로를 탐색해야 하고, 여러 대의 단말기가 동시에 경로 탐색을 요청 할 때 여러 대의 단말기가 요청하는 횟수에 상응하는 횟수만큼 전구간에 걸친 경로 탐색을 수행해야 하는 문제점이 개선 될 것이다. 결과적으로, 서버 리소스를 효율적으로 사용할 수 있고 서버 과부하 문제가 방지될 수 있다.That is, it is necessary to search the route by calculating the time required for the entire area from the origin to the destination, and when a plurality of terminals request the route search at the same time, the route search is performed by the number of times corresponding to the number of times requested by several terminals. Problems to be solved will be improved. As a result, server resources can be efficiently used and server overloading problems can be prevented.

도 3은 교통 정보가 갱신됨에 따라 도 2의 최단 경로가 변경되는 일 예를 나타내는 도면이다.3 is a diagram showing an example in which the shortest path of FIG. 2 is changed as the traffic information is updated.

도 3을 참조하면, 교통 정보를 반영하여 최단 교통 허브 경로들이 갱신됨으로써, 출발지(S)로부터 목적지(D)까지 연결하는 최단 경로가 갱신될 수 있다.Referring to FIG. 3, the shortest path connecting from the source S to the destination D can be updated by updating the shortest transportation hub routes reflecting the traffic information.

최단 교통 허브 경로 및 해당 경로의 구간 소요 시간은 기 설정된 주기마다 갱신 되어 교통 허브 경로 저장부에 저장될 수 있다. 따라서, 교통 정보에 따라 교통 허브 경로 저장부에 저장된 최단 교통 허브 경로 및 해당 경로의 구간 소요 시간은 변경될 수 있다. 예를 들어, 도 2a 내지 도 2d와 비교해 보면, 제1 교통 허브(H1)와 제2 교통 허브(H2)를 연결하는 교통 허브 간선의 구간 소요 시간은 7에서 8로 변경될 수 있다..The shortest transportation hub route and the required time period of the route may be updated every predetermined period and stored in the transportation hub route storage unit. Accordingly, the shortest transportation hub route stored in the transportation hub route storage unit and the required time duration of the route may be changed according to the traffic information. For example, in comparison with FIGS. 2A to 2D, the required time interval of the traffic hub trunk line connecting the first and second transport hubs H1 and H2 may be changed from 7 to 8.

단말기가 경로 탐색 요청 신호를 전송할 때 최단 경로 탐색부는 출발지(S) 및 목적지(D)와의 구간 소요 시간이 최단으로 소요되는 허브들을 선택할 수 있다. 도 3에서 제1 교통 허브(H1), 제6 교통 허브(H6), 및 제7 교통 허브(H7)는 선택된 교통 허브들이다. 출발지(S)로부터 최단 시간에 도달할 수 있는 제1 교통 허브(H1)는 출발지 교통 허브, 목적지로(D)부터 최단 시간에 도달할 수 있는 제6 교통 허브(H6) 및 제7 교통 허브(H7)는 목적지 교통 허브이다.When the terminal transmits the route search request signal, the shortest path search unit can select the hubs that require the shortest time required between the departure point S and the destination D. In FIG. 3, the first transport hub H1, the sixth transport hub H6, and the seventh transport hub H7 are selected transport hubs. The first transportation hub H1 that can reach the shortest time from the departure place S is a departure point transportation hub, a sixth transportation hub H6 that can reach the shortest time from the destination D and a seventh transportation hub H7) is the destination transportation hub.

교통 허브 경로 탐색부는 출발지 교통 허브(H1)으로부터 목적지 교통 허브(H6, H7)을 연결하는 탐색 교통 허브 경로를 탐색할 수 있다. 도 3의 제1 교통 허브(H1)로부터 교통 허브를 통과하여 제6 교통 허브(H6) 또는 제7 교통 허브(H7)를 연결할 수 있는 다양한 교통 허브 경로가 존재할 수 있다. 즉, 제1 교통 허브(H1) 및 제6 교통 허브(H6)를 연결하는 제1 교통 허브 경로, 제1 교통 허브(H1), 제4 교통 허브(H4), 및 제6 교통 허브(H6)을 연결하는 제2 교통 허브 경로, 제1 교통 허브(H1), 제4 교통 허브(H4), 및 제7 교통 허브(H7)을 연결하는 제3 교통 허브 경로 등이 존재할 수 있다. 이 중, 탐색 교통 허브 경로는 최단 소요 시간에 상응하는 제1 교통 허브(H1), 제4 교통 허브(H4) 및 제7 교통 허브(H7)를 연결하는 제3 교통 허브 경로로 선택될 수 있다.The transportation hub route search unit can search for the navigation transportation hub route connecting the destination transportation hubs H6 and H7 from the source transportation hub H1. There may be various transportation hub paths through which the sixth or seventh transportation hub H7 can be connected from the first transportation hub H1 of FIG. 3 through the transportation hub. A first transport hub H1, a fourth transport hub H4 and a sixth transport hub H6 for connecting the first and second transport hubs H1 and H6. A third transportation hub path connecting the first transportation hub H1, the fourth transportation hub H4, and the seventh transportation hub H7 may be present. The search transportation hub path may be selected as a third transportation hub path connecting the first, fourth, and seventh transportation hubs H1, H4, and H7 corresponding to the shortest required time .

최단 경로 탐색부는 출발지(S)로부터 출발지 교통 허브인 제1 교통 허브(H1)을 연결하는 제1 경로 및 목적지(D)로부터 목적지 교통 허브인 제7 교통 허브(H7)을 연결하는 제2 경로를 탐색할 수 있다. 도 3에서 제6 교통 허브(H6) 및 제7 교통 허브(H7) 둘 다 목적지 교통 허브이지만 탐색 교통 허브 경로에 포함된 제7 교통 허브(H7)를 기준으로 최단 경로 탐색부는 제2 경로를 탐색한다.The shortest path search unit searches the first route connecting the first transportation hub H1 as the departure location transportation hub and the second route connecting the seventh transportation hub H7 as the destination transportation hub from the destination D Can be searched. In FIG. 3, the sixth and seventh transport hubs H6 and H7 are both the destination transport hubs. However, the seventh transport hub H7 included in the search transport hub route is referred to as the shortest route search unit, do.

최단 경로 탐색부는 도 3에서 출발지(S)와 제1 교통 허브(H1), 제4 교통 허브(H4), 제7 교통 허브(H7), 및 목적지(D)를 연결한 경로를 출발지(S)부터 목적지(D)에 도달 할 수 있는 최단 경로로서 탐색할 수 있다. The shortest path search unit is a route S connecting the source S, the first transport hub H1, the fourth transport hub H4, the seventh transport hub H7, and the destination D as a source S, As the shortest path that can reach the destination D.

따라서, 경로 탐색 시스템을 사용하면, 교통 정보가 변경 되더라도 변경된 교통정보에 상응하여 출발지(S)로부터 목적지(D)까지 최단 시간이 소요되는 경로가 탐색될 수 있다. 또한, 경로 탐색 시스템은 경로 탐색의 시간을 줄이고, 서버 과부하를 방지할 수 있다.Therefore, even if the traffic information is changed, the route searching system can search the route that takes the shortest time from the source S to the destination D in accordance with the changed traffic information. In addition, the path search system can reduce the time of path search and prevent server overload.

도 4는 본 발명의 다른 실시예들에 따른 경로 탐색 시스템을 나타내는 블록도이다.4 is a block diagram illustrating a path search system in accordance with another embodiment of the present invention.

도 4를 참조하면, 경로 탐색 서버(100B)은 교통 허브 생성부(110), 교통 허브 경로 탐색부(120), 교통 허브 경로 저장부(130), 최단 경로 탐색부(140), 및 교통 정보 저장부(150)를 포함할 수 있다. 다만, 본 실시예에 따른 경로 탐색 서버(100B)은 교통 정보 저장부(150)가 추가된 것을 제외하면, 도 1의 경로 탐색 서버와 실질적으로 동일하므로, 동일 또는 유사한 구성 요소에 대해서는 동일한 참조 번호를 사용하고, 중복되는 설명은 생략하기로 한다. 4, the route search server 100B includes a traffic hub generating unit 110, a traffic hub path searching unit 120, a traffic hub path storing unit 130, a shortest path searching unit 140, And may include a storage unit 150. However, since the route search server 100B according to the present embodiment is substantially the same as the route search server of FIG. 1 except that the traffic information storage unit 150 is added, And a duplicate description will be omitted.

교통 정보 저장부(150)에는 교통 정보를 누적한 누적 교통 정보가 저장될 수 있다. 저장된 누적 교통 정보는 다양한 방식으로 분석 될 수 있다. 평일과 주말 및 공휴일을 나눠서 분석할 수도 있고 요일 별로 나눠서 분석할 수도 있다. 나아가 시간 별로 나눠서 분석할 수도 있다. 또한, 다양한 분석 방법을 병합하여 누적 교통 정보를 분석할 수 있다. 저장된 누적 교통 정보를 분석한 결과는 교통 허브 생성부(110)에서 교통 허브 생성 시 활용될 수 있다. The traffic information storage unit 150 may store accumulated traffic information that accumulates traffic information. The stored cumulative traffic information can be analyzed in various ways. Weekdays, weekends, and holidays can be divided into two parts. It can also be analyzed by time division. In addition, cumulative traffic information can be analyzed by merging various analysis methods. The result of analyzing the stored cumulative traffic information can be utilized when the transportation hub is generated in the transportation hub generating unit 110.

예를 들면, 5년 간의 누적된 교통 정보를 바탕으로 피서객이 가장 몰리는 날짜와 장소를 예측할 수 있고, 예측된 날짜와 장소를 기준으로 교통 허브를 생성할 수 있다.For example, based on the accumulated traffic information for five years, it is possible to predict the date and place where the visitor is most likely to be driven, and to create a transportation hub based on the predicted date and place.

생성된 교통 허브를 이용하여 출발지로부터 목적지까지의 경로를 탐색하는 과정은 도 1를 참조로 설명한 구성들이 출발지부터 목적지까지의 경로를 탐색하는 과정과 실질적으로 동일하거나 유사하므로 생략하겠다. The process of searching for the route from the origin to the destination using the generated transportation hub will be omitted because the configurations described with reference to FIG. 1 are substantially the same or similar to the process of searching for the route from the origin to the destination.

이와 같은 교통 허브 시스템을 이용하면, 누적 교통 정보를 고려하여 교통 허브를 생성하기 때문에 현대인들의 변화하는 라이프 스타일에 맞추어 교통 허브를 생성하는 것이 가능해진다.Using such a transportation hub system, a transportation hub is created in consideration of cumulative traffic information, thereby making it possible to create a transportation hub according to a changing lifestyle of modern people.

도 5는 본 발명의 실시예들에 따른 경로 탐색 방법을 나타내는 순서도이다.5 is a flowchart illustrating a path search method according to embodiments of the present invention.

도 5를 참조하면, 일 실시예에서 경로 탐색을 위한 복수의 교통 허브들이 생성(S110)되는 단계, 출발지 교통 허브 및 목적지 교통 허브가 선택(S120)되는 단계, 탐색 교통 허브 경로가 탐색(S130)되는 단계, 출발지 교통 허브 및 목적지 교통 허브에 기초하여 각각 제1경로 및 제2경로가 탐색(S140)되는 단계, 및 제1 경로, 탐색 교통 허브 경로, 제2 경로를 연결함으로써, 출발지로부터 목적지까지의 최단 경로가 탐색(S150)되는 단계를 포함할 수 있다.Referring to FIG. 5, in one embodiment, a plurality of transport hubs for route search are created S110, a source transport hub and a destination transport hub are selected S120, a search transport hub path is selected S130, (S140) a first route and a second route, respectively, based on a source transport hub and a destination transport hub, and connecting a first route, a search transport hub route, and a second route, (S150).

경로 탐색을 위한 복수의 교통 허브들이 생성(S110)될 수 있다. 예를 들면, 교통 허브들은 교통량이 많은 교차로 또는 고속도로 톨게이트 등의 위치에 생성될 수 있다. 즉, 교통 허브들은 주말에는 시외지역 관광지에 생성되고, 평일 출퇴근 시간에는 공단 진입 및 출입 교차로에 교통 허브들을 생성 되는 등 다양한 기준으로 시간과 요일별 교통 허브가 생성될 수 있다.A plurality of transportation hubs for path search may be created (S110). For example, transportation hubs can be created at locations such as highway intersections or highway tolls. In other words, transportation hubs are created at sightseeing areas in the suburbs on weekends, and transportation hubs are created on the basis of various criteria such as entry and exit intersections during the weekday commute, and a transportation hub for each hour and day.

출발지 교통 허브 및 목적지 교통 허브가 선택(S120)될 수 있다. 단말기가 경로 탐색 요청 신호를 전송할 때 최단 경로 탐색부는 출발지 및 목적지와의 구간 소요 시간이 최단으로 소요되는 교통 허브들이 선택될 수 있다. 출발지로부터 최단 시간에 도달할 수 있는 교통 허브는 출발지 교통 허브, 목적지로부터 최단 시간에 도달할 수 있는 교통 허브는 목적지 교통 허브이다. 출발지 교통 허브 및 목적지 교통 허브는 하나의 교통 허브가 선택될 수 있고 복수의 교통 허브가 선택될 수도 있다.The source transport hub and the destination transport hub may be selected (S120). When the terminal transmits a route search request signal, the shortest route search unit may select the transportation hubs that require the shortest time required between the source and destination. The transportation hub that can reach the shortest time from the departure point is the departure transportation hub, and the transportation hub that can reach the shortest time from the destination is the destination transportation hub. The originating transport hub and the destination transport hub may be selected as one transport hub and a plurality of transport hubs may be selected.

교통 허브들을 통과하고 출발지 교통 허브로부터 목적지 교통 허브를 연결하는 교통 허브 경로들 중 최단 소요 시간에 상응하는 탐색 교통 허브 경로가 탐색(S130)될 수 있다.The search transportation hub path corresponding to the shortest time among the transportation hub paths that pass through the transportation hubs and connect the destination transportation hub from the source transportation hub may be searched (S130).

최단 교통 허브 경로들은 2개의 교통 허브들을 선택하고, 2개의 교통 허브들을 연결함으로써 탐색될 수 있다. 예를 들어, 도 3에서 최단 교통 허브 경로는 제3 교통 허브(H3)와 제7 교통 허브(H7) 사이의 최단 교통 허브 경로로서, 제3 교통 허브(H3), 제1 교통 허브(H1), 제4 교통 허브(H4), 및 제7 교통 허브(H7)를 연결함으로써 탐색될 수 있다. 최단 교통 허브 경로는 Dijkstra 알고리즘, Bellman-Ford 알고리즘, Floyd-Warshall 알고리즘 등과 같은 최단 경로 알고리즘을 이용하여 도출될 수 있다.The shortest transport hub routes can be searched by selecting two transport hubs and connecting the two transport hubs. 3, the shortest transportation hub path is a shortest transportation hub path between the third transportation hub H3 and the seventh transportation hub H7, and includes a third transportation hub H3, a first transportation hub H1, The fourth transportation hub H4, and the seventh transportation hub H7. The shortest transport hub path can be derived using shortest path algorithms such as the Dijkstra algorithm, the Bellman-Ford algorithm, the Floyd-Warshall algorithm, and so on.

일 실시예에서, 모든 교통 허브 쌍에 대한 교통 허브 경로들이 탐색되고, 교통 허브 경로 저장부에 탐색된 최단 교통 허브 경로들이 저장될 수 있다. 탐색 교통 허브 경로을 탐색하기 위해, 교통 허브 경로 저장부에 저장된 최단 교통 허브 경로들을 이용함으로써 탐색 교통 허브 경로를 탐색 요청 시마다 최단 교통 허브 경로를 탐색하는 과정을 반복해서 수행할 필요가 없어질 수 있다. 예를 들어, 도 3에서 제3 교통 허브(H3)와 제7 교통 허브(H7) 사이의 최단 교통 허브 경로는 제3 교통 허브(H3), 제1 교통 허브(H1), 제4 교통 허브(H4), 및 제7 교통 허브(H7)를 연결하는 최단 교통 허브 경로를 교통 허브 경로 저장부에 저장할 수 있다. 또한, 교통 허브 탐색부는 제3 교통 허브로부터 제7 교통 허브까지의 탐색 교통 허브를 탐색 시 저장된 경로를 사용할 수 있다.In one embodiment, the transport hub paths for all transport hub pairs are searched, and the shortest transport hub paths searched in the transport hub path store may be stored. It is possible to eliminate the need to repeatedly search for the shortest transportation hub path for each search request of the search traffic hub path by using the shortest transportation hub paths stored in the transportation hub path storage for searching the search traffic hub path. For example, in FIG. 3, the shortest transportation hub path between the third transportation hub H3 and the seventh transportation hub H7 includes a third transportation hub H3, a first transportation hub H1, a fourth transportation hub H4) and the seventh transport hub H7 may be stored in the transport hub route storage unit. In addition, the traffic hub search unit can use the stored path when searching for the search traffic hub from the third traffic hub to the seventh traffic hub.

출발지로부터 교통 허브까지 최단 시간에 도달할 수 있는 제1 경로 및 교통 허브로부터 목적지까지 최단 시간에 도달할 수 있는 제2 경로가 탐색(S140)될 수 있다. 만약 복수의 교통 허브가 출발지 교통 허브 또는 목적지 교통 허브로 선택되었다면 탐색 교통 허브 경로에 포함된 허브를 제1 경로 또는 제2 경로 탐색하는 기준으로 정한다.A first path that can reach the shortest time from the source to the transportation hub and a second path that can reach the shortest time from the transportation hub to the destination can be searched S140. If a plurality of transport hubs are selected as a source transport hub or a destination transport hub, the hub included in the search transport hub route is set as a reference for searching the first route or the second route.

마지막으로, 제1 경로, 제2 경로 및 교통 허브 경로 탐색부가 탐색한 탐색 교통 허브를 연결하여 출발지부터 목적지에 도달할 수 있는 최단 경로가 탐색(S150)될 수 있다.Finally, the first path, the second path, and the shortest path that can reach the destination from the start point of the search can be searched (S150) by connecting the search transport hub that the search is made by the transport hub route search section.

일 실시예에서, 교통 허브들은 기 지정된 주기마다 갱신될 수 있다. 교통 허브의 위치정보를 기 지정된 주기 마다 갱신함으로써 교통 허브 경로 탐색부 및 최단 경로 탐색부가 탐색 작업 수행 시 사용하는 정보를 기 지정된 주기마다 갱신 할 수 있다. 나아가 최단 경로 탐색부는 갱신된 교통 허브를 고려한 제1 경로 및 제2 경로를 탐색할 수 있고, 교통 허브 경로 탐색부는 갱신 된 교통 허브를 고려한 탐색 교통 허브 경로를 탐색 할 수 있다. 결과적으로 최단 경로 탐색부은 기 지정된 주기마다 갱신된 정보를 바탕으로 출발지로부터 목적지까지의 최단 경로를 탐색할 수 있다.In one embodiment, the transport hubs may be updated at predefined intervals. The location information of the transportation hub is updated every predetermined period so that the information used in performing the search operation by the traffic hub path searching unit and the shortest path searching unit can be updated every predetermined period. Further, the shortest path search unit can search the first path and the second path considering the updated traffic hub, and the traffic hub path search unit can search the search traffic hub path considering the updated traffic hub. As a result, the shortest path search unit can search for the shortest path from the source to the destination based on the information updated every predetermined period.

이와 같은 방식의 경로 탐색 시스템을 사용하면, 경로 탐색 요청 시 출발지로부터 가까운 허브까지의 경로 및 허브로부터 목적지까지의 경로만 종래 기술을 이용하여 탐색하고 허브 사이는 저장된 최단 교통 허브 경로를 사용하여 경로 탐색을 하기 때문에 경로 탐색 요청 시 전구간에 걸친 구간 소요 시간을 계산하는 과정이 생략되어 경로 탐색 시간이 줄어들 수 있다. 또한, 복수의 단말기들로부터 발생하는 경로 탐색 요청에 대해 반복되는 탐색 작업을 줄임으로써 서버 리소스를 효율적으로 사용할 수 있고 서버 과부하 문제가 방지 될 수 있다.When a route search system of this type is used, only the route from the origin to the nearest hub and the route from the hub to the destination are searched using the conventional technology, and between the hubs, Therefore, the path search time can be reduced by omitting the process of calculating the time required for the entire route in the route search request. In addition, server resources can be efficiently used and server overloading problems can be prevented by reducing the number of repeated search operations for route search requests generated from a plurality of terminals.

본 발명은 교통 허브를 이용한 경로 탐색 시스템 또는 경로 탐색 방법을 구비한 전자 기기에 다양하게 적용될 수 있다. 예를 들어, 본 발명은 네비게이션 장치 등에 적용될 수 있다.The present invention can be applied variously to an electronic device having a route search system or a route search method using a transportation hub. For example, the present invention can be applied to a navigation device or the like.

상기에서는 본 발명의 실시예들을 참조하여 설명하였지만, 해당 기술분야에서 통상의 지식을 가진 자는 하기의 특허청구범위에 기재된 본 발명의 사상 및 영역으로부터 벗어나지 않는 범위 내에서 본 발명을 다양하게 수정 및 변경시킬 수 있음을 이해할 것이다.While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those skilled in the art that various changes and modifications may be made therein without departing from the spirit and scope of the invention as defined in the appended claims. You will understand.

110: 교통 허브 생성부
120: 교통 허브 경로 탐색부
130: 교통 허브 경로 저장부
140: 최단 경로 탐색부
150: 교통 허브 경로 저장부
100A: 경로 탐색 서버
100B: 경로 탐색 서버
200: 단말기110: Traffic hub generating unit
120: Traffic hub path search section
130: Transport hub route storage unit
140: Shortest path search section
150: Transport hub route storage unit
100A: path search server
100B: Path search server
200: terminal

Claims

A traffic hub generating unit for generating a plurality of traffic hubs for path search;
A traffic hub path search unit searching for the shortest traffic hub paths corresponding to the shortest required time among the traffic hub paths connecting traffic hubs through traffic hub trunks using traffic information; And
And a shortest path search unit searching for a shortest path from the source to the destination using the shortest transportation hub paths.

The method as claimed in claim 1, wherein the shortest path search unit uses the traffic information to determine a start time of the start time from the start point to the transportation hubs, A first route for connecting the departure location transportation hub from the departure location and a second route for connecting the destination transportation hub from the destination are selected by selecting a destination transportation hub corresponding to the shortest time among the times, Path search system.

3. The route search system according to claim 2, wherein the traffic hub path search unit searches for a search traffic hub path connecting the destination traffic hub from the source traffic hub.

4. The route search system according to claim 3, wherein the shortest path search unit searches for the shortest path from the source to the destination by connecting the first route, the search transportation hub route, and the second route, .

The method according to claim 1,
Further comprising: a transportation hub path storing unit in which the shortest transportation hub paths are stored,
Wherein the traffic hub path searching unit stores the shortest traffic hub paths in the traffic hub path storing unit.

The route search system according to claim 1, wherein the traffic hub path search unit updates the shortest traffic hub paths at predetermined intervals.

The system of claim 1, wherein the traffic hub generator updates the traffic hubs at predetermined intervals.

The method according to claim 1,
Further comprising: a traffic information storage unit in which the traffic information is cumulatively stored,
Wherein the traffic hub generating unit generates the traffic hubs based on the traffic information stored in the traffic information storage unit.

Generating a plurality of transport hubs for path search;
The destination transportation hub corresponding to the shortest time required from the departure point to the transportation hubs using the traffic information, and the destination transportation hub corresponding to the shortest time required from the destination to the transportation hubs ;
Searching for a search transportation hub path corresponding to the shortest required time among the transportation hub routes connecting the destination transportation hub from the source transportation hub through the transportation hub trunks using the traffic information; And
And searching for a shortest path from the source to the destination using the search transportation hub path.

10. The method of claim 9, wherein the step of searching for the shortest path
Searching for a first route connecting the departure location transportation hub from the departure location and searching for a second route connecting the destination transportation hub from the destination; And
Searching the shortest path from the source to the destination by connecting the first route, the search transportation hub route, and the second route.

The method of claim 9, wherein the traffic hubs are updated every predetermined period.