Route search method for navigation device

• US 7,890,258 B2
• Filed: 12/24/2004
• Issued: 02/15/2011
• Est. Priority Date: 01/16/2004
• Status: Active Grant

• Current Assignee: Zoom Video Communications, Inc.
• Original Assignee: Xanavi Informatics Corporation (Hitachi, Ltd.)
• Inventors: Amaya, Shinichi, Endo, Yoshinori
• Primary Examiner(s): Tran; Khoi
• Assistant Examiner(s): Kiswanto; Nicholas
• Application Number:
  US10/586,356
• Publication Number:
  US 20070162222A1
• Time in Patent Office: 2,244 Days
• Field of Search: None
• US Class Current: 701/209
• 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/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality
• CPC Class Codes: G08G 1/09685 where the complete route is computed only once and not updated
• CPC Class Codes: G08G 1/096866 where the complete route is shown to the driver

Abstract

A navigation device that calculates an expected travel time or an expected arrival time for each retrieved route, using link costs predetermined for calculation of expected travel times regardless of search conditions. As the link costs for the calculation of expected travel times, are used link travel times obtained by statistically processing traffic information collected in the past, for example.

Claims

1. A route search method for a navigation device, wherein:

said navigation device comprises a storage unit that stores link data for each link as a component of roads on a map and statistical data including link travel times obtained by statistically processing traffic information collected previously; and

said method comprises;

a step of establishing a plurality of route search conditions, to derive a plurality of routes based on the plurality of route search conditions, respectively;

a route search step, in which, for each of said plurality of route search conditions, a cost of each link is determined using said link data or said statistical data depending on the route search condition in question, and a route having a smallest total cost for traveling from a departure point to a destination is searched for; and

a travel time calculation step, in which an expected travel time for each of the plurality of routes retrieved in said route search step is calculated commonly using same said statistical data, to derive comparable expected travel times of the plurality of routes, respectively, which are based on commonly using same said statistical data.

2. A route search method according to claim 1 for a navigation device, wherein:

said link data includes a link travel time obtained from map information; and

in said route search step, a cost of each link is determined using a link travel time included in said statistical data when a search condition is established in order to perform a search using the statistical data, and a cost of each link is determined using the link travel time included in said link data when a search condition is established in order to perform a search without using the statistical data, and then a route having a smallest total cost for traveling from the departure point to the destination is searched for.

3. A route search method according to claim 2 for a navigation device, wherein:

said link data includes link length information; and

in said route search step, a cost of each link is determined using the link length information included in said link data when a search condition is established in order to perform a search giving priority to a travel distance, and then a route having a smallest total cost for traveling from the departure point to the destination is searched for.

19. A route search method according to claim 1 for a navigation device, comprising:

a display comparison step, in which the plurality of routes and the expected travel times of the plurality of routes are outputted to a user for user review.

20. A navigation device according to claim 1, comprising:

a display comparison unit, in which the plurality of routes and the expected travel times of the plurality of routes are outputted to a user for user review.

4. A route search method for a navigation device, wherein:

said navigation device comprises a storage unit that stores link data for each link as a component of roads on a map and statistical data including link travel times obtained by statistically processing traffic information collected previously; and

said method comprises;

a step of establishing a plurality of route search conditions, to derive a plurality of routes based on the plurality of route search conditions, respectively;

a route search step, in which a cost of each link is determined using link length information included in said link data when a search condition is established in order to perform a search giving priority to a travel distance, and a cost of each link is determined using a link travel time included in said statistical data when a search condition is established in order to perform a search that gives priority to a travel time and uses the statistical data, and a cost of each link is determined using a link travel time obtained from map information included in said link data when a search condition is established in order to perform a search that gives priority to a travel time and does not use the statistical data, and then a route having a smallest total cost for traveling from a departure point to a destination is searched for; and

a travel time calculation step, in which an expected travel time for each of the plurality of routes retrieved in said route search step is calculated commonly using same said statistical data, to derive comparable expected travel times of the plurality of routes, respectively, which are based on commonly using same said statistical data.

5. A route search method according to claim 4 for a navigation device, wherein:

said link data for each link includes road type information of the link in question; and

in said route search step, when a search condition is established in order to perform a route search giving priority to a specific road type, a cost of a link of said specific road type is determined lower in comparison with links of other road types, based on said road type information.

6. A route search method according to claim 5 for a navigation device, wherein:

said navigation device displays the expected travel times calculated in said travel time calculation step.

7. A route search method for a navigation device, wherein:

said navigation device comprises a storage unit that stores link data for each link as a component of roads on a map and statistical data including link travel times obtained by statistically processing traffic information collected previously;

said method comprises;

a step of establishing a plurality of route search conditions, to derive a plurality of routes based on the plurality of route search conditions, respectively;

a route search step, in which a cost of each link is determined using said link data or said statistical data depending on a search condition, and a route having a smallest total cost for traveling from a departure point to a destination is searched for; and

a route guidance step, in which route guidance is performed using the route retrieved in said route search step; and

an expected travel time used for said route guidance is calculated commonly using same said statistical data, to derive comparable expected travel times of the plurality of routes, respectively, which are based on commonly using same said statistical data.

9. A route search method according to claim 7 for a navigation device, wherein:

said navigation device performs a receiving step in which selection of use or non-use of the statistical data is received; and

when a route search without using the statistical data is selected in said receiving step, then, in said route search step, a route search is performed without using the statistical data, and calculation of said expected travel time is performed using said link data and without using the statistical data.

8. A route search method for a navigation device, wherein:

said navigation device comprises a storage unit that stores link travel times used for calculating an expected travel time for traveling from a departure point to a destination; and

said method comprises;

a step of establishing a plurality of route search conditions, to derive a plurality of routes based on the plurality of route search conditions, respectively;

a route search step, in which, for each of said plurality of route search conditions, a cost of each link is determined depending on the route search condition in question, and a route having a smallest total cost is searched for; and

a travel time calculation step, in which an expected travel time for each of the plurality of routes retrieved in said route search step is calculated commonly using same said link travel times stored in said storage unit, disregarding said route search condition, to derive comparable expected travel times of the plurality of routes, respectively, which are based on commonly using same said link travel times.

10. A navigation device comprising:

a storage unit that stores link data for each link as a component of roads on a map and statistical data including link travel times obtained by statistically processing traffic information collected previously;

a search condition establishing unit that establishes a plurality of route search conditions, to derive a plurality of routes based on the plurality of route search conditions, respectively;

a route search unit that determines, for each of said plurality of route search conditions, a cost of each link using said link data or said statistical data depending on the route search condition in question, and searches for a route having a smallest total cost for traveling from a departure point to a destination; and

a travel time calculation unit that calculates an expected travel time commonly using same said statistical data, for each of the plurality of routes retrieved by said route search unit, to derive comparable expected travel times of the plurality of routes, respectively, which are based on commonly using same said statistical data.

14. A navigation device according to claim 10, wherein:

said link data includes a link travel time obtained from map information; and

in said route search unit, a cost of each link is determined using a link travel time included in said statistical data when a search condition is established in order to perform a search using the statistical data, and a cost of each link is determined using the link travel time included in said link data when a search condition is established in order to perform a search without using the statistical data, and then a route having a smallest total cost for traveling from the departure point to the destination is searched for.

15. A navigation device according to claim 14, wherein:

said link data includes link length information; and

in said route search unit, a cost of each link is determined using the link length information included in said link data when a search condition is established in order to perform a search giving priority to a travel distance, and then a route having a smallest total cost for traveling from the departure point to the destination is searched for.

11. A navigation device comprising:

a storage unit that stores link data for each link as a component of roads on a map and statistical data including link travel times obtained by statistically processing traffic information collected previously;

a search condition establishing unit that establishes a plurality of route search conditions, to derive a plurality of routes based on the plurality of route search conditions, respectively;

a route search unit that;

determines a cost of each link using link length information included in said link data when a search condition is established in order to perform a search giving priority to a travel distance;

determines a cost of each link using a link travel time included in said statistical data when a search condition is established in order to perform a search that gives priority to a travel time and uses the statistical data;

determines a cost of each link using a link travel time obtained from map information included in said link data when a search condition is established in order to perform a search that gives priority to a travel time and does not use the statistical data; and

searches for a route having a smallest total cost for traveling from a departure point to a destination; and

a travel time calculation unit that calculates an expected travel time commonly using same said statistical data for each of the plurality of routes retrieved by said route search unit, to derive comparable expected travel times of the plurality of routes, respectively, which are based on commonly using same said statistical data.

16. A navigation device according to claim 11, wherein:

said link data for each link includes road type information of the link in question; and

in said route search unit, when a search condition is established in order to perform a route search giving priority to a specific road type, a cost of a link of said specific road type is determined lower in comparison with links of other road types, based on said road type information.

17. A navigation device according to claim 16, wherein:

said navigation device displays the expected travel times calculated in said travel time calculation unit.

12. A navigation device, wherein:

said navigation device comprises;

a storage unit that stores link data for each link as a component of roads on a map and statistical data including link travel times obtained by statistically processing traffic information collected previously;

a search condition establishing unit that establishes a plurality of route search conditions, to derive a plurality of routes based on the plurality of route search conditions, respectively;

a route search unit that determines a cost of each link using said link data or said statistical data depending on a search condition and searches for a route having a smallest total cost for traveling from a departure point to a destination; and

a route guidance unit that performs route guidance using the route retrieved by said route search unit; and

an expected travel time used for said route guidance is calculated commonly using same said statistical data, to derive comparable expected travel times of the plurality of routes, respectively, which are based on commonly using same said statistical data.

18. A navigation device according to claim 12, comprising:

a receiving unit receiving selection of use or non-use of the statistical data; and

when a route search without using the statistical data is selected in said receiving unit, then, in said route search unit, a route search is performed without using the statistical data, and calculation of said expected travel time is performed using said link data and without using the statistical data.

13. A navigation device comprising:

a storage unit that stores link travel times used for calculation of an expected travel time for traveling from a departure point to a destination;

a search condition establishing unit that establishes a plurality of route search conditions, to derive a plurality of routes based on the plurality of route search conditions, respectively;

a route search unit that determines, for each of said plurality of route search conditions, a cost of each link depending on the route search condition in question, and searches for a route having a smallest total cost; and

a travel time calculation unit that calculates an expected travel time commonly using same said link travel times stored in said storage unit disregarding said route search condition, for each of the plurality of routes retrieved by said route search unit, to derive comparable expected travel times of the plurality of routes, respectively, which are based on commonly using same said link travel times.