Tuning a schedule of transportation resources using mathematical programming

• US 7,734,493 B1
• Filed: 04/28/2005
• Issued: 06/08/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 III, GEORGE H
• Application Number:
  US11/116,901
• Time in Patent Office: 1,867 Days
• Field of Search: 705/8
• US Class Current: 705/7.22
• 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. An article comprising a machine-readable medium storing instructions for generating a refined schedule for a network of transportation resources, the instructions causing a data processing apparatus to perform operations comprising:

identifying an original schedule including a set of original routes, each of the original routes including a plurality of segments, and each segment in each of the original routes having an associated original departure or arrival window;

expanding the original departure or arrival window associated with a plurality of the segments;

identifying alternative candidate routes based on the expanded departure or arrival windows, wherein at least one of the alternative candidate routes includes a different set of segments than a corresponding original route in the original schedule;

evaluating the alternative candidate routes by using mathematical programming to determine a score for each alternative candidate route based on an objective function; and

selecting a refined schedule including at least one of the alternative candidate routes, the refined schedule selected based at least in part on the scores for the alternative candidate routes.

2. The article of claim 1 wherein the refined schedule includes a plurality of alternative candidate routes based on the original schedule, the selection of the refined schedule comprising identifying possible variations of instances in the original schedule.

3. The article of claim 2 wherein each possible variation of an instance comprises at least one of a time or a sequential connection between segments of a route, the time or the sequential connection for the possible variation associated with at least one particular segment of a route, and the time or the sequential connection being different than a time or a sequential connection associated with the instance.

4. The article of claim 3 wherein each instance in the original schedule comprising a segment of a route and each instance corresponding to at least one of a departure time, an arrival time, or a sequential connection with another segment of the route.

5. The article of claim 4 wherein each possible variation of an instance comprises at least one variation selected from a group consisting of a different departure time within a particular deviation from the departure time of the instance, a different arrival time within a particular deviation from the arrival time of the instance, and a sequential connection with a segment from a different route of the original schedule.

6. The article of claim 2 wherein each alternative candidate route comprises a possible variation of at least one instance in the original schedule.

7. The article of claim 2 wherein the selection of the refined schedule further comprises identifying a plurality of substitute schedules, each substitute schedule comprising portions of the original schedule and a set of alternative candidate routes.

8. The article of claim 7 wherein the original schedule and each substitute schedule include service for a predetermined set of segments, at least one segment in each substitute schedule having a different associated sequential connection than a sequential connection associated with the at least one segment in the original schedule.

9. The article of claim 7 wherein selecting the refined schedule further comprises using an objective function to calculate a composite score associated with the original schedule and with each substitute schedule based on values relating to schedule characteristics.

10. The article of claim 9 wherein the values relating to schedule characteristics relate to at least one of an estimated ability to meet demand, estimated revenues, estimated costs, or an estimated resource utilization.

11. The article of claim 9 further comprising comparing the composite scores associated with the original schedule and the substitute schedules, wherein selecting a refined schedule comprises selecting one of the original schedule or a substitute schedule as the refined schedule based on comparing the scores.

12. A computer-implemented method for generating a refined schedule, the method comprising the following steps performed by one or more processors:

identifying an original schedule including routes to be traveled by transportation resources, each of the routes including a plurality of segments, and each segment in each of the original routes having an associated original departure or arrival window;

identifying alternative candidate routes based on expanded departure or arrival windows associated with a plurality of the segments, wherein at least one of the alternative candidate routes includes a different set of segments than a corresponding route in the original schedule;

evaluating the alternative candidate routes by using mathematical programming to determine a score for each alternative candidate route based on an objective function that quantifies a desirability of at least one schedule characteristic; and

selecting a refined schedule including at least one of the alternative candidate routes, the refined schedule selected based at least in part on the scores for the alternative candidate routes.

13. The method of claim 12, wherein the alternative candidate routes are included in a plurality of alternative schedules generated by expanding the original departure or arrival windows associated with the plurality of the segments, the method further comprising:

performing a comparison of the original schedule and the plurality of alternative schedules using the objective function; and

identifying the refined schedule from the original schedule and the plurality of alternative schedules based on the comparison.

14. The method of claim 13 wherein generating a plurality of alternative schedules further comprises exchanging segments between at least two routes in the original schedule.

15. The method of claim 14 wherein generating a plurality of alternative schedules comprises:

selecting a sample of the routes in the original schedule;

identifying alternative times for segments from the expanded departure or arrival windows in each of the routes in the sample; and

identifying alternative sequences of segments using segments from at least some of the routes in the sample.

16. The method of claim 15 wherein the alternative times comprise times within a predetermined deviation from a corresponding departure or arrival window in the original schedule.

17. The method of claim 15 wherein selecting a sample of the routes in the original schedule comprises using a selection function to select routes having a relatively higher probability of modifications producing a schedule that compares favorably to the original schedule based on the objective function.

18. The method of claim 16 wherein selecting a sample of the routes comprises iteratively selecting routes using the selection function.

19. The method of claim 15 wherein:

each alternative schedule includes a combination of routes selected from a group consisting of the routes in the original schedule and the alternative candidate routes; and

performing a comparison of the original schedule and the plurality of alternative schedules comprises;

using the objective function to calculate a route score for each route selected from the group consisting of the alternative candidate routes and the routes in the original schedule; and

calculating a composite score for each alternative schedule by combining the scores of the routes in the combination of routes for the alternative schedule.

20. The method of claim 19 wherein calculating a composite score for each alternative schedule further comprises including at least one value reflecting a desirability of the combination of at least two routes in the alternative schedule.

21. The method of claim 19 wherein using an objective function that quantifies a desirability of at least one schedule characteristic comprises using values relating to at least one of an estimated ability to meet demand, estimated revenues, estimated costs, or an estimated resource utilization.

22. The method of claim 19 wherein selecting a refined schedule comprises selecting a schedule from the group consisting of the alternative schedules and the original schedule having a composite score indicating an increased desirability relative to other schedules in the group.