Generating and tuning an allocation of transportation resources

• US 7,860,740 B1
• Filed: 06/08/2010
• Issued: 12/28/2010
• Est. Priority Date: 04/28/2005
• Status: Expired due to Fees

• Current Assignee: Southwest Airlines Company
• Original Assignee: Southwest Airlines Company
• Inventors: Heinold, Alex Michael, Anbil, Ranga
• Primary Examiner(s): Jeanty; Romain
• Assistant Examiner(s): WALKER III, GEORGE H
• Application Number:
  US12/796,578
• Time in Patent Office: 203 Days
• Field of Search: 705/8
• US Class Current: 705/7.12
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling

Abstract

Techniques for refining a schedule involve identifying schedule alternatives to an original schedule and generating one or more substitute schedules using one or more of the schedule alternatives. An objective function is used to perform an analysis of the original schedule and the one or more substitute schedules, and a refined schedule is selected based on the analysis.

Claims

1. A computer-implemented method for automatically generating a seed schedule for a network of transportation resources, the method comprising:

defining a plurality of constraints for generating a seed schedule, the seed schedule corresponding to a plurality of segments to be served by a plurality of transportation resources, each segment representing a path to be traversed by a transportation resource and corresponding to a departure from a first market in a market pair and an arrival at a second market in the market pair;

assigning at least one of a possible departure window or a possible arrival window to each market pair in the seed schedule using the computer, with each departure window defining a plurality of possible departure times and each arrival window defining a plurality of possible arrival times;

using the computer to eliminate particular departure times or arrival times within the possible departure windows or possible arrival windows using constraint programming and based on a degree to which remaining departure times of the possible departure windows or remaining arrival times of the possible arrival windows satisfy the plurality of constraints;

identifying a plurality of routes in the seed schedule based on the plurality of constraints using the computer, each route in the plurality of routes including a plurality of sequentially connected segments, each segment having associated remaining departure or arrival times; and

generating the seed schedule from the identified plurality of routes using the computer.

2. The method of claim 1, wherein the plurality of constraints include mandatory and optional constraints.

3. The method of claim 1, wherein the plurality of constraints include a marketing day defining a start time and end time for at least one of departures or arrivals of transportation resources for a particular market.

4. The method of claim 1, wherein at least one of the plurality of routes includes a first segment sequentially connected to a second segment based on at least one of a market spacing constraint, a gate constraint, a simultaneous departure and arrival constraint, or preferred one-stop connections.

5. The method of claim 1, wherein eliminating particular departure times or arrival times includes eliminating the particular departure times or arrival times in an iterative process, wherein during at least one iteration, a particular departure time, arrival time, or sequential connection between particular segments is set as a constant value for future iterations.

6. The method of claim 5, wherein the plurality of constraints are applied in a sequence based on a predefined hierarchy of constraints, the constraints arranged in a hierarchy based on relative importance of each constraint to generation of the seed schedule.

7. The method of claim 6 wherein during each iteration, a potential elimination of a particular departure time or arrival time based on a constraint in the hierarchy that conflicts with a potential elimination of a different departure time or arrival time based on a different constraint higher in the hierarchy is prevented from occurring.

8. The method of claim 1, wherein eliminating particular departure times or arrival times includes eliminating potential sequential connections of particular segments.

9. The method of claim 1, wherein constraint propagation is used to apply changes across the possible departure windows or possible arrival windows of each of the market pairs based on elimination of a particular departure time or arrival time associated with a particular market pair.

10. An article comprising a non-transitory, machine-readable medium storing instructions for generating a seed schedule for a network of transportation resources, the instructions causing data processing apparatus to perform operations comprising:

defining a plurality of constraints for generating a seed schedule, the seed schedule corresponding to a plurality of segments to be served by a plurality of transportation resources, each segment representing a path to be traversed by a transportation resource and corresponding to a departure from a first market in a market pair and an arrival at a second market in the market pair;

assigning at least one of a possible departure window or a possible arrival window to each market pair in the seed schedule, with each departure window defining a plurality of possible departure times and each arrival window defining a plurality of possible arrival times;

eliminating particular departure times or arrival times within the possible departure windows or possible arrival windows using constraint programming and based on a degree to which remaining departure times of the possible departure windows or remaining arrival times of the possible arrival windows satisfy the plurality of constraints;

identifying a plurality of routes in the seed schedule based on the plurality of constraints, each route in the plurality of routes including a plurality of sequentially connected segments, each segment having associated remaining departure or arrival times; and

generating the seed schedule from the identified plurality of routes.

11. The article of claim 10, wherein the plurality of constraints include a marketing day defining a start time and end time for at least one of departures or arrivals of transportation resources for a particular market.

12. The article of claim 10, wherein at least one of the plurality of routes includes a first segment sequentially connected to a second segment based on at least one of a market spacing constraint, a gate constraint, a simultaneous departure and arrival constraint, or preferred one-stop connections.

13. The article of claim 10, wherein eliminating particular departure times or arrival times includes eliminating the particular departure times or arrival times in an iterative process, wherein during at least one iteration, a particular departure time, arrival time, or sequential connection between particular segments is set as a constant value for future iterations.

14. The article of claim 13, wherein the plurality of constraints are applied in a sequence based on a predefined hierarchy of constraints, the constraints arranged in a hierarchy based on relative importance of each constraint to generation of the seed schedule.

15. The article of claim 14 wherein during each iteration, a potential elimination of a particular departure time or arrival time based on a constraint in the hierarchy that conflicts with a potential elimination of a different departure time or arrival time based on a different constraint higher in the hierarchy is prevented from occurring.

16. The article of claim 10, wherein eliminating particular departure times or arrival times includes eliminating potential sequential connections of particular segments.

17. The article of claim 10, wherein constraint propagation is used to apply changes across the possible departure windows or possible arrival windows of each of the market pairs based on elimination of a particular departure time or arrival time associated with a particular market pair.

18. A system for generating a seed schedule for a network of transportation resources, the system comprising:

memory operable to store a plurality of constraints associated with generating a seed schedule, the seed schedule corresponding to a plurality of segments to be served by a plurality of transportation resources, each segment representing a path to be traversed by a transportation resource and corresponding to a departure from a first market in a market pair and an arrival at a second market in the market pair; and

one or more processors operable to;

assign at least one of a possible departure window or a possible arrival window to each market pair in the seed schedule, with each departure window defining a plurality of possible departure times and each arrival window defining a plurality of possible arrival times;

eliminate particular departure times or arrival times within the possible departure windows or possible arrival windows using constraint programming and based on a degree to which remaining departure times of the possible departure windows or remaining arrival times of the possible arrival windows satisfy the plurality of constraints;

identify a plurality of routes in the seed schedule based on the plurality of constraints, each route in the plurality of routes including a plurality of sequentially connected segments, each segment having associated remaining departure or arrival times; and

generate the seed schedule from the identified plurality of routes.

19. The system of claim 18, wherein eliminating particular departure times or arrival times includes eliminating the particular departure times or arrival times in an iterative process, wherein during at least one iteration, a particular departure time, arrival time, or sequential connection between particular segments is set as a constant value for future iterations.