Route search apparatus, route search method and computer-readable storage medium storing program

Patent metadata

Field	Value
Publication number	US-2016363455-A1
Application number	US-201515121576-A
Country	US
Kind code	A1
Filing date	Feb 19, 2015
Priority date	Feb 27, 2014
Publication date	Dec 15, 2016
Grant date	—

Abstract

A route search apparatus configured to search a route from a set place of departure to a set destination comprises network data that includes nodes and links representing a road network, an average cost value indicating an average of travel time of each of the links, and a variance value indicating a degree of variance of the travel time, and a route searcher configured to determine the route from the place of departure to the destination as a recommended route, based on the average cost value, the variance value and a weight coefficient of the variance value.

First claim

1 - 14 . (canceled)

15 . A route search apparatus configured to search a route from a set place of departure to a set destination, the route search apparatus comprising:
a storage part configured to store network data that includes nodes and links representing a road network, an average cost value indicating an average of travel time of each of the links, and a variance value indicating a degree of variance of the travel time; and a route searcher configured to determine the route from the place of departure to the destination as a recommended route, based on an overall cost value calculated according to a function including the average cost value, the variance value and a weight coefficient of the variance value.

16 . The route search apparatus according to claim 15 , wherein the route searcher calculates the overall cost value by adding a correction value calculated as a product of the weight coefficient and a value having a positive correlation to an integrated value of the variance values corresponding to links that are passed through between the place of departure and the destination, to an integrated value of the average cost values corresponding to the links, in a plurality of route candidates that are candidates of the recommended route.

17 . The route search apparatus according to claim 15 , wherein the route searcher determines a route from the place of departure to a node corresponding to a specific point in the middle of the route from the place of departure to the destination, as a halfway route of the recommended route, based on a candidate overall cost value that is provided as a sum of a first term representing an integrated value of the average cost values corresponding to links that are passed through from the place of departure to the node corresponding to the specific point in the middle of the route from the place of departure to the destination and a second term representing a correction value calculated based on the weight coefficient and an integrated value of the variance values corresponding to the links that are passed through.

18 . The route search apparatus according to claim 16 , wherein the route searcher determines a route from the place of departure to a node corresponding to a specific point in the middle of the route from the place of departure to the destination, as a halfway route of the recommended route, based on a candidate overall cost value that is provided as a sum of a first term representing an integrated value of the average cost values corresponding to links that are passed through from the place of departure to the node corresponding to the specific point in the middle of the route from the place of departure to the destination and a second term representing a correction value calculated based on the weight coefficient and an integrated value of the variance values corresponding to the links that are passed through.

19 . The route search apparatus according to claim 17 , wherein the route searcher determines, as the halfway route, a halfway route candidate having a smallest candidate overall cost value out of a plurality of the candidate overall cost values, among a plurality of halfway route candidates that are candidates of the halfway route.

20 . The route search apparatus according to claim 17 , wherein when there are a plurality of the candidate overall cost values that are different from each other by at most a predetermined value, out of the candidate overall cost values of a plurality of halfway route candidates that are candidates of the halfway route, the route searcher determines the halfway route, based on one of the first term and the second term that is selected according to the weight coefficient.

21 . The route search apparatus according to claim 17 , wherein
the route searcher performs:
a first determination process that determines a first halfway route candidate having a smallest candidate overall cost value out of a plurality of the candidate overall cost values, among a plurality of halfway route candidates that are candidates of the halfway route;
a second determination process that is performed when there is at least one provisional second halfway route candidate having a smaller integrated value of the average cost values than an integrated value of the average cost values of the first halfway route candidate, out of remaining halfway route candidates that are the halfway route candidates other than the first halfway route candidate, and determines a second halfway route candidate having a smallest candidate overall cost value out of at least one provisional second halfway route candidate; and
a third determination process that specifies the second halfway route candidate determined by the second determination process, as the first halfway route candidate, specifies the halfway route candidate other than the determined first halfway route candidate and second halfway route candidate, as the remaining halfway route candidate, and repeats the second determination process, and
the route searcher determines the first halfway route candidate and the second halfway route candidate determined by the first to the third determination processes, as the halfway routes.

22 . The route search apparatus according to claim 18 , wherein the route searcher determines, as the halfway route, a halfway route candidate having a smallest candidate overall cost value out of a plurality of the candidate overall cost values, among a plurality of halfway route candidates that are candidates of the halfway route.

23 . The route search apparatus according to claim 18 , wherein when there are a plurality of the candidate overall cost values that are different from each other by at most a predetermined value, out of the candidate overall cost values of a plurality of halfway route candidates that are candidates of the halfway route, the route searcher determines the halfway route, based on one of the first term and the second term that is selected according to the weight coefficient.

24 . The route search apparatus according to claim 18 , wherein
the route searcher performs:
a first determination process that determines a first halfway route candidate having a smallest candidate overall cost value out of a plurality of the candidate overall cost values, among a plurality of halfway route candidates that are candidates of the halfway route;
a second determination process that is performed when there is at least one provisional second halfway route candidate having a smaller integrated value of the average cost values than an integrated value of the average cost values of the first halfway route candidate, out of remaining halfway route candidates that are the halfway route candidates other than the first halfway route candidate, and determines a second halfway route candidate having a smallest candidate overall cost value out of at least one provisional second halfway route candidate; and
a third determination process that specifies the second halfway route candidate determined by the second determination process, as the first halfway route candidate, specifies the halfway route candidate other than the determined first halfway route candidate and second halfway route candidate, as the remaining halfway route candidate, and repeats the second determination process, and
the route searcher determines the first halfway route candidate and the second halfway route candidate determined by the first to the third determination processes, as the halfway routes.

25 . The route search apparatus according to claim 15 ,
wherein when there are a plurality of halfway route candidates that are candidates of a halfway route from the place of depart

Assignees

• Zenrin Co Ltd
• Toyota Motor Co Ltd
• Aisin Aw Co

Inventors

• Masutani Tomohiko
• Tashiro Hiroyuki
• Arita Tomoko
• Nakamura Motohiro
• Kodan Tomoki
• Ikeno Atsushi
• Kato Yoshitaka
• Koshiba Sadahiro
• Maekawa Kazuteru
• Ushida Koichi

Classifications

• G08G1/096838

  where the user preferences are taken into account or the user selects one route out of a plurality · CPC title

• G08G1/096827

  where the route is computed onboard · CPC title

• G01C21/3453 Primary

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title