User-controlled alternative routing

• US 9,423,262 B2
• Filed: 11/20/2014
• Issued: 08/23/2016
• Est. Priority Date: 12/29/2005
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: MapQuest, Inc. (Apollo Global Management, Inc.)
• Inventors: Nesbitt, David W.
• Primary Examiner(s): Dager, Jonathan M
• Application Number:
  US14/548,894
• Publication Number:
  US 20150149077A1
• Time in Patent Office: 642 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries

Abstract

A user may indicate a preference of a route when alternative routes are available between an origin and a destination. The mapping system may enable a user to identify a region, a point or a set of points to help control, guide or otherwise influence the determination of a route favored by the user. While the identified region, point or set of points may be included in the route, the identified region, point or set of points need not necessarily be included in the route.

Claims

1. A computer-implemented mapping system for determining a route between an origin and a destination, comprising:

a non-transitory memory storing a set of instructions; and

at least one processor that executes the set of instructions to perform operations comprising;

receiving, based on input from a user, a designated location, the designated location being different from the location of the origin or the destination;

determining a lowest-cost route from the origin to the destination influenced by the designated location, wherein determining the lowest-cost route comprises;

determining a degree of proximity of a link proximate to the designated location,

determining a type of designated location that was received,

adjusting a cost of the proximate link based on the determined degree of proximity and the determined type of the designated location, and

determining a total cost of the proximate link based on the adjusted cost of the proximate link; and

providing the lowest-cost route for display to the user.

2. The computer-implemented mapping system of claim 1, wherein the determined type of the designated location reflects a favored designated location and indicates a preference for a route closer to the designated location, and further wherein the cost of the proximate link is decreased based on the degree of proximity.

3. The computer-implemented mapping system of claim 1, wherein the determined type of the designated location reflects a disfavored designated location and indicates a preference for a route further from the designated location, and further wherein the cost of the proximate link is increased based on the degree of proximity.

4. The computer-implemented mapping system of claim 1, wherein the cost of the proximate link depends on a density of a plurality of links within an area represented in the computer-implemented mapping system.

5. The computer-implemented mapping system of claim 1, wherein the designated location is based on a selection by a user on an interactive map, the interactive map comprising a resizable indicator for identifying a wide area as the designated location.

6. A method for determining a route between an origin and a destination, the method comprising the following operations performed by at least one processor:

receiving, based on input from a user, a designated location, the designated location being different from the location of the origin or the destination;

determining a lowest-cost route from the origin to the destination influenced by the designated location, wherein determining the lowest-cost route comprises;

determining a degree of proximity of a link proximate to the designated location,

determining a type of designated location that was received, and

adjusting a cost of the proximate link based on the determined degree of proximity and the determined type of the designated location; and

providing the lowest-cost route for display to the user.

7. The method of claim 6, wherein the type of the designated location reflects a favored designated location and indicates a preference for a route closer to the designated location, and further wherein the cost of the proximate link is decreased based on the degree of proximity.

8. The method of claim 6, wherein the type of the designated location reflects a disfavored designated location and indicates a preference for a route further from the designated location, and further wherein the cost of the proximate link is increased based on the degree of proximity.

9. The method of claim 6, wherein the cost of the proximate link depends on a density of a plurality of links within an area.

10. The method of claim 6, wherein determining the lowest-cost route further comprises accessing at least part of a routing graph including the proximate link, the routing graph representing a network of roads.

11. The method of claim 10, wherein determining the lowest-cost route further comprises determining an adjacency set using the routing graph, the adjacency set comprising a second link adjacent to an end node of the proximate link, and processing the second link.

12. The method of claim 11, wherein processing the second link comprises determining a total cost of the second link based on a total cost of the proximate link, an intersection cost, and a cost of the second link.

13. The method of claim 11, wherein the routing graph includes temporary information about the second link and further wherein the processing of the second link comprises overwriting the temporary information.

14. The method of claim 6, wherein receiving the designated location comprises receiving a selection by the user identifying the designated location on an interactive map.

15. The method of claim 14, wherein the interactive map comprises a resizable indicator for identifying a wide area as the designated location.

16. A non-transitory computer-readable medium containing instructions that when executed by at least one processor cause the at least one processor to:

receive, based on input from a user, a designated location, the designated location being different from the location of the origin or the destination;

determine a lowest-cost route from the origin to the destination influenced by the designated location, wherein determining the lowest-cost route comprises;

determine a degree of proximity of a link proximate to the designated location,

determine a type of designated location that was received, and

adjust a cost of the proximate link based on the determined degree of proximity and the determined type of the designated location; and

provide the lowest-cost route for display to the user.

17. The non-transitory computer-readable medium of claim 16, wherein determining the lowest-cost route further comprises:

access at least part of a routing graph including the proximate link, the routing graph representing a network of roads;

determine an adjacency set using the routing graph, the adjacency set comprising a second link adjacent to an end node of the proximate link; and

determine a total cost of the second link based on a total cost of the proximate link, an intersection cost, and a cost of the second link.

18. The non-transitory computer-readable medium of claim 17, wherein the routing graph includes temporary information about the second link and processing the second link comprises overwriting the stored temporary information.

19. The non-transitory computer-readable medium of claim 16, wherein the input of the user comprises a selection on an interactive map identifying the designated location.

20. The non-transitory computer-readable medium of claim 16, wherein the cost of the proximate link depends on a density of a plurality of links within an area represented in a mapping system.