Tuning a schedule of transportation resources using mathematical programming

• US 7,848,944 B1
• Filed: 06/08/2010
• Issued: 12/07/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
• Primary Examiner(s): Jeanty; Romain
• Assistant Examiner(s): Walker; George H
• Application Number:
  US12/796,531
• Time in Patent Office: 182 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 iteratively refining a seed schedule for a network of transportation resources, the method comprising:

identifying a first seed schedule including a plurality of segments, with each segment connecting two markets and having at least one of a corresponding departure time or a corresponding arrival time, the first seed schedule further including paths to be traversed by a particular transportation resource, each path including a plurality of sequentially connected segments;

defining at least one of additional candidate departure windows or additional candidate arrival windows for at least one segment in the first seed schedule;

generating additional candidate paths with the computer from a set of available segments, each additional candidate path including a different plurality of sequentially connected segments than the paths in the first seed schedule, wherein the set of available segments includes at least a portion of the segments in the first seed schedule and at least a portion of the segments having at least one of additional candidate departure windows or arrival windows;

using the computer to generate a composite score using mathematical programming for the first seed schedule and at least one possible alternative schedule, wherein the at least one possible alternative schedule includes a different combination of candidate paths than the first seed schedule; and

identifying a replacement schedule with the computer by comparing the composite scores for the at least one possible alternative schedule and the first seed schedule.

2. The method of claim 1, wherein the composite score is generated based on at least a demand curve.

3. The method of claim 1, wherein the composite score is generated using an objective function defining a relative desirability of at least one particular combination of candidate paths.

4. The method of claim 3, wherein the composite score is determined based at least in part on a proximity loss of the at least one possible alternative schedule, wherein the proximity loss is an estimate of a reduction in demand resulting from proximity of nonstop flights to one-stop flights for particular market pairs.

5. The method of claim 1 further comprising using the replacement schedule as a second seed schedule in a second iteration of refining the first seed schedule if the replacement schedule is different from the first seed schedule.

6. The method of claim 1 wherein the first seed schedule is generated using constraint programming.

7. The method of claim 1 further comprising selecting one of the first seed schedule or the replacement schedule as a final schedule for fleet assignment.

8. The method of claim 1, further comprising selecting a final schedule for fleet assignment after a number of iterations of refining the first seed schedule, after a predefined time, or after a desired level of efficiency or revenue is reached.

9. The method of claim 1, wherein each segment is associated with at least one of a particular departure time or a particular arrival time of a particular transportation resource traveling from a particular origination market to a particular destination market.

10. The method of claim 1, wherein at least one additional candidate path including a different plurality of sequentially connected segments corresponds to a path in the first seed schedule, the at least one additional candidate path traversing the same sequence of markets as the corresponding path in the first seed schedule but including at least one segment with a different departure or arrival window as a corresponding segment in the corresponding path.

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

identifying a first seed schedule including a plurality of segments, with each segment connecting two markets and having at least one of a corresponding departure time or a corresponding arrival time, the first seed schedule further including paths to be traversed by a particular transportation resource, each path including a plurality of sequentially connected segments;

defining at least one of additional candidate departure windows or additional candidate arrival windows for at least one segment in the first seed schedule;

generating additional candidate paths from a set of available segments, each additional candidate path including a different plurality of sequentially connected segments than the paths in the first seed schedule, wherein the set of available segments includes at least a portion of the segments in the first seed schedule and at least a portion of the segments having at least one of additional candidate departure windows or arrival windows;

generating a composite score using mathematical programming for the first seed schedule and at least one possible alternative schedule, wherein the at least one possible alternative schedule includes a different combination of candidate paths than the first seed schedule; and

identifying a replacement schedule by comparing the composite scores for the at least one possible alternative schedule and the first seed schedule.

12. The article of claim 11, wherein the composite score is generated based on at least a demand curve.

13. The article of claim 11, wherein the composite score is generated using an objective function defining a measure of efficiency of at least one of meeting demand, estimated revenue, estimated costs, or estimated resource utilization.

14. The article of claim 13, wherein the composite score is determined based at least in part on a proximity loss of the at least one possible alternative schedule, wherein the proximity loss is an estimate of a reduction in demand resulting from proximity of nonstop flights to one-stop flights for particular market pairs.

15. The article of claim 11 wherein the operations further comprise using the replacement schedule as a second seed schedule in a second iteration of refining the first seed schedule if the replacement schedule is different from the first seed schedule.

16. A system for refining a seed schedule for a network of transportation resources, the system comprising:

memory operable to store information associated with a first seed schedule and possible alternative schedules; and

one or more processors operable to;

identify a first seed schedule including a plurality of segments, with each segment connecting two markets and having at least one of a corresponding departure time or a corresponding arrival time, the first seed schedule further including paths to be traversed by a particular transportation resource, each path including a plurality of sequentially connected segments;

define at least one of additional candidate departure windows or additional candidate arrival windows for at least one segment in the first seed schedule;

generate additional candidate paths from a set of available segments, each additional candidate path including a different plurality of sequentially connected segments than the paths in the first seed schedule, wherein the set of available segments includes at least a portion of the segments in the first seed schedule and at least a portion of the segments having at least one of additional candidate departure windows or arrival windows;

generate a composite score using mathematical programming for the first seed schedule and at least one possible alternative schedule, wherein the at least one possible alternative schedule includes a different combination of candidate paths than the first seed schedule; and

identify a replacement schedule by comparing the composite scores for the at least one possible alternative schedule and the first seed schedule.

17. The system of claim 16, wherein the composite score is generated using an objective function defining a relative desirability of at least one particular combination of candidate paths.

18. The system of claim 16, wherein the one or more processors are further operable to use the replacement schedule as a second seed schedule in a second iteration of refining the first seed schedule if the replacement schedule is different from the first seed schedule.