Route searching apparatus and route searching method

• US 8,583,661 B2
• Filed: 06/24/2009
• Issued: 11/12/2013
• Est. Priority Date: 06/27/2008
• Status: Active Grant

• Current Assignee: Toyota Jidosha Kabushiki Kaisha (Toyota Motor Corporation)
• Original Assignee: Toyota Jidosha Kabushiki Kaisha (Toyota Motor Corporation)
• Inventors: Namba, Toshiyuki, Sekiyama, Hiroaki, Fujii, Daigo, Okamoto, Keisuke
• Primary Examiner(s): SOMERS, MARC S
• Application Number:
  US13/001,524
• Publication Number:
  US 20110145290A1
• Time in Patent Office: 1,602 Days
• Field of Search: 707/705, 707/706, 707/736, 707/748, 707/749, 707/758, 707/769, 707/780, 707/918, 707/919, 707/920
• US Class Current: 707/749
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles

Abstract

A route searching apparatus includes a travel route accumulation unit, an algorithm selection unit to select route searching algorithms to meet the preference of a user based on the accumulated travel routes, and a route searching unit to perform a route search up to a destination by using the selected algorithms. Preferably, the algorithm searching unit searches for each of the travel routes accumulated in the accumulation unit by means of several algorithms, calculates, for each algorithm, a match rate between the searched route and the actual travel route, and selects an algorithm of the highest match rate. Also, it is preferable that a condition common to roads avoided by the user is extracted from the accumulated travel routes, and a route search is performed by adjusting search costs so as to make such roads less prone to be selected.

Claims

1. A route searching apparatus capable of using a plurality of route searching algorithms, comprising:

a non-transitory computer readable storage medium including a travel history table that stores a history of a travel route;

a travel route accumulation unit that acquires routes which have been traveled and accumulates the routes in the travel history table;

an algorithm selection unit that selects a route searching algorithm to meet a preference of a user based on the travel routes accumulated in the travel history table; and

a route searching unit that performs a route search up to a destination by using the algorithm selected by the algorithm selection unit,

wherein the algorithm selection unit comprises

a route searching part configured to search for a route leading from a starting point to a destination point of each of the travel routes accumulated in the travel history table by means of the plurality of algorithms,

a route match rate table configured to store a route match rate, the route match rate being a match rate between the route obtained as a result of the search and an actual travel route,

a route match rate calculation part configured to calculate the route match rate for each algorithm and to store the calculated route match rate in the route match rate table,

an algorithm preference degree table configured to store an algorithm preference degree, the algorithm preference degree being a match rate between a route selection tendency of the user and the algorithm, and

an algorithm preference degree calculation part configured to calculate, for each algorithm, the algorithm preference degree based on the route match rate of each route stored in the route match rate table,

and wherein the route searching unit selects, as an algorithm to meet the preference of the user, an algorithm of which the algorithm preference degree with respect to the route selection tendency of the user is the highest.

2. The route searching apparatus as set forth in claim 1, wherein

the algorithm selection unit further comprises a mismatch point extraction part configured to seek mismatch points that are points at which the route obtained as a result of the search and the actual travel route branch from each other, and

the route searching part is further configured to perform, when there exists a mismatch point, a new route search from the mismatch point onward, and to calculate the route match rate by making use of this search result, too.

3. The route searching apparatus as set forth in claim 2, further comprising:

a mismatch point table configured to store mismatch points, the mismatch the mismatch points being points at which the route obtained as a result of the search and the actual travel route branch from each other, wherein

the algorithm selection unit further comprises a mismatch point extraction part configured to seek the mismatch points and store the mismatch points in the mismatch point table;

the route searching apparatus further comprising an avoidance point extraction part configured to extract a common point for a plurality of mismatch points stored in the mismatch point table and obtained from a plurality of search results; and

when performing a route search by means of said selected algorithms, the route searching unit performs the route search by making larger the cost for a link matching the common point.

4. The route searching apparatus as set forth in claim 3, wherein

the route searching unit performs the search by using the selected algorithms, and when there exists a link matching the common point on the searched route, a route search is performed again after the cost of the link is set larger.

5. The route searching apparatus as set forth in claim 1, further comprising:

a mismatch point table configured to store mismatch points, the mismatch points being points at which the route obtained as a result of the search and the actual travel route branch from each other, wherein

the algorithm selection unit further comprises a mismatch point extraction part configured to seek the mismatch points and store the mismatch points in the mismatch point table;

the route searching apparatus further comprises an avoidance point extraction part configured to extract a common point for a plurality of mismatch points stored in the mismatch point table and obtained from a plurality of search results; and

when performing a route search by means of the selected algorithms, the route searching unit performs the route search by making larger the cost for a link matching the common point.

6. The route searching apparatus as set forth in claim 5, wherein

the route searching unit performs the search by using the selected algorithms, and when there exists a link matching the common point on the searched route, a route search is performed again after the cost of the link is set larger.

7. A route searching method comprising:

a travel route accumulation step to acquire and accumulate routes which have been traveled;

an algorithm selection step to select a route searching algorithm to meet preference of a user based on the accumulated travel routes; and

a route searching step to perform a route search up to a destination by using the selected algorithm,

wherein the algorithm selection step comprises;

a step to search for a route leading from a starting point to a destination point of each of the travel routes accumulated in the travel route accumulation step by means of a plurality of algorithms,

a step to calculate a route match rate for each algorithm which is a match rate between the route obtained as a result of the search and an actual travel route,

a step to calculate, for each algorithm, a match rate between a route selection tendency of the user and the algorithm based on the route match rate of each route, and

a step to select, as an algorithm to meet the preference of the user, an algorithm of which match rate with respect to the route selection tendency of the user is the highest.

8. The route searching method as set forth in claim 7, wherein

in the algorithm selection step, mismatch points are sought that are points at which the route obtained as a result of the search and the actual travel route branch from each other, and when there exists a mismatch point, a new route search is performed from the mismatch point onward, and the route match rate is calculated by making use of this search result, too.

9. The route searching method as set forth in claim 8, wherein

in the algorithm selection step, mismatch points are sought that are points at which the route obtained as a result of the search and the actual travel route branch from each other, and a common point for a plurality of mismatch points obtained from a plurality of search results is extracted;

and

in the route searching step, when a route search is performed by means of the selected algorithms, the route search is performed by making larger the cost for a link matching the common point.

10. The route searching method as set forth in claim 9, wherein

in the route searching step, the search is performed by using the selected algorithms, and when there exists a link matching the common point on the searched route, a route search is performed again after the cost of the link is set larger.

11. The route searching method as set forth in claim 7, wherein

in the algorithm selection step, mismatch points are sought that are points at which the route obtained as a result of the search and the actual travel route branch from each other, and a common point for a plurality of mismatch points obtained from a plurality of search results is extracted;

and

in the route searching step, when a route search is performed by means of the selected algorithms, the route search is performed by making larger the cost for a link matching the common point.

12. The route searching method as set forth in claim 11, wherein

in the route searching step, the search is performed by using the selected algorithms, and when there exists a link matching the common point on the searched route, a route search is performed again after the cost of the link is set larger.