Method and apparatus for searching a route

• US 6,072,409 A
• Filed: 01/28/1998
• Issued: 06/06/2000
• Est. Priority Date: 01/29/1997
• Status: Expired due to Term

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Fushimi, Makoto, Ueyama, Yoshiki, Yagyu, Takeshi
• Primary Examiner(s): Wu, Daniel J.
• Assistant Examiner(s): TWEEL JR, JOHN ALEXANDER
• Application Number:
  US09/014,588
• Time in Patent Office: 860 Days
• Field of Search: 340/988, 340/990, 340/995, 73/178 R, 701/117, 701/200, 701/202, 701/209
• US Class Current: 340/995.19
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• 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

Abstract

In areas where composite intersection traffic regulation exits, nodes and links for use in the conventional network are separated into a plurality of nodes and links, respectively. For example, one node is separated into N1a to N1c, and one link is separated into L1a to L1c. Then, the whole road network is represented by separating the network into a road network (L1a, L2a, L3a, L4a, L5a, N1a, N2a) in view of entering links (L1a, L3a) which the composite intersection traffic regulation does not affect, and road networks α (L1b, L2b, L3b, L4b, N1b, N2b) and β (L1c, L2c, L3c, L5c, N1c, N2c) in view of entering links (L4b, L5c) which the composite intersection traffic regulation affects, and one-way traffic regulations are set on suitable links to allow for a representation of the composite intersection transfer regulation. Use of such map data enables selections which are compliant with the composite intersection traffic regulation without requiring a specific processing at the time of the search processing.

Claims

1. A method for selecting an optimum route between two arbitrary points on map data, said method comprising:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes and separate link data obtained by separating each road on the map into a plurality of links; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and/or setting right/left-turn traffic regulations to the separate node data.

2. A method for selecting an optimum route between two arbitrary points on map data, said method comprising:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and unified link data obtained by unifying part of the separate link data; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the unified link data and/or setting right/left-turn traffic regulations to the separate node data.

3. A method for selecting an optimum route between two arbitrary points on map data, said method comprising:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and virtual link data obtained by connecting nodes separated from one intersection by a virtual link; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the virtual link data and/or setting right/left-turn traffic regulations to the separate node data.

4. A method for selecting an optimum route between two arbitrary points on map data, said method comprising:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data;

wherein the map data includes at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersection; and

wherein said searching for the optimum route, at the time of searching for the optimum route, also judges whether it is possible to pass through to a next point from the composite intersection traffic regulation information and arrival route information to a point to be searched for, and terminating a search to the next point if it is impossible.

5. A method as claimed in claim 4, wherein the map data records link information to be recorded as the composite intersection traffic regulation information with connection numbers of the links connecting to one node.

6. A method as claimed in claim 4, wherein the map data doubly records the composite intersection traffic regulation information having the same contents in a node or link on an entering side and in a node or link on an exit side, and wherein said searching for the optimum route performs search processing from both of the two points set for a search on the map data.

7. A method as claimed in claim 4, wherein a plurality of kinds of the composite intersection traffic regulation are previously expressed in patterns and different identifiers are set thereto respectively, and the map data records the composite intersection traffic regulation information of said composite intersection traffic regulation expressed in patterns with the identifiers.

8. An apparatus for selecting an optimum route between two arbitrary points on map data, said apparatus comprising:

a map data storage portion for storing the map data;

a point setting portion for setting the two points to be searched for on the map data stored in said map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by said point setting portion based on the map data stored in said map data storage portion;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes and separate link data obtained by separating each road on the map into a plurality of links; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and/or setting right/left-turn traffic regulations to the separate node data.

9. An apparatus for selecting an optimum route between two arbitrary points on map data, said apparatus comprising:

a map data storage portion for storing the map data;

a point setting portion for setting the two points to be searched for on the map data stored in said map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by said point setting portion based on the map data stored in said map data storage portion;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and unified link data obtained by unifying part of the separate link data; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the unified link data and/or setting right/left-turn traffic regulations to the separate node data.

10. An apparatus for selecting an optimum route between two arbitrary points on map data, said apparatus comprising:

a map data storage portion for storing the map data;

a point setting portion for setting the two points to be searched for on the map data stored in said map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by said point setting portion based on the map data stored in said map data storage portion;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and virtual link data obtained by connecting nodes separated from one intersection by a virtual link; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the virtual link data and/or setting right/left-turn traffic regulations to the separate node data.

11. An apparatus for selecting an optimum route between two arbitrary points on map data, said apparatus comprising:

a map data storage portion for storing the map data including at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersection;

a point setting portion for setting the two points to be searched for on the map data stored in said map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by said point setting portion based on the map data stored in said map data storage portion;

wherein said route searching portion, at the time of searching for the optimum route, judges whether it is possible to pass through to a next point from the composite intersection traffic regulation information and arrival route information to a point to be searched for, and terminates a search to the next point if it is impossible.

12. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

said map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes and separate link data obtained by separating each road on the map into a plurality of links; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and/or setting right/left-turn traffic regulations to the separate node data.

13. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

said map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and unified link data obtained by unifying part of the separate link data; and

said map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the unified link data and/or setting right/left-turn traffic regulations to the separate node data.

14. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

said map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and virtual link data obtained by connecting nodes separated from one intersection by a virtual link; and

said map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the virtual link data and/or setting right/left-turn traffic regulations to the separate node data.

15. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersection; and

said map data records link information to be recorded as the composite intersection traffic regulation information with connection numbers of the links connecting to one node.

16. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersection; and

said map data doubly records the composite intersection traffic regulation information having the same contents in a node or link on an entering side and in a node or link on an exit side.

17. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersections;

a plurality of kinds of the composite intersection traffic regulation are previously expressed in patterns and different identifiers being set thereto respectively; and

said map data records the composite intersection traffic regulation information of said composite intersection traffic regulation expressed in patterns with the identifiers.

18. A method for selecting an optimum route between two arbitrary points on map data, said method comprising:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data;

wherein the map data includes at least node data indicating intersections on a map as nodes rod link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by replacing the node data or the link data composing an actual road network with a more complicated virtual road network to which information of new links or nodes are added; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the link data and/or setting right/left-turn traffic regulations to the node data.

19. An apparatus for selecting an optimum route between two arbitrary points on map data, said apparatus comprising:

a map data storage portion for storing the map data;

a point setting portion for setting the two points to be searched for on the map data stored in said map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by said point setting portion based on the map data stored in said map data storage portion;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by replacing the node data or the link data composing an actual road network with a more complicated virtual road network to which information of new links or nodes are added; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the link data and/or setting right/left-turn traffic regulations to the node data.

20. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by replacing the node data or the link data composing an actual road network with a more complicated virtual road network to which information of new links or nodes are added; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and/or setting right/left-turn traffic regulations to the separate node data.