Route searching system, route searching method, navigation system and computer program product

• US 7,171,306 B2
• Filed: 04/22/2004
• Issued: 01/30/2007
• Est. Priority Date: 04/25/2003
• Status: Active Grant

• Current Assignee: Pioneer Corporation
• Original Assignee: Pioneer Corporation
• Inventors: Hirose, Chihiro
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US10/829,423
• Publication Number:
  US 20040215389A1
• Time in Patent Office: 1,013 Days
• Field of Search: 701/209, 701/201, 701/202, 701/208, 701/204, 340/995.11, 340/995.14, 340/995.15, 340/995.21, 340/995.23, 340/995.27, 705/400
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries

Abstract

A route searching system is provided with: a road map database for storing a road map data; a searching device for performing a link cost calculation on the basis of the road map data and thereby searching an optimal route. The searching device increases or decreases the link cost of a link corresponding to a road section that requires a difficult turn on a route option, the difficult turn being a right turn or a left turn, one of which is more difficult than the other in accordance with a traffic rule, and connecting a node corresponding to an intersection, in at least two cases depending on the difficulty of the difficult turn at the intersection.

Claims

1. A route searching system comprising:

a road map database for storing a road map data, the road map data including (i) node data that indicates nodes that correspond to predetermined kinds of points on a road including at least an intersection, and (ii) link data that indicates a link that corresponds to a road section that connects the predetermined kinds of points on a road corresponding to the nodes; and

a searching device for calculating link costs as for individual links that correspond to individual road sections that consist of individual route options from a first point to a second point, on the basis of said road map database, and thereby searching one of the individual route options whose total link cost is the lowest, as an optimal route, from among a plurality of links that correspond to all the road sections of the individual route options,

wherein said searching device increases or decreases the link cost of a link corresponding to a road section that requires a difficult turn on the individual route options, the difficult turn being the right turn or the left turn one of which is more difficult than the other in accordance with a traffic rule, and connecting to a node that corresponds to the intersection, in at least two cases depending on difficulty of the difficult turn at the intersection.

2. The route searching system according to claim 1, wherein said searching device judges a link corresponding to the road section that requires the difficult turn, and connecting to a node that corresponds to the intersection, from among said plurality of links, on the basis of said road map database, and increases or decreases the link cost of the judged link, depending on the difficulty of the difficult turn.

3. The route searching system according to claim 1, wherein said searching device increases or decreases the link cost of a link corresponding to the road section that requires the difficult turn, depending on at least one of a road width, the number of lanes, a road type and an existence of a traffic signal, which are indicated by attribute information of the link or the node included in at least one of the link data or the node data.

4. The route searching system according to claim 1, wherein said searching device,

firstly calculates temporarily link costs of a plurality of links corresponding to said all the road sections, and then

judges whether or not a link corresponding to the road section that requires the difficult turn exists in said plurality of links corresponding to said all the road sections, and if exists, calculates link costs of said plurality of links corresponding to all the road sections, by adding a first predetermined value to link costs that are temporarily calculated, depending on the difficulty of the difficult turn.

5. The route searching system according to claim 4, wherein said searching device increases the first predetermined value, as a connection angle formed by two links connected to the node corresponding to the intersection decreases.

6. The route searching system according to claim 4, wherein said searching device temporarily calculates the link cost, and then judges whether or not a link corresponding to a road section that requires an easy turn, the easy turn being the right turn or the left turn one of which is easier than the other, exists in said plurality of links corresponding to said all the road sections, and if exists, calculates link costs of said plurality of links corresponding to said all the road sections, by adding a second predetermined value, which is smaller than the first predetermined value, to link costs that are temporarily calculated.

7. The route searching system according to claim 1, wherein said searching device determines a node corresponding to the intersection, on the basis of a connection angle formed by two links connected to each node on the route options, and increases the link cost of the link corresponding to the road section that requires the difficult turn and connecting to the determined node corresponding to the intersection.

8. The route searching system according to claim 1, further comprising:

an inputting device for inputting a starting point or a current position as the first point and inputting a destination as the second point; and

an outputting device for outputting the searched optimal route in a predetermined format.

9. A route searching system comprising:

a road map database for storing a road map data, the road map data including data that indicates (i) intersections and (ii) a road section connecting the intersections; and

a searching device for calculating a cost, that is a quantitative index of the difficulty or facility in driving as for individual road sections that consist of individual route options from a first point to a second point, on the basis of said road map database, and thereby searching one of the individual route options whose total cost is the lowest, as an optimal route, from among all the road sections of the individual route options,

wherein said searching device increases or decreases the cost of a road section that requires a difficult turn after passing the intersection on the individual route options from among a plurality of road sections that consist of all road sections of the individual route options, the difficult turn being the right turn or the left turn one of which is more difficult than the other in accordance with a traffic rule, in at least two cases depending on difficulty of the difficult turn at the intersection.

10. The route searching system according to claim 9, further comprising:

an inputting device for inputting a starting point or a current position as the first point and inputting a destination as the second point; and

an outputting device for outputting the searched optimal route in a predetermined format.

11. A navigation system comprising:

a route searching system provided with;

a road map database for storing a road map data, the road map data including (i) node data that indicates nodes that correspond to predetermined kinds of points on a road including at least an intersection, and (ii) link data that indicates a link that corresponds to a road section that connects the predetermined kinds of points on a road corresponding to the nodes; and

a searching device for calculating link costs as for individual links that correspond to individual road sections that consist of individual route options from a first point to a second point, on the basis of said road map database, and thereby searching one of the route options whose total link cost is the lowest, as an optimal route, from among a plurality of links that correspond to all the road sections of the individual route options, wherein said searching device increases or decreases the link cost of a link corresponding to a road section that requires a difficult turn on the individual route options, the difficult turn being the right turn or the left turn one of which is more difficult than the other in accordance with a traffic rule, and connecting to a node that corresponds to the intersection, in at least two cases depending on difficulty of the difficult turn at the intersection;

a locating device for locating a current position; and

a route guiding device for performing predetermined kinds of route guidance, on the basis of the current position that is located by the locating device and the optimal route that is searched by the searching device.

12. The navigation system according to claim 11, further comprising:

a center device and a navigation terminal device, which are connected to each other via a communication network, wherein

at least a part of said road map database is included in said center device, and

said locating device and said route guiding device are included in said navigation terminal device.

13. A route searching method of calculating link costs as for individual links that correspond to individual road sections that consist of individual route options from a first point to a second point, on the basis of a road map database for storing a road map data, the road map data including (i) node data that indicates nodes that correspond to predetermined kinds of points on a road including at least an intersection, and (ii) link data that indicates a link that corresponds to a road section that connects the predetermined kinds of points on a road corresponding to the nodes;

and thereby searching one of the route options whose total link cost is the lowest, as an optimal route, from among a plurality of links that correspond to all the road sections of the route options, said method comprising;

a determining process of determining a link corresponding to a road section that requires a difficult turn on the route options, the difficult turn being the right turn or the left turn one of which is more difficult than the other in accordance with a traffic rule, and connecting to a node that corresponds to the intersection, on the basis of said road map database; and

a increasing or decreasing process of increasing or decreasing the link cost of the determined link, in at least two cases depending on difficulty of the difficult turn at the intersection.

14. A route searching method of calculating a cost, that is a quantitative index of the difficulty or facility in driving as for individual road sections that consist of individual route options from a first point to a second point, on the basis of a road map database for storing a road map data, the road map data including data that indicates (i) intersections and (ii) a road section connecting the intersections;

and thereby searching one of the individual route options whose total cost is the lowest, as an optimal route, from among all the road sections of the individual route options, said method comprising;

a determining process of determining a road section that requires a difficult turn after passing the intersection on the route options from among a plurality of road sections that consist of all road sections of the individual route options, the difficult turn being the right turn or the left turn one of which is more difficult than the other in accordance with a traffic rule; and

an increasing or decreasing process of increasing or decreasing the cost of the determined road section, in at least two cases depending on difficulty of the difficult turn at the intersection.

15. A computer program product in a computer-readable medium for tangibly embodying a program of instructions executable by a computer to make the computer function as at least a searching device for calculating link costs as for individual links that correspond to individual road sections that consist of individual route options from a first point to a second point, on the basis of a road map database, and thereby searching one of the individual route options whose total link cost is the lowest, as an optimal route, from among a plurality of links that correspond to all the road sections of the individual route options, wherein said searching device increases or decreases the link cost of a link corresponding to a road section that requires a difficult turn on the individual route options, the difficult turn being the right turn or the left turn one of which is more difficult than the other in accordance with a traffic rule, and connecting to a node that corresponds to the intersection, in at least two cases depending on difficulty of the difficult turn at the intersection.

16. A navigation system comprising:

a route searching system provided with;

a road map database for storing a road map data, the road map data including data that indicates (i) intersections and (ii) a road section connecting the intersections; and

a searching device for calculating a cost, that is a quantitative index of the difficulty or facility in driving as for individual road sections that consist of individual route options from a first point to a second point, on the basis of said road map database, and thereby searching one of the individual route options whose total cost is the lowest, as an optimal route, from among all the road sections of the route options, wherein said searching device increases or decreases the cost of a road section that requires a difficult turn after passing the intersection on the route options from among a plurality of road sections that consist of all road sections of the individual route options, the difficult turn being the right turn or the left turn one of which is more difficult than the other in accordance with a traffic rule, in at least two cases depending on difficulty of the difficult turn at the intersection;

a locating device for locating a current position; and

a route guiding device for performing predetermined kinds of route guidance, on the basis of the current position that is located by the locating device and the optimal route that is searched by the searching device.

17. A computer program product in a computer-readable medium for tangibly embodying a program of instructions executable by a computer to make the computer function as at least a searching device for calculating a cost, that is a quantitative index of the difficulty or facility in driving as for individual road sections that consist of individual route options from a first point to a second point, on the basis of said road map database, and thereby searching one of the individual route options whose total cost is the lowest, as an optimal route, from among all the road sections of the individual route options, wherein said searching device increases or decreases the cost of a road section that requires a difficult turn after passing the intersection on the individual route options from among a plurality of road sections that consist of all road sections of the individual route options, the difficult turn being the right turn or the left turn one of which is more difficult than the other in accordance with a traffic rule, in at least two cases depending on difficulty of the difficult turn at the intersection.