Route calculation system, route calculation method, and route calculation program

• US 9,726,507 B2
• Filed: 03/04/2014
• Issued: 08/08/2017
• Est. Priority Date: 03/28/2013
• Status: Active Grant

• Current Assignee: Aisin AW Company Limited (Aisin Corp.)
• Original Assignee: Aisin AW Company Limited (Aisin Corp.)
• Inventors: Tanizaki, Daisuke, Shibata, Tomofumi
• Primary Examiner(s): Troost, Aaron L
• Application Number:
  US14/766,073
• Publication Number:
  US 20150377637A1
• Time in Patent Office: 1,253 Days
• 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/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality
• CPC Class Codes: G09B 29/007 using computer methods

Abstract

Route calculation systems, methods, and programs extract from stored past routes, past routes that at least partly pass through a departure point area and at least partly pass through a destination area, and calculate, for each extracted past route, a new departure point side section route and a new destination side section route. The systems, methods, and programs calculate, for each extracted past route, a new candidate route that sequentially passes through the calculated new departure point side section route, a past section route, and the calculated new destination side section route. The systems, methods, and programs compute a cost of each calculated new candidate route and set the new route as the new candidate route having the smallest computed cost.

Claims

1. A route calculation system for a vehicle, the route calculation system comprising:

a memory that stores;

map information;

route information including past routes, the past routes being routes traveled by the vehicle in the past from past departure points to past destinations; and

a route calculation program; and

a processor that, when executing the stored program;

determines a new departure point and a new destination for a new route;

extracts, from the stored past routes, one or more stored past routes that at least partly pass through a departure point area and at least partly pass through a destination area according to the stored map information and the stored route information, the departure point area being a range area including the new departure point, the destination area being a range area including the new destination;

calculates, for each of the extracted past routes, a new departure point side section route that is a route from the new departure point to an exit point, the exit point being a point at which the extracted past route intersects with a border of the departure point area on a side of the past destination of the extracted past route;

calculates, for each of the extracted past routes, a new destination side section route that is a route from an entrance point to the new destination, the entrance point being a point at which the extracted past route intersects with a border of the destination area on a side of the past departure point of the extracted past route;

assembles, for each of the extracted past routes, a new candidate route that sequentially includes the following three sections;

the calculated new departure point side section route;

a past section route that is a part of the extracted past route between the exit point and the entrance point; and

the calculated new destination side section route;

computes a cost of each calculated new candidate route;

sets, as the new route from the new departure point to the new destination, the new candidate route having the smallest computed cost; and

outputs the new route for display on a display in the vehicle.

2. The route calculation system according to claim 1, wherein the processor, when executing the stored program:

calculates each new candidate route based on only the stored route information of one or more past routes that were calculated during a predetermined period of time just before calculating the new route.

3. The route calculation system according to claim 1, wherein:

the memory stores calculation condition information including calculation conditions when the past routes were calculated; and

the processor, when executing the stored program;

determines a calculation condition of the new route; and

based on the stored calculation condition information, extracts one or more stored past routes that were calculated under the same calculation condition as the determined calculation condition; and

calculates a new candidate route for each of the extracted one or more past routes that were calculated under the same calculation condition.

4. The route calculation system according to claim 1, wherein:

the memory stores road type information including road types of roads forming the past routes; and

the processor, when executing the stored program;

based on the stored road type information, extracts one or more past routes, in which a road whose road type is highway forms at least the past section route; and

sets the new route from among each of the extracted past routes having the road whose road type is highway forming at least the past section.

5. The route calculation system according to claim 1, wherein the processor, when executing the stored program:

when the new departure point and the new destination have been determined, computes a distance from the new departure point to the new destination; and

only when the computed distance is equal to or more than a predetermined distance, sets the new route based on the stored map information and the stored route information.

6. A route calculation method for a vehicle, the method comprising:

accessing, with a processor, map information;

accessing, with the processor, route information including past routes, the past routes being routes traveled by the vehicle in the past from past departure points to past destinations;

determining, with the processor, a new departure point and a new destination for a new route;

extracting, with the processor, from the stored past routes, one or more stored past routes that at least partly pass through a departure point area and at least partly pass through a destination area according to the stored map information, the departure point area being a range area including the new departure point, the destination area being a range area including the new destination;

calculating, with the processor, for each of the extracted past routes, a new departure point side section route that is a route from the new departure point to an exit point, the exit point being a point at which the extracted past route intersects with a border of the departure point area on a side of the past destination of the extracted past route;

calculating, with the processor, for each of the extracted past routes, a new destination side section route that is a route from an entrance point to the new destination, the entrance point being a point at which the extracted past route intersects with a border of the destination area on a side of the past departure point of the extracted past route;

assembling, with the processor, for each of the extracted past routes, a new candidate route that sequentially includes the following three sections;

the calculated new departure point side section route;

a past section route that is a part of the extracted past route between the exit point and the entrance point; and

the calculated new destination side section route;

computing, with the processor, a cost of each calculated new candidate route;

setting, with the processor, as the new route from the new departure point to the new destination, the new candidate route having the smallest computed cost; and

outputting, with the processor, the new route for display on a display in the vehicle.

7. A computer-readable storage medium storing a computer-executable route calculation program for a vehicle, the program comprising:

instructions for accessing map information;

instructions for accessing route information including past routes, the past routes being routes traveled by the vehicle in the past from past departure points to past destinations;

instructions for determining a new departure point and a new destination for a new route;

instructions for extracting, from the stored past routes, one or more stored past routes that at least partly pass through a departure point area and at least partly pass through a destination area according to the stored map information, the departure point area being a range area including the new departure point, the destination area being a range area including the new destination;

instructions for calculating, for each of the extracted past routes, a new departure point side section route that is a route from the new departure point to an exit point, the exit point being a point at which the extracted past route intersects with a border of the departure point area on a side of the past destination of the extracted past route;

instructions for calculating, for each of the extracted past routes, a new destination side section route that is a route from an entrance point to the new destination, the entrance point being a point at which the extracted past route intersects with a border of the destination area on a side of the past departure point of the extracted past route;

instructions for assembling, for each of the extracted past routes, a new candidate route that sequentially includes the following three sections;

the calculated new departure point side section route;

a past section route that is a part of the extracted past route between the exit point and the entrance point; and

the calculated new destination side section route;

instructions for computing a cost of each calculated new candidate route;

instructions for setting, as the new route from the new departure point to the new destination, the new candidate route having the smallest computed cost; and

instructions for outputting the new route for display on a display in the vehicle.