Optimum route determination

• US 5,486,822 A
• Filed: 05/26/1994
• Issued: 01/23/1996
• Est. Priority Date: 11/09/1990
• Status: Expired due to Fees

• Current Assignee: Sumitomo Electric Industries Limited (Sumitomo Corporation)
• Original Assignee: Sumitomo Electric Industries Limited (Sumitomo Corporation)
• Inventors: Inoue, Takuya, Hashimoto, Takeo, Tenmoku, Kenji
• Primary Examiner(s): SWARTHOUT, BRENT
• Application Number:
  US08/250,105
• Time in Patent Office: 607 Days
• Field of Search: 340/988, 340/990, 340/995, 340/905, 73/178 R, 364/449, 364/444
• US Class Current: 340/995.22
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

An optimum route determination apparatus comprises a plurality of specific points selected from a road map on the basis of a fixed criterion, and an optimum route leading to each destination in which one of the specific points is a departure point and which has been calculated in advance. A route memory has a route table in which data of an initial route leading from the one of the specific points to at least the next specific point through which the optimum route passes are stored in correspondence with the each destination and the one of the specific points. An initialization unit is provided for setting a destination, a specific point near to a vehicle'"'"'s current location, and specific points along the optimum route. An initial route acquisition unit is provided for retrieving the route table to acquire the data of the initial route in accordance with the destination and the specific point set by the initialization unit.

Claims

1. In an optimum route determination apparatus which, according to a destination set by a vehicle operator, reads road map data of an area containing a departure point and that destination out of a road map memory for a road map and which determined an optimum route leading from the departure point to the destination based on the road map data, selection means exterior to said optimum route determination apparatus having previously selected a plurality of specific points, calculation means exterior to said optimum route determination apparatus having previously calculated a plurality of optimum routes which lead from said plurality of specific points to a plurality of destinations, respectively, passing in sequence through specific points and each specific point representing at least one departure point in a respective optimum route, said optimum route determination apparatus comprising:

a route memory having stored therein a route table containing data of said specific points, data of said destinations and data of a plurality of initial routes, one of said initial routes leading from one of said specific points to at least the next specific point in said sequence positioned on one of said optimum routes leading from said one of said specific points to one of said destinations, and not including all specific points comprising the optimum route to a respective destination, wherein said data of said data of said specific points, said data of said destinations and said data of said initial routes are contained in said route table in such a manner that the data of said one of said initial routes is acquired by searching said route table for said one of said specific points and one of said destinations;

initialization means for setting one of said destinations and one of said specific points near to a current location of a vehicle; and

initial route acquisition means for searching said route table for the specific point and the destination set by said initialization means to acquire said data of said initial route,

said initialization means then replacing said one of said specific points with the next specific point, said initial route acquisition means and said initialization means then repeating the searching and replacing operations until one of said optimum routes is constituted by the repeatedly acquired initial route data.

2. In an optimum route determination apparatus which, according to a destination set by a vehicle operator, reads road map data of an area containing a departure point and that destination out of a road map memory and which determines an optimum route leading from the departure point to the destination based on the road map data, selection means exterior to said optimum route determination apparatus having previously selected a plurality of specific points, calculation means exterior to said optimum route determination apparatus having previously calculated a plurality of optimum routes which lead from a plurality of departure points to said plurality of specific points, respectively, passing in sequence through the departure points and specific points, each specific point representing at least one destination point in a respective optimum route, said optimum route determination apparatus comprising:

a route memory having stored therein a route table containing data of said departure points, data of said specific points and data of a plurality of end routes, each end route not including all specific points comprising the optimum route from the departure point to a specific point representing a respective destination, one of said end routes leading to said one of said specific points from at least a first specific point positioned closer to the departure point than said one of said specific points, wherein one of said optimum routes leading from one of said departure points to said one of said specific points passes through said first specific point, and said data of said departure points, said data of said specific points and said data of said end routes are contained in said route table in such a manner that the data of said one of said end routes is acquired by searching said route table for said one of said departure points and said one of said specific points;

initialization means for setting one of said departure points and one of said specific points near to a destination of a trip;

end route acquisition means for searching said route table for the departure point and the specific point set by said initialization means to acquire said data of said end route,

said initialization means then replacing said one of said specific points with said first specific point, said end route acquisition means and said initialization means then repeating the searching and replacing operations until one of said optimum routes are constituted by the repeatedly acquired end route data.

3. An optimum route determination apparatus as set forth in claim 2, wherein said road map data comprise combination of nodes and links, and points on said road map are specified by said links.

4. An optimum route determination apparatus as set forth in claim 2, wherein said road map data comprise combination of nodes and links, and points on said road map are specified by said nodes.

5. An optimum route determination apparatus as set forth in claim 2, wherein said route table of said route memory has stored therein data of said end route, when a distance between said departure point and said destination is longer than a predetermined distance.

6. In an optimum route determination apparatus which, according to a destination set by a vehicle operator, reads road map data of an area containing a departure point and that destination out of a road map memory for a road map and which determines an optimum route leading from the departure point, to the destination based on the road map data, selection means exterior to said optimum route determination apparatus having previously selected a plurality of specific points, calculation means exterior to said optimum route determination apparatus having previously calculated a plurality of optimum routes which lead from said plurality of specific points to a plurality of destinations, respectively, and said specific points being departure points, said optimum route determination apparatus comprising:

a route memory having stored therein a route table containing data of said specific points, data of said destinations and data of a plurality of initial routes, one of said initial routes leading from one of said specific points to at least a next specific point which is positioned on one of said optimum routes leading from said one of said specific points to one of said destinations, each specific point representing at least one departure point in a respective optimum route, wherein said data of said specific points, said data of said destinations and said data of said initial routes are contained in said route table in such a manner that the data of said one of said initial routes is acquired by searching said route table for said one of said specific points and said one of said destinations;

each initial route not including all specific points comprising the optimum route to a respective destination;

initialization means for setting one of said destinations and one of said specific points near to a current location of a vehicle; and

initial route acquisition means for searching said route table for the specific point and the destination set by said initialization means to acquire said data of said initial route,

said initialization means then replacing said one of said specific points with the next specific point, said initial route acquisition means and said initialization means then repeating the searching and replacing operations until one of said optimum routes is constituted by the repeatedly acquired initial route data,

wherein when the same initial route is stored with respect to different destinations, said route table of said route memory having stored therein said same initial route in correspondence with an aggregation of said different destinations.

7. An optimum route determination apparatus as set forth in claim 6, wherein said road map data comprise combination of nodes and links, and points on said road map are specified by said links.

8. An optimum route determination apparatus as set forth in claim 6, wherein said road map data comprise combination of nodes and links, and points on said road map are specified by said nodes.

9. An optimum route determination apparatus as set forth in claim 6, wherein said route table of said route memory has stored therein data of said initial route, when a distance between said departure point and said destination is longer than a predetermined distance.

10. In an optimum route determination apparatus which, according to a destination set by a vehicle operator, reads map data of an area containing a departure point and that destination out of a road map memory and which determines an optimum route leading from the departure point to the destination based on the road map data, selection means exterior to said optimum route determination apparatus having previously selected a plurality of specific points, calculation means exterior to said optimum route determination apparatus having previously calculated a plurality of optimum routes which lead from a plurality of departure points to said plurality of specific points, respectively, passing in sequence through the departure points and specific points, each specific point representing at least one destination point in a respective optimum route and said specific points being destinations, said optimum route determination apparatus comprising:

a route memory having stored therein a route table containing data of said departure points, data of said specific points and data of a plurality of end routes, each end route not including all specific points comprising the optimum route from the departure point to a specific point representing a respective destination, one of said end routes leading to said one of said specific points from at least a first specific point positioned closer to the departure point than said one of said specific points, wherein one of said optimum routes leading from one of said departure points to said one of said specific points passes through said first specific point, and said data of said departure points, said data of said specific points and said data of said end routes are contained in said route table in such a manner that said data of said end route is acquired by searching said route table for said one of said departure points and said one of said specific points;

initialization means for setting one of said departure points and one of said specific points near to a destination of a trip; and

end route acquisition means for searching said route table for the departure point and the specific point set by said initialization means to acquire said data of said end route,

said initialization means then replacing said one of said specific points with said first specific point, said end route acquisition means and said initialization means then repeating the searching and replacing operations until one of said optimum routes is constituted by the repeatedly acquired end route data,

wherein when the same end route is stored with respect to different departure points, said route table of said route memory having stored therein said same end route in correspondence with an aggregation of said different departure points.

11. An optimum route determination apparatus as set forth in claim 10, wherein said road map data comprise combination of nodes and links, and points on said road map are specified by said links.

12. An optimum route determination apparatus as set forth in claim 10, wherein said road map data comprise combination of nodes and links, and points on said road map are specified by said nodes.

13. An optimum route determination apparatus as set forth in claim 10, wherein said route table of said route memory has stored therein data of said end route, when a distance between said departure point and said destination is longer than a predetermined distance.