Rush hour modeling for routing and scheduling

• US 20050021223A1
• Filed: 04/15/2004
• Published: 01/27/2005
• Est. Priority Date: 04/15/2003
• Status: Abandoned Application

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Heaps, Charles, Simon, Stephen, Clementi, Ralph, Francis, McClellan, Kraisser, Clifton, Mudd, Thomas
• Application Number:
  US10/828,850
• Publication Number:
  US 20050021223A1
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 1/0104 Measuring and analyzing of parameters relative to traffic conditions
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality
• CPC Class Codes: G08G 1/09685 where the complete route is computed only once and not updated
• CPC Class Codes: G08G 1/096888 where input information is obtained using learning systems, e.g. history databases

Abstract

A rush hour modeling system that is configured for modifying existing travel time/distance data to reflect special traffic conditions, such as rush hour traffic conditions. The system is configured to receive information defining one or more time windows, geographic areas, and road segments in which special traffic conditions occur. The system is also configured to receive travel rules that reflect the special traffic conditions. The travel rules are used to modify a travel time/distance matrix to reflect the effect of the special traffic conditions on “normal” travel times and distances. Existing routing and scheduling systems can then use the modified travel matrix to plan and schedule routes for delivery vehicles more accurately. Additionally, the modified travel matrix can be used to model traffic conditions through a particular geographic area or on a particular road segment.

Claims

1. A computer readable medium storing computer-executable instructions for:

receiving a time window;

receiving “

geographic area”

information, said information defining a geographic area;

receiving a travel rule that is to apply to said geographic area during said time window; and

after receiving said time window, said “

geographic area”

information, and said travel rule, applying said travel rule to said geographic area to schedule a route for one or more vehicles during said time window.

2. The computer readable medium of claim 1 further comprising:

receiving a second time window;

receiving a second travel rule that is to apply to said geographic area during said second time window; and

after receiving said second time window and said second travel rule, applying said second travel rule to said geographic area to schedule a route for one or more vehicles during said second time window.

3. The computer readable medium of claim 1 further comprising:

receiving a second travel rule that is to apply to said geographic area during said time window; and

after receiving said second travel rule, applying said second travel rule to said geographic area to schedule a route for one or more vehicles during said time window.

4. The computer readable medium of claim 1 further comprising:

receiving additional “

geographic area”

information, said additional information defining a second geographic area;

receiving a second travel rule;

after receiving said additional “

geographic area”

information and said second travel rule, applying said second travel rule to said second geographic area to schedule a route for one or more vehicles during said time window.

5. The computer readable medium of claim 1, wherein said travel rule comprises a speed variation model, said speed variation model comprising a percentage increase or decrease from a normal travel speed.

6. The computer readable medium of claim 1, wherein said travel rule comprises one or more vehicle based restrictions that are to apply to said geographic area during said time window.

7. The computer readable medium of claim 1, wherein said “

geographic area”

information comprises three of more points selected by a user to define a polygon, said polygon having boundaries that define a geographic area.

8. A computer readable medium storing computer-executable instructions for:

receiving a time window;

receiving “

geographic area”

information, said information defining a geographic area;

receiving a travel rule that is to apply to said geographic area during said time window; and

after receiving said time window, said “

geographic area”

information, and said travel rule, applying said one or more travel rules to determine whether to schedule a route for one or more vehicles through at least a portion of said geographic area during said time window.

9. The computer readable medium of claim 8, wherein the travel rule comprises a speed variation model, said speed variation model comprising a percentage increase or decrease from a normal travel speed.

10. The computer readable medium of claim 8, wherein the travel rule comprises one or more vehicle based restrictions that are to apply to said geographic area during said time window.

11. A computer readable medium storing computer-executable instructions for:

receiving a time window;

receiving “

geographic area”

information, said information defining a geographic area;

receiving a travel rule that is to apply to said geographic area during said time window; and

after receiving said time window, said “

geographic area”

information, and said travel rule, applying said travel rule to model the speed of travel of one or more vehicles traveling through said geographic area during said time window.

12. The computer readable medium of claim 11, wherein the travel rule comprises a speed variation model, said speed variation model comprising a percentage increase or decrease from a normal travel speed.

13. The computer readable medium of claim 11, wherein the travel rule comprises one or more vehicle-based restrictions that are to apply to said geographic area during said time window.

14. A computer readable medium storing computer-executable instructions for:

receiving a time window;

receiving “

geographic area”

information, said information defining a geographic area;

receiving a travel rule that is to apply to said geographic area during said time window;

after receiving said time window, said “

geographic area”

information, and said travel rule, applying said travel rule to said geographic area to generate a time/distance matrix that reflects traffic conditions within said geographic area during said time window; and

utilizing said time/distance matrix to schedule a route for one or more vehicles when said one or more vehicles are scheduled for travel within said time window.

15. A computer readable medium storing computer-executable instructions for:

receiving a first geographic area and a first travel rule that is associated with said first geographic area;

receiving a second geographic area, said second geographic area at least partially overlapping said first geographic area, wherein an area within both said first geographic area and said second geographic area defines an overlapped geographic area;

receiving a second travel rule that is associated with said second geographic area;

after receiving said first and second geographic areas and said first and second travel rules, determining whether said first or said second travel rule should be applied to one or more vehicles traveling through at least a portion of said overlapped geographic area;

in response to determining that the first travel rule should be applied to one or more vehicles traveling within the overlapped geographic area, applying the first travel rule to model traffic conditions for one or more vehicles traveling through at least a portion of the overlapped geographic area; and

in response to determining that the second travel rule should be applied to one or more vehicles traveling within the overlapped geographic area, applying the second travel rule to model traffic conditions for one or more vehicles traveling through at least a portion of the overlapped geographic area.

16. A computer readable medium storing computer-executable instructions for:

receiving a first geographic area and a first travel rule that is associated with said first geographic area;

receiving a second geographic area at least partially overlapping the first geographic area, wherein an area within both the first geographic area and the second geographic area defines an overlapped geographic area;

receiving a second travel rule that is associated with said second geographic area;

after receiving said first and second geographic areas and said first and second travel rules, determining whether said first or said second travel rules should be applied to one or more vehicles traveling through at least a portion of said overlapped geographic area;

in response to determining that the first travel rule should be applied to one or more vehicles traveling within the overlapped geographic area, applying the first travel rule to determine whether to schedule a route for one or more vehicles through the overlapped geographic area; and

in response to determining that the second travel rule should be applied to one or more vehicles traveling within the overlapped geographic area, applying the second travel rule to determine whether to schedule a route for one or more vehicles through the overlapped geographic area.

17. The computer readable medium of claim 16 wherein the determination of whether said first or second travel rule should be applied to vehicles traveling through at least a portion of said overlapped geographic area is determined by priority numbers assigned to said first and second geographic areas.

18. The computer readable medium of claim 16 wherein the determination of whether said first or second travel rule should be applied to vehicles traveling through at least a portion of said overlapped geographic area is determined by which of said first and second geographic areas was created first.

19. A computer readable medium storing computer-executable instructions for:

receiving a time window;

receiving “

road segment”

information, said information defining a road segment;

receiving a direction of travel restriction that is to apply to said road segment during said time window; and

after receiving said “

road segment”

information and said direction of travel restriction, applying said direction of travel restriction to schedule one or more routes so that substantially no route includes travel by one or more vehicles in the restricted direction of travel on said road segment during said time window.

20. The computer readable medium of claim 19 wherein the “

road segment”

information comprises two points on a road that are selected by a user, the portion of road between the two points defining said road segment.

21. A computer readable medium storing computer-executable instructions for:

receiving a time window;

receiving “

road segment”

information, said information defining a road segment;

receiving a vehicle based restriction that is to apply to said road segment; and

after receiving said “

road segment”

information and said vehicle based restriction, applying said vehicle based restriction to schedule one or more routes so that substantially no route includes travel on said road segment during said time window by one or more vehicles that satisfy the criteria for the vehicle-based restrictions.

22. A computer readable medium storing computer-executable instructions for:

receiving a time window;

receiving “

road segment”

information, said information defining a road segment;

receiving a speed variation model that is to apply to said road segment, said speed variation model comprising a percentage increase or decrease from a normal travel time; and

after receiving said “

road segment”

information and said speed variation model, applying said speed variation model to schedule one or more routes.

23. A computer readable medium storing computer executable instructions for:

receiving “

geographic area”

information, said information defining a geographic area;

receiving a first time window in which a first speed variation model is to apply within the geographic area;

receiving a second time window in which a second speed variation model is to apply within the geographic area;

after receiving said “

geographic area”

information, said first time window and said first speed variation model, applying said first speed variation model to estimate a travel time associated with vehicles traveling within at least a portion of said geographic area within said first time window; and

after receiving said “

geographic area”

information, said second time window and said second speed variation model, applying said second speed variation model to model traffic conditions for one or more vehicles traveling within at least a portion of said geographic area within said second time window.

24. A computer readable medium storing computer-executable instructions for:

receiving “

geographic area”

information, said information defining a geographic area;

receiving a “

no travel”

time window for said geographic area;

receiving “

no travel”

instructions, said instruction specifying that substantially no vehicles should be scheduled to travel within said geographic area during the “

no travel”

time window; and

after receiving said “

geographic area”

information, said “

no travel”

time window, and said “

no travel”

instruction, scheduling vehicles so that the system schedules substantially no vehicles to travel within said geographic area during said “

no travel”

time window.

25. A computer readable medium storing computer-executable instructions for:

receiving “

geographic area”

information, said information defining a geographic area;

receiving a first speed variation model that is to apply to a first road classification within the geographic area;

receiving a second speed variation model that is to apply to a second road classification within the geographic area;

after receiving said “

geographic area”

information, said first speed variation model, and said first road classification, applying the first speed variation model to estimate travel times associated with vehicles traveling on roads of the first classification through at least a portion of the geographic area; and

after receiving said “

geographic area”

information, said second speed variation model, and said second road classification, applying the second speed variation model to estimate travel times associated with vehicles traveling on roads of the second classification through at least a portion of the geographic area.

26. A computer readable medium storing computer-executable instructions for:

receiving a time window;

receiving a road segment classification;

receiving a travel rule that is to apply to road segments that are assigned to said road segment classification during said time window; and

after receiving said time window, said road segment classification, and said travel rule, applying said travel rule to road segments assigned to said road segment classification to schedule a route for one or more vehicles during said time window.

27. The computer readable medium of claim 26 further comprising:

receiving a second road segment classification;

receiving a second travel rule that is to apply to road segments that are assigned to said second road segment classification during said time window; and

after receiving said second road segment classification and said second travel rule, applying said travel rule to road segments assigned to said second road segment classification to schedule a route for one or more vehicles during said time window.

28. The computer readable medium of claim 26 further comprising:

receiving “

road segment”

information, said information defining a road segment and assigning a classification to said road segment;

after receiving said road segment information, applying said travel rule to said road segment if said classification assigned to said road segment is said road segment classification associated with said travel rule