Apparatus for and method of searching for an optimal route for vehicles

Patent metadata

Field	Value
Publication number	US-2024210187-A1
Application number	US-202318543695-A
Country	US
Kind code	A1
Filing date	Dec 18, 2023
Priority date	Dec 23, 2022
Publication date	Jun 27, 2024
Grant date	—

Abstract

An apparatus for searching for an optimal route based on a well-used road includes a GPS module configured to detect a current vehicular position. The apparatus also includes a storage module configured to store digital map data. The apparatus also includes a processor configured to select an extension link, which is to be extended according to priority, from among a plurality of search links starting from a departure link, in order to search for an optimal route based on a route search engine on the basis of the current vehicular position and the digital map data. The processor is also configured to work out an ETA cost for the extension link for a search route through an estimated-time-of-arrival (ETA) prediction model based on a well-used road to search for the optimal route.

First claim

What is claimed is:

1 . An apparatus for searching for an optimal route based on a well-used road, the apparatus comprising:
a GPS module configured to detect a current vehicular position; a storage module configured to store digital map data; and a processor configured to:
select an extension link, which is to be extended according to priority, from among a plurality of search links starting from a departure link, in order to search for an optimal route based on a route search engine on the basis of the current vehicular position and the digital map data; and
determine an estimated-time-of-arrival (ETA) cost for the extension link for a search route through an estimated-time-of-arrival (ETA) prediction model based on a well-used road to search for the optimal route.

2 . The apparatus of claim 1 , wherein the extension link refers to a search link to be searched next time according to the priority stored in a priority queue (PQ).

3 . The apparatus of claim 1 , wherein, when determining an ETA cost for the extension link for the search route, the processor is further configured to determine the ETA cost by adding a cost from a current link to a destination to a cost from a departure to the current link.

4 . The apparatus of claim 1 , wherein, when the well-used road is matched to the extension link by utilizing the ETA prediction model, the processor is further configured to modify and reflect a cost for the well-used road by utilizing the ETA prediction model that is based on the well-used road.

5 . The apparatus of claim 4 , wherein the processor is further configured to reflect the modified cost in the well-used road and thus insert the extension link, which undergoes cost calculation, into a priority queue (PQ).

6 . The apparatus of claim 1 , wherein in order to select the well-used road, the processor is further configured to:
analyze a traffic distribution by utilizing probe data; select links representing a high traffic level (N %); select a core link that is a link representing a high level (K %) of passing-through by Odid's, from among the links representing the high traffic level (N %); and select the well-used road passing through the selected core link.

7 . The apparatus of claim 6 , wherein in order to select the well-used road passing through the selected core link, the processor is further configured to:
extract all origin-destinations (OD's) passing through the core link; extract a link through which even one of all OD's pass; generate a table showing the number of Odid's that pass through each link; analyze the number of Odid's that pass through the core link, as a reference; select links through which Odid's pass, representing a high level (H %) with the core link as a reference; select the well-used road in a manner that connects the links selected with the core link as the reference until the links are no longer connected to each other.

8 . A method of searching for an optimal route based on a well-used road, the method comprising:
selecting, by a processor, an extension link, which is to be extended according to priority, from among a plurality of search links starting from a departure link in order to search for an optimal route based on a route search engine; determining, by the processor, an estimated-time-of-arrival (ETA) cost for the extension link for a search route through an ETA prediction model based on a well-used road to search an optimal route.

9 . The method of claim 8 , wherein the extension link refers to a search link to be searched next time according to the priority stored in a priority queue (PQ).

10 . The method of claim 8 , wherein, determining the ETA cost for the extension link for the search route comprises determining, by the processor, the ETA cost by adding a cost from a current link to a destination to a cost from a departure to the current link.

11 . The method of claim 8 , further comprises: when the well-used road is matched to the extension link by utilizing the ETA prediction model, modifying and reflecting, by the processor, a cost for the well-used road by utilizing the ETA prediction model that is based on the well-used road.

12 . The method of claim 11 , further comprising, when the modified cost is reflected in the well-used road, inserting, by the processor, the extension link, which undergoes cost calculation, into a priority queue (PQ).

13 . The method of claim 8 , further comprising, in order to select the well-used road:
analyzing, by the processor, a traffic distribution by utilizing probe data; selecting, by the processor, links representing a high traffic level (N %); selecting, by the processor, a core link that is a link representing a high level (K %) of passing-through by Odid's, from among the links representing the high traffic level (N %); and selecting, by the processor, the well-used road passing through the selected core link.

14 . The method of claim 13 , further comprising, in order to select the well-used road passing through the selected core link:
extracting, by the processor, all origin-destinations (OD's) passing through the core link; extracting, by the processor, a link through which even one of all OD's pass; generating, by the processor, a table showing the number of Odid's that pass through each link; analyzing, by the processor, the number of Odid's that pass through the core link, as a reference; selecting, by the processor, links through which Odid's pass, representing a high level (H %) with the core link as a reference; and selecting, by the processor, the well-used road in a manner that connects the links selected with the core link as the reference until the links are no longer connected to each other.

Assignees

• Hyundai Autoever Corp

Inventors

• Son Sangkyu
• Rhee Ruda
• Kang Ahyoung
• Yoo Hyunsang

Classifications

• G01C21/3889

  Transmission of selected map data, e.g. depending on route · CPC title

• G01S19/42

  Determining position · CPC title

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/3492 Primary

  employing speed data or traffic data, e.g. real-time or historical (traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968) · CPC title

• G01C21/343 Primary

  Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047) · CPC title