RUSH HOUR MODELING FOR ROUTING AND SCHEDULING

• US 20090018760A1
• Filed: 09/23/2008
• Published: 01/15/2009
• Est. Priority Date: 04/15/2003
• Status: Active Grant

• Current Assignee: Roadnet Technologies (Solera Holdings 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
• Granted Patent: US 8,433,511 B2
• Time in Patent Office: Days
• US Class Current: 701/117
• 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 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 by determining which of said first and second geographic areas was created first;

in response to determining that said first geographic area was created first, 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 said second geographic area was created first, 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.

2. The computer readable medium storing computer-executable instructions from claim 1 further for:

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

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

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

in response to determining that said first geographic area was created first, 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;

in response to determining that said second geographic area was created first, 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; and

in response to determining that said third geographic area was created first, applying the third travel rule to model traffic conditions for one or more vehicles traveling through at least a portion of the overlapped geographic area.

3. 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 by determining which of said first and second geographic areas was created first;

in response to determining that said first geographic area was created first, applying the first travel rule to determine whether to schedule a route for one or more vehicles through at least a portion of the overlapped geographic area; and

in response to determining that said second geographic area was created first, applying the second travel rule to determine whether to schedule a route for one or more vehicles through at least a portion of the overlapped geographic area.

4. The computer readable medium storing computer-executable instructions from claim 3 further for:

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

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

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

in response to determining that said first geographic area was created first, applying the first travel rule to determine whether to schedule a route for one or more vehicles through at least a portion of the overlapped geographic area;

in response to determining that said second geographic area was created first, applying the second travel rule to determine whether to schedule a route for one or more vehicles through at least a portion of the overlapped geographic area; and

in response to determining that said third geographic area was created first, applying the third travel rule to determine whether to schedule a route for one or more vehicles through at least a portion of the overlapped geographic area.

5. 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 by determining which of said first and second geographic areas was created first;

in response to determining that said first geographic area was created first, applying the first travel rule to schedule a route for one or more vehicles through at least a portion of the overlapped geographic area; and

in response to determining that said second geographic area was created first, applying the second travel rule to schedule a route for one or more vehicles through at least a portion of the overlapped geographic area.

6. The computer readable medium storing computer-executable instructions from claim 5 further for:

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

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

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

in response to determining that said first geographic area was created first, applying the first travel rule to schedule a route for one or more vehicles through at least a portion of the overlapped geographic area;

in response to determining that said second geographic area was created first, applying the second travel rule to schedule a route for one or more vehicles through at least a portion of the overlapped geographic area; and

in response to determining that said third geographic area was created first, applying the third travel rule to schedule a route for one or more vehicles through at least a portion of the overlapped geographic area.