Method of selecting route and terminal thereof

• US 8,150,609 B2
• Filed: 12/12/2007
• Issued: 04/03/2012
• Est. Priority Date: 05/01/2007
• Status: Active Grant

• Current Assignee: LG Electronics, Inc. (LG Corporation)
• Original Assignee: LG Electronics, Inc. (LG Corporation)
• Inventors: Yun, Kyungso
• Primary Examiner(s): MANCHO, RONNIE M
• Application Number:
  US11/955,147
• Publication Number:
  US 20080275639A1
• Time in Patent Office: 1,574 Days
• Field of Search: 701/209, 701/200, 701/213, 701/25, 701/202, 701/201, 701/120, 701/118, 701/119, 701/117, 701/123, 701/207, 340/995, 340/988, 340/990, 340/995.13, 340/933, 340/907, 340/910, 342/454
• US Class Current: 701/118
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3492 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 Class Codes: G08G 1/091 Traffic information broadcasting broadcasting communication H04H
• CPC Class Codes: G08G 1/096716 where the received information does not generate an automatic action on the vehicle control
• CPC Class Codes: G08G 1/09675 where a selection from the received information takes place in the vehicle
• CPC Class Codes: G08G 1/096775 where the origin of the information is a central station
• CPC Class Codes: G08G 1/0968 Systems involving transmission of navigation instructions to the vehicle
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data

Abstract

A method of selecting a travel route including receiving message information formed in a hierarchical structure and including traffic information, receiving a first position value and a second position value corresponding to first and second positions, searching for travel routes between the first and second positions, classifying the travel routes from the first position to the second position into a plurality of individual road links, calculating a route cost for a first road link that includes the first position and a second road link directly connected to the first road link based on an average link speed for the first and second road links, respectively, calculating a route cost for each additional road link after the first and second road links up to a last road link including the second position based on one of a current traffic congestion status information and a predicted traffic congestion status information, and calculating a total route cost for all of the road links for the travel routes from the first position to the second position.

Claims

1. A method of selecting a travel route, the method comprising:

receiving a first position value and a second position value corresponding to first and second positions by a navigation terminal;

searching for travel routes between the first and second positions;

classifying the travel routes from the first position to the second position into a plurality of individual road links;

receiving message information formed in a hierarchical structure and including traffic information, the traffic information including at least average link speed and predicted average link speed for the plurality of individual road links for predetermined periods of time;

calculating a route cost for a first road link that includes the first position and a second road link directly connected to the first road link based on the average link speed for the first and second road links, respectively;

calculating a route cost for each additional road link after the first and second road links up to a last road link including the second position based on one of the average link speed and the predicted average link speed; and

calculating a total route cost for all of the road links for the travel routes from the first position to the second position,

wherein the route costs for the first and second road links are calculated by dividing the average link speed of the first road link by a distance of the first road link and by dividing the average link speed of the second road link by a distance of the second road link, respectively.

2. The method of claim 1, wherein the route cost for said each additional road link is calculated by dividing the predicted average link speed for said each additional road link by a distance of the corresponding road link.

3. The method of claim 1, wherein the first position is a current position or a starting position of a vehicle that is going to travel from the first position to the second position.

4. The method of claim 1, wherein the second position is a destination position that a vehicle is traveling to.

5. The method of claim 1, wherein the predicted average link speed is a predicted travel time required for the corresponding road link at a time of arriving at the corresponding road link.

6. The method of claim 1, wherein the message information formed in the hierarchical structure is a Transport Protocol Expert Group (TPEG) message.

7. The method of claim 1, further comprising:

determining if a new message information is going to be received before traveling through the first road link; and

calculating the route cost for the first and second road links using the previously received average link speed, when the determining step determines the new message information is not going to be received before traveling through the first road link.

8. The method of claim 1, further comprising;

selecting a travel route that has a highest total route cost; and

performing a routing process to route a vehicle along the selected travel route having the highest total route cost.

9. The method of claim 8, further comprising:

determining if a specific event has occurred; and

re-searching for travel routes between the first and second positions when the determining step determines the specific event has occurred.

10. The method of claim 9, wherein the determining step determines the specific event has occurred when traveling into a new road link and when receiving updated message information.

11. A navigation terminal, comprising:

a receiving unit configured to receive message information formed in a hierarchical structure and including traffic information, the traffic information including at least average link speed and predicted average link speed for predetermined periods of time;

an input unit configured to receive a first position value and a second position value corresponding to first and second positions; and

a control unit configured to search for travel routes between the first and second positions, to classify the travel routes from the first position to the second position into a plurality of individual road links, to calculate a route cost for a first road link that includes the first position and a second road link directly connected to the first road link based on the average link speed for the first and second road links, respectively, to calculate a route cost for each additional road link after the first and second road links up to a last road link including the second position based on one of the average link speed and the predicted average link speed, and to calculate a total route cost for all of the road links for the travel routes from the first position to the second position,

wherein the route costs for the first and second road links are calculated by dividing the average link speed of the first road link by a distance of the first road link and by dividing the average link speed of the second road link by a distance of the second road link, respectively.

12. The navigation terminal of claim 11, wherein the route cost for said each additional road link is calculated by dividing the predicted average link speed for said each additional road link by a distance of the corresponding road link.

13. The navigation terminal of claim 11, wherein the first position is a current position or a starting position of a vehicle that is going to travel from the first position to the second position.

14. The navigation terminal of claim 11, wherein the second position is a destination position that a vehicle is traveling to.

15. The navigation terminal of claim 11, wherein the predicted average link speed is a predicted travel time required for the corresponding road link at a time of arriving at the corresponding road link.

16. The navigation terminal of claim 11, wherein the message information formed in the hierarchical structure is a Transport Protocol Expert Group (TPEG) message.

17. The navigation terminal of claim 11, wherein the control unit is further configured to determine if a new message information is going to be received before traveling through the first road link, and to calculate the route cost for the first and second road links using the previously received average link speed, when the determining step determines the new message information is not going to be received before traveling through the first road link.

18. The navigation terminal of claim 11, the control unit is further configured to select a travel route that has a highest total route cost;

and to perform a routing process to route a vehicle along the selected travel route having the highest total route cost.

19. The navigation terminal of claim 18, the control unit is further configured to determine if a specific event has occurred, and to re-search for travel routes between the first and second positions when the determining step determines the specific event has occurred.

20. The navigation terminal of claim 19, wherein the control unit is further configured to determine the specific event has occurred when traveling into a new road link and when receiving updated message information.