KR20050014477A - System for route searching of car and method thereof - Google Patents
System for route searching of car and method thereofInfo
- Publication number
- KR20050014477A KR20050014477A KR1020030053123A KR20030053123A KR20050014477A KR 20050014477 A KR20050014477 A KR 20050014477A KR 1020030053123 A KR1020030053123 A KR 1020030053123A KR 20030053123 A KR20030053123 A KR 20030053123A KR 20050014477 A KR20050014477 A KR 20050014477A
- Authority
- KR
- South Korea
- Prior art keywords
- path
- route
- optimal
- destination
- link
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Ceased
Links
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G01C21/3407—Route searching; Route guidance specially adapted for specific applications
- G01C21/343—Calculating itineraries
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G01C21/3453—Special cost functions, i.e. other than distance or default speed limit of road segments
- G01C21/3492—Special cost functions, i.e. other than distance or default speed limit of road segments employing speed data or traffic data, e.g. real-time or historical
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
- G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
-
- G—PHYSICS
- G08—SIGNALLING
- G08G—TRAFFIC CONTROL SYSTEMS
- G08G1/00—Traffic control systems for road vehicles
- G08G1/09—Arrangements for giving variable traffic instructions
- G08G1/0962—Arrangements for giving variable traffic instructions having an indicator mounted inside the vehicle, e.g. giving voice messages
- G08G1/0968—Systems involving transmission of navigation instructions to the vehicle
- G08G1/096805—Systems involving transmission of navigation instructions to the vehicle where the transmitted instructions are used to compute a route
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Navigation (AREA)
Abstract
Description
본 발명은 차량의 경로 탐색 시스템 및 그 방법에 관한 것으로, 특히 출발지 링크와 목적지 링크를 이용한 차량의 경로 탐색 시스템 및 그 방법에 관한 것이다.The present invention relates to a vehicle route search system and method, and more particularly, to a vehicle route search system and method using a source link and a destination link.
차량의 경로 탐색은 출발지와 목적지를 설정하고, 이와 관련된 교통정보 등을 이용하여 최적 경로를 탐색하는 것으로, 출발지 링크와 목적지 링크를 미리 설정하여 탐색한다.The route search of the vehicle is to set a starting point and a destination, and to search for an optimal path using traffic information and the like, and to set a starting link and a destination link in advance.
도 1은 일반적인 차량의 경로 탐색 시스템에서의 경로 탐색 순서를 나타낸 것이다.1 illustrates a path search sequence in a path search system of a general vehicle.
도 1에 도시된 바와 같이, 경로 요청자(이하 운전자라고 함)가 무선 단말이나 차량 네비게이션(Navigation) 등을 통하여 경로 탐색을 요청하고(S100), 출발지 링크와 목적지 링크 및 탐색 조건을 설정하면(S110~S120), 설정된 조건에 맞는 최적 경로를 탐색하여 탐색된 경로를 운전자의 단말기로 제공한다(S130~S140).As illustrated in FIG. 1, when a route requester (hereinafter referred to as a driver) requests a route search through a wireless terminal or a vehicle navigation (S100), and sets a source link, a destination link, and a search condition (S110). S120), the system searches for an optimal route meeting the set condition and provides the found route to the driver's terminal (S130 to S140).
그런데 이러한 종래의 경로 탐색 방법은 목적지 링크가 설정된 상태에서 경로를 탐색하므로, 목적지 주변에 존재하는 교차로, 인터체인지(IC), 분기점(JC) 등의 목적지 접근 링크에 따라 최적 경로가 달라지는 것을 반영하지 못할 뿐만 아니라, 출발지 링크에서 목적지 링크로 가기 위해 목적지 주변에서 크게 우회하는 경로 탐색이 이루어지기도 한다.However, since the conventional route search method searches for a route in a state where a destination link is set, it cannot reflect that the optimum route varies depending on a destination access link such as an intersection, an interchange (IC), a branch point (JC), and the like that exist near the destination. In addition, a route search is made that greatly detours around the destination to get from the source link to the destination link.
본 발명은 이와 같은 문제점을 해결하기 위한 것으로, 본 발명이 이루고자 하는 기술적 과제는 목적지 주변의 링크를 목적지 후보 링크로 설정하여 목적지 주변에서 우회하지 않는 최적 경로를 탐색하기 위한 차량의 경로 탐색 시스템 및 그 방법을 제공하는 것이다.The present invention is to solve such a problem, the technical problem to be achieved by the present invention is to set the link around the destination as a destination candidate link to search for the optimal route that does not detour around the destination of the vehicle and its To provide a way.
도 1은 일반적인 차량의 경로 탐색 시스템에서의 경로 탐색 순서를 나타낸 도이다.1 is a diagram illustrating a path search order in a general path search system of a vehicle.
도 2는 본 발명의 실시예에 따른 차량의 경로 탐색 시스템의 구성을 나타낸 도이다.2 is a diagram illustrating a configuration of a route search system for a vehicle according to an exemplary embodiment of the present invention.
도 3은 본 발명의 실시예에 따른 차량의 경로 탐색 시스템의 동작 순서를 나타낸 도이다.3 is a view showing an operation sequence of the route search system of a vehicle according to an embodiment of the present invention.
도 4a 내지 도 4d는 본 발명의 실시예에 따른 차량의 경로 탐색 시스템에서 최적 경로를 탐색하는 과정을 순차적으로 나타낸 도이다.4A through 4D are diagrams sequentially illustrating a process of searching for an optimal route in a vehicle route searching system according to an exemplary embodiment of the present invention.
상기한 바와 같은 목적을 실현하기 위한 본 발명의 특징에 따른 차량의 경로 탐색 시스템은, 소정 시간 간격으로 교통 상황에 대한 제반 교통정보를 수집하는교통정보 수집부; 상기 교통정보 수집부에서 수집된 교통정보를 경로탐색에 적합한 데이터 형태로 변환하는 교통정보 처리부; 경로 요청자의 무선단말을 통하여 전송된 목적지 정보를 바탕으로 목적지 후보링크를 설정하고, 상기 목적지 후보링크와 상기 교통정보 처리부에서 전송되는 교통정보를 지도 정보에 반영하여 출발지와 목적지간의 최적경로를 탐색하는 경로탐색 엔진부; 및 상기 경로 요청자의 무선단말과 무선망을 통하여 통신하면서 상기 경로 요청자의 경로 탐색 요청을 접수하여 상기 경로탐색 엔진부로 전송하고, 상기 경로탐색 엔진부로부터 전송되는 상기 최적경로를 상기 경로 요청자의 무선단말로 전송하는 경로처리부를 포함한다.According to an aspect of the present invention, there is provided a route search system for a vehicle, the traffic information collecting unit collecting various traffic information on a traffic situation at predetermined time intervals; A traffic information processing unit converting the traffic information collected by the traffic information collecting unit into a data form suitable for route search; Setting a destination candidate link based on the destination information transmitted through the wireless terminal of the route requester, and searching for an optimal route between the starting point and the destination by reflecting the destination candidate link and the traffic information transmitted from the traffic information processing unit on the map information. Path search engine unit; And receiving the path search request of the path requester while communicating with the wireless terminal of the path requester through a wireless network, transmitting the path request to the path search engine unit, and transmitting the optimum path transmitted from the path search engine unit to the path terminal. It includes a route processing unit for transmitting to.
이때, 상기 경로탐색 엔진부는,At this time, the path search engine unit,
상기 경로 요청자의 무선단말을 통하여 전송된 목적지 정보를 바탕으로 목적지 후보링크를 설정하는 목적지 후보 설정부; 및 상기 목적지 후보링크와 상기 교통정보 처리부에서 전송되는 교통정보를 지도 정보에 반영하여 출발지와 목적지간의 최적경로를 탐색하는 최적경로 탐색부를 포함한다.A destination candidate setting unit for setting a destination candidate link based on destination information transmitted through the radio terminal of the route requester; And an optimum path search unit for searching for an optimal path between a starting point and a destination by reflecting the destination candidate link and the traffic information transmitted from the traffic information processing unit to map information.
상기 목적지 후보 설정부는,The destination candidate setting unit,
상기 경로 요청자의 무선단말을 통하여 전송된 목적지로부터 소정 범위 내에 포함되는 링크를 목적지 후보링크로 설정한다.A link included in a predetermined range from a destination transmitted through the radio terminal of the route requester is set as a destination candidate link.
상기 경로처리부는,The route processing unit,
상기 경로 요청자의 무선단말로부터 출발지 링크 정보, 목적지 정보 및 최적경로 결정 기준 옵션 정보를 전송받으며,Source link information, destination information, and optimal route determination criteria option information are received from the radio terminal of the route requester;
상기 경로탐색 엔진부는,The path search engine unit,
상기 출발지 링크로부터 상기 목적지 후보링크까지의 최적후보 경로를 탐색한 후, 상기 최적경로 결정 기준 옵션 정보를 바탕으로 상기 최적후보 경로 중 최적 경로를 결정한다.After searching for the optimal candidate path from the source link to the destination candidate link, the optimal path among the optimal candidate paths is determined based on the optimal path determining criteria option information.
또한, 본 발명의 특징에 따른 차량의 경로 탐색 방법은, a) 무선망을 통하여 접속한 경로 요청자의 무선단말로부터 출발지 링크와 목적지간의 경로 탐색 요청을 접수하는 단계; b) 상기 목적지 정보를 바탕으로 목적지 후보링크를 설정하고, 현재 교통상황에 대하여 수집, 가공한 교통정보를 지도 정보에 반영하여 상기 출발지 링크와 목적지 후보링크간의 최적 경로를 도출하는 단계; 및 c) 상기 도출된 최적경로를 무선망을 통해 상기 경로 요청자의 무선단말로 제공하는 단계를 포함한다.In addition, the route search method of the vehicle according to an aspect of the present invention, a) receiving a route search request between the source link and the destination from the radio terminal of the route requester connected via the wireless network; b) establishing a destination candidate link based on the destination information, and deriving an optimal path between the source link and the destination candidate link by reflecting the traffic information collected and processed for the current traffic situation on the map information; And c) providing the derived optimal path to a wireless terminal of the path requester through a wireless network.
상기 b) 단계에서, 상기 목적지로부터 소정 범위 내에 포함되는 링크를 목적지 후보링크로 설정한다.In step b), a link included in a predetermined range from the destination is set as a destination candidate link.
또한, 상기 a) 단계에서, 상기 경로 요청자의 무선단말로부터 최적경로 결정 기준 옵션 정보를 더 전송받으며,Further, in the step a), the optimal path determination criteria option information is further transmitted from the radio terminal of the path requester.
상기 b) 단계에서, 상기 출발지 링크로부터 상기 목적지 후보링크까지의 최적후보 경로를 탐색한 후, 상기 최적경로 결정 기준 옵션 정보를 바탕으로 상기 최적후보 경로 중 최적 경로를 결정한다.In step b), after searching for an optimal candidate path from the source link to the destination candidate link, the optimal path among the optimal candidate paths is determined based on the optimal path determination reference option information.
이때, 상기 최적경로 결정 기준 옵션은 최단옵션 또는 최적옵션이고,At this time, the optimal path determination reference option is the shortest option or the best option,
상기 b) 단계에서, 상기 최적경로 결정 기준 옵션이 최단옵션이면 상기 최적후보 경로 중 주행거리가 가장 짧은 경로를 최적 경로로 결정하고, 상기 최적경로 결정 기준 옵션이 최적옵션이면 최단경로(Dijkstra) 알고리즘을 적용하여 상기 최적후보 경로 중 코스트가 가장 작은 경로를 최적 경로를 결정한다.In the step b), if the optimal route determination criterion option is the shortest option, the route having the shortest driving distance among the optimal candidate routes is determined as the optimal route, and if the optimal route determination criterion option is the optimal option, the Dijkstra algorithm The optimal path is determined by the path having the smallest cost among the optimal candidate paths.
아래에서는 첨부한 도면을 참고로 하여 본 발명의 실시예에 대하여 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 상세히 설명한다. 그러나 본 발명은 여러 가지 상이한 형태로 구현될 수 있으며 여기에서 설명하는 실시예에 한정되지 않는다. 도면에서 본 발명을 명확하게 설명하기 위해서 설명과 관계없는 부분은 생략하였다. 명세서 전체를 통하여 유사한 부분에 대해서는 동일한 도면 부호를 붙였다.DETAILED DESCRIPTION Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings so that those skilled in the art may easily implement the present invention. As those skilled in the art would realize, the described embodiments may be modified in various different ways, all without departing from the spirit or scope of the present invention. In the drawings, parts irrelevant to the description are omitted in order to clearly describe the present invention. Like parts are designated by like reference numerals throughout the specification.
먼저, 본 발명의 실시예에 따른 차량의 경로 탐색 시스템에 대하여 도 2를 참고로 하여 상세하게 설명한다.First, a path search system for a vehicle according to an exemplary embodiment of the present invention will be described in detail with reference to FIG. 2.
도 2는 본 발명의 실시예에 따른 차량의 경로 탐색 시스템의 구성을 도시한 것이다.2 is a block diagram of a vehicle route search system according to an exemplary embodiment of the present invention.
도 2에 나타낸 바와 같이, 본 발명의 실시예에 따른 차량의 경로 탐색 시스템은 운전자의 무선단말(100)과 무선망(200)을 통하여 무선단말(100)과 연결되며 무선단말(100)로부터의 경로 검색 요청을 접수하여 경로 탐색을 수행하는 교통정보를 제공하는 교통센터(300)를 포함한다.As shown in FIG. 2, a vehicle route search system according to an exemplary embodiment of the present invention is connected to a wireless terminal 100 through a wireless terminal 100 and a wireless network 200 of a driver and is provided from the wireless terminal 100. It includes a traffic center 300 that receives the route search request and provides traffic information for performing a route search.
이때, 교통센터(300)는 교통정보 수집부(310), 교통정보 처리부(320), 경로탐색 엔진부(330) 및 경로처리부(340)를 포함한다.In this case, the traffic center 300 includes a traffic information collecting unit 310, a traffic information processing unit 320, a path search engine unit 330, and a path processing unit 340.
교통정보 수집부(310)는 영상 검지기나 프로브 카(probe car) 등의 교통국이나 교통감시 장치들을 이용하여 현재 교통 상황에 대한 제반 교통정보들을 수집한다.The traffic information collecting unit 310 collects all traffic information on the current traffic situation by using a traffic station or a traffic monitoring device such as an image detector or a probe car.
교통정보 처리부(320)는 교통정보 수집부(310)에서 수집된 교통정보들 중에서 경로탐색을 위해 필요한 정보만을 추출하고, 이 정보들을 경로 탐색에 적합하도록 데이터 처리하여 경로탐색 엔진부(330)로 전송한다.The traffic information processor 320 extracts only information necessary for the path search from the traffic information collected by the traffic information collector 310, processes the information to be suitable for the path search, and passes the data to the path search engine unit 330. send.
경로탐색 엔진부(330)는 경로 탐색 알고리즘을 적용하여 경로를 탐색하는 부분으로, 목적지 후보 설정부(331)와 최적경로 탐색부(332)를 포함한다. 목적지 후보 설정부(331)는 목적지로부터 소정 범위 내에 포함되는 링크를 목적지 후보링크로 선택하며, 최적경로 탐색부(332)는 목적지 후보 설정부(331)에서 선택된 목적지 후보링크 정보와 교통정보 처리부(320)에서 전송되는 현재 교통정보들을 지도정보에 반영하여 경로를 탐색한다.The path search engine unit 330 searches for a path by applying a path search algorithm, and includes a destination candidate setting unit 331 and an optimum path search unit 332. The destination candidate setting unit 331 selects a link included in a predetermined range from the destination as the destination candidate link, and the optimum path search unit 332 may select the destination candidate link information and the traffic information processing unit selected by the destination candidate setting unit 331. The route is searched by reflecting the current traffic information transmitted from 320 in the map information.
경로처리부(340)는 경로탐색 엔진부(330)에서 탐색한 경로를 무선단말(100)로 전송하고, 무선단말(100)과 교통센터(300)간의 송수신 데이터를 처리한다.The route processing unit 340 transmits the route searched by the route search engine unit 330 to the wireless terminal 100 and processes transmission / reception data between the wireless terminal 100 and the traffic center 300.
다음, 도 3 및 도 4를 참조하여 본 발명의 실시예에 따른 차량의 경로 탐색 시스템의 동작에 대하여 자세하게 설명한다.Next, the operation of the route search system of the vehicle according to the exemplary embodiment of the present invention will be described in detail with reference to FIGS. 3 and 4.
도 3은 본 발명의 실시예에 따른 차량의 경로 탐색 시스템의 동작 순서를 나타낸 도이다.3 is a view showing an operation sequence of the route search system of a vehicle according to an embodiment of the present invention.
도 3에 도시된 바와 같이, 운전자가 무선단말(100)을 이용하여 무선망(200)을 통해 교통센터(300)에 접속하여 출발지 링크와 목적지를 설정한 후 경로 탐색을 요청하면, 교통센터(300)의 경로처리부(340)는 무선단말(100)로부터 전송되는 출발지 링크와 목적지 정보를 수신하여 경로탐색 엔진부(330)로 전송한다.(S300~S310)As shown in FIG. 3, when the driver accesses the traffic center 300 through the wireless network 200 using the wireless terminal 100, sets a starting link and a destination, and requests a route search, the traffic center ( The route processing unit 340 of 300 receives the source link and the destination information transmitted from the wireless terminal 100 and transmits the received link and the destination information to the route search engine 330. (S300 to S310).
경로탐색 엔진부(330)의 목적지 후보 설정부(331)는 무선단말(100)로부터 수신한 목적지 정보를 바탕으로 목적지로부터 소정 범위 내에 포함된 링크를 목적지 후보링크로 설정하고, 이렇게 설정된 목적지 후보 링크를 출발지 링크 정보와 함께 최적경로 탐색부(332)로 전송한다.(S320)The destination candidate setting unit 331 of the route search engine unit 330 sets a link included in a predetermined range from the destination as the destination candidate link based on the destination information received from the wireless terminal 100, and the destination candidate link thus set up. To be transmitted to the optimal path search unit 332 with the source link information (S320).
이때, 경로탐색 엔진부(330)는 교통정보 수집부(310) 및 교통정보 처리부(320)로부터 현재 교통상황에 대한 교통정보를 수신한 상태이다. 따라서, 최적경로 탐색부(332)는 수신한 출발지 링크 정보와 목적지 정보 및 목적지 후보 링크 정보를 알고리즘에 적용하여 최적 경로를 산출한다.(S340~S350)At this time, the route search engine unit 330 receives traffic information on the current traffic situation from the traffic information collecting unit 310 and the traffic information processing unit 320. Accordingly, the optimal path search unit 332 calculates an optimal path by applying the received source link information, the destination information, and the destination candidate link information to the algorithm. (S340 to S350).
최종적으로 경로탐색 엔진부(330)에서 산출된 경로는 경로처리부(340)를 통해 다시 무선단말(100)로 전송된다.(S360)Finally, the path calculated by the path search engine unit 330 is transmitted to the wireless terminal 100 again through the path processing unit 340 (S360).
이때, 경로탐색 엔진부(330)의 목적지 후보 설정부(331)에서 목적지 후보 링크를 설정하고 최적경로 탐색부(332)에서 최적 경로를 탐색하는 과정이 도 4a 내지 도 4d에 도시되어 있다.In this case, the process of setting the destination candidate link in the destination candidate setting unit 331 of the path search engine unit 330 and searching for the optimum path in the optimal path search unit 332 is illustrated in FIGS. 4A to 4D.
도 4a는 운전자의 무선단말(100)을 통하여 수신한 출발지점과 도착지점의 위치를 나타낸 것이다.Figure 4a shows the location of the starting point and the arrival point received via the driver's wireless terminal 100.
이후 도 4b에 도시한 바와 같이, 운전자가 무선단말(100)을 통하여 출발지 링크 및 최적 경로 결정 기준 옵션을 설정하고 경로 탐색을 요청하면, 교통센터(300)의 목적지 후보 설정부(331)는 무선단말(100)로부터 수신한 목적지로부터 소정 범위 내에 포함된 목적지 후보 링크를 설정하고, 설정된 목적지 후보 링크를 최적경로 탐색부(332)로 전송한다.Subsequently, as shown in FIG. 4B, when the driver sets a source link and an optimal route determination criterion option through the wireless terminal 100 and requests a route search, the destination candidate setting unit 331 of the traffic center 300 wirelessly. The destination candidate link included in the predetermined range is set from the destination received from the terminal 100, and the set destination candidate link is transmitted to the optimum path search unit 332.
이때, 목적지 후보링크 설정에 있어서 설정 범위가 너무 커지면 후보링크의수가 많아져서 불필요한 링크가 후보로 설정될 확률이 높아지기 때문에, 목적지 후보링크 설정 범위는 목적지의 좌표를 중심으로 반경 50m 정도로 한다. 또한, 본선 이외의 본선 링크간을 연결하는 램프, 교차로 링크 등은 목적지 종료 링크로서 적합하지 않으므로, 목적지 후보링크 설정은 본선 링크(분리 및 비분리 포함)만으로 제한한다. 도 4b에서 목적지 후보링크 설정 범위는 둥근 원으로 표시하였으며, 이 범위 안에 포함되어 목적지 후보링크로 설정된 링크는 굵은 선으로 표시하였다. 본 발명의 실시예에서는 5개의 목적지 후보링크가 설정되었다.At this time, if the setting range is too large in setting the destination candidate link, the number of candidate links increases, so that the probability of setting unnecessary links as candidates increases, so the destination candidate link setting range is about 50 m around the coordinates of the destination. In addition, ramps, intersection links, and the like that connect between main lines other than the main line are not suitable as destination end links, so the destination candidate link setting is limited to main line links (including separation and non-separation only). In FIG. 4B, a destination candidate link setting range is indicated by a round circle, and a link included in this range and set as a destination candidate link is indicated by a thick line. In the embodiment of the present invention, five destination candidate links are set.
다음으로, 도 4c에 도시한 바와 같이 최적경로 탐색부(332)는 출발지 링크 정보와 목적지 정보 및 목적지 후보 링크 정보를 이용하여 최적후보 경로를 산출한다. 본 발명의 실시예에서는 5가지의 최적후보 경로가 탐색되었다.Next, as illustrated in FIG. 4C, the optimum path search unit 332 calculates an optimal candidate path using the source link information, the destination information, and the destination candidate link information. In the embodiment of the present invention, five optimal candidate paths have been searched.
이후, 최적경로 탐색부(332)는 산출된 최적후보 경로 중 운전자가 요청한 최적경로 결정 기준 옵션(최단옵션 또는 최적옵션)에 적합한 최적경로를 선택한다.Thereafter, the optimum path search unit 332 selects an optimal path suitable for the optimal path determination reference option (shortest option or optimal option) requested by the driver among the calculated optimal candidate paths.
즉, 운전자가 최단옵션을 선택한 경우에는 탐색된 최적후보 경로 중 주행거리가 가장 짧은 경로를 최적경로로 선택하고, 운전자가 최적옵션(통행시간이 가장 짧은 경로)을 선택한 경우에는 종래의 최단경로(Dijkstra) 알고리즘을 적용하여 최적후보 경로 중 최단경로를 선택한다.In other words, if the driver selects the shortest option, the path that has the shortest mileage is selected as the optimal path among the found optimal candidate paths, and if the driver selects the optimal option (the path with the shortest travel time), the conventional shortest path ( Dijkstra) algorithm is applied to select the shortest path among the best candidate paths.
이때, Dijkstra 알고리즘은 수형망(Tree Building) 알고리즘으로서 경로 비용에 대한 우선순위를 이용하여 임의의 한 지점으로부터의 최단비용 트리를 작성하는 것으로, 링크 탐색시 목적지 후보링크들 중에서 가장 먼저 탐색이 종료되는 경로를 최적경로로 선택한다.At this time, the Dijkstra algorithm is a tree building algorithm that creates the shortest cost tree from any one point by using the priority of the path cost. Select the path as the best path.
Dijkstra 알고리즘의 절차는 다음과 같다.The procedure of Dijkstra algorithm is as follows.
먼저, 네트워크 상의 모든 노드 j에 대해 dhj(j=1, 2,.., N-1)를 임시 표지(label) πi로 기록하는데, 출발노드(h)에 j를 연결하는 링크가 없으면 dhj=∞로 간주한다.(πi←dhj, πh＊←0)First, dhj (j = 1, 2, .., N-1) is written as a temporary label π i for all the nodes j on the network. If there is no link connecting j to the starting node h, then dhj = ∞ (πi ← dhj, πh ＊ ← 0)
표지는 출발노드로부터 네트워크 상의 모든 노드까지의 최단거리 추정치를 각 노드에 기록한 것으로서, πi는 출발노드로부터 각 노드까지의 추정 최단거리이고, πi*는 출발 노드로부터 각 노드까지의 실제 최단거리이다. dhj는 경로 길이로 노드 h에서 j까지의 길이이고, N은 네트워크 상의 총 노드수이다.The marker is a record of the shortest distance estimates from each node to all nodes on the network, π i is the estimated shortest distance from the starting node to each node, and π i * is the actual shortest distance from the starting node to each node. dhj is the path length from nodes h to j and N is the total number of nodes on the network.
다음, 모든 임시 표지(πi) 중에서 최소치를 선택하여 이를 영구표지( πi*)하고, 영구 표지된 노드를 i라고 하면 πi←minj(πi), πh*←πi가 된다.Next, the minimum value among all temporary markers (πi) is selected and the permanent marker (πi * ), and if the permanently labeled node is i, then πi ← minj (πi) and πh * ← πi.
이렇게 영구 표지된 노드 i의 모든 인접 노드 j의 임시 표지를 수정하고, 영구 표지(πi*)에 링크의 비용 dij를 합한 값과 기존의 임시 표지 πj를 비교하여 작은 값을 선택한다.( πj←min(πj, πi*+ dij))Modify the temporary markers of all neighboring nodes j of the permanently marked node i and compare the existing temporary marker πj with the sum of the cost dij of the link to the permanent marker (πi * ) and select a smaller value. (Πj ← min (πj, πi * + dij))
더 이상 임시 표지가 없으면 최적 경로 알고리즘을 종료한다.If there is no longer a temporary mark, the optimal path algorithm terminates.
도 4d는 이러한 Dijkstra 알고리즘에 의하여 선택된 최적경로를 나타낸 것이다.Figure 4d shows the optimal path selected by this Dijkstra algorithm.
마지막으로, 교통센터(300)는 경로탐색 엔진부(330)에서 산출된 경로를 경로처리부(340)를 통하여 무선단말(100)로 전송한다.Finally, the traffic center 300 transmits the path calculated by the path search engine 330 to the wireless terminal 100 through the path processor 340.
이상에서 본 발명의 바람직한 실시예에 대하여 상세하게 설명하였지만 본 발명은 이에 한정되는 것은 아니며, 그 외의 다양한 변경이나 변형이 가능하다.Although the preferred embodiment of the present invention has been described in detail above, the present invention is not limited thereto, and various other changes and modifications are possible.
이와 같이 본 발명에 의한 차량의 경로 탐색 시스템 및 그 방법에 따르면, 목적지 주변에 위치한 다수의 목적지 후보 링크를 설정하고 출발지 링크와 목적지 후보링크를 기준으로 경로를 탐색함으로써 목적지 주변에서 우회하는 링크가 탐색되는 것을 방지하여 운전자에게 최적 경로를 제공할 수 있는 효과가 있다.As described above, according to the vehicle route search system and method thereof, a link that bypasses around the destination is searched by setting a plurality of destination candidate links located around the destination and searching the route based on the source link and the destination candidate link. There is an effect that can provide the optimal route to the driver by preventing it.
Claims (11)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020030053123A KR20050014477A (en) | 2003-07-31 | 2003-07-31 | System for route searching of car and method thereof |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020030053123A KR20050014477A (en) | 2003-07-31 | 2003-07-31 | System for route searching of car and method thereof |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| KR20050014477A true KR20050014477A (en) | 2005-02-07 |
Family
ID=37225609
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1020030053123A Ceased KR20050014477A (en) | 2003-07-31 | 2003-07-31 | System for route searching of car and method thereof |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR20050014477A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100705224B1 (en) * | 2005-05-16 | 2007-04-06 | 엘지전자 주식회사 | Moving Path Search Method of Moving Object in Navigation System |
-
2003
- 2003-07-31 KR KR1020030053123A patent/KR20050014477A/en not_active Ceased
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100705224B1 (en) * | 2005-05-16 | 2007-04-06 | 엘지전자 주식회사 | Moving Path Search Method of Moving Object in Navigation System |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3496479B2 (en) | Road data maintenance system | |
| JP4793703B2 (en) | Center device for route guidance system | |
| JP4992099B2 (en) | Comfortable walking route search server and program | |
| US7339496B2 (en) | Geographic data transmitting method, information delivering apparatus and information terminal | |
| US6349261B1 (en) | Method and apparatus for determining route within traffic network | |
| KR100493092B1 (en) | Navigation apparatus and method for calculating optimal path | |
| CN100414254C (en) | Device and method for calculating a path from a deviated position to an original path and its navigation system | |
| JP4977164B2 (en) | Car navigation method, car navigation system, center device, and car navigation device | |
| JPH10214400A (en) | Dynamic route guidance device | |
| JP2001041757A (en) | Digital map location information transmission method and device for implementing the method | |
| KR100678254B1 (en) | Navigation device and method for guiding a route using multipath | |
| US20080242315A1 (en) | Traffic data collection utilizing a cellular communication network and probe units | |
| JP2015156171A (en) | Travel time data preparation device, travel time data preparation method, and program | |
| KR100515203B1 (en) | System and Method for Providing Traffic Information using Node Selection Technique | |
| KR100647742B1 (en) | Public transportation based navigation service system and method | |
| KR100665470B1 (en) | Traffic information processing method using short distance dedicated communication and optimal route calculation method using the same | |
| JP5359577B2 (en) | Information management center and in-vehicle terminal | |
| CN100593802C (en) | Systems and methods for providing origin and destination navigation information | |
| KR20050014477A (en) | System for route searching of car and method thereof | |
| JP3233066B2 (en) | Route guidance device | |
| KR100517808B1 (en) | Car multi-routing searching system and method thereof | |
| KR100695346B1 (en) | Navigation method using real-time traffic information of satellite DMB | |
| CN105651292B (en) | Air navigation aid and device | |
| JP2006275647A (en) | On-vehicle communication navigation terminal device, navigation server device, navigation system, control method therefor, and control program | |
| KR100753933B1 (en) | Location method, location system, location server and user terminal |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A201 | Request for examination | ||
| PA0109 | Patent application |
Patent event code: PA01091R01D Comment text: Patent Application Patent event date: 20030731 |
|
| PA0201 | Request for examination | ||
| PG1501 | Laying open of application | ||
| E902 | Notification of reason for refusal | ||
| PE0902 | Notice of grounds for rejection |
Comment text: Notification of reason for refusal Patent event date: 20050729 Patent event code: PE09021S01D |
|
| E601 | Decision to refuse application | ||
| PE0601 | Decision on rejection of patent |
Patent event date: 20051020 Comment text: Decision to Refuse Application Patent event code: PE06012S01D Patent event date: 20050729 Comment text: Notification of reason for refusal Patent event code: PE06011S01I |