Route selection method and apparatus therefor

• US 5,502,640 A
• Filed: 06/22/1994
• Issued: 03/26/1996
• Est. Priority Date: 03/19/1991
• 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: Ueyama, Yoshiki, Yagyu, Takeshi
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US08/264,246
• Time in Patent Office: 643 Days
• Field of Search: 364/444, 364/449, 364/443, 364/436, 364/450, 364/448, 340/990, 340/995, 340/988, 73/178 R
• US Class Current: 701/200
• 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

Abstract

A route connecting a point and another point on a network is derived in advance with respect to entire pairs of two points, and the route is stored with a transit point placed on the route in a memory. When a route between two points is retrieved, the route is divided by the transit point, and a route in each division is retrieved. Subsequently, plural routes of the divisions are connected and thus the route between the two points is derived.

Claims

1. A route selection method comprising the steps of:

defining, in advance, a connection network that includes a plurality of points representing points on a map between which a person may travel;

storing, in advance in a memory, various combinations of pairs of said points, wherein each pair of points includes a first point representing an arbitrary starting point on said map, a second point representing an arbitrary destination point on said map, and at least one transit point, if said transit point exists, said transit point corresponding to one of said plurality of points in said connection network that is located between said first point and said second point in that pair of points and through which a person must travel in progressing from said first point to said second point in that pair of points;

selecting any two points from said plurality of points in said connection network;

searching said memory for a first pair of points corresponding to said selected two points and retrieving a first transit point associated with said first pair of points if said first transit point exists;

searching said memory repeatedly for additional pairs of points stored therein and retrieving transit points associated with each additional pair of points retrieved, wherein a first point in each of said additional pairs of points corresponds to one of said selected two points and a second point in each of said additional pairs of points corresponds to a transit point retrieved in a preceding searching operation, if present, until a pair of points having no transit point associated therewith is located; and

determining a route between said two selected points by combining said two selected points with all of said transit points retrieved during said searching and retrieving operations.

2. A route selection method comprising the steps of:

defining, in advance, a connection network that includes a plurality of points representing points on a map between which a person may travel, said plurality of points being subdivided into a plurality minor points and a plurality route store points;

storing, in advance in a route store memory, various combinations of pairs of said route store points, and storing at least one transit point associated with each pair of said route store points, if said transit point exists, wherein said transit point associated with a pair of route store points corresponds to one of said plurality of points in said connection network that is located between a first route store point and a second route store point in that pair of route store points through which a person must travel in progressing from said first route store point to said second route store point in that pair of route store points;

selecting any two points from said plurality of points in said connection network, wherein one of said selected two point corresponds to a starting point and another of said selected two points corresponds to a destination point to which a user desires to travel;

determining if said selected two points corresponds to any of said route store points stored in said route store memory;

retrieving from said route store memory a first route store point proximate to said starting point, and determining a first route from said starting point to said first route store point if said starting point does not correspond to any of said route store points;

retrieving from said route store memory a second route store point proximate to said destination point, and determining a second route from said destination point to said second route store point if said destination point does not correspond to any of said route store points;

searching said route store memory for a first pair of route store points corresponding to said first and said second route store points and retrieving a first transit point associated with said first pair of points, if said first transit point exists;

searching said route store memory repeatedly for additional pairs of route stores points stored therein and retrieving a transit point associated with each additional pair of route store points retrieved, wherein a first route store point in each of said additional pairs of route store points corresponds to one of said first and said second route store points and a second route store point in each of said additional pairs of route store points corresponds a transit point retrieved in a preceding searching operation, if present, until a pair of route store points having no transit point associated therewith is located;

determining a searched route between said first and said second route store points by combining said first and said second route store points with all of said transit points retrieved during said searching and retrieving operations; and

determining a complete route between said starting point and said destination point by combining said first route, said second route and said searched route.

3. A route selection method comprising the steps of:

defining, in advance, a connection network that includes a plurality of points representing points on a map between which a person may travel, said plurality of points being subdivided into a plurality minor points and a plurality route store points;

storing, in advance in a route store memory, various combinations of pairs of said route store points, and storing at least one transit point associated with each pair of route store points, if said transit point exists, wherein said transit point associated with a pair of route store points corresponds to one of said plurality of points in said connection network that is located between a first route store point and a second route store point in that pair of route store points through which a person must travel in progressing from said first route store point to said second route store point in that pair of route store points;

selecting any two points from said plurality of points in said connection network, wherein one of said selected two points corresponds to a starting point and another of said selected two points corresponds to a destination point to which a user desires to travel;

determining if either of said selected two points corresponds to any one of said route store points;

retrieving from said route store memory a plurality of first route store points proximate to said starting point, and determining a plurality of first routes from said starting point to said plurality of first route store points, if said starting point does not correspond to any one of said route store points;

retrieving from said route store memory a plurality of second route store points proximate to said destination point, and determining a plurality of second routes from said destination point to said plurality of second route store points if said destination point does not correspond to any of said route store points;

conducting searching operations of said route store memory to determine a plurality of complete routes between said starting point and said destination point, each searching operation including the steps of;

searching said route store memory for a pair of route store points that includes a first route store point from said plurality of first route store points and a second route store point from said plurality of second route store points and retrieving a transit point associated with said pair of route store points, if said transit point exists;

searching said route store memory repeatedly for additional pairs of route stores points stored therein and retrieving transit points associated therewith, wherein a first route store point in said additional pairs of route store points corresponds to one of said first route store point and said second route store point and a second route store point in said additional pairs of route store points corresponds a transit point retrieved in a preceding searching operation, if present, said repeated searching continuing until a pair of route store points having no transit point associated therewith is located;

determining a searched route between said first and said second route store points by combining said first and said second route store points with all of said transit points retrieved during said searching and retrieving operations; and

determining a complete route between said starting point and said destination point by combining said first

route, said second route and said searched route associated with one another.

4. A route selection method as defined in claim 3, further comprising the steps of:

selecting a predetermined number of said plurality of complete routes between said starting point and said destination point; and

outputting said predetermined number of selected routes.

5. A route selection method comprising the steps of:

(a) defining, in advance, a connection network having a hierarchy structure and a plurality of points representing points on a map between which a person may travel, wherein said hierarchy structure includes a plurality of hierarchies from a lowest hierarchy to a highest hierarchy and said plurality of points are associated with at least one of said plurality of hierarchies, and wherein for each hierarchy there exists a plurality of transition points representing a connection points between hierarchies;

(b) storing, in a route memory in advance, data representing said plurality of points and data representing a predetermined number of complete routes between a predetermined number points located in a same hierarchy;

(c) selecting two points from said plurality of points in said connection network and stored in said route memory, said two points corresponding to a starting point and a destination point;

(d) defining a first reference point as said starting point and a first object point as said destination point;

(e) conducting a first searching operation of said route memory for a complete route in a first hierarchy between said first reference point and said first object point;

(f) changing a hierarchy in which a route is searched for to a hierarchy above said first hierarchy if no complete route is found during said searching operation of said first hierarchy;

(g) retrieving a first transition point located in said first hierarchy proximate to said first reference point and retrieving a first complete route between said first reference point and said first transition point, if said first reference point is not one of said plurality of transition points between said first hierarchy and said hierarchy above said first hierarchy;

(h) retrieving a second transition point located in said first hierarchy proximate to said first object point and retrieving a second complete route between said first object point and said second transition point, if said first object point is not one of said plurality of transition points between said first hierarchy and said hierarchy above said first hierarchy;

(i) conducting a second searching operation of said route memory for a complete route in said hierarchy above said first hierarchy between said first transition point and said second transition point;

(j) repeating steps (f)-(i) until a complete route is found, wherein each time steps (f)-(i) are carried out, said first hierarchy in which a route is searched for is incremented to a next higher hierarchy, said first transition point becomes said first reference point and said second transition point becomes said first object point; and

(k) determining a final complete route between said starting point and said destination point by combining all of said first routes, all of said second routes and said complete route.

6. A route selection method comprising the steps of:

(a) defining, in advance, a connection network having a hierarchy structure and a plurality of points representing points on a map between which a person may travel, wherein said hierarchy structure includes a plurality of hierarchies from a lowest hierarchy to a highest hierarchy and said plurality of points are associated with at least one of said plurality of hierarchies, and wherein for each hierarchy there exists a plurality of migration points representing connection points between hierarchies;

(b) storing, in a memory in advance, data representing said plurality of points, data representing said migration points, data representing distance ranges associated with each of said migration points, and data representing a predetermined number of complete routes between points located in a same hierarchy, said points located in said same hierarchy including said points associated with that hierarchy and migration points associated with that hierarchy;

(c) selecting two points from said plurality of points in said connection network stored in said memory, said two points corresponding to a starting point and a destination point;

(d) retrieving a first group of said migration points associated with said starting point, said first group of migration points including migration points associated with each hierarchy in said plurality of hierarchies, a first group of routes from said starting point to said first group of migration points, a second group of migration points associated with said destination point, said second group of migration points including migration points associated with each hierarchy in said plurality of hierarchies, and a second group of routes from said destination point to said second group of migration point;

(e) determining whether any of said second group of migration points in a first hierarchy are within said distance ranges associated with said first group of migration points in said first hierarchy, and if not, repeating said determining step with respect to a next higher hierarchy until it is determined that at least one migration point from said second group of migration points is within a distance range of at least one migration point from said first group of migration points and retrieving all routes associated with said at least one migration point from said first group of migration points;

(f) determining whether said at least one migration point from said second group of migration points is included in any one of said routes associated with said at least one migration point from said first group of migration points; and

(g) obtaining a complete route from said starting point to said destination point if at least one migration point from said second group of migration points is included in any one of said routes associated with said at least one migration point from said first group of migration points, said complete route being obtained by connecting a first route from said starting point to said at least of one migration point from said first group of migration points, a second route from said destination point to said at least of one migration point from said second group of migration points, and a third route that includes said at least one migration point from said first group of migration points and said at least one migration point from said second group of migration points determined in step (f).

7. A route selection method according to claim 6, further comprising the step of repeating steps (e)-(g) using a still higher hierarchy in said determining operation of step (e), if at least one migration point from said second group of migration points is not included in any one of said routes associated with said at least one migration point from said first group of migration points.

8. A route selection method according to claim 6, wherein, if a plurality of routes exist after completing steps (e) and (f), determining which of said plurality of route to use in said obtaining step based on characteristic data associated with said routes.

9. A route selection method according to claim 8, wherein said characteristic data includes at least one of distance data, travel time, and traffic congestion.

10. A route selection apparatus that establishes a complete route between two points on a connection network that includes a plurality of points representing points on a map between which a person may travel, said apparatus comprising:

memory means for storing various combinations of pairs of said points in a memory, wherein a first point in each pair of points represents an arbitrary starting point on said map and a second point in each pair of points represents an arbitrary destination point on said map, and, storing only one transit point associated with each pair of points, if said transit point exists, said transit point associated with a pair of said points corresponds to one of said plurality of points in said connection network that is located between said first point and said second point that pair of points and through which a person must travel in progressing from said first point to said second point in that pair of points;

input means for selecting any two points from said plurality of points in said connection network;

means for searching said memory for a first pair of points corresponding to said selected two points and retrieving a first transit point associated with said first pair of points if said first transit point exists;

means for repeatedly searching said memory for additional pairs of points stored therein and retrieving transit points associated with each additional pair of points retrieved, wherein a first point in said additional pairs of points corresponds to one of said selected two points and a second point in said additional pairs of points corresponds to a transit point retrieved in a preceding searching operation, if present, until a pair of points having no transit point associated therewith is located; and

means for determining said complete route between said two selected points by combining said two selected points with all of said transit points retrieved during said searching and retrieving operations.

11. A route selection apparatus that establishes a complete route between two points on a connection network that includes a plurality of points representing points on a map between which a person may travel, said plurality of points being subdivided into a plurality minor points and a plurality route store points, said apparatus comprising:

route store memory means for storing various combinations of pairs of said route store points, and storing at least one transit point associated with each pair of said route store points, if said transit point exists, wherein said transit point associated with a pair of said route store points corresponds to one of said plurality of points in said connection network that is located between a first route store point and a second route store point in that pair of route store points through which a person must travel in progressing from said first route store point to said second route store point in that pair of route store points;

input means for selecting any two points from said plurality of points in said connection network, wherein one of said selected two points corresponds to a starting point and another of said selected two points corresponds to a destination point to which a user desires to travel;

means for determining if either of said selected two points corresponds to any of said route store points stored in said route store memory;

means for retrieving from said route store memory a first route store point proximate to said starting point and for determining a first route from said starting point to said first route store point if said starting point does not correspond to any of said route store points;

means for retrieving from said route store memory a second route store point proximate to said destination point and for determining a second route from said destination point to said second route store point if said destination point does not correspond to any of said route store points;

means for searching said memory for a first pair of route store points corresponding to said first and said second route store points and retrieving a first transit point associated with said first pair of points, if said first transit point exists;

means for repeatedly searching said memory for additional pairs of route stores points stored therein and retrieving a transit point associated with each additional pair of route store points retrieved, wherein a first route store point in said additional pairs of route store points corresponds to one of said first and said second route store points and a second route store point in said additional pairs of route store points corresponds a transit point retrieved in a preceding searching operation, if present, said repeated searching continuing until a pair of route store points having no transit point associated therewith is located;

means for obtaining a searched route between said first and said second route store points by combining said first and said second route store points with all of said transit points retrieved during said searching and retrieving operations; and

means for obtaining said complete route between said starting point and said destination point by combining said first route, said second route and said searched route.

12. A route selection apparatus for establishing a route between two points in a connection network that includes a plurality of points representing points on a map between which a person may travel, said plurality of points being subdivided into a plurality minor points and a plurality route store points, said apparatus comprising:

route store memory for storing various combinations of pairs of said route store points, and storing at least one transit point associated with each pair of route store points, if said transit point exists, wherein said transit point associated with a pair of said route store points corresponds to one of said plurality of points in said connection network that is located between a first route store point and a second route store point in that pair of route store points through which a person must travel in progressing from said first route store point to said second route store points that pair of route store points;

input means for selecting any two points from said plurality of points in said connection network, wherein one of said selected two points corresponds to a starting point and another of said selected two points corresponds to a destination point to which a user desires to travel;

means for determining if either of said selected two points corresponds to any one of said route store points;

means for retrieving from said route store memory a plurality of first route store points proximate to said starting point and for determining a plurality of first routes from said starting point to said plurality of first route store points, if said starting point does not correspond to any one of said route store points;

means for retrieving from said route store memory a plurality of second route store points proximate to said destination point and for determining a plurality of second routes from said destination point to said plurality of second route store points if said destination point does not correspond to any of said route store points;

wherein searching operations of said route store memory are conducted to determine a plurality of complete routes between said starting point and said destination point, said searching operations being conducted by;

means for searching said route store memory for a pair of route store points that includes a first route store point from said plurality of first route store points and a second route store point from said plurality of second route store points and retrieving a transit point associated with said pair of route store points, if said transit point exists;

means for repeatedly searching said route store memory for additional pairs of route stores points stored therein and retrieving a transit point associated with each additional pair of route store points retrieved, wherein a first route store point in said additional pairs of route store points corresponds to one of said first route store point and said second route store point and a second route store point in said additional pairs of route store points corresponds a transit point retrieved in a preceding searching operation, if present, and wherein said means for repeatedly searching continues said repeated searching operation until a pair of route store points having no transit point associated therewith is located;

means for obtaining a searched route between said first and said second route store points by combining said first and said second route store points with all of said transit points retrieved during said searching and retrieving operations; and

means for obtaining a complete route between said starting point and said destination point by combining said first route, said second route and said searched route associated with one another.

13. A route selection apparatus as defined in claim 12, further comprising:

means for selecting a predetermined number of said plurality of complete routes between said starting point and said destination point; and

means for outputting said predetermined number of selected routes.

14. A route selection apparatus for obtaining a complete route between two points on a connection network having a hierarchy structure and a plurality of points representing points on a map between which a person may travel, wherein said hierarchy structure includes a plurality of hierarchies from a lowest hierarchy to a highest hierarchy and said plurality of points are associated with at least one of said plurality of hierarchies, and wherein for each hierarchy there exists a plurality of transition points representing a connection points between hierarchies, said apparatus comprising:

route memory for storing data representing said plurality of points and data representing a predetermined number of complete routes between a predetermined number of points located in a same hierarchy;

input means for selecting two points from said plurality of points in said connection network and stored in said route memory, said two points corresponding to a starting point and a destination point;

means for defining a first reference point as said starting point and a first object point as said destination point;

first searching means for conducting a first searching operation of said route memory for a complete route in a first hierarchy between said first reference point and said first object point;

changing means for changing a hierarchy in which a route is searched for to a hierarchy above said first hierarchy if no complete route is found during said searching operation of said first hierarchy;

retrieving means for retrieving from said route memory a first transition point located in said first hierarchy proximate to said first reference point and retrieving a first complete route between said first reference point and said first transition point, if said first reference point is not one of said plurality of transition points between said first hierarchy and said hierarchy above said first hierarchy, and for retrieving a second transition point located in said first hierarchy proximate to said first object point and retrieving a second complete route between said first object point and said second transition point, if said first object point is not one of said plurality of transition points between said first hierarchy and said hierarchy above said first hierarchy;

wherein said searching means conducts a second searching operation of said route memory for a complete route in said hierarchy above said first hierarchy between said first transition point and said second transition point;

means for operating said changing means, said retrieving means and said searching means until a complete route is found, wherein each time said changing means, said retrieving means and said searching means are operated, said first hierarchy in which a route is searched for is incremented to a next higher hierarchy, said first transition point becomes said first reference point and said second transition point becomes said first object point; and

means for obtaining said complete route between said starting point and said destination point by combining all of said first routes, all of said second routes and said complete route.

15. A route selection apparatus for obtaining a complete route between two points on a connection network having a hierarchy structure and a plurality of points representing points on a map between which a person may travel, wherein said hierarchy structure includes a plurality of hierarchies from a lowest hierarchy to a highest hierarchy and said plurality of points are associated with at least one of said plurality of hierarchies, and wherein for each hierarchy there exists a plurality of migration points representing connection points between hierarchies, said apparatus comprising:

memory means for storing, in a memory in advance, data representing said plurality of points, data representing said migration points, data representing distance ranges associated with each of said migration points, and data representing a predetermined number of complete routes between points located in a same hierarchy, said points located in said same hierarchy including said points associated with that hierarchies and migration points associated with that hierarchy;

input means for selecting two points from said plurality of points in said connection network stored in said memory, said two points corresponding to a starting point and a destination point;

means for retrieving a first group of said migration points associated with said starting point, said first group of migration points including migration points associated with each hierarchy in said plurality of hierarchies, a first group of routes from said starting point to said first group of migration points, a second group of migration points associated with said destination point, said second group of migration points including migration points associated with each hierarchy in said plurality of hierarchies, and a second group of routes from said destination point to said second group of migration point;

determining means for determining whether any of said second group of migration points in a first hierarchy are within said distance ranges associated with said first group of migration points in said first hierarchy, and if not, for repeating said determining operation with respect to a next higher hierarchy until it is determined that at least one migration point from said second group of migration points is within a distance range of at least one migration point from said first group of migration points and retrieving all routes associated with said at least one migration point from said first group of migration points, and for determining whether said at least one migration point from said second group of migration points is included in any one of said routes associated with said at least one migration point from said first group of migration points; and

obtaining means for obtaining a complete route from said starting point to said destination point if at least one migration point from said second group of migration points is included in any one of said routes associated with said at least one migration point from said first group of migration points, said complete route being obtained by connecting a first route from said starting point to said at least of one migration point from said first group of migration points, a second route from said destination point to said at least of one migration point from said second group of migration points, and a third route that includes said at least one migration point from said first group of migration points and said at least one migration point from said second group of migration points determined by said determining means.

16. A route selection apparatus according to claim 15, further comprising means for operating said determining means and said obtaining means, wherein each time said determining means and said obtaining means are operated a still higher hierarchy is used in said determining operation, if at least one migration point from said second group of migration points is not included in any one of said routes associated with said at least one migration point from said first group of migration points.

17. A route selection apparatus according to claim 15, further comprising means, if a plurality of routes exist after operating said determining means, for determining which of said plurality of route to be used said obtaining means based on characteristic data associated with said routes.

18. A route selection apparatus according to claim 17, wherein said characteristic data includes at least one of distance data, travel time, and traffic congestion.