Route Searching Device, Route Searching Method and Program

• US 20070239349A1
• Filed: 07/20/2004
• Published: 10/11/2007
• Est. Priority Date: 07/20/2004
• Status: Active Grant

• Current Assignee: Navitime Japan Co. Ltd.
• Original Assignee: Navitime Japan Co. Ltd.
• Inventors: Kikuchi, Shin, Ohnishi, Keisuke
• Granted Patent: US 7,587,273 B2
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3423 Multimodal routing, i.e. combining two or more modes of transportation, where the modes can be any of, e.g. driving, walking, cycling, public transport
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A route seeking device, a route seeking method, and a program capable of determining a guide route requiring a small number of transfers of transportation means by a single route seek. In the route seeking device comprising a route seeking section for seeking a route from a start point to a goal with reference to a route network DB consisting of nodes, links to which attribute information representing the groups to which the links belong is added, and costs. The route seeking section calculates a specific upper-order bit in a link cost accumulation value memory of the link as logic “1” such that the potential at the reached node of a spreading node exceeds a potential assumed in route seek if the attribute information on the tracked link is different from that of a link spreading from the reached node with the potential at the reached node is calculated by accumulating the costs of the links along an outgoing link from the start node, and outputs the thus determined route of minimum accumulation cost as a guide route requiring the smallest number of transfers.

Claims

1. A route searching device provided with route terminal points, intersections and branching points as nodes, which comprises links which connect the nodes, a route network database containing the corresponding costs of the links, and a route searching section which uses a label setting method for searching a route from a starting point to a destination by referring to the route network database,

whereby each link is stored in the route network database comprising attribute information which represents a group to which such link belongs;

the route searching section calculates a specific upper-order bit in the link cost cumulative value memory of such link as logic “

1”

, where the potential of a link spreading at a node reached by the user exceeds the potential assumed in route searching if the attribute information on the tracked link is different from that of the link spreading from the node reached when the potential at the node reached is calculated by summing up the costs of the links along an outgoing link from the starting point node; and

the route searching section outputs the thus-determined route with lowest accumulated cost as the guide route requiring the least number of link attribute changes.

2. The route searching device according to claim 1, wherein the route searching section performs the following functions:

store, in a working memory, a link cost cumulative value on the tracked link if the attribute information on the tracked link is the same as the attribute information of a spreading link, and stores in the working memory a specific upper-order bit in a link cost cumulative value memory of the said link as logic “

1”

such that the potential at the node reached by a spreading link exceeds the potential assumed in route searching if the attribute information on the tracked link is different from the attribute information of the spreading link;

sort the link cost cumulative values stored in the said working memory; and

count the number of link attribute changes in the route search being conducted if, from the sorting results, the link having the lowest link cost cumulative value is a link whose specific upper-order bit in the link cost cumulative value memory was set to logic “

1”

due to differences in link attributes.

3. The route searching device according to claim 2, wherein the route searching section counts the number of link attribute changes in the route search being conducted, and, continues the route search by restoring the cost of the link whose specific upper-order bit in the link cost cumulative value memory was set to logic “

1”

due to differences in link attributes, to the actual link cost value.

4. The route searching device according to any one of claims 1 to 3, wherein the route searching section carries out a route search by limiting the number of times that the attributes of such a link may change to a certain number.

5. A route searching method having route terminal points, intersections and branching points as nodes, which comprises links which connect the nodes, a route network database containing the corresponding costs of the links, and a route searching section which uses a label setting method for searching a route from a starting point to a destination by referring to the route network database, whereby each link is stored in the route network database comprising attribute information which represents a group to which such link belongs, and comprises the following steps:

the route searching section calculates a specific upper-order bit in a link cost cumulative value memory of such link as logic “

1”

such that the potential at the node reached by a spreading link exceeds the potential assumed in route searching if the attribute information on the tracked link is different from that of the link spreading from the node reached when the potential thereat is calculated, by adding up the costs of the links along an outgoing link from the starting point node; and

the route searching section outputs the thus-determined route of lowest cumulative cost as a guide route requiring the least number of link attribute changes.

6. The route searching method according to claim 5, wherein the route searching section performs the following steps:

store in a working memory the link cost cumulative value on the tracked link if the attribute information on the tracked link is the same as the attribute information of a spreading link, and store in the working memory a specific upper-order bit in the link cost cumulative value memory of such link as logic “

1”

where the potential at the node reached by a spreading link exceeds the potential assumed in route searching if the attribute information on the tracked link is different from the attribute information of such spreading link;

sort the link cost cumulative values stored in the said working memory; and

count the number of attribute changes of the link in the route search if, from the sorting results, the link having the lowest link cost cumulative value is a link whose specific upper-order bit in the link cost cumulative value memory was set to logic “

1”

, due to differences in link attributes.

7. The route searching method according to claim 6 comprising a method wherein the route searching section counts the number of link attribute changes in the route search, and, continues the route search by restoring the link cost of the link whose specific upper-order bit in a link cost cumulative value memory was set to logic “

1”

due to differences in link attributes, to the actual link cost value.

8. The route searching method according to any one of claims 5 to 7, wherein the route searching section carries out a route search by limiting the number of times that the attributes of the link may change to a certain number.

9. A program for a computer comprising a route searching device providing nodes consisting of the terminal points, intersections and diverging points of a route, and links connecting the nodes, a route network database containing the corresponding costs of the links, and a route searching section which uses a label setting method for searching a route from a starting point to a certain destination by referring to the said route network database, wherein each link which is recorded in the route network database comprising attribute information which represents a group to which such link belongs, characterized by executing:

an operation which calculates a specific upper-order bit in a link cost cumulative value memory of the link as logic “

1”

where the potential at the node reached by a spreading link exceeds the potential assumed in route searching if the attribute information on the tracked link is different from the attribute information of such spreading link when the potential at the reached node is calculated by accumulating the costs of the links along an outgoing link from the starting point node; and

an operation which outputs the thus-determined route of lowest cumulative cost as a guide route requiring the least number of link attribute changes.

10. The program for a computer comprising the route searching device according to claim 9, wherein the route searching section executes:

an operation which stores in a working memory the link cost cumulative value of the tracked link if the attribute information on the tracked link is the same as the attribute information of a spreading link as logic “

1”

, and stores in the working memory a specific upper-order bit in the link cost cumulative value memory of such link as logic “

1”

wherein the potential cost at the reached node of a spreading link exceeds the potential cost assumed in route searching if the attribute information on the tracked link is different from the attribute information of the spreading link;

an operation which sorts the link cost cumulative values stored in the working memory; and

an operation which counts the number of attribute changes of the link in the route search if, from the sorting results, the link having the lowest link cost cumulative value is a link whose specific upper-order bit in a link cost cumulative value memory was set to logic “

1”

due to differences in link attributes.

11. The program for a computer comprising the route searching device according to claim 10, wherein the route searching section executes an operation which counts the number of link attribute changes in the route search, and, continues the route search by restoring the link cost of the link whose specific upper-order bit in the link cost cumulative value memory was set to logic “

1”

, due to differences in link attributes, to the actual link cost value.

12. The program for a computer comprising the route searching device according to any one of claims 9 to 11, wherein the route searching section carries out a route search by limiting the frequency by which the attributes of such link may change to a certain number.