Integrated decision support system for optimizing the training and transition of airline pilots

• US 20030105656A1
• Filed: 11/13/2001
• Published: 06/05/2003
• Est. Priority Date: 11/13/2001
• Status: Active Grant

• Current Assignee: Navitaire LLC (Amadeus Global Travel Distribution S.A.)
• Original Assignee: Accenture Global Services GmbH (Accenture PLC)
• Inventors: Thengvall, Benjamin Glover, Pachon, Julian Enrique
• Granted Patent: US 7,346,528 B2
• Time in Patent Office: Days
• US Class Current: 705/8
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change
• CPC Class Codes: G06Q 10/1097 Task assignment

Abstract

An automated optimization system for generating training plans for airline pilots covering both pilot transitions and assignment to training classes for pilots who have received a system bid award, wherein such training plans are generated in less than one hour by first solving a MIP Model of the training/transition problem with an LP relaxation to determine a first level of feasibility, and then solving the MIP Model for an optimized feasible solution from which the training plan is derived.

Claims

1. An adaptive, dynamic, integrated, and automated optimizer system for rapid generation of alternative pilot training plans in response to a user request, which comprises:

a data base system having stored therein system bid information, pilot data, training information, and user request information including optimization options selected by said user request;

an optimizer controller in electrical communication with said data base system for receiving and acknowledging said user request, and generating therefrom an optimizer session for storage in said data base;

an optimizer container in electrical communication with said optimizer controller and receiving said optimizer session for issuing data requests and training plan generation requests;

an optimizer data provider in electrical communication with said optimizer container and said data base system, and receiving said data requests for retrieving data from said data base system for use in the generation of said alternative pilot training plans; and

an optimizer engine in electrical communication with said optimizer container and said optimizer data provider for generating a mixed integer programming model of said optimizer session in response to said training plan generation requests and based upon data retrieved by said optimizer data provider from said data base system, for solving a linear program relaxation of said mixed integer programming model and thereafter solving said mixed integer programming model to provide a feasible optimized solution, and for deriving an optimized pilot training plan from said feasible optimized solution.

2. The adaptive, dynamic, integrated, and automated optimizer system of claim 1, wherein said mixed integer programming model is comprised of an objective function with variables and constraints, and said objective function is:

3. The adaptive, dynamic, integrated, and automated optimizer system of claim 2, wherein two of said constraints respectively cause all pilots who are straight advances to a same position to be advanced in seniority order, and all pilots who are straight displacements to be advanced in reverse seniority order as follows:

4. The adaptive, dynamic, integrated, and automated optimizer system of claim 2, wherein two of said constraints track shortages in block hours per position, and excesses in block hours per position as follows:

5. The adaptive, dynamic, integrated, and automated optimizer system of claim 2, wherein said constraints include three constraints to determine pay protection for pilots in a training set based on an order in which said pilots are trained and advanced, as follows:

6. The adaptive, dynamic, integrated, and automated optimizer system of claim 2, wherein said constraints include three constraints to determine pay protection for displaced pilots in a training set based on an order in which said displaced pilots are trained and advanced, as follows:

7. The adaptive, dynamic, integrated, and automated optimizer system of claim 2, wherein said constraints include two constraints to respectively determine pay protection for pilots in a training set that are already pay protected at a beginning of a planning horizon, and pay protection for pilots in a training set that are pay protected because they are advanced after an effective date, as follows:

8. The adaptive, dynamic, integrated, and automated optimizer system of claim 2, wherein said constraints include a constraint to determine pay protection for pilots 58 years old that could have held a position but said position was not awarded, as follows:

9. The automated optimizer system of claim 2, wherein said constraints include four constraints to determine pay protection for pilots 58 years old that hold a position but could have held a better one, as follows:

10. The adaptive, dynamic, integrated, and automated optimizer system of claim 2, wherein said user request includes number of new hires and a request to cluster new hires into groups, and said constraints include following three constraints:

11. The adaptive, dynamic, integrated, and automated optimizer system of claim 2, wherein said user request includes a requirement to cluster new hires into groups, and said optimizer engine determines an optimal number of new hires, and said constraints include following three constraints:

12. The adaptive, dynamic, integrated, and automated optimizer system of claim 2, wherein said user request includes a requirement for said optimizer engine to determine balance of captains and first officers in groups for a training class, and Max {N_c, N_f}=N_c, then a first of following constraints is added to said constraints for each fleet and each bid period to track said groups, and a second of said following constraints is added thereafter to said constraints to enforce minimum percentage:

Σ

captains going to training in month t+C_t>

=Σ

first officers going to training in month t+F_t, and

13. The adaptive, dynamic, integrated, and automated optimizer system of claim 2, wherein said user request includes a requirement for said optimizer engine to determine balance of captains and first officers in groups for a training class, and Max {N_c, N_f}=N_f, then a first of following constraints is added to said constraints for each fleet and each bid period to track said groups, and a second of said following constraints is added thereafter to said constraints to enforce minimum percentage:

Σ

captains going to training in month t+C_t<

=Σ

first officers going to training in month t+F_t, and

14. The adaptive, dynamic, integrated, and automated optimizer system of claim 1, which further includes an optimizer protocol layer in electrical communication with a user and said optimizer controller for accommodating interactive communications between said user and said optimizer controller.

15. The adaptive, dynamic, integrated, and automated optimizer system of claim 1, wherein said optimizer engine determines costs associated with said LP relaxation, and uses said costs to modify cost factors of an objective function of said MIP Model to provide weightings of both block hour and dollar costs.

16. The adaptive, dynamic, integrated, and automated optimizer system of claim 2, wherein said optimizer engine minimizes an objective function of said mixed integer programming model to have a lowest value within a region defined by said constraints.

17. The adaptive, dynamic, integrated, and automated optimizer system of claim 1, wherein parameters of said mixed integer programming model are altered to provide multiple alternative solutions of said mixed integer programming model.

22. The method of claim 14, wherein a CPLEX software library is used to solve said MIP Model.

18. A method for rapidly generating alternative optimized plans for training airline pilots, which comprises the following steps:

receiving training problem information including system bid information, pilot data, and training information by way of a data input device, and a user request by way of a user interface, wherein said user request includes optimization options for generating said alternative optimized plans;

sorting said training problem information for each of said airline pilots for addition to a set of lists;

creating variables and constraints from said set of lists, and an MIP Model from said variables and said constraints;

solving a linear programming relaxation of said MIP Model to generate a first solution with said variables having first values;

if said first solution is feasible, modifying block hour costs to have a value roughly twice as large as dollar costs;

solving said MIP Model to generate a second solution with said variables having second values; and

if said second solution is feasible, generating a training plan with associated costs from said second values.

19. The method of claim 18, wherein said set of lists includes a retirement list, a no award list, a furlough list, a list of possible release months for pilots in said no award list and said furlough list, a list of 58 year old pilots, an advancement training list, a list of advancement months for pilots in said advancement training list, a list of classes to attend, a list of possible pay protecting pilots, an exception list, and a list of possible new hire advancement months;

20. The method of claim 18, wherein the step of generating a training plan includes the following steps:

creating a second set of lists including a list of pilots to be trained, a list of advancement pilots, a list of no award pilots, a list of furlough pilots, a list of release pilots, and a list of new hire pilots from said second values;

determining pilot headcount in each position each day from times of occurrence of pilot training, pilot advancement, no award releases, furlough releases, and hiring of new hires;

calculating block hour capability by multiplying said pilot headcount by pilot utilization values provided by a user for each position and each bid period;

comparing said block hour capability with required block hours provided by said user for each position and each bid period to determine block hour shortages and block hour excesses;

creating class rosters for said pilots to be trained for each bid period;

compute dollar costs associated with said second solution; and

preparing training plan based upon said second set of lists, said pilot headcount, said block hour shortages, said block hour excesses, said class rosters, and said dollar costs.

21. The method of claim 18, wherein a CPLEX software library is used to solve said linear programming relaxation.

23. The method of claim 20, wherein said training plan includes values for all of said variables in said MIP Model, and at least one of said list of advancement pilots, said list of pilots to be trained, said list of no award pilots, said list of furlough pilots, said list of possible pay protecting pilots, and class rosters for all pilots to be trained.

24. The method of claim 18, wherein said training plan includes at least one of pay protection costs, no award costs, furlough costs, and new hire costs associated with said second solution.

25. The method of claim 20, wherein said dollar costs include at least one of new hire, pay protection, no award, and furlough costs.

26. The method of claim 18, wherein said MIP Model is comprised of an objective function with said variables and said constraints.

27. The method of claim 18, wherein said optimization options include level of importance of cost factors in said objective function.

28. The method of claim 18, wherein said MIP Model is comprised of an objective function with variables and constraints, and said objective function is:

29. The method of claim 18, wherein two of said constraints respectively cause all of said airline pilots who are straight advances to a same position to be advanced in seniority order, and all of said airline pilots who are straight displacements to be advanced in reverse seniority order as follows:

30. The method of claim 18, wherein two of said constraints track shortages in block hours per position, and excesses in block hours per position as follows:

31. The method of claim 18, wherein said constraints include three constraints to determine pay protection for said airline pilots in a training set based on an order in which said airline pilots are trained and advanced, as follows:

32. The method of claim 18, wherein said constraints include three constraints to determine pay protection for displaced pilots in a training set based on an order in which said displaced pilots are trained and advanced, as follows:

33. The method of claim 18, wherein said constraints include two constraints to respectively determine pay protection for said airline pilots in a training set that are already pay protected at a beginning of a planning horizon, and pay protection for said airline pilots in a training set that are pay protected because they are advanced after an effective date, as follows:

34. The method of claim 18, wherein said constraints include a constraint to determine pay protection for said airline pilots 58 years old that could have held a position but said position was not awarded, as follows:

35. The method of claim 18, wherein said constraints include four constraints to determine pay protection for said airline pilots 58 years old that hold a position but could have held a better one, as follows:

36. The method of claim 18, wherein said user request includes number of new hires and a request to cluster new hires into groups, and said constraints include following three constraints:

37. The method of claim 18, wherein said user request includes a requirement to cluster new hires into groups, and said optimizer engine determines an optimal number of said new hires, and said constraints include following three constraints:

38. The method of claim 18, wherein said user request includes a requirement for said optimizer engine to determine balance of captains and first officers in groups for a training class, and Max {N_c, N_f}=N_c, and a first of following constraints is added to said constraints for each fleet and each bid period to track said groups, and a second of said following constraints is added thereafter to said constraints to enforce minimum percentage:

Σ

captains going to training in month t+C_t>

=Σ

first officers going to training in month t+F_t, and

39. The method of claim 18, wherein said user request includes a requirement for said optimizer engine to determine balance of captains and first officers in groups for a training class, and Max {N_c, N_f}=N_f, and a first of following constraints is added to said constraints for each fleet and each bid period to track said groups, and a second of said following constraints is added thereafter to said constraints to enforce minimum percentage:

Σ

captains going to training in month t+C_t<

=Y first officers going to training in month t+F_t, and