Method of and apparatus for generating routes
First Claim
1. A method of generating a plurality of diverse routes from a source to a destination in a weighted directed graph, comprising the steps of:
- generating a source routing tree from the source to a first set of points of the graph;
generating a destination routing tree from a second set of points of the graph to the destination; and
combining the source and destination trees to form the routes;
wherein the combining step comprises selecting each sub-route common to and traversed in the same direction by the source and destination trees.
1 Assignment
0 Petitions
Accused Products
Abstract
A method is provided of generating a plurality of diverse routes from a source to a destination in a weighted directed graph. Such a method may be used for route planning or navigation with the weighted directed graph representing a road network, but may also be used in other applications. A source routing tree is generated from the source to a first set of points of the graph, which may comprise some or all of the points. A destination routing tree is generated from some or all of the points of the graph to the destination. The trees are then combined to form the routes. For example, the sub-routes common to and transverses in the same direction by the source and destination trees may be selected. The sub routes may then be formed into the routes by extending each sub-route as necessary to the source and destination along the source and destination trees.
-
Citations
46 Claims
-
1. A method of generating a plurality of diverse routes from a source to a destination in a weighted directed graph, comprising the steps of:
-
generating a source routing tree from the source to a first set of points of the graph; generating a destination routing tree from a second set of points of the graph to the destination; and combining the source and destination trees to form the routes; wherein the combining step comprises selecting each sub-route common to and traversed in the same direction by the source and destination trees. - View Dependent Claims (2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 14, 15, 16, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46)
-
-
7. A method of generating a plurality of diverse routes from a source to a destination in a weighted directed graph, comprising the steps of:
-
generating a source routing tree from the source to a first set of points of the graph; generating a destination routing tree from a second set of points of the graph to the destination; and combining the source and destination trees to form the routes; wherein the graph comprises a first set of links, each of which has a first priority of use, and a second set of links, each of which has a second priority of use greater than the first priority, and wherein the first set of points comprises points interconnected by the links of the first or second set in a first region of the graph containing the source and points interconnected by the links of the second set but not of the first set in a second region of the graph outside the first region.
-
-
8. A method of generating a plurality of diverse routes from a source to a destination in a weighted directed graph, comprising the steps of:
-
generating a source routing tree from the source to a first set of points of the graph; generating a destination routing tree from a second set of points of the graph to the destination; and combining the source and destination trees to form the routes; wherein the graph comprises a first set of links, each of which has a first priority of use, and a second set of links, each of which has a second priority of use greater than the first priority, and wherein the second set of points comprises points interconnected by the links of the first or second set in a third region of the graph containing the destination and points interconnected by the links of the second set but not of the first set in a fourth region of the graph outside the third region.
-
-
17. A method of generating a plurality of diverse routes from a source to a destination in a weighted directed graph, comprising the steps of:
-
generating a source routing tree from the source to a first set of points of the graph; generating a destination routing tree from a second set of points of the graph to the destination; and combining the source and destination trees to form the routes; and assigning a goodness value to each route, wherein the combining step comprises selecting each sub-route common to and traversed in the same direction by the source and destination trees, wherein the combining step further comprises extending each sub-route as necessary to the source and destination along the source and destination trees to form one of the routes, and wherein the measure is a function of the length of the sub-route and the length of the route. - View Dependent Claims (18)
-
Specification