Waypoint adjustment and advertisement for flexible routing

• US 7,693,652 B2
• Filed: 04/05/2006
• Issued: 04/06/2010
• Est. Priority Date: 04/05/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cheung, Matthew
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US11/398,046
• Publication Number:
  US 20070239348A1
• Time in Patent Office: 1,462 Days
• Field of Search: 701200-212, 701/300, 340/988, 340/990, 340/995.1
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3423 Multimodal routing, i.e. combining two or more modes of transportation, where the modes can be any of, e.g. driving, walking, cycling, public transport
• 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/3697 Output of additional, non-guidance related information, e.g. low fuel level G01C21/3679 takes precedence

Abstract

A unique routing system and method that facilitates adjusting waypoint locations to optimize a cost function and presenting more relevant contextual advertisements based in part on the waypoint locations. The system and method involve examining waypoint locations including a start, end, and any in-between waypoint to determine whether they are reachable or routable according to the preferred mode of transportation. Adjustments can be made to one or more of the waypoint locations in order to accommodate this mode of transportation in view of a given cost function. Adjustments can be made that optimize the cost function to minimize overall costs. Multi-modal routing can be initiated as well to configure a route using the selected or adjusted waypoints and multiple modes of transportation in order to optimize the cost function. Adjustments and the selection of contextual advertisements can be based on user intention and several other route related factors.

Claims

1. A system that facilitates configuring a most reasonable and cost-effective travel route comprising:

at least one processor that executes the following computer executable components stored on at least one computer readable medium;

a route generation component that receives selected waypoint locations;

a waypoint adjustment component that determines whether it is more cost-effective to adjust any of the selected waypoint locations based at least in part upon optimizing a cost function to minimize overall travel costs; and

an inference component that infers user preferences based on previous waypoint selections in order to facilitate desirable route configuration.

2. The system of claim 1, wherein the waypoint locations comprise a start waypoint, an end waypoint, and one or more waypoints in between the start and the end waypoints.

3. The system of claim 1, wherein the route generation component determines whether the selected waypoint locations are reachable based on a desired mode of transportation and other weighted factors.

4. The system of claim 1, wherein the cost function is a weighted function of at least one of the following:

time, fuel, equipment cost, distance, and other expenses associated with travel.

5. The system of claim 1, wherein the waypoint adjustment component determines whether to adjust one or more selected waypoint locations based in part on the desired mode of transportation and adjusts one or more waypoint locations accordingly.

6. The system of claim 5 further comprises a multi-modal route generation module that configures a multi-modal route using one of the selected or adjusted waypoint locations that optimizes the cost function while utilizing at least two modes of transportation.

7. The system of claim 1, wherein the waypoint adjustment component evaluates user intention according to at least one of the following:

distance between waypoint locations, time, fuel consumption, and businesses located within a selected distance from a selected waypoint location when determining cost-effective adjustments to the waypoint locations.

8. The system of claim 1 further comprises a contextual advertisement presentation component that selects and presents one or more contextual advertisements based at least in part on one of the following:

user intention, interest profile, route, route type, purpose for route, distance between waypoint locations, adjusted waypoint locations, mode of transportation, wait times, and locality where waiting or stopping.

9. The system of claim 8, wherein the one or more contextual advertisements are selected to facilitate optimizing the cost function.

10. The system of claim 1, further comprising a comparison component that permits a user to narrow preferences or to modify weights of factors considered in the cost function.

11. A method that facilitates configuring a most reasonable and cost-effective travel route comprising:

employing a processor to execute computer readable instructions stored on a computer readable medium to perform the following acts;

receiving selected waypoint locations;

determining whether it is more cost-effective to adjust any of the selected waypoint locations based at least in part upon optimizing a cost function to minimize overall travel costs, wherein the cost function is a weighted function of expenses related to at least one of fuel, equipment, parking, toll fees, lodging, and food; and

inferring user preferences based on previous route or waypoint location selections.

12. The method of claim 11 further comprises adjusting one or more selected waypoint locations based in part on at least one of the following:

user intention, mode of transportation, time, fuel consumption, and user preferences.

13. The method of claim 11 further comprises determining whether the selected waypoint locations are reachable by a desired mode of transportation;

and adjusting one or more of the waypoint locations to accommodate the desired mode of transportation given the cost function.

14. The method of claim 13 further comprises initiating multi-modal routing after adjusting the one or more waypoint locations in order to further optimize the cost function and minimize overall costs.

15. The method of claim 11 further comprises selecting and presenting one or more contextual advertisements based at least in part on at least one of the following:

waypoint location, adjust waypoint location, user intentions, interest profile, route, route type, wait times, mode of transportation, and distance between waypoint locations.

16. The method of claim 15, wherein the mode of transportation comprises motorized vehicle, bicycle, train, car, airplane, helicopter, bus, boat, ship, and foot.

17. The method of claim 11, wherein the cost function comprises a weighted function that is customizable.

18. A system that facilitates configuring a most reasonable and cost-effective travel route comprising:

at least one processor that executes the following computer executable components stored on at least one computer readable medium;

a route generation component for receiving selected waypoint locations;

a waypoint adjustment component for determining whether it is more cost-effective to adjust any of the selected waypoint locations based at least in part upon optimizing a cost function to minimize overall travel costs, wherein the cost function is a weighted function of expenses related to at least one of fuel, equipment, parking, toll fees, lodging, and food;

an inference component for inferring user preferences based on previous waypoint selections in order to facilitate desirable route configuration; and

a contextual advertisement presentation component for selecting and presenting one or more contextual advertisements based at least in part on at least one of the following;

a waypoint location, an adjusted waypoint location, user intentions, a route, a route type, wait times, a mode of transportation, and a distance between waypoint locations.

19. A method for travel routing, comprising:

employing a processor to execute computer readable instructions stored on a computer readable medium to perform the following acts;

receiving a waypoint selection of a user;

determining that the waypoint selection is inconsistent with the user'"'"'s intent;

evaluating areas surrounding the waypoint;

based on the evaluating, inferring a likely intent of the user; and

based on the inferred likely intent, changing the waypoint to a different waypoint.

20. The method of claim 19, further comprising presenting an advertisement for a business along a path to a waypoint based at least in past on a waiting time associated with the business.