Path searching method and path search device

• US 9,482,543 B2
• Filed: 03/12/2013
• Issued: 11/01/2016
• Est. Priority Date: 03/15/2012
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Shinagawa, Akio, Tamai, Kyohei
• Primary Examiner(s): LANG, MICHAEL DEAN
• Application Number:
  US13/796,559
• Publication Number:
  US 20130245940A1
• Time in Patent Office: 1,330 Days
• Field of Search: 701408-540
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

A computer determines to which of a plurality of levels each of a plurality of road types for which a path search is performed corresponds, according to a distance between a departure point and a destination point. Next, the computer performs a first path search for the road type associated with a first level from the departure point to the destination point, and a second path search for the road type associated with the first level from the destination point to the departure point. Then, the computer performs a third path search for the road type associated with a second level according to a point obtained in the first path search and a point obtained in the second path search, and generates path information according to a result of the first path search, the second path search, and the third path search.

Claims

1. A path searching method performed by a computer, the method comprising:

determining a classification pattern from a plurality of classification patterns by using a distance between a departure point and a destination point, each of the plurality of classification patterns comprising a plurality of road types classified into one of a plurality of levels and representing a correspondence between the plurality of levels and the plurality of road types, each of the plurality of classification patterns corresponding to one of a plurality of distance ranges, wherein the determining the classification pattern includes determining that a same road type belongs to a different level among the plurality of levels depending on which of the plurality of distance ranges the distance belongs to;

performing, by using a processor, a first path search from the departure point to the destination point and a second path search from the destination point to the departure point while changing a search target from a road type at a lower level to a road type at a higher level according to the determined classification pattern;

performing, by using the processor, a third path search from the departure point to the destination point for a road network including a first network, a second network and a third network, wherein the first network includes a group of road links obtained by the first path search, the second network includes a group of road links obtained by the second path search and the third network includes a group of road links of a road type at a highest level in the determined classification pattern; and

generating path information according to a result of the third path search.

2. The path searching method according to claim 1, further comprising

when the distance belongs to a specific distance range among the plurality of distance ranges and a road associated with a level other than a specific level among the plurality of levels exists between two roads that are associated with the specific level, changing the level of the road associated with the level other than the specific level to the specific level.

3. A path search device comprising

a processor configured to execute a process including:

determining a classification pattern from a plurality of classification patterns by using a distance between a departure point and a destination point, each of the plurality of classification patterns comprising a plurality of road types classified into one of a plurality of levels and representing a correspondence between the plurality of levels and the plurality of road types, each of the plurality of classification patterns corresponding to one of a plurality of distance ranges, wherein the determining the classification pattern includes determining that a same road type belongs to a different level among the plurality of levels depending on which of the plurality of distance ranges the distance belongs to;

performing a first path search from the departure point to the destination point and a second path search from the destination point to the departure point while changing a search target from a road type at a lower level to a road type at a higher level according to the determined classification pattern;

performing a third path search from the departure point to the destination point for a road network including a first network, a second network and a third network, wherein the first network includes a group of road links obtained by the first path search, the second network includes a group of road links obtained by the second path search and the third network includes a group of road links of a road type at a highest level in the determined classification pattern; and

generating path information according to a result of the third path search.

4. A computer-readable recording medium having stored therein a program for causing a computer to execute a process comprising:

determining a classification pattern from a plurality of classification patterns by using a distance between a departure point and a destination point, each of the plurality of classification patterns comprising a plurality of road types classified into one of a plurality of levels and representing a correspondence between the plurality of levels and the plurality of road types, each of the plurality of classification patterns corresponding to one of a plurality of distance ranges, wherein the determining the classification pattern includes determining that a same road type belongs to a different level among the plurality of levels depending on which of the plurality of distance ranges the distance belongs to;

performing a first path search from the departure point to the destination point and a second path search from the destination point to the departure point while changing a search target from a road type at a lower level to a road type at a higher level according to the determined classification pattern;

performing a third path search from the departure point to the destination point for a road network including a first network, a second network and a third network, wherein the first network includes a group of road links obtained by the first path search, the second network includes a group of road links obtained by the second path search and the third network includes a group of road links of a road type at a highest level in the determined classification pattern; and

generating path information according to a result of the third path search.

5. A path searching method performed by a computer, the method comprising:

determining a classification pattern from a plurality of classification patterns by using a distance between a departure point and a destination point, each of the plurality of classification patterns comprising a plurality of road types classified into one of a plurality of levels and representing a correspondence between the plurality of levels and the plurality of road types, each of the plurality of classification patterns corresponding to one of a plurality of distance ranges, wherein the determined classification pattern corresponds to a distance range including the distance between the departure point and the destination point;

performing, by using a processor, a first path search from the departure point to the destination point and a second path search from the destination point to the departure point while changing a search target from a road type at a lower level to a road type at a higher level according to the determined classification pattern;

performing, by using the processor, a third path search from the departure point to the destination point for a road network including a first network, a second network and a third network, wherein the first network includes a group of road links obtained by the first path search, the second network includes a group of road links obtained by the second path search and the third network includes a group of road links of a road type at a highest level in the determined classification pattern; and

generating path information according to a result of the third path search.

6. The path searching method according to claim 5, further comprising

when the distance belongs to a specific distance range among the plurality of distance ranges and a road associated with a level other than a specific level among the plurality of levels exists between two roads that are associated with the specific level, changing the level of the road associated with the level other than the specific level to the specific level.

7. A path search device comprising

a processor configured to execute a process including:

determining a classification pattern from a plurality of classification patterns by using a distance between a departure point and a destination point, each of the plurality of classification patterns comprising a plurality of road types classified into one of a plurality of levels and representing a correspondence between the plurality of levels and the plurality of road types, each of the plurality of classification patterns corresponding to one of a plurality of distance ranges, wherein the determined classification pattern corresponds to a distance range including the distance between the departure point and the destination point;

performing a first path search from the departure point to the destination point and a second path search from the destination point to the departure point while changing a search target from a road type at a lower level to a road type at a higher level according to the determined classification pattern;

performing a third path search from the departure point to the destination point for a road network including a first network, a second network and a third network, wherein the first network includes a group of road links obtained by the first path search, the second network includes a group of road links obtained by the second path search and the third network includes a group of road links of a road type at a highest level in the determined classification pattern; and

generating path information according to a result of the third path search.

8. A computer-readable recording medium having stored therein a program for causing a computer to execute a process comprising:

determining a classification pattern from a plurality of classification patterns by using a distance between a departure point and a destination point, each of the plurality of classification patterns comprising a plurality of road types classified into one of a plurality of levels and representing a correspondence between the plurality of levels and the plurality of road types, each of the plurality of classification patterns corresponding to one of a plurality of distance ranges, wherein the determined classification pattern corresponds to a distance range including the distance between the departure point and the destination point;

performing a first path search from the departure point to the destination point and a second path search from the destination point to the departure point while changing a search target from a road type at a lower level to a road type at a higher level according to the determined classification pattern;

performing a third path search from the departure point to the destination point for a road network including a first network, a second network and a third network, wherein the first network includes a group of road links obtained by the first path search, the second network includes a group of road links obtained by the second path search and the third network includes a group of road links of a road type at a highest level in the determined classification pattern; and

generating path information according to a result of the third path search.