Automated route determination based on day of route traversal

• US 20040044465A1
• Filed: 12/30/2002
• Published: 03/04/2004
• Est. Priority Date: 08/29/2002
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Nesbitt, David W.
• Application Number:
  US10/330,560
• Publication Number:
  US 20040044465A1
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A preferred route may be determined from an origin location to a destination location. The determination is made by processing directed links (e.g., one-way edges) in a graph that includes one or more links and two or more nodes. The determination of a preferred route may include an estimate of the time required at one or more intersections along alternative routes and/or an estimate of the time required to travel the alternative routes based on the day of the week or the day of the year in which travel occurs.

Claims

1. A method for determining a preferred route using a computer-implemented routing system, the method comprising:

using a routing system to access an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

using the routing system to determine a preferred route from the origin to the destination based at least in part upon a variable cost for traversing at least one link in the routing graph, the variable cost being based on a day in which the at least one link is to be traversed; and

communicating the preferred route from the routing system to a user system.

2. The method of claim 1 wherein the day comprises a day of a week.

3. The method of claim 2 wherein the variable cost is based on a time of day.

4. The method of claim 2 wherein the variable cost differs based on whether the day of the week is a weekday or a weekend day.

5. The method of claim 1 wherein the day comprises a day of a year.

6. The method of claim 5 wherein the variable cost is based on a time of day.

7. The method of claim 5 wherein the variable cost differs based on whether the day of the year comprises a holiday or a non-holiday.

8. The method of claim 7 wherein the variable cost differs based on whether the day of the year comprises holiday or a non-holiday observed by the nation in which the route occurs.

9. The method of claim 1 wherein the variable cost comprises a variable cost based on empirical data about traffic patterns on different days.

10. The method of claim 1 wherein the variable cost comprises a variable cost based on observational data about traffic patterns on different days.

11. The method of claim 1 wherein the variable cost comprises variable cost based on intuitive data about traffic patterns on different days.

12. The method of claim 1 wherein the routing system comprises a routing system provided through an Internet service provider.

13. The method of claim 1 wherein the routing system and the user system use the same processor.

14. The method of claim 1 wherein communicating the preferred route comprises communicating the preferred route over a connection that is established using the Internet.

15. A computer-readable medium or propagated signal having embodied thereon a computer program configured to determine a preferred route using a computer-implemented routing system, the medium or signal comprising one or more code segments configured to:

use a routing system to access an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

use the routing system to determine a preferred route from the origin to the destination based at least in part upon a variable cost for traversing at least one link in the routing graph, the variable cost being based on a day in which the at least one link is to be traversed; and

communicate the preferred route from the routing system to a user system.

16. The medium or signal of claim 15 wherein the day comprises a day of a week.

17. The medium or signal of claim 16 wherein the variable cost is based on a time of day.

18. The medium or signal of claim 16 wherein the variable cost differs based on whether the day of the week is a weekday or a weekend day.

19. The medium or signal of claim 15 wherein the day comprises a day of a year.

20. The medium or signal of claim 19 wherein the variable cost is based on a time of day.

21. The medium or signal of claim 19 wherein the variable cost differs based on whether the day of a year comprises a holiday or a non-holiday.

22. The medium or signal of claim 21 wherein the variable cost differs based on whether the day of the year comprises a holiday or a non-holiday observed by the nation in which the route occurs.

23. The medium or signal of claim 15 wherein the variable cost comprises a variable cost based on empirical data about traffic patterns on different days.

24. The medium or signal of claim 15 wherein the variable cost comprises a variable cost based on observational data about traffic patterns on different days.

25. The medium or signal of claim 15 wherein the variable cost comprises a variable cost based on intuitive data about traffic patterns on different days.

26. The medium or signal of claim 15 wherein the routing system comprises a routing system provided through an Internet service provider.

27. The medium or signal of claim 15 wherein the routing system and the user system use the same processor.

28. The medium or signal of claim 15 wherein the one or more code segments configured to communicate the preferred route comprise one or more code segments to communicate the preferred route over a connection that is established using the Internet.

29. A system for determining a preferred route, the system configured to:

access an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

determine a preferred route from the origin to the destination based at least in part upon a variable cost for traversing at least one link in the routing graph, the variable cost being based on a day in which the at least one link is to be traversed; and

communicate the preferred route from the routing system to a user system.

30. The system of claim 29 wherein the day comprises a day of a week.

31. The system of claim 30 wherein the variable cost is based on a time of day.

32. The system of claim 31 wherein the variable cost differs based on whether the day of the week is a weekday or a weekend day.

33. The system of claim 29 wherein the day comprises a day of a year.

34. The system of claim 33 wherein the variable cost is based on a time of day.

35. The system of claim 33 wherein the variable cost differs based on whether the day of the year comprises a holiday or a non-holiday.

36. The system of claim 35 wherein the variable cost differs based on whether the day of the year comprises a holiday or a non-holiday observed by the nation in which the route occurs.

37. The system of claim 29 wherein the variable cost comprises a variable cost based on empirical data about traffic patterns on different days.

38. The system of claim 29 wherein the variable cost comprises a variable cost based on observational data about traffic patterns on different days.

39. The system of claim 29 wherein the variable cost comprises a variable cost based on intuitive data about traffic patterns on different days.

40. The system of claim 29 wherein the routing system comprises a routing system provided through an Internet service provider.

41. The system of claim 29 wherein the routing system and the user system use the same processor.

42. The system of claim 29 wherein the system is configured to communicate the preferred route over a connection that is established using the Internet.