Rush hour modeling for routing and scheduling

• US 8,433,511 B2
• Filed: 09/23/2008
• Issued: 04/30/2013
• Est. Priority Date: 04/15/2003
• Status: Active Grant

• Current Assignee: Roadnet Technologies (Solera Holdings Incorporated)
• Original Assignee: United Parcel Service of America (United Parcel Service Incorporated)
• Inventors: Heaps, Charles, Kraisser, Clifton, Clementi, Ralph, Mudd, Thomas, Simon, Stephen, Francis, McClellan
• Primary Examiner(s): Tarcza, Thomas
• Assistant Examiner(s): TISSOT, ADAM D
• Application Number:
  US12/236,306
• Publication Number:
  US 20090018760A1
• Time in Patent Office: 1,680 Days
• Field of Search: 701117-119, 701200-202, 701208-210, 701/23, 701/408, 701/411, 701414-416, 701/422, 701/423, 703/6, 340/22, 340/401
• US Class Current: 701/422
• 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 non-transitory computer readable medium storing computer-executable instructions for:

receiving data defining boundaries of a first geographic area and a first travel role that is associated with said first geographic area, the first travel role modeling traffic conditions within the first geographic area during a first time window comprising a first start time and a first end time;

receiving data defining boundaries of 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 role that is associated with said second geographic area, the second travel rule-modeling traffic conditions within the second geographic area during a second time window comprising a second start time and a second end time;

determining that said first time window and second time window overlap inasmuch as said first start time or said first end time or both said first start time and said first end time fall between said second start time and said second end time;

determining based on priority factors 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 said first travel rule should be applied, 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 during the same time window; and

in response to determining that said second travel role should be applied, 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 during the same time window.

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

receiving data defining boundaries of 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, the third travel rule-modeling traffic conditions within the third geographic area and during a third time window comprising a third start time and a third end time;

determining that said first time window, second time window, and said third time window overlap inasmuch as said first start time or said first end time or both said first start time and said first end time fall between said second start time and said second end time, and said third start time or said third end time or both said third start time and said third end time fall in the overlapping timeframe of said first time window and said second time window;

determining based on priority factors 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 in response to determining that said first travel rule should be applied 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 during the same time window;

in response to determining that said second travel rule should be applied 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 during the same time window; and

in response to determining that said third travel rule should be applied 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 during the same time window.

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

receiving data defining boundaries of a first road segment 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 first road segment defines the overlapped geographic area;

receiving a third travel rule that is associated with said first road segment, the third travel rule modeling traffic conditions within the first road segment and during a third time window comprising a third start time and a third end time;

determining that said first time window, second time window, and said third time window overlap inasmuch as said first start time or said first end time or both said first start time and said first end time fall between said second start time and said second end time, and said third start time or said third end time or both said third start time and said third end time fall in the overlapping timeframe of said first time window and said second time window;

determining based on priority factors 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;

in response to determining that said first travel rule should be applied, 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 during the same time window;

in response to determining that said second travel rule should be applied, 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 during the same time window; and

in response to determining that said third travel rule should be applied, 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 during the same time window.

4. The computer readable medium storing computer-executable instructions of claim 1, claim 2, or claim 3 wherein said priority factors comprise priority numbers assigned to each travel rule by a user.

5. The computer readable medium storing computer-executable instructions of claim 1, claim 2, or claim 3 wherein said priority factors comprise determining which geographic area was created first.

6. The computer readable medium storing computer-executable instructions of claim 3 wherein said priority factors comprise applying the travel rule associated with a road segment when a travel rule associated with a road segment conflicts with a travel rule associated with a geographic area.

7. A non-transitory computer readable medium storing computer-executable instructions for:

receiving data defining boundaries of a first road segment and a first travel rule that is associated with said first road segment, the first travel rule modeling traffic conditions within the first road segment during a first time window comprising a first start time and a first end time;

receiving data defining boundaries of a second road segment at least partially overlapping the first road segment, wherein an area within both the first road segment and the second road segment defines an overlapped geographic area;

receiving a second travel rule that is associated with said second road segment, the second travel rule modeling traffic conditions within the second road segment during a second time window comprising a second start time and a second end time;

determining that said first time window and second time window overlap inasmuch as said first start time or said first end time or both said first start time and said first end time fall between said second start time and said second end time;

determining based on priority factors 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 said first travel rule should be applied, 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 during the same time window;

and in response to determining that said second travel rule should be applied, 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 during the same time window.

8. The computer readable medium storing computer-executable instructions from claim 7 further for:

receiving data defining boundaries of a first geographic area at least partially overlapping the first road segment and the second road segment, wherein an area within both the first road segment, the second road segment, and the first geographic area defines the overlapped geographic area;

receiving a third travel rule that is associated with said first geographic area, the third travel rule modeling traffic conditions within the first geographic area and during a third time window comprising a third start time and a third end time;

determining that said first time window, second time window, and said third time window overlap inasmuch as said first start time or said first end time or both said first start time and said first end time fall between said second start time and said second end time, and said third start time or said third end time or both said third start time and said third end time fall in the overlapping timeframe of said first time window and said second time window;

determining based on priority factors 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;

in response to determining that said first travel rule should be applied, 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 during the same time window;

in response to determining that said second travel rule should be applied, 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 during the same time window; and

in response to determining that said third travel rule should be applied, 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 during the same time window.

9. The computer readable medium storing computer-executable instructions from claim 7 further for:

receiving data defining boundaries of a third road segment at least partially overlapping the first road segment and the second road segment, wherein an area within both the first road segment, the second road segment, and the third road segment defines the overlapped geographic area;

receiving a third travel rule that is associated with said third road segment, the third travel rule modeling traffic conditions within the third road segment and during a third time window comprising a third start time and a third end time;

determining that said first time window, second time window, and said third time window overlap inasmuch as said first start time or said first end time or both said first start time and said first end time fall between said second start time and said second end time, and said third start time or said third end time or both said third start time and said third end time fall in the overlapping timeframe of said first time window and said second time window;

determining based on priority factors 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;

in response to determining that said first travel rule should be applied, 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 during the same time window;

in response to determining that said second travel rule should be applied, 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 during the same time window; and

in response to determining that said third travel rule should be applied, 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 during the same time window.

10. The computer readable medium storing computer-executable instructions of claim 7, claim 8, or claim 9 wherein said priority factors comprise priority numbers assigned to each travel rule by a user.

11. The computer readable medium storing computer-executable instructions of claim 8 or claim 9 wherein said priority factors comprise determining which geographic area was created first.

12. The computer readable medium storing computer-executable instructions of claim 8 wherein said priority factors comprise applying the travel rule associated with a road segment when a travel rule associated with a road segment conflicts with a travel rule associated with a geographic area.