METHOD OF AND APPARATUS FOR GENERATING ROUTES

• US 20100036606A1
• Filed: 09/18/2007
• Published: 02/11/2010
• Est. Priority Date: 10/30/2006
• Status: Active Grant

• Current Assignee: Cotares Limited
• Original Assignee: Cotares Limited
• Inventors: Jones, Alan Henry
• Granted Patent: US 8,249,810 B2
• Time in Patent Office: Days
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• CPC Class Codes: G09B 29/106 using electronic means
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/34 Source routing

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.

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.

2. The method of claim 1, wherein the first set comprises all of the points of the graph.

3. The method of claim 1, wherein the second set comprises all of the points of the graph.

4. The method of claim 1, wherein the first and second sets comprise points of the graph adjacent both the source and the destination.

5. The method of claim 1, wherein the first and second sets comprise the same points.

6. The method of claim 1, 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.

7. The method of claim 6, 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. The method of claim 6, 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.

9. The method of claim 1, wherein the source and destination trees are minimum cost trees.

10. The method of claim 1, wherein the combining step comprises selecting each sub-route common to and traversed in the same direction by the source and destination trees.

11. The method of claim 10, wherein the source and destination trees include back-pointers and the sub-routes are selected by finding sequences of adjacent points which are pointed to by back-pointers of both the source and destination trees.

12. The method of claim 10, wherein the points of the source and destination trees are associated with costs and the sub-routes are selected by finding sequences of adjacent points for which the sums of the costs from the source and destination trees are the same.

13. The method of claim 10, 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.

14. The method of claim 10, wherein the points of the source and destination trees are associated with costs and the sub-routes are selected by finding sequences of adjacent points for which the sums of the costs from the source and destination trees are the same, 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 further comprising selecting at least one via point which is not on any sub-route or extended sub-route, calculating from the source and destination trees a minimum cost route from the source via the at least one via point to the destination, and comparing the calculated cost with the same sum of the costs for at least one of the selected sub-routes.

15. The method of claim 14, further comprising forming the difference between the or each calculated cost and the same sum for the selected sub-route.

16. The method of claim 15, further comprising deselecting the or each via point for which the difference between the calculated cost and the same sum is greater than a threshold.

17. The method of claim 1, further comprising assigning a measure of goodness to each route.

18. The method of claim 17, 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.

19. The method of claim 18, wherein the measure is a function of the difference between the length of the sub-route and the length of the route.

20. The method of claim 17, further comprising selecting only some of the routes in accordance with the measures of goodness.

21. The method of claim 20, further comprising selecting the N routes of highest measure of goodness, where N is a positive integer.

22. The method of claim 20, further comprising selecting at least some of the routes whose measures of goodness are greater than a threshold.

23. The method of claim 1, further comprising storing at least one of the routing trees.

24. The method of claim 1, wherein the graph comprises links associated with costs.

25. The method of claim 24, wherein the cost of traversing each of the at least some links varies with a parameter of traversal.

26. The method of claim 25, wherein the cost of traversing each of the at least some links varies with the time of traversal.

27. The method of claim 25, wherein the first of the generating steps to be performed includes calculating and storing the costs of the links for the prevailing transversal parameter values and the stored costs are used during the second of the generating steps to be performed.

28. The method of claim 27, wherein the destination tree generating step is performed before the source tree generating step.

29. The method of claim 1, wherein the routes are ordered in accordance with at least one property of each route.

30. The method of claim 29, further comprising assigning a measure of goodness to each route, wherein the property is the measure of goodness.

31. The method of claim 1, wherein the graph represents a road network and the routes are road routes.

32. The method of claim 1, wherein the graph represents an integrated circuit or a printed circuit and the routes are interconnections.

33. The method of claim 1, wherein the graph represents a wiring installation and the routes are wiring interconnections.

34. The method of claim 32, further comprising:

assigning a measure of goodness to each route;

selecting only some of the routes in accordance with the measures of goodness; and

choosing the order of placement of the interconnections in accordance with at least one of the number of selected routes and the measures of goodness.

35. The method of claim 34, wherein the interconnections with the lowest numbers of selected routes are placed first.

36. The method of claim 1, wherein the graph represents a communication network and the routes are communication paths.

37. The method of claim 36, wherein the network is an internet.

38. A method of navigation, including generating road routes by a method as claimed in claim 31.

39. The method of claim 38, further comprising presenting information about the road routes to a user.

40. The method of claim 39, further comprising presenting information about a choice of routes from a point from which a plurality of routes diverge when the user approaches the point.

41. The method of claim 40, wherein the information is displayed in a form representing a road sign.

42. The method of claim 38, further comprising offering guidance to a user along a selected one of the routes.

43. The method of claim 42, 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 further comprising offering guidance, when the user leaves the selected route, to the sub-route of the selected route.

44. A computer program for performing a method as claimed in claim 1.

45. A computer-readable medium carrying a program as claimed in claim 44.

46. Transmission across a communication path of a program as claimed in claim 44.

47. A computer programmed to perform a program as claimed in claim 44.

48. A computer containing a program as claimed in claim 44.

49. An apparatus arranged to perform a method as claimed in claim 1.