Method and apparatus for mixed static and dynamic routing

• US 8,812,228 B2
• Filed: 12/10/2009
• Issued: 08/19/2014
• Est. Priority Date: 12/10/2009
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq B.V.
• Inventors: Konig, Mirko
• Primary Examiner(s): Tran, Dalena
• Application Number:
  US12/635,457
• Publication Number:
  US 20110144898A1
• Time in Patent Office: 1,713 Days
• Field of Search: 701/400, 701408-412, 701/418, 701/426, 701/467, 701/469, 340/988, 340/995.1, 340/995.19, 455/456.1, 455/456.2, 455/457
• US Class Current: 701/400
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing

Abstract

Techniques for mixed static and dynamic routing include determining a subset of less than all of a plurality of stopover points of an initial route of ordered stopover points. In the subset, all stopover points are marked as dynamic to indicate that their order is allowed to change. It is also determined whether there are at least two stopover points for which order may be changed. If there are at least two stopover points for which order may be changed, then a computed route is determined in which an order in the computed route of the stopover points of the subset minimizes a metric for the entire route compared to any other allowed order of the stopover points of the subset.

Claims

1. A method comprising:

determining, by a processor, a subset of less than all of a plurality of stopover points of an initial route of ordered stopover points that are marked as dynamic to indicate that their order is changeable, the subset including one or more other subsets of less than all of the stopover points of the subset;

determining whether there are at least two stopover points for which order is changeable; and

if there are at least two stopover points for which order is changeable, then causing a computed route to be determined in which an order in the route of the stopover points of the subset minimizes a metric for the entire route compared to any other allowed order of the stopover points of the subset.

2. A method of claim 1, wherein:

causing the computed route to be determined further comprises causing the marked stopover points to be sent to a navigation service; and

in response to causing the marked stopover points to be sent, receiving the computed route from the navigation service.

3. A method of claim 1, wherein determining the subset of stopover points marked as dynamic, comprises receiving from a navigation client data that indicates the initial route of ordered stopover points and the stopover points marked as dynamic.

4. A method of claim 1, wherein:

at least one stopover point not in the subset is marked fixed to indicate that the at least one stopover point retains an original overall position in the computed route; and

causing the computed route to be determined further comprises causing the computed route to be determined so that the at least one stopover point marked fixed retains an original overall position in the computed route.

5. A method of claim 4, wherein:

at least one stopover point in the subset is marked no jump dynamic to indicate that the at least one stopover point is prevented from changing order relative to the at least one stopover point marked fixed; and

causing the computed route to be determined further comprises causing the computed route to be determined so that the at least one no jump dynamic stopover point does not change order relative to the at least one stopover point marked fixed.

6. A method of claim 1, further comprising determining the plurality of stopover points of the route based on data received from a social networking service.

7. A method of claim 1, further comprising causing the computed route to be sent to a social networking service.

8. A method of claim 1, further comprising determining a time constraint for a corresponding stopover point of the route;

and causing the computed route to be determined further comprises causing the computed route to be determined so that a user arrives at the corresponding stopover point at a time that satisfies the time constraint.

9. A method of claim 8, wherein determining the time constraint further comprises determining the time constraint based on data received from a social networking service.

10. A method of claim 1, further comprising:

determining a contact constraint for a corresponding stopover point of the route, wherein a contact constraint determines what contacts of a user are present in a vicinity of the corresponding stopover point; and

causing the computed route to be determined further comprises causing the computed route to be determined so that a user arrives at the corresponding stopover point when conditions satisfy a contact constraint.

11. A method of claim 1, wherein the metric for the entire route is based at least in part on external real time data.

12. An apparatus comprising:

at least one processor; and

at least one memory including computer program code,

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following;

determine a subset of less than all of a plurality of stopover points of an initial route of ordered stopover points that are marked as dynamic to indicate that their order is changeable, the subset including one or more other subsets of less than all of the stopover points of the subset;

determine whether there are at least two stopover points for which order is changeable; and

if there are at least two stopover points for which order is changeable, then cause a computed route to be determined in which an order in the route of the stopover points of the subset minimizes a metric for the entire route compared to any other allowed order of the stopover points of the subset.

13. An apparatus of claim 12, wherein:

at least one stopover point not in the subset is marked fixed to indicate that the at least one stopover point retains an original overall position in the computed route; and

causing the computed route to be determined further comprises causing the computed route to be determined so that the at least one stopover point marked fixed retains an original overall position in the computed route.

14. An apparatus of claim 13, wherein:

at least one stopover point in the subset is marked no jump dynamic to indicate that the at least one stopover point is prevented from changing order relative to the at least one stopover point marked fixed; and

causing the computed route to be determined further comprises causing the computed route to be determined so that the at least one no jump dynamic stopover point does not change order relative to the at least one stopover point marked fixed.

15. An apparatus of claim 12, wherein the apparatus is further caused, at least in part, to determine a time constraint for a corresponding stopover point of the route;

and causing the computed route to be determined further comprises causing the computed route to be determined so that a user arrives at the corresponding stopover point at a time that satisfies the time constraint.

16. An apparatus of claim 12, wherein the apparatus is a mobile phone further comprising:

user interface circuitry and user interface software configured to facilitate user control of at least some functions of the mobile phone through use of a display and configured to respond to user input; and

a display and display circuitry configured to display at least a portion of a user interface of the mobile phone, the display and display circuitry configured to facilitate user control of at least some functions of the mobile phone.

17. A computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:

determine a subset of less than all of a plurality of stopover points of an initial route of ordered stopover points that are marked as dynamic to indicate that their order is changeable, the subset including one or more other subsets of less than all of the stopover points of the subset;

determine whether there are at least two stopover points for which order is changeable; and

if there are at least two stopover points for which order is changeable, then determine a computed route in which an order in the route of the stopover points of the subset minimizes a metric for the entire route compared to any other allowed order of the stopover points of the subset.

18. A computer-readable storage medium of claim 17, wherein:

at least one stopover point not in the subset is marked fixed to indicate that the at least one stopover point retains an original overall position in the computed route; and

causing the computed route to be determined further comprises causing the computed route to be determined so that the at least one stopover point marked fixed retains an original overall position in the computed route.

19. A computer-readable storage medium of claim 18, wherein:

at least one stopover point in the subset is marked no jump dynamic to indicate that the at least one stopover point is prevented from changing order relative to the at least one stopover point marked fixed; and

causing the computed route to be determined further comprises causing the computed route to be determined so that the at least one no jump dynamic stopover point does not change order relative to the at least one stopover point marked fixed.

20. A computer-readable storage medium of claim 17, wherein the apparatus is caused, at least in part, to further determine a time constraint for a corresponding stopover point of the route;

and causing the computed route to be determined further comprises causing the computed route to be determined so that a user arrives at the corresponding stopover point at a time that satisfies the time constraint.