Method and apparatus for determining route within traffic network
First Claim
Patent Images
1. A method of determining, by use of a computer, a route from a start location to a target location within a traffic network, in which locations are represented as nodes and a route between adjacent nodes is represented as a link, the determination being performed in accordance with a label determination method under the conditions of minimum cost, while travel time or travel distance is evaluated as cost, the method comprising:
- (1) choosing at least one entrance station of a transportation network to be used whose straight-line distance as measured from the start location falls within a predetermined range and at least one exit station of the transportation network whose straight-line distance as measured from the target location falls within the predetermined range, and estimating cost of a walking route from the start location to the entrance station and cost of a walking route from the exit station to the target location, on the basis of the respective straight-line distances, each calculated by use of latitude/longitude data; and
(2) incorporating, as links, the walking routes having estimated costs into a traffic network comprising the transportation network in order to express a comprehensive traffic network to thereby enable the computer to determine a route under desired cost conditions in accordance with the label determination method.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of determining, by use of a computer, a minimum-cost route from a start location to a target location within a traffic network in accordance with a label determination method, in which traffic network locations are represented as nodes and a route between adjacent nodes is represented as a link. The method comprises (1) choosing at least one entrance station of a transportation network to be used whose straight-line distance as measured from the start location falls within a predetermined range and at least one exit station of the transportation network whose straight-line distance as measured from the target location falls within the predetermined range, and estimating cost of a walking route from the start location to the entrance station and cost of a walking route from the exit station to the target location, on the basis of the respective straight-line distances, each calculated by use of latitude/longitude data; and (2) incorporating, as links, the walking routes having estimated costs into a traffic network comprising the transportation network in order to express a comprehensive traffic network to thereby enable the computer to determine a route under desired cost conditions in accordance with the label determination method.
96 Citations
12 Claims
-
1. A method of determining, by use of a computer, a route from a start location to a target location within a traffic network, in which locations are represented as nodes and a route between adjacent nodes is represented as a link, the determination being performed in accordance with a label determination method under the conditions of minimum cost, while travel time or travel distance is evaluated as cost, the method comprising:
-
(1) choosing at least one entrance station of a transportation network to be used whose straight-line distance as measured from the start location falls within a predetermined range and at least one exit station of the transportation network whose straight-line distance as measured from the target location falls within the predetermined range, and estimating cost of a walking route from the start location to the entrance station and cost of a walking route from the exit station to the target location, on the basis of the respective straight-line distances, each calculated by use of latitude/longitude data; and
(2) incorporating, as links, the walking routes having estimated costs into a traffic network comprising the transportation network in order to express a comprehensive traffic network to thereby enable the computer to determine a route under desired cost conditions in accordance with the label determination method. - View Dependent Claims (2)
processing routine (1) in which the start node is labeled with a temporary label (*,
0), and each of the remaining nodes is labeled with a temporary label (Φ
, ∞
) during initial value setting, where “
*”
means that no link reaches the start node, “
Φ
”
means that no link has yet reached the corresponding node, and “
∞
”
means a numerical value which is sufficiently large within the context of a relevant problem;
processing routine (2) in which among nodes bearing temporary labels, a node having the lowest potential is selected, when the selected node is the target location, the route determination being ended, and processing routine (4) being performed, and when the selected node is not the target location, processing routine (3) being performed successively;
processing routine (3) in which the potential of an end node which is linked from the node having the lowest potential and which has a temporary label is calculated, when the thus-calculated potential of the end node is lower than the potential indicated by the temporary label of the end node, the potential indicated by the temporary label of the end node being replaced with the calculated potential of the end node, the temporary label of the node having the lowest potential being rendered permanent, and the processing routine (2) being executed; and
processing routine (4) in which permanent labels are followed backward from the target location to the start location in order to determine a route of lowest potential, including walking routes.
-
-
3. A system for determining, by use of a computer, a route from a start location to a target location within a traffic network, in which locations are represented as nodes and a route between adjacent nodes is represented as a link, the determination being performed in accordance with a label determination method under the conditions of minimum cost, while travel time or travel distance is evaluated as cost, the system comprising:
-
(1) means for choosing at least one entrance station of a transportation network to be used whose straight-line distance as measured from the start location falls within a predetermined range and at least one exit station of the transportation network whose straight-line distance as measured from the target location falls within the predetermined range, and for estimating cost of a walking route from the start location to the entrance station and cost of a walking route from the exit station to the target location, on the basis of the respective straight-line distances, each calculated by use of latitude/longitude data; and
(2) means for incorporating, as links, the walking routes having estimated costs into a traffic network comprising the transportation network in order to express a comprehensive traffic network to thereby enable the computer to determine a route under desired cost conditions in accordance with the label determination method. - View Dependent Claims (4)
processing routine (1) in which the start node is labeled with a temporary label (*,
0), and each of the remaining nodes is labeled with a temporary label (Φ
, ∞
) during initial value setting, where “
*”
means that no link reaches the start node, “
Φ
”
means that no link has yet reached the corresponding node, and “
∞
”
means a numerical value which is sufficiently large within the context of a relevant problem;
processing routine (2) in which among nodes bearing temporary labels, a node having the lowest potential is selected, when the selected node is the target location, the route determination being ended, and processing routine (4) being performed, and when the selected node is not the target location, processing routine (3) being performed successively;
processing routine (3) in which the potential of an end node which is linked from the node having the lowest potential and which has a temporary label is calculated, when the thus-calculated potential of the end node is lower than the potential indicated by the temporary label of the end node, the potential indicated by the temporary label of the end node being replaced with the calculated potential of the end node, the temporary label of the node having the lowest potential being rendered permanent, and the processing routine (2) being executed; and
processing routine (4) in which permanent labels are followed backward from the target location to the start location in order to determine a route of lowest potential, including walking routes.
-
-
5. A computer readable record medium storing therein a program for determining, by use of a computer, a route from a start location to a target location within a traffic network, in which locations are represented as nodes and a route between adjacent nodes is represented as a link, the determination being performed in accordance with a label determination method under the conditions of minimum cost, while travel time or travel distance is evaluated as cost, the program comprising:
-
(1) processing for choosing at least one entrance station of a transportation network to be used whose straight-line distance as measured from the start location falls within a predetermined range and at least one exit station of the transportation network whose straight-line distance as measured from the target location falls within the predetermined range, and for estimating cost of a walking route from the start location to the entrance station and cost of a walking route from the exit station to the target location, on the basis of the respective straight-line distances, each calculated by use of latitude/longitude data; and
(2) processing for incorporating, as links, the walking routes having estimated cost into a traffic network comprising the transportation network in order to express a comprehensive traffic network to thereby enable the computer to determine a route under desired cost conditions in accordance with the label determination method. - View Dependent Claims (6)
processing routine (1) in which the start node is labeled with a temporary label (*,
0), and each of the remaining nodes is labeled with a temporary label (Φ
, ∞
) during initial value setting, where “
*”
means that no link reaches the start node, “
Φ
”
means that no link has yet reached the corresponding node, and “
∞
”
means a numerical value which is sufficiently large within the context of a relevant problem;
processing routine (2) in which among nodes bearing temporary labels, a node having the lowest potential is selected, when the selected node is the target location, the route determination being ended, and processing routine (4) being performed, and when the selected node is not the target location, processing routine (3) being performed successively;
processing routine (3) in which the potential of an end node which is linked from the node having the lowest potential and which has a temporary label is calculated, when the thus-calculated potential of the end node is lower than the potential indicated by the temporary label of the end node, the potential indicated by the temporary label of the end node being replaced with the calculated potential of the end node, the temporary label of the node having the lowest potential being rendered permanent, and the processing routine (2) being executed; and
processing routine (4) in which permanent labels are followed backward from the target location to the start location in order to determine a route of lowest potential, including walking routes.
-
-
7. A method of determining, by use of a computer, a route from a start location to a target location within a traffic network, in which traffic network locations are represented as nodes and a route between adjacent nodes is represented as a link, the determination being performed in accordance with a label determination method under the conditions of minimum cost, while travel time or travel distance is evaluated as cost, the method comprising:
-
(1) calculating cost of a walking route from the start location to at least one entrance station of a transportation network to be used and cost of a walking route from at least one exit station of the transportation network to the target location, the cost involved in each of the walking routes falling within a designated cost range, and the walking routes being determined by a label determination method which utilizes a road network created from map data including latitude/longitude information and which determines the walking routes under desired cost conditions; and
(2) incorporating, as links, the walking routes having calculated costs into a traffic network comprising the transportation network in order to express a comprehensive traffic network to thereby enable the computer to determine a route under desired cost conditions in accordance with the label determination method. - View Dependent Claims (8)
processing routine (1) in which the start node is labeled with a temporary label (*,
0), and each of the remaining nodes is labeled with a temporary label (Φ
, ∞
) during initial value setting, where “
*”
means that no link reaches the start node, “
Φ
”
means that no link has yet reached the corresponding node, and “
∞
”
means a numerical value which is sufficiently large within the context of a relevant problem;
processing routine (2) in which among nodes bearing temporary labels, a node having the lowest potential is selected, when the selected node is the target location, the route determination being ended, and processing routine (4) being performed, and when the selected node is not the target location, processing routine (3) being performed successively;
processing routine (3) in which the potential of an end node which is linked from the node having the lowest potential and which has a temporary label is calculated, when the thus-calculated potential of the end node is lower than the potential indicated by the temporary label of the end node, the potential indicated by the temporary label of the end node being replaced with the calculated potential of the end node, the temporary label of the node having the lowest potential being rendered permanent, and the processing routine (2) being executed; and
processing routine (4) in which permanent labels are followed backward from the target location to the start location in order to determine a route of lowest potential, including walking routes.
-
-
9. A system of determining, by use of a computer, a route from a start location to a target location within a traffic network, in which locations are represented as nodes and a route between adjacent nodes is represented as a link, the determination being performed in accordance with a label determination method under the conditions of minimum cost, while travel time or travel distance is evaluated as cost, the system comprising:
-
(1) means for calculating cost of a walking route from the start location to at least one entrance station of a transportation network to be used and cost of a walking route from at least one exit station of the transportation network to the target location, the cost involved in each of the walking routes falling within a designated cost range, and the walking routes being determined by a label determination method which utilizes a road network created from map data including latitude/longitude information and which determines the walking routes under desired cost conditions; and
(2) means for incorporating, as links, the walking routes having calculated costs into a traffic network comprising the transportation network in order to express a comprehensive traffic network to thereby enable the computer to determine a route under desired cost conditions in accordance with the label determination method. - View Dependent Claims (10)
processing routine (1) in which the start node is labeled with a temporary label (*,
0), and each of the remaining nodes is labeled with a temporary label (Φ
, ∞
) during initial value setting, where “
*”
means that no link reaches the start node, “
Φ
”
means that no link has yet reached the corresponding node, and “
∞
”
means a numerical value which is sufficiently large within the context of a relevant problem;
processing routine (2) in which among nodes bearing temporary labels, a node having the lowest potential is selected, when the selected node is the target location, the route determination being ended, and processing routine (4) being performed, and when the selected node is not the target location, processing routine (3) being performed successively;
processing routine (3) in which the potential of an end node which is linked from the node having the lowest potential and which has a temporary label is calculated, when the thus-calculated potential of the end node is lower than the potential indicated by the temporary label of the end node, the potential indicated by the temporary label of the end node being replaced with the calculated potential of the end node, the temporary label of the node having the lowest potential being rendered permanent, and the processing routine (2) being executed; and
processing routine (4) in which permanent labels are followed backward from the target location to the start location in order to determine a route of lowest potential, including walking routes.
-
-
11. A computer readable record medium storing therein a program for determining, by use of a computer, a route from a start location to a target location within a traffic network, in which locations are represented as nodes and a route between adjacent nodes is represented as a link, the determination being performed in accordance with a label determination method under the conditions of minimum cost, while travel time or travel distance is evaluated as cost, the program comprising:
-
(1) processing for calculating cost of a walking route from the start location to at least one entrance station of a transportation network to be used and cost of a walking route from at least one exit station of the transportation network to the target location, the cost involved in each of the walking routes falling within a designated cost range, and the walking routes being determined by a label determination method which utilizes a road network created from map data including latitude/longitude information and which determines the walking routes under desired cost conditions; and
(2) processing for incorporating, as links, the walking routes having calculated costs into a traffic network comprising the transportation network in order to express a comprehensive traffic network to thereby enable the computer to determine a route under desired cost conditions in accordance with the label determination method. - View Dependent Claims (12)
processing routine (1) in which the start node is labeled with a temporary label (*,
0), and each of the remaining nodes is labeled with a temporary label (Φ
, ∞
) during initial value setting, where “
*”
means that no link reaches the start node, “
Φ
”
means that no link has yet reached the corresponding node, and “
∞
”
means a numerical value which is sufficiently large within the context of a relevant problem;
processing routine (2) in which among nodes bearing temporary labels, a node having the lowest potential is selected, when the selected node is the target location, the route determination being ended, and processing routine (4) being performed, and when the selected node is not the target location, processing routine (3) being performed successively;
processing routine (3) in which the potential of an end node which is linked from the node having the lowest potential and which has a temporary label is calculated, when the thus-calculated potential of the end node is lower than the potential indicated by the temporary label of the end node, the potential indicated by the temporary label of the end node being replaced with the calculated potential of the end node, the temporary label of the node having the lowest potential being rendered permanent, and the processing routine (2) being executed; and
processing routine (4) in which permanent labels are followed backward from the target location to the start location in order to determine a route of lowest potential, including walking routes.
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeNavitime Japan Co. Ltd.
-
Original AssigneeNavitime Japan Co. Ltd.
-
InventorsKikuchi, Shin, Ohnishi, Keisuke
-
Primary Examiner(s)Nguyen, Tan
-
Assistant Examiner(s)Tran, Dalena
-
Application NumberUS09/520,219Time in Patent Office714 DaysField of Search701/202, 701/209, 701/207, 701/212, 701/200, 701/201, 701/211, 701/210, 701/26, 701/208, 340/955, 340/988US Class Current701/209CPC Class CodesG01C 21/34 Route searching; Route guid...G01C 21/3423 Multimodal routing, i.e. co...
