Calculating an optimal route based on specified intermediate stops

• US 10,386,197 B2
• Filed: 05/17/2016
• Issued: 08/20/2019
• Est. Priority Date: 05/17/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Salowitz, Elizabeth Picchietti, Thomas, Myron Clifford
• Primary Examiner(s): Mawari, Redhwan K
• Assistant Examiner(s): Torchinsky, Edward
• Application Number:
  US15/157,169
• Publication Number:
  US 20170336221A1
• Time in Patent Office: 1,190 Days
• Field of Search: None
• 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: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G01C 21/3605 Destination input or retrieval
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G01C 21/3682 output of POI information on a road map G01C21/3614, G01C21/3685 take precedence
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 30/0282 Rating or review of business operators or products
• CPC Class Codes: G06Q 50/10 Services

Abstract

Calculating an optimal route based on specified intermediate stops is described herein. A mapping application is configured to compute a route from a start point to an end point in dependence upon criteria specifying one or more intermediate stops. The initial route determination incorporates consideration of the one or more specified intermediate stops as part of calculating the route. In one example, a request is received to search for an intermediate stop that satisfies search criteria indicating at least a type of location. In response to the search, search results are obtained with multiple options for routes between the start point and end point including intermediate stops that satisfy the search criteria. An optimal route is selected from the multiple options based upon defined optimization criteria. Optimization criteria may include but is not limited to distance, travel time, traffic data, weather conditions, date and time, and so forth.

Claims

1. A method implemented by a computing device comprising:

receiving a route search input comprising a start point, an end point, and an intermediate stop before a route is generated, the intermediate stop corresponding to search criteria indicating at least a type of location of the intermediate stop;

responsive to the route search input, generating multiple route options for routes between the start point and the end point, the multiple route options including a first route from the start point to the end point via the intermediate stop, the multiple route options further including a plurality of routes with intermediate stops that satisfy the search criteria indicating the type of location and without constraining the generating to a pre-established route between the start point and the end point; and

selecting an optimal route from the multiple route options based on defined optimization criteria.

2. A method as recited in claim 1, wherein the type of location is a location category.

3. A method as recited in claim 1, wherein the intermediate stop search criteria indicates a type of the location for multiple intermediate stops.

4. A method as recited in claim 1, further comprising exposing a representation of the optimal route in a map view presented via a user interface of a map navigation tool implemented by the computing device.

5. A method as recited in claim 1, wherein the optimization criteria include factors to account for one or more of:

overall distance, travel time, traffic data, weather conditions, date and time, fuel economy, or distance and travel time to reach the intermediate stop.

6. A method as recited in claim 1, wherein selecting the optimal route includes ranking the multiple route options according to the optimization criteria, selecting a highest ranking route from the multiple route options as a current route, and initiating route navigation and guidance for the current route.

7. A method as recited in claim 1, wherein generating the multiple route options includes providing a ranked and ordered list of the multiple route options that match the search criteria according to a search algorithm.

8. A method as recited in claim 1, wherein the route search input is received via route search functionality provided via user interface of a map navigation application that enables the route search input as search parameters including designation of the start point, the end point, and the intermediate stop corresponding to the search criteria specifying one or more of the intermediate stops.

9. A method as recited in claim 1, further comprising rendering a view of the multiple route options via a user interface for an application used to initiate the search, wherein the view includes at least one of:

a map view depicting a representation of the multiple route options, or a list view providing a ranked and ordered list of the multiple route options.

10. A method as recited in claim 1, wherein generating the multiple route options comprises establishing a search area according to a configurable parameter that sets boundaries for the search in relation to the start point, the end point, and the intermediate stop, and conducting the search for the intermediate stops that satisfy the search criteria within the search area.

11. A method implemented by a map navigation tool deployed on a computing device comprising:

obtaining input for a route search specifying a start point, an end point, and an intermediate stop before a route from the start point to the intermediate stop to the end point is calculated, the intermediate stop corresponding to a type of intermediate stop to include in the route;

calculating one or more route options between the start point and the end point that include intermediate stops matching the type of intermediate stop without dependence upon a pre-established route, the one or more route options including the route;

scoring and ranking the one or more route options according to optimization criteria; and

selecting a highest ranked route from the one or more route options as an optimal route based on the scoring and ranking.

12. A method as recited in claim 11, wherein selecting the highest ranked route comprises automatically selecting the highest ranked route as a current route and initiating route navigation and guidance for the current route without additional user input.

13. A method as recited in claim 11, further comprising exposing the calculated one or more route options using visual indicators included in a map view presented via a user interface for the map navigation tool.

14. A method as recited in claim 13, wherein the visual indicators are selectable by a user to confirm a particular one of the one or more route options as a current route.

15. A method as recited in claim 11, wherein the optimization criteria include at least a factor for overall distance, such that the highest ranked route corresponds to a shortest overall distance.

16. A method as recited in claim 11, wherein the optimization criteria include at least a factor for overall travel time, such that the highest ranked route corresponds to a minimum overall travel time.

17. A computing device comprising:

a processing system; and

one or more computer-readable storage media storing instructions that, when executed via the processing system, implement a map navigation tool configured to perform operations to calculate optimal routes based on specified intermediate stops, the operations including;

obtaining input for a route search specifying a start point, an end point, and an intermediate stop before a route from the start point to the intermediate stop to the end point is calculated, the intermediate stop corresponding to a category of intermediate stop to include in the route;

calculating one or more route options between the start point and the end point that include intermediate stops matching the category of intermediate stop without constraining the calculation to a pre-established route, the one or more route options including the route;

exposing the one or more route options for selection by a user via a user interface for the map navigation tool; and

responsive to receiving a selection of one of the route options via the user interface, initiating route navigation to guide the user along the route option that is selected.

18. A computing device as recited in claim 17, wherein exposing the one or more route options comprises displaying at least one of a map view having visual indicators to show available route options or a list view of the available route options.

19. A computing device as recited in claim 17, wherein calculating the one or more route options comprises scoring and ranking multiple route options according to optimization criteria to derive a set of top ranking routes.

20. A computing device as recited in claim 17, wherein initiating the route navigation comprises causing output of map views and navigational instructions via the map navigation tool to guide the user, including at least a view of the route option that is selected and directions to one or more intermediate stops included in the route option that is selected.