Calculating an Optimal Route based on Specified Intermediate Stops

• US 20170336221A1
• Filed: 05/17/2016
• Published: 11/23/2017
• 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
• Granted Patent: US 10,386,197 B2
• Time in Patent Office: Days
• 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 request to search between a start point and an end point for a route with an intermediate stop that satisfies search criteria indicating at least a type of location;

responsive to the request, obtaining search results with multiple route options for routes between the start point and the end point including intermediate stops that satisfies the search criteria, the multiple route options being calculated in dependence upon the search criteria indicating the type of location and without constraining the calculation to a pre-established route between the start point and 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 type of location is a specific name of a business or place with multiple distinct locations.

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 route options one to another according to the optimization criteria, picking a highest ranking route from the 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 obtaining the search results comprises generating and providing a ranked and ordered list of route options that match the search criteria according to a search algorithm.

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

9. A method as recited in claim 1, further comprising rendering a view of the search results 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 routes, or a list view providing a ranked and ordered list of the multiple routes to enable selection of a route by a user from available options.

10. A method as recited in claim 1, wherein obtaining search results comprises establishing a search area according to a configurable parameter that sets boundaries for the search and conducting a search for intermediate stops that satisfies the search criteria with 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 a type of intermediate stop to include in a route;

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

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

selecting a highest ranked route from the 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 picking 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 one or more route options that are calculated 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, 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 a category of intermediate stop to include in a route;

calculating one or more route options between the start point and end point that include a stop matching the category of intermediate stop without constraining the calculation to a pre-established 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 the 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 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.