Generating and tuning an allocation of transportation resources

• US 7,707,056 B1
• Filed: 04/28/2005
• Issued: 04/27/2010
• Est. Priority Date: 04/28/2005
• Status: Expired due to Fees

• Current Assignee: Southwest Airlines Company
• Original Assignee: Southwest Airlines Company
• Inventors: Anbil, Ranga, Heinold, Alex Michael
• Primary Examiner(s): Jeanty; Romain
• Assistant Examiner(s): WALKER III, GEORGE H
• Application Number:
  US11/117,770
• Time in Patent Office: 1,825 Days
• Field of Search: 705 7- 12
• 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/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management

Abstract

A schedule for a network of transportation resources is produced by generating a proposed schedule that satisfies at least one predefined constraint using constraint programming. Multiple schedule alternatives including the proposed schedule and at least one alternative to the proposed schedule are identified, and the schedule alternatives are analyzed using an objective function to identify a refined schedule.

Claims

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

identifying a plurality of constraints for a potential schedule;

automatically building a proposed schedule by;

assigning specific schedule options corresponding to each of a plurality of sets of previously unassigned schedule options in each of a plurality of iterations, wherein the schedule options include at least one of possible departure windows or possible arrival windows for the transportation resources;

eliminating particular schedule options following each iteration of assigning specific schedule options, including at least portions of the possible departure windows or possible arrival windows, based on the plurality of constraints using constraint programming;

identifying a set of remaining schedule options defining the proposed schedule following the plurality of iterations, including at least one of a set of remaining departure windows or a set of remaining arrival windows, wherein the set of remaining schedule options are identified based on a degree to which the identified schedule options satisfy the plurality of constraints and the proposed schedule includes a plurality of routes, with each route including a sequential association of a plurality of segments, the sequential association of the plurality of segments for each route determined by;

generating a set of potential sequential associations of at least two segments and

selecting sequential associations from the set of potential sequential associations to generate a route based on a degree to which the route satisfies the plurality of constraints;

identifying a plurality of schedule alternatives, the plurality of schedule alternatives including the proposed schedule and at least one alternative to the proposed schedule, wherein the alternative comprises at least one departure time or arrival time not included in the proposed schedule; and

analyzing the plurality of schedule alternatives using an objective function.

2. The article of claim 1 wherein the plurality of constraints includes at least one constraint selected from a group consisting of a number of transportation resources, services to be provided by transportation resources, a number of segments to be served by transportation resources between each of a plurality of locations, and constraints on sequential associations of segments.

3. The article of claim 1 wherein each of the at least one alternative to the proposed schedule comprises a modification of at least a part of the proposed schedule.

4. The article of claim 3 wherein the proposed schedule includes a plurality of routings, each routing including a sequential association of a plurality of segments, and the modification comprises a change of at least one routing to produce a sequential association including at least one different segment.

5. The article of claim 4 wherein the modification comprises exchanging segments between at least two of the plurality of routings to produce at least two different routings.

6. The article of claim 3 wherein the proposed schedule includes at least one of a plurality of departure times or a plurality of arrival times and the modification comprises a change of at least one departure time or arrival time.

7. The article of claim 1 wherein analyzing the plurality of schedule alternatives comprises determining a score associated with each schedule alternative, the score produced using the objective function.

8. The article of claim 1 wherein analyzing the plurality of schedule alternatives comprises identifying a preferred schedule alternative.

9. The article of claim 8 further comprising:

generating a new plurality of schedule alternatives, the new plurality of schedule alternatives including the preferred schedule alternative and at least one alternative to the preferred schedule alternative; and

identifying a new preferred schedule alternative based on analyzing the new plurality of schedule alternatives using the objective function.

10. The article of claim 1 wherein the plurality of constraints comprises at least one constraint defining a restriction that the proposed schedule is required to satisfy and at least one preference.

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

defining a plurality of constraints;

using a processor to execute a constraint programming algorithm to automatically build a proposed schedule stored in memory by;

assigning specific schedule options corresponding to each of a plurality of sets of previously unassigned schedule options in each of a plurality of iterations, wherein the schedule options include at least one of possible departure windows or possible arrival windows for the transportation resources;

eliminating particular schedule options following each iteration of assigning specific schedule options, including at least portions of the possible departure windows or possible arrival windows, based on the plurality of constraints using constraint programming;

identifying a set of remaining schedule options defining the proposed schedule following the plurality of iterations, including at least one of a set of remaining departure windows or a set of remaining arrival windows, wherein the set of remaining schedule options are identified based on a degree to which the identified schedule options satisfy the plurality of constraints and the proposed schedule includes a plurality of routings, each routing including sequential associations of segments to be traveled by the transportation resources, the sequential associations selected from a set of potential sequential associations, each potential sequential association including at least two segments;

identifying a plurality of schedule alternatives, the plurality of schedule alternatives including the proposed schedule and at least one alternative to the proposed schedule, wherein the alternative comprises at least one departure time or arrival time not included in the proposed schedule; and

using a processor to analyze the plurality of schedule alternatives based on an objective function to identify at least one preferred schedule alternative.

12. The method of claim 11 wherein the plurality of constraints comprise services to be provided by transportation resources.

13. The method of claim 12 wherein the services to be provided by the transportation resources comprise segments to be traveled by the transportation resources.

14. The method of claim 11 wherein the plurality of routings are selected based on a degree to which the plurality of routings to satisfy the plurality of constraints.

15. The method of claim 13 wherein the proposed schedule is automatically built using a constraint propagation algorithm.

16. The method of claim 13 wherein the at least one alternative to the proposed schedule comprises a modification of at least one of changing at least two of the routings or changing a time associated with at least one segment.

17. The method of claim 16 wherein the objective function provides a measure of efficiency of each of the plurality of schedule alternatives.

18. The method of claim 17 wherein the measure of efficiency relates to at least one of demand, revenue, costs, or resource utilization.

19. The method of claim 17 further comprising:

identifying a plurality of new schedule alternatives, the plurality of new schedule alternatives including a particular one of the at least one preferred schedule alternatives and at least one modification of the particular preferred schedule alternative; and

analyzing the plurality of new schedule alternatives using the objective function to identify a new preferred schedule alternative.

20. The method of claim 17 further comprising performing a plurality of iterations of:

identifying a plurality of new schedule alternatives; and

analyzing the plurality of new schedule alternatives using the objective function to identify a new preferred schedule alternative, wherein the plurality of new schedule alternatives includes a preferred schedule alternative from a preceding iteration and at least one modification of the preferred schedule alternative from the preceding iteration.

21. A system for automatically building a schedule for a network of transportation resources, the system comprising:

a constraint programming module stored on a machine-readable storage medium operable to cause a processor to automatically build a proposed schedule based on a set of constraints, the proposed schedule including a plurality of segments to be served by the transportation resources and at least one instance of each segment, wherein each instance of each segment corresponds to a departure time or an arrival time for the segment, and the constraint programming module is operable to automatically build the proposed schedule by identifying sequential associations of segments to produce routes and identifying at least one valid instance of each segment, with each route including a subset of the plurality of segments and each segment assigned to a particular route and using constraint propagation to eliminate combinations of segments and instances of segments that do not satisfy the set of constraints; and

a mathematical programming module stored on a machine-readable storage medium operable to cause a processor to produce a modified schedule based on the proposed schedule using an objective function to evaluate a plurality of potential schedules, the plurality of potential schedules including the proposed schedule and the modified schedule, wherein the modified schedule includes at least one departure time or arrival time not included in the proposed schedule and an evaluation of the modified schedule using the objective function indicates an increased desirability relative to at least the proposed schedule.

22. The system of claim 21 wherein the mathematical programming module is further operable to evaluate the plurality of potential schedules in a plurality of iterations, with each iteration evaluating a corresponding subset of the plurality of potential schedules derived from a schedule identified in a preceding iteration and each iteration identifying a schedule from the corresponding subset of potential schedules, the identified schedule having an increased desirability relative to other potential schedules in the corresponding subset of potential schedules based on an evaluation using the objective function.

23. The system of claim 21 wherein the objective function produces a score corresponding to each of the plurality of potential schedules, with the score corresponding to the modified schedule being relatively higher than the score corresponding to each of the other potential schedules in the plurality of potential schedules.

24. The system of claim 21 wherein the mathematical programming module is operable to produce a modified schedule based on the proposed schedule by:

producing a plurality of schedule alternatives based on the proposed schedule;

evaluating the proposed schedule and the schedule alternatives using the objective function; and

identifying the modified schedule from the proposed schedule and the schedule alternatives based on the evaluation using the objective function.

25. The system of claim 24 wherein each of the plurality of schedule alternatives comprises a modification of a portion of the proposed schedule and the modified schedule comprises the proposed schedule as modified by at least one of the schedule alternatives.

26. The system of claim 24 wherein each of the plurality of schedule alternatives comprises an overall alternative schedule to the proposed schedule.