Method and apparatus for searching a route

• US 6,014,607 A
• Filed: 09/25/1997
• Issued: 01/11/2000
• Est. Priority Date: 09/30/1996
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Ihara, Yasuhiro, Ueyama, Yoshiki, Yagyu, Takeshi
• Primary Examiner(s): Chin, Gary
• Application Number:
  US08/936,914
• Time in Patent Office: 838 Days
• Field of Search: 701/200, 701/202, 701/207, 701/208, 701/209, 701/210, 73/178 R, 340/988, 340/990, 340/995
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

Road network data is divided into a plurality of road network areas and one or a plurality of routes are obtained between the divided road network areas. The obtained routes are stored into a route data storage device 1. When a starting point and a destination are specified from a point input device 2, an area investigating device 3 investigates two road network areas to which the points belong. A route retrieving device 4 retrieves the route data corresponding to the combination of the obtained two road network areas from the route data storage device 1. A peripheral route searching device 8 searches for connecting routes in the road network areas to which the starting point and the destination belong, on the basis of the road network data stored in the road network data storage device 7. Further, the peripheral route searching device 8 produces the entire route from the starting point to the destination by using the route data retrieved from the route data storage device 1 and the connecting routes searched for in the vicinities of the starting point and the destination and presents the route to a user through an output device 6. This way, routes between arbitrary two road network areas are obtained in advance and stored as route data. When a starting point and a destination are specified, the route data between the corresponding road network areas are retrieved and a route from the starting point to the destination is presented on the basis of the retrieved route data. Thus the route can be searched for in an instant.

Claims

1. A method for searching for an optimum route between two arbitrarily specified points on road network data, said method comprising:

dividing the road network data into a plurality of road network areas;

obtaining, in advance, routes between each of the plurality of road network areas obtained in said dividing the road network data, and recording the obtained routes as route data into a route recording medium;

investigating, when a starting point and a destination are specified, to obtain two road network areas from the plurality of road network areas to which the starting point and the destination respectively belong;

retrieving the route data which corresponds to a combination of the two road network areas obtained in said investigating from the route recording medium;

searching for a route from the starting point to the destination on a basis of the route data retrieved in said retrieving the route data and presenting the searched route to a user; and

producing map data for displaying a background and recording the map data into a map recording medium;

wherein, in said searching for the route, the map data corresponding to the route data retrieved in said retrieving the route data is read from the map recording medium and displayed, and the searched route is displayed over the displayed map data; and

wherein, in the map data, a plurality of partial map data required when displaying a route between two road network areas are collected together in advance for each combination of the road network areas, and the plurality of collected partial map data are recorded in the map recording medium in an interrelated manner so that the data can be read by a single access operation.

2. A method for searching for an optimum route between two arbitrarily specified points on road network data, said method comprising:

dividing the road network data into a plurality of road network areas;

obtaining, in advance, routes between each of the plurality of road network areas obtained in said dividing the road network data, and recording the obtained routes as route data into a route recording medium;

investigating, when a starting point and a destination are specified, to obtain two road network areas from the plurality of road network areas to which the starting point and the destination respectively belong;

retrieving the route data which corresponds to a combination of the two road network areas obtained in said investigating from the route recording medium; and

searching for a route from the starting point to the destination on a basis of the route data retrieved in said retrieving the route data and presenting the searched route to a user;

wherein said searching for the route further comprises;

searching, in a vicinity of the starting point, for a first connecting route from the starting point to the route in the route data retrieved in said retrieving the route data on the basis of the road network data;

searching, in a vicinity of the destination, for a second connecting route from the destination to the route in the route data retrieved in said retrieving the route data on the basis of the road network data;

producing an entire route from the starting point to the destination by using the first and second connecting routes searched for in said searching for the first connecting route and said searching for the second connecting route and the route in the route data retrieved from said retrieving the route data; and

displaying the entire route produced in said producing the entire route.

3. A route searching method as claimed in claim 2, wherein the route data recorded in the route recording medium further includes information about a boundary point at which each of the routes intersects a road network area;

wherein, in said searching for the first connecting route, routes are searched for from the starting point to all boundary points of the road network area to which the starting point belongs; and

wherein, in said searching for the second connecting route, routes are searched for from the destination to all boundary points of the road network area to which the destination belongs.

4. A method for searching for an optimum route between two arbitrarily specified points on road network data, said method comprising:

dividing the road network data into a plurality of road network areas;

obtaining, in advance, routes between each of the plurality of road network areas obtained in said dividing the road network data, and recording the obtained routes as route data into a route recording medium;

investigating, when a starting point and a destination are specified, to obtain two road network areas from the plurality of road network areas to which the starting point and the destination respectively belong;

retrieving the route data which corresponds to a combination of the two road network areas obtained in said investigating from the route recording medium; and

searching for a route from the starting point to the destination on a basis of the route data retrieved in said retrieving the route data and presenting the searched route to a user;

wherein, in said obtaining routes, at least one route is obtained between the road network areas and the obtained routes are recorded as the route data into the route recording medium; and

wherein said searching for the route further comprises;

displaying the at least one obtained route on the basis of the route data retrieved in said retrieving the route data;

selecting, when the at least one obtained route is displayed in said displaying, one of the obtained routes in response to an operation by the user;

searching for a first connecting route from the starting point to the route selected in said selecting one of the obtained routes in a vicinity of the starting point on a basis of the road network data;

searching for a second connecting route from the destination to the route selected in said selecting one of the obtained routes in a vicinity of the destination on a basis of the road network data; and

producing an entire route from the starting point to the destination by using the first and second connecting routes searched for in said searching for a first connecting route and said searching for a second connecting route and the route selected in said selecting one of the obtained routes.

5. A route searching method as claimed in claim 4, wherein the route data recorded in the route recording medium further comprises information about a boundary point at which each of the routes intersects a road network area;

wherein said searching for the first connecting route further comprises searching for routes from the starting point to all boundary points of the road network area to which the starting point belongs; and

wherein said searching for the second connecting route further comprises searching for routes from the destination to all boundary points of the road network area to which the destination belongs.

6. A route searching method as claimed in claim 5, wherein said searching for routes from the starting point to all boundary points and said searching for routes from the destination to all boundary points are performed while the user is selecting the one route from among the obtained routes.

7. A method for searching for an optimum route between two arbitrarily specified points on road network data, said method comprising:

dividing the road network data into a plurality of road network areas;

obtaining, in advance, routes between each of the plurality of road network areas obtained in said dividing the road network data, and recording the obtained routes as route data into a route recording medium;

investigating, when a starting point and a destination are specified, to obtain two road network areas from the plurality of road network areas to which the starting point and the destination respectively belong;

retrieving the route data which corresponds to a combination of the two road network areas obtained in said investigating from the route recording medium; and

searching for a route from the starting point to the destination on a basis of the route data retrieved in said retrieving the route data and presenting the searched route to a user;

wherein said dividing the road network data further comprises;

dividing the road network data into road network areas of minimum-units; and

dividing the road network data into road network areas of collective units each including a plurality of the minimum-units;

wherein said obtaining routes comprises;

searching for two of the minimum-unit road network areas as a target;

obtaining, when the distance between the minimum-unit road network areas searched for in said searching for two of the minimum-unit road network areas is shorter than a predetermined distance, a route between the searched minimum-unit road network areas and recording the obtained route as the route data into the route recording medium; and

obtaining, when the distance between the minimum-unit road network areas searched for in said searching for two of the minimum-unit road network areas is longer than a predetermined distance, a route between the collective-unit road network areas to which the searched minimum-unit road network areas belong, and recording the obtained route and the route data into the route recording medium;

wherein said searching for two of the minimum-unit road network areas, said obtaining a route between the searched minimum-unit road network areas, and said obtaining a route between the collective-unit road network areas are repeatedly performed; and

wherein said investigating to obtain two road network areas further comprises;

investigating, when the distance between the starting point and the destination is shorter than the predetermined distance, to obtain the minimum-unit road network areas to which the starting point and the destination belongs; and

investigating, when the distance between the starting point and the destination is longer than the predetermined distance, to obtain the collective-unit road network areas to which the starting point and the destination belongs.