SYSTEM TOOL FOR AIRCRAFT ROUTING By PAULA MARGARET GRAY B . S c , Carleton University, Ottawa, 1983 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OP SCIENCE IN BUSINESS' ADMINISTRATION i n THE FACULTY OF GRADUATE STUDIES acuity of Commerce and Business Administration We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA October 1985 © P a u l a Margaret Gray, 1985 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y available for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the head of my department or by h i s or her representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of /^^l^^^ 5 ZOOM from Seven-Day to Three-Day Display. . 29 Figure 3-6 ZOOM from Three-Day to One-Day Display. . . 29 Figure 3-7 HALF-SCREEN LEFT Option 30 Figure 3-8 ZOOM to Eight-Hour Display 30 Figure 3-9 NEW PROGRAM FUNCTIONS Option 32 Figure 3.10 SELECT Aircraft Option 32 Figure 3.11 FIX Aircraft Option 33 Figure 3.12 FIX Aircraft with DOWN Option 33 Figure 3-13 SORT by Downtime Option 34 Figure 3-14 SPLIT SCREEN Option 34 Figure 3.15 SWAP Option : Select First Flight 37 Figure 3>l6 SWAP Option : Select Second Flight 37 Figure 3-17 Aircraft Routings Swapped 38 Figure 3-18 Aircraft Routings Brought Back to Cycle . . 38 Figure 3.19 REASSIGN Option : Select Flight 39 Figure 3.20 REASSIGN Option : Select Aircraft 39 Figure 3-21 Flight Reassigned. 40 Figure 3-22 Second Reassignment-to Match up Flights . . 40 Figure 3.23 VIEW FLIGHT with Omitted Information. . . . 43 Figure 3-24 VIEW FLIGHT Outside Window 43 i v LIST OF FIGURES (Cont'd) Figure 3.25 ADD NEW OPTION : Se lect Location and Add Information hk Figure 3'26 New Information Added and Displayed . . . . . kk Figure 3.27 CHANGE Option : Se lect F l i g h t and Adjust Information kS Figure 3-28 Information Changed and Displayed 45 Figure 3.29 DELETE Option : Se lect F l i g h t and View Information 46 Figure 3-30 Information Deleted and Displayed . . . . 46 Figure A . l Example of Cyc l ing Charts 60 Figure A.2 Example of Maintenance Schedule 61 Figure A.3 Example of A i r c r a f t U t i l i z a t i o n Charts . . . 62 v -ACKNOWLEDGEMENT The author of this thesis would like to express her appreciation to many who were involved in the development of this project. F i r s t , Mr. E, Bollo, Manager of Advanced Information Systems, CP Air, who gave the opportunity and support for this work. Many CP Air employees have taken the time to answer questions and give help when i t was needed. It is not possible to mention each by name. As well, the author i s grateful for the support of her thesis supervisors, Professor Dean Uyeno, Professor Maurice Queyranne, and Professor Michael Tretheway. Finally, the author would like to acknowledge her friends, who have been patient and encouraging through-out this project, 0 ' v i 1 SYSTEM TOOL FOR AIRCRAFT ROUTING CHAPTER 1 INTRODUCTION 1.1 Background on Scheduling The major concern of an a i r l ine is to plan and operate an aircraft schedule that wil l best serve the public, yield the greatest profits and maximize the ut i l i za t ion of its equipment. The process from schedule planning to operation in general wi l l involve the following aspects: 1. Schedule Construction This is the preparation of a working schedule of f l ights so that passenger demand is best sat isf ied. Typical questions that must be answered in this preparation are: a. Market Planning - What c i t ies should be served? b. Frequency Planning - What is the design of the route structure? - How often should these routes be flown? - What aircraft type and seat configuration is best for these f1ights? c. Time-of-Day Planning - What departure times should be assigned to these 2 f1ights? d. Aircraft Rotations (flight patterns that could be operated by the aircraft) Can this schedule be operated with the given fleet? - What is the minimal number of aircraft needed to operate the schedule? 2. Schedule Evaluation This is the analysis of a given working schedule. Typical questions include: a. What are the expected costs and revenues to be generated from operating this schedule? b. Is i t operationally feasible? Are there sufficient opportunities for ma i ntenance? Are the times between fl ights sufficient to service the aircraft? - Can crews be feasibly assigned? c. Are there opportunities for extra flying? d. Could the schedule be adjusted so that i t required fewer aircraft? e. How well can the schedule handle changes that wi l l inevitably occur? - Are there sufficient opportunities for aircraft exchanges to be performed? (places where aircraft could be rerouted) In general, the development of the schedule is an 3 i t e r a t i v e process of schedule const ruct ion and e v a l u a t i o n . 3. A i r c r a f t Routing Once a f i n a l vers ion of the schedule has been approved, a i r c r a f t t a i l numbers (al l a i r c r a f t are uniquely numbered) are assigned to the f l i g h t s . In genera l , th i s involves ad just ing the a i r c r a f t ro ta t ions prev iously developed. k. Dynamic Scheduling Many changes to the plan occur during the l i f e of the schedule. These changes can sometimes be handled qu i te e a s i l y , but a l s o can have rami f i ca t ions invo lv ing reschedul ing of f l i g h t s and a i r c r a f t throughout the per iod of the schedule. If reschedul ing is requ i red , then an attempt is made to return to the o r i g i n a l plan as soon as p o s s i b l e . The foil-owing are examples of poss ib le changes that might occur : a . Requests for extra usage c h a r t e r s , extra s e c t i o n s , crew t r a i n i n g , adve r t i s ing requirements, e t c . b. Adjustments to maintenance schedule - unexpected maintenance work, an a i r c r a f t la te out of i t s check, or extreme v a r i a t i o n s in a i r c r a f t f l y i n g hours that could cause maintenance reschedul i ng c. Emergency s i t u a t i o n s - weather cond i t i ons , crew u n a v a i l a b i l i t y , or equ i pment fa i1ure h These changes can only be handled as they a r i s e in schedule o p e r a t i o n , and hence th is area is r e f e r r e d to as "dynamic schedu l ing" . Etschmaier and Mathaisel (1984) give a conc ise and complete overview of the work that has been done in each of these a reas . In summary the i r f ind ings are : 1. The problem of a i r c r a f t schedul ing does not have an a n a l y t i c a l so lu t ion due to a changing environment, cons t ra in ts that are dependent on circumstances and people, and a m u l t i - c r i t e r i a ob ject ive func t ion that cannot be completely q u a n t i f i e d . 2. The l i m i t a t i o n s of the computer and the v e r s a t i l i t y of the human mind in planning dec is ions in a changing environment have been recognized. Thus the " s t a t e - o f -t h e - a r t " work is concentrat ing on developing an in te r face between man and machine so that both perform the tasks they are best su i ted f o r . 3. There are no systems in p r a c t i c a l use that have found an optimal balance between the ro les of human judgement and c a p a b i l i t i e s of the computer, and few that have any imbedded Operations Research models for op t imiza t ion and s imu la t ion . The use of Operations Research has mostly been to help conceptual ize and formal ize the schedul ing process . The focus of this project is in the areas of aircraft routing and dynamic scheduling. The main purpose being to track the individual aircraft in order to be able to dynamically plan and respond to the changes that wi l l occur during' the l i fe of the schedule. Etschmaier and Mathaisel (1984) report that no work specif ical ly in this area has been published to date. 6 1.2 Si tuation at CP Air At CP Air , several areas of Operations are responsible for managing the aircraft routings and any subsequent schedule changes. Maintenance Planning establishes the maintenance schedule and the routing of the narrow-body aircraft ; Operations Planning routes the wide-body aircraft and co-ordinates a l l changes to the schedule beyond the next ten days of operation; and Operations Control handles a l l unforeseen circumstances during the next ten-day period. Operations Planning is the key source of planned aircraft routings and the key co-ordinator of the decision-making process involving aircraft usage. The role of Operations Planning has been termed "Aircraft Cycling and Substitutions". Aircraft cycling involves routing the aircraft onto repeating patterns of f l ights . The main purpose of aircraft cycling is to eff ic iently satisfy the requirements of the schedule and maintenance. Often a l l the requirements cannot be met and aircraft substitutions are necessary. For a more detailed description of Operations Planning, see Appendix A. The present approach to aircraft routing is a tried and proven method used in the same or similar form by many air l ines as well as CP Ai r . It involves producing large charts that graphically portray the aircraft routings. However it is a manual system and therefore the process is long and tedious. The charts have to be drawn and the 7 schedule graphically displayed on it before the cycling begins. The cycling requires numerous iterations in order to assess different routing patterns to satisfy maintenance requirements and other constraining situations. The aircraft are then routed according to the cycling pattern chosen, making adjustments where necessary. Subsequent changes to the schedule and routings cause the charts to become messy with a l l the erasures of lines and drawing of new ones. The analysis of a range of alternatives can also be a long and tedious process. Some alternatives can be evaluated by modifying the permanent routings on the master sheets. More often, when a complex set of circumstances occurs involving several aircraft , it is_ necessary to reproduce the charts for the period of time required and experiment with d i f f i cu l t routings until a satisfactory solution is reached. This then has to be transferred to the master sheets and the old routing erased. Occasionally the solution wil l not satisfy a l l the cycling conditions and some further manipulation is required. As well , a record of a l l the changes must be compiled and a f l ight order distributed to a l l the departments concerned, especially Maintenance Planning, Crew Scheduling and Payload Control (personnel who control passenger booking) when the changes have affected the maintenance plan, type of aircraft or the seat configuration. 8 The size of the fleet has now made it impossible to arrange a l l the aircraft on one sheet so cross referencing to a second sheet becomes d i f f i c u l t . It is very apparent that there are heavy time and labor requirements to produce and update the aircraft u t i l i za t ion charts. Even minor changes could cause much work to keep the charts up to date and everyone informed. This is clearly an inefficient use of manpower. The present manual method does not adequately support the needs of the Operations Planning area. What is needed is an automated system that wi l l include the information produced on the charts plus the ab i l i ty to make changes so that the resulting information can be more effectively used than with the present manual method. 9 CHAPTER 2 DECISION SUPPORT APPROACH 2.1 Decision Support Systems A Decision Support System (DSS) is an interactive computer-based system that helps decision-makers u t i l i z e data and models to solve semi-structured problems. Traditional programming techniques cannot be applied to these problems since in general they involve many qualitative constraints requiring human judgment. DSS tries to create a balance between these two factors of human judgment and ab i l i ty of the computer. It focuses its attention on key decisions and tries to improve the effectiveness of the decision-making process. Effectiveness l ies in the ab i l i ty to identify what information is needed in order to solve the problem and to present this in a clear and usable manner. The decision-maker must then be able to analyze a range of alternatives plus the consequences of each. According to Keen and Morton (1978), DSS can be useful in a situation that ifivolves some of the following character i st i cs: "1. The existence of a large data base, so large that the manager has d i f f i cu l ty accessing and making conceptual 10 use of i t . 2. The necess i ty of manipulation or computation in the process of a r r i v i n g at a s o l u t i o n . 3. The ex istence of some time pressure , e i ther for the f i n a l answer or for the process by which the d e c i s i o n is reached. k. The necess i ty of judgment e i ther to recognize or decide what cons t i tu tes the problem, or to c reate a l t e r n a t i v e s , or to choose a s o l u t i o n . The judgment may def ine the nature of the va r iab les that are considered or the values that are put on the known v a r i a b l e s . " A Decis ion Support System is t o o l - o r i e n t e d rather than process -o r iented and thus does not r e s t r i c t the user to a p re -def ined process , but rather allows him to develop h is own methods for so l v ing problems. Thus the system needs to be b u i l t with feedback from the user to ensure that the development is proceeding c o r r e c t l y . The approach is to implement an i n i t i a l design and then af te r a short per iod of use, the system is evaluated and modi f ied . This i t e r a t i v e design is repeated several times un t i l a s tab le system is es tab l i shed. Thus the development of a dec i s ion support tool can be viewed as a learning process (see Lembersky, 1984) for the user by which he d iscovers new leve ls of support for dec i s i on-mak i ng 12 2.2 System Objectives The main objectives of this project are defined to be: 1. To implement a decision support system. A DSS approach to the areas of aircraft routing and dynamic scheduling seems appropriate because of the following characteristics: a. The existence of a large data base, with the need to reference, visualize and cross-reference information on aircraft routings. b. The necessity of experimenting with complex routings . until a satisfactory solution is reached. c. The existence of some time pressure for answers, in particular the handling of emergency situations in Operations Control. d. The existence of many constraints and objectives (some qualitative) that require human judgement to discern how to pr ior i t i ze in a given situation. Typical constraints include: i . Maintenance requirements Aircraft must be brought in -for checks at the proper times, and the must be balanced. i i . Operational Requirements A typical operational requirement mai ntenance f lying hours is the time 13 required to serv ice an a i r c r a f t depending on the s t a t i o n . i i i . Route R e s t r i c t i o n s The label ' route r e s t r i c t i o n 1 is used to denote a broad c l a s s of requirements cons t ra in ing c e r t a i n a i r c r a f t to c e r t a i n f l i g h t s . The most common route r e s t r i c t i o n is for a i r c r a f t to f l y those f l i g h t s that al low for i t s type and seat c o n f i g u r a t i o n . Cer ta in routes a l s o requi re a i r c r a f t with spec ia l c h a r a c t e r i s t i c s such as maindeck baggage, bunks, or extended range ( larger fuel tanks) . There are often q u a l i t a t i v e cons iderat ions where one a i r c r a f t is better su i ted than another. In genera l , a f l i g h t is never s p l i t using two d i f f e r e n t a i r c r a f t s ince th is is an inconvenience for the passengers and baggage handlers . i v . S ta t ion (Airport) requirements S tat ion requirements refer to any cons iderat ions that are p a r t i c u l a r to a c e r t a i n a i r p o r t . An example of a s ta t ion requirement is that Toronto a i r p o r t is c losed between midnight and 7:00 a.m. Another cons iderat ion could be the a v a i l a b i l i t y of f i r e prevention workers at the time of a r r i v a l at an a i r p o r t . v. A v a i l a b i l i t y of a properly t ra ined crew Crews are t ra ined for s p e c i f i c a i r c r a f t so an 14 a i rcraft subst i tut i on may require crew reschedu1i ng. As well , there are limits to the hours the crew are required to work, so a crew would be entitled to "book-off" if the delay of a f l ight caused these limits to be exceeded. These constraints are enforced as much as possible, however, no constraint is absolutely binding. For instance, aircraft can be substituted, bunks can be added, maintenance requirements have bu i l t - in leeway, aircraft can be serviced in less time if necessary, and special arrangements can be made for station requirements. There is a cost associated with violating any constraint and this cost is both monetary and qualitative in terms of passenger inconvenience. In any situation, an effort is made to minimize the passenger inconvenience. For this reason, human judgement is required to determine the best course of action. These constraints must be balanced as often there is no "r ight" solution, but there are "better" solutions. Aircraft routing and dynamic changes rely on the experience of the planner in discerning which constraints have higher priori ty in a given situation. A computer program could not hope to replicate this experience. Thus a DSS would allow the planner to use his experience, and since it is tool-oriented rather than process-oriented it would allow a variety of planners to develop their own methods. 2. To implement a DS system that is easy to use. 15 Although the users have years of invaluable exper ience, they are non - technica l people. It is important for them to become f a m i l i a r with the computer and what i t can do for them. In order to develop an useful tool that the users w i l l support , th i s system should: - requi re a minimal knowledge of computers or computer 1anguages - use concepts f a m i l i a r to them - s t a r t small and bu i ld depending on the i r d i r e c t i v e s . 3- To focus on key aspects of the problem that w i l l d i r e c t l y support the decis ion-making process. These have been def ined to be: a . I d e n t i f i c a t i o n of downtime periods ( id le time for the a i r c r a f t ) in terms of c i t y , time and length. This w i l l e s t a b l i s h the a i r c r a f t a v a i l a b i l i t y for extra usage, given the current rout ings . b. I d e n t i f i c a t i o n of exchange p o i n t s . The exchange points are the places in time where two a i r c r a f t are at the same c i t y at the same time and each could perform the o t h e r ' s next a l l o c a t e d f l i g h t . These cons t i tu te the bas ic means of a i r c r a f t r e r o u t i n g . c . Generation of "what - i f " s i t u a t i o n s . It is important to be able to experiment with the a i r c r a f t rout ings without necessar i l y making the changes permanent, yet a lso to have the opt ion to do so. 16 Thus the aim is to develop a set of interactive-graphic tools that wil l allow for modifications to a given schedule and set of aircraft routings. These graphic tools wi l l help to make the DSS approach similar to the existing manual methods. The key aspect involved in developing aircraft routings is that the planner needs a starting solution of routings that satisfy schedule requirements from which he can make adjustments for maintenance requirements. The present approach at CP Air starts with basic cycles that are weekly f l ight patterns that could be operated by the a ircraft . (1) Operational cycles are developed by rotating the aircraft onto the basic cycles in order to satisfy some maintenance requirements. Further adjustments to the operational cycles have to be made in order to satisfy a l l schedule and maintenance requirements. See Appendix A for a more detailed description. Another approach used by other a ir l ines is the computer generation of aircraft routings to meet schedule requirements and maintenance requirements. The question then arises whether or not it is necessary to reproduce the present approach exactly, or if there are better ways of routing aircraft . Often the operational (1) These weekly cycle patterns were developed in schedule planning for many potential schedules, and were used to i l lustrate that the given schedule could be performed with CP Ai r ' s f leet . 17 cycles after adjustments do not end up resembling the basic eye 1es. For now, the approach taken to aircraft routing wil l be to i n i t i a l i z e the routings to meet basic schedule requirements, then modify them with the above tools to obtain the planned aircraft routings that satisfy a l l schedule and maintenance requirements. If desired, these routings can be f i r s t modified to resemble the weekly cycle patterns. The tools can then be used to handle a l l subsequent changes. 18 CHAPTER 3 SYSTEM CAPABILITIES 3.1 Overview The following sections describe the basic functions provided by the system. 3.1.1 Aircraft Routings A First-In-First-Out (FIFO) algorithm is used to route the aircraft considering schedule requirements of aircraft type and seating.- See Appendix B for a more detailed description of thi-s program. These routings are copied to the interactive system for further manipulation. Within this system, two sets of routings are maintained, a working version and a permanent version. Modifications are made only on the working version, but at any point this version can be made permanent. Alternatively, at any point the working version can be reset from the permanent. 3.1.2 Typical Display Elements The following is a description of the basic elements that would be found on a display. 19 1. Season of the current schedule. An example of th i s would be 'S : W85' for i n d i c a t i n g that the information is from the Winter 1985 schedule . 2. T imel ine corresponding to the d i s p l a y . A l l times used are GMT times (Greenwich Mean Time) , where each date is shown as YYMMDD/day of week, separated by hour counts to ind icate the r e l a t i v e f low of t ime. 3. A i r c r a f t t a i l numbers. Present ly t a i l numbers which uniquely i d e n t i f y the a i r c r a f t , are shown along the v e r t i c a l ax is of the d i s p l a y . Considerat ion w i l l be given to whether a i r c r a f t type and/or conf igura t ion need to be shown. h. Display of rout ings corresponding to t a i l numbers. A rout ing is t y p i c a l l y d isp layed as a sequence of - f l i g h t numbers with downtime periods in each c i t y h igh l ighted with co lor bars . These downtime per iods have been colored for the major c i t i e s , p laces where a i r c r a f t are commonly exchanged. For instance, Vancouver is colored b lue , and Toronto green. The a r r i v a l and departure times are marked below the b a r s . 5. D e f i n i t i o n of Program Function keys. There are several sets of program funct ions a v a i l a b l e . A d e f i n i t i o n of the current set is d isp layed at a l l t imes. 6. Function i n d i c a t o r . The name of the funct ion cur rent l y in use is labelled, in order to c lar i fy whether the system is waiting for the user to complete a function, or awaiting the next. In the latter case the indicator wi11 display 1CMD : 1 . 7. Command/Message l ine . This f ie ld confirms with the user the task he is performing with the program function keys and the cursor. In general, the system wil l await for a Perform or Abort si-gnal before proceeding. This f ie ld is also used to build and view f l ight messages, as well as reporting to the user any error messages. 3 . 1 . 3 Window Concept The main problem with creating ways of displaying information on a screen, is that the user is accustome_d to seeing larger quantities of information at a glance. The manual charts show one week of routings for either the wide or narrow-body aircraft . To compensate for this the display behaves as if a window were placed on top of the aircraft u t i l i za t ion charts. The following functions are provided to control the movement of the window: 1. LEFT/RIGHT moves the window backwards and forwards in t i me 2. HLEFT/HRIGHT moves the window half a screen back or forward in time 3 . UP/DOWN moves the window up and down through the ai rcraft . 21 3.1 .4 Time Intervals In order to allow for seeing an overall picture of the routings as well as the deta i l , four different displays are available, each with varying amounts of information. 1. The seven-day display shows the f l ight numbers of the aircraft routings for a one-week period. This is similar to the routings maintained on the walls in Operations Control and Maintenance Planning. 2. The three-day display shows the f l ight numbers and downtime periods of the aircraft routings. Downtime periods that are approximately one hour, only warrant one column on the display and are asterisked to indicate that the airport code has been omitted. The main use for this display would be to. scan for large downtime periods or exchange points. 3. The one-day display shows the f l ight numbers, downtime periods and GMT times for a one-day time interval . Information that had to be omitted due to space limitations is asterisked. Each column represents twenty minutes. h. The eight-hour display is the most detailed and indicates the same information as the one-day. In general, no information has to be omitted from this display. Each column represents approximately seven minutes. 22 Functions are provided for moving between the different displays. They are: 1. ZOOM to a smaller time interval. 2. WIDE to a larger time interval. 3 . 1 . 5 Adjusting View One problem with the present manual method is cross-referencing aircraft , especially when they are in separate books. The following functions were provided to help in this area: 1. SELECT specific aircraft to be grouped together. 2. SORT the aircraft by downtime in a particular airport. This wi l l move a l l aircraft that are in the specified airport code for the time interval currently being viewed to the top of the display in order of decreasing downtime size. 3- FIX an aircraft to the top of the display. This wi l l allow a specified aircraft to be displayed at a l l times, and thus compared against a l l other aircraft with the window functions. h. SPLIT wil l simultaneously display the temporary and permanent routings, so that changes can be compared against the original routings. This referencing back allows the user to have a better understanding for the consequences of his changes, as well as indicating what 23 further changes are necessary in order to bring the aircraft back to the original routing at the earliest poss i ble pi ace. 3 - 1 . 6 Updating of Data Base In order to understand the update functions, the following terms have been defined for this project. F1ight Sector is the service provided between a city pair with a defined origin and destination c i ty , characterized by departure and arrival times. F1i ght is a combination of one or more f l ight sectors, characterized by a common f l ight number and aircraft requirement. Flight Occurrence is the scheduled service of a f l ight on a particular date in time. Aircraft Routing is the assignment of f l ight occurrences to the a ircraft . The aircraft routings can be modified with the following functions: 1. SWAP the aircraft routings at the exchange point specified by two f l ight occurrences. 2. REASSIGN a f1ight occurrence to another a ircraft . Capabilities for updating f1ight information are: 1. ADDNEW adds a new fl ight to the data base and assigns 24 an occurrence of i t to the s p e c i f i e d a i r c r a f t . 2. ADDOLD assigns a new occurrence of a f l i g h t already in the data base to the s p e c i f i e d a i r c r a f t . 3. CHANGE modif ies the f l i g h t information for a f l i g h t occurrence, by c reat ing a new f l i g h t and rep lac ing the o ld f l i g h t occurrence with a new f l i g h t occurrence. 4. DELETE removes a f l i g h t occurrence from an a i r c r a f t . In both the CHANGE and DELETE opt ions , i f there are no occurrences of a f l i g h t remaining, then the f l i g h t is removed from the data base. F i n a l l y a f a c i l i t y • has been provided to add, change, de le te and view messages to a p a r t i c u l a r f l i g h t occurrence. These are indicated by a red f l a g on the f l i g h t number. 25 3.2 Sample Runs Examples of the system capabilit ies can be seen in the following pictures. The system is menu-driven with a main menu and submenus, as seen in Figures 3«1 and 3«2. Options 2 and 3 on the main menu for creating back-up versions of experimental routings, and for producing hardcopy output of selected information have not been implemented yet. ENTER YOUR CHOICE |_. 1- DISPLAY/UPDATE ROUTINGS 2- BACK-UP VERSION 3- HARD-COPY Pf: 1-HELP 3-BACI 12-: F i gure 3 • 1 Main Selection Menu ENTER DATE(DD-HH-YY): 1- 8 HOUR DISPLAY 2- 1 DAY DISPLAY 3- 3 DAY DISPLAY 4- 7 DAY DISPLAY DATA Is AVAILABLE m zV-UCI-ob IU M-HUV-8!> PF: 1-HELP 3-1- • 12-EXIT 27 Figures 3-3 to 3-8 display the various time intervals for viewing the routings, as well as several windowing options. Figures 3-3 and 3-4 i l lustrate the seven-day display with the use of the DOWN option to view from the wide-body aircraft to the narrow. The cursor was moved from November h to November 6 before ZOOMing to the three-day display, as seen in Figure 3-5, and ZOOMing again to the one-day display is seen in F i gure 3•6• The HALF-SCREEN LEFT option is i l lustrated in Figure 3.7. The Cursor was then repositioned to the time interval desired before ZOOMing to the eight-hour display. The ZOOM f ac i l i ty analyses the cursor position, and zooms to the corresponding time interval , positioning the top of the window on the aircraft identif ied. 28 '-387 8 0 202-203 381 311 478-479 254 284 285 301 -302 322-323 384 185-214 284 312 285-284 215 •3Tb 301 -302 3 201-200 478-479 283 254 Figure 3.3 Seven-day Display -54-%2 fc-%4 44|948-985 -A«9 r"7-31-b51 -b52-254 2bb-2fa7-5 29-20-91 I M-2fe • - 52-B5-44-45 -40-12 2b-3b-97 5-24-25-9 257-40-12 -1b Z8-Z1-9 -54-%2 59-30-72 175 95-90-27 22-23-944 989 b21-b22-2 b0-2b3-25 4 95-90-2T 05-b0b 35-50-84 2b 948-985 77-31-42-43-44-45 257-4:-9; 1b 948-985 0-bbl 29-20-91 99b 59-30-72 975 95-90-27 59-30-975 258-251-b 58-b43-b4 ob2-82-17 5l-2b0-2b 58 81 »-21-9t>5 •54-9fa2 2b 35-50 J5-5>:4-b 3-to0"-c>. - . ' - - - - 4 ; • H i 18-7-b3-5|b5-%4 3-9b4 b21-b22-b b28-250-2|bb-90-27 40.1 |53 948-985 29-971 23-185 51-42-43-1 5b-57 59-b09-b0 258-251-31 4-b05-b0b 2 33-b07-b0l Figure 3.4 Seven-day Display with DOWN Option 29 30 Figure 3.7 HALF-SCREEN LEFT Option Figure 3.8 ZOOM to Eight-hour Display 31 Figures 3-9 to 3«14 i l lustrate the f a c i l i t i e s for adjusting the view of the current information. This requires changing to a new set of program function keys, as seen in Figure 3>9. A set of aircraft were selected in Figure 3-10» which resulted in each of these being moved to the top of the d i splay. The FIX option was used to place aircraft 751 in a fixed f ie ld at the top of the display in Figures 3-11 and 3.12. The SORT option is i l lustrated in Figure 3-13. where it has sorted the aircraft in Vancouver (YVR) for November 6. This option sorts over whatever time interval the user is currently viewing. The SPLIT SCREEN option (Figure 3-14) displayed the permanent routings above the temporary routings, separated by the date 1i ne. A new aircraft ordering established by the SORT or SELECT option is maintained until either it is cancelled by using one of these options again, or the original ordering is RESTOREd. Similarly for the FIX and SPLIT SCREEN options. This allows for using the f a c i l i t i e s on the other program function sets with the new view established. 32 Figure 3.10 SELECT Aircraft Option 33 F i gure 3.11 . FIX Aircraft Option 34 Figure 3.13 SORT by Downtime Option Figure 3.14 SPLIT SCREEN Option 35 Figures 3-15 to $.22 i l lustrate the f a c i l i t i e s for rerouting the aircraft . These are located on the Modify Routings choice when changing to a new set of program function keys. The f i r s t sequence i l lustrates the SWAP f a c i l i t y , where the user must specify an exchange point by identifying two fl ights occurrences with the cursor. See Figures 3-15 and 3.16. A f l ight occurrence is always identified by placing the cursor anywhere on the area from the downtime preceding i t , to the end of the f l ight occurrence. The sy.stem then waits for the user to give the action signal (PF11 = ABORT function, PF12 = PERFORM function) before proceeding. At this point the system validates the input, checks that c i t ies match, and checks'the times. If the turnaround times (time intervals between consecutive f l ights occurrences) are less than a specified minimum, then the system flags this and waits for permission to proceed. Any errors are flagged and the function is aborted. Figure 3*17 shows the routings swapped at the specified exchange point. In Figure 3• 18, an exchange was performed two days later to bring the aircraft back to their original routings. This is commonly referred to as bringing the aircraft "back to cycle" . The REASSIGN option proceeds in a similar fashion to the SWAP option. Figures 3.19 to 3.22 i l lustrate the 36 reassignment of flights 69 and 60 on November 6, from aircraft 336 to aircraft 337• The main difference between the SWAP option and the REASSIGN option is the added f l e x i b i l i t y of being able to reallocate single f l ights occurrences, especially if an aircraft must be flown empty in order to position i t . The '?'s on the downtime interval indicate that the c i t ies on the routings do not match. 37 F igure 3.15 SWAP Option : Select f i r s t f l ight Figure 3.16 SWAP Option : Select second f l ight 38 Figure 3.17 Aircraft Routings Swapped F i gure 3 • 18 Aircraft Routings Brought Back to Cycle 39 F i gure 3.19 REASSIGN Option : Select Flight Figure 3.20 REASSIGN Option : Select Aircraft ho F i gure 3.22 Second Reassignment to Match up Flights 41 Figures 3-23 to 3«30 i l lustrate some of the options for updating f l ight information. These are located on the UPDATE option of the Modify Routings program -function keys. The VIEW FLIGHT f a c i l i t y displays f l ight information for the f l ight indicated by the cursor. This is particularly useful when information had to be omitted, or the user wishes to view the fl ights outside the edges of the window, as seen in Figures 3-23 and 3-24. (In Figure 3•>23• there was not enough room to write the f l ight number, 260) By VIEWing a f l ight and then using the ADD OLD Option, the user can add another occurrence of a f l ight already in the data base. (Not i l lustrated in figures.) The ADD NEW option allows the user to add a new f l ight to the data base. The user f i r s t specifies where he wishes to place the f l ight , then f i l l s in the f l ight information on the table provided. The system waits for the PERFORM signal before processing the val id i ty checks. If there are any errors, then the system flags a message and the user is requested to modify the information or ABORT the function. Similar to the SWAP option, the system needs approval if the turnaround times are less than the minimum required. The information then is added and redisplayed. Figures 3.25 and 3.26 i l lustrate the ADD NEW option, where a maintenance period has been added to the downtime. The CHANGE option (Figures 3.27 and 3.28) was used to change the times for this maintenance period. Similar checks to the ADD options were performed. 42 The DELETE option (Figures 3•29 and 3-30) was then used remove this maintenance period. A3 Figure 3.23 VIEW FLIGHT with Omitted Information Figure 3.24 VIEW FLIGHT Outside Window Figure 3.25 ADD NEW Option : Select Location and Add Information Figure 3.26 New Information Added and Displayed Figure 3-28 Information Changed and Displayed 46 Figure 3-29 DELETE Option : Select FJight and View Information Figure 3.30 Information Deleted and Displayed A7 CHAPTER it BASIC ELEMENTS OF THE INTERACTIVE SYSTEM 4.1 Data St ructures Important cons iderat ions in s e t t i n g up the data s t ructures were: 1. A l l s t ruc tures should be dynamic and allow for changes. 2. Must be able to re ference , r e a l l o c a t e and modify each f l i g h t occurrence. 3. A i r c r a f t rout ings need to be stored for the pe r iod , referenced by date and al low for changes, i .e . - , a i r c r a f t exchanges should be easy to perform. it. A l l the sectors of a f l i g h t are normally assigned to the same a i r c r a f t , so a f l i g h t occurence is chosen as the bas ic e n t i t y for the rout ings . The data are stored in the fo l lowing three basic groups: 1 . Schedule Data Within t h i s group, there are three c a t e g o r i e s . a . Schedule C h a r a c t e r i s t i c s - Season of schedule b. F l i g h t C h a r a c t e r i s t i c s - f1 i gh t numbers - number of f l i g h t sectors 48 - s t a r t i n g locat ion of sector information c . Sector C h a r a c t e r i s t i c s - or i g i n - d e s t i n a t i o n - departure time - a r r i v a l time Schedule data are stored in vectors/matr ices of informat ion, where a f l i g h t is uniquely referenced by the row index into the F l i g h t C h a r a c t e r i s t i c vec to rs . Thus a f l i g h t occurrence is uniquely referenced by the pai r (date, row index). 2. Routing Data The routings then are sequent ial l i s t s of f l i g h t occurrences. Each rout ing is referenced by a number from one to the maximum number of rout ings , a v a r i a b l e va lue . This reference number a lso indexes a matrix conta in ing information on the a i r c r a f t assigned to the rout ings . A i r c r a f t information includes t a i l number, type of a i r c r a f t , c o n f i g u r a t i o n , and number of s e a t s . This information was set up and used in e s t a b l i s h i n g the i n i t i a l set of a i r c r a f t rout ings . 3- Message Data Messages can be added to the f l i g h t occurrences. Two s t ructures are maintained for th i s purpose. The f i r s t is a l i s t of f l i g h t occurrences that have messages associated to 49 them and the second contains the corresponding messages. 4.2 Bui ld ing a Display The concepts and process for const ruct ing a d i sp lay are descr ibed below. 1. Determine the day and time interva l that the user wishes to view. 2. From the above information e s t a b l i s h a date range for v iewing. 3. Find the set of f l i g h t s for each rout ing that under l ie th i s date range, add the adjacent f l i g h t at each end of the range. 4. Ca lcu la te the locat ions for each a r r i v a l and departure i f they were to be placed on a tape c a l i b r a t e d according to the time interva l s e l e c t e d . 5 . The date range determines the le f t -most and r ight -most column of the tape that w i l l be part of the d i s p l a y . Compare the a r r i v a l and departure locat ions against these values and b u i l d the d i sp lay based on those that f a l l w i th in the range. 6. Send th i s d i sp lay to the screen adjust ing for any user spec i f i cat ions . 4 .3 Referencing a Display The usual means for the user to reference the d i sp lay 50 is with the cursor. The position of the cursor can be easily translated back to a position on the imaginary underlying tape structure, and back to time if needed. The row position immediately gives the routing, and the column position indicates which f l ight by comparing it against the arrival and departure locations temporarily saved for the current display. In general, each function provided references the display, makes the appropriate changes to the data, and either redisplays the current information, or rebuilds the display for a new range of information. See Appendix B for a more detailed description of the interactive system. 51 CHAPTER 5 AREAS OF FURTHER WORK Further work in the area of aircraft scheduling might involve the following l i s t of capabi1ities : 1. Multi-user system. Presently, the system is for a single-user. Operations Planning wil l use the system i n i t i a l l y as the system is developed, but ultimately what is needed is a multi-user system for Maintenance Planning, Operations Control and Operations Planning, who are a l l involved with the different aspects of aircraft routing. Further tools would have to be added to meet the specific needs of each of these areas. For instance, Maintenance would need to see flying hour counts for the a ircraf t . The output of this system would also be beneficial to many other areas of the a i r l ine , such as Payload Control, or Crew Scheduli ng. 2. Global Changes. Presently, a l l changes made to the routings and schedule can only be done on an individual basis. It would be beneficial , in terms of the user-effort involved, to be able to make changes effective throughout the period or a 52 r e s t r i c t e d set of c i rcumstances. 3. Stor ing of A l te rnat i ves The c a p a b i l i t y of s to r ing the. d i f f e r e n t scenar ios developed for later reference would be a major asset to the "what - i f " process . k. I d e n t i f i c a t i o n of A i r c r a f t Rerout ings. The users have expressed the need for the computer to answer the fo l lowing quest ions : - What d i f f e r e n t ways can the a i r c r a f t be rerouted in order to p o s i t i o n a s p e c i f i c a i r c r a f t at a given time and place? - What exchanges are necessary in order to br ing the a i r c r a f t back to the i r c y c l i n g patterns? 5. S t a t i s t i c s Generat ion. Typ ica l s t a t i s t i c s that might be b e n e f i c i a l a re : - to ta l a i r c r a f t f l y i n g hours - weekly a i r c r a f t f l y i n g hours - f l y i n g hours remaining to next maintenance check - a i r c r a f t u t i l i z a t i o n (comparison of f l y i n g hours to downtime hours) 6. Report Generat ion. Present l y , changes made to the data base are logged and can be output to a f i l e . It would be b e n e f i c i a l to develop a report ing system for these changes and for a s t a t i s t i c update. 53 ~l. Hardcopy F a c i l i t y . Presently, the displays can be printed, but without the color bars. They are d i f f i cu l t to read for this reason. This f a c i l i t y should be further developed. As well , options for printing selected information could be added. 8. Aircraft Rotations Modelling. It would be possible to use the present and future system capabilit ies for the development of aircraft rotations. (See Lebeuf, 1985) Operations research models could be added as further tools for user support. Etshmaier and Mathaisel (1984) discuss the models that have been used by other a i r l ines . These include assignment models, network flow models, dynamic programming, branch and bound, and various heuristic methods. (See also Hoist and- Sorenseff, 1984; Kayukawa, 1983) The aircraft rotations would also provide input to many other systems at CP Air that presently require manual data entry of f l ight connections. 5h CHAPTER 6 CONCLUSION 6.1 Summary This project can be summarized with the following remarks: 1. The DSS approach to aircraft routing and dynamic scheduling is very appropriate given the changing •circumstances and constraints. The system allows the - user to make decisions based on his knowledge and •experience, and attempts to support him in this, process. The system has focused on the key aspects of highlighting downtime periods apd exchange points, and key functions for modifying the information. One of its main strengths lies in the simplicity of approach and use. 2 . The system is a starting point in an area that has long needed some helpful automated tools. It wi l l save time and labor in charting, experimenting and f inal iz ing changes, aspects that have been burdensome with present approach. More work can be done in striking a better balance between man and machine. Presently the balance is heavy 55 on the human side, and more capabilit ies should be added to support the work. Beyond this there are many opportunities for growth and development into such areas as schedule planning and maintenance planning. 6.2 Stage of Implementation Operations Control have affirmed the usefulness of the tools in discussions and demonstrations, and some options, such as the message faci 1 ity, were added at their request. They have been eager to see the system put into practice and the project is just now in the stages of system testing and user-training. It wil l be used in parallel with the work in Operations Planning this f a l l . This wi l l allow for a more thorough evaluation, and appropriate modifications and enhancements can be made. 56 BIBLIOGRAPHY 1. Benbasat, I. and Y. Wand. "A Dialogue Generator and Its Use in DSS Design", Information and Management 5, 1982, pp. 231-241. 2. Benbasat, I. and Y. Wand. "A Structured Approach to Designing Human/Computer Dialogues", Working Paper No. 835, 1982. 3. Etschmaier, M. M. and D. Mathaisel."Aircraft Scheduling: the State of the Art" , Proc. of XXIV AGIFORS Symp., France, 1984. 4. Gaines, B. R. "The Technology of Interaction - Dialogue Programming Rules", Int. J . Man-Machine Studies 14, 1981, pp. 133-150. 5- Hoist, 0. and B. Sorensen. "Combined Scheduling and Maintenance Planning for an Aircraft Fleet", Operations Research, 1984. 6. Kayukawa, K. "ARAJIN (Aircraft Routing and Automatically Job Integrating at Narita Base Station) System", Proc. of XXIII AGIFORS Symp., Tennessee, 1983 -7. Keen, P. G. , and M. S. Morton. Decision Support Systems An Organizational Perspective, Addison-Wes1ey Publishing Co., Reading, Mass., 1978. 8. Lebeuf, D. " L 1 A11ocation des Appareils pour un Horaire Aerien : Une Approche Interactive-Graphique", M.S"c. Thesis, University of Montreal, Centre for Transportation Research, Montreal, 1985-9. Lembersky, M.R., and U. H. Chi. " 'Decision Simulators' Speed Implementation and Improve Operations", Interfaces 14, 1984, pp. 1-15. 10. Sprague, R. H. and E. D. Carlson. Building Effective Decision Support Systems, Prentice-Hall Inc., New Jersey, 1982. 57 APPENDIX A PRESENT APPROACH TO AIRCRAFT CYCLING AND SUBSTITUTIONS A . l Ini t ia l izat ion of Aircraft Routings A . l . T Preparation of Charts The entire schedule for the six-month period is visually displayed on a master copy of the Aircraft Ut i l izat ion Chart, a grid of time versus type of route, to show the location of the aircraft at any given time. The chart covers one week from Sunday to Saturday in Greenwich Mean Time (GMT), and the routes are categorized by aircraft type and d i s t r i c t . The organization of the charts is planned for each period in a way that wi l l be most beneficial for the planner. The charts must then be drawn, and the fl ights placed according to route categories chosen. Each f l ight is displayed as a horizontal bar indicating its GMT times, c i ty codes, f1ight number, and dates for which the f l ight is operative. The chart is then duplicated and each week is individualized by dating the- days and whiting out the fl ights which are inoperative for that week. A.1.2 Establish Operational Cycles The next step in the aircraft routing process is to develop operational cycles of f l ights that wil l be used as a pattern to route aircraft for the period. Using the basic cycling charts from the schedule development process, as seen in Figure A . l , aircraft exchange points are found so that the aircraft can be rotated onto the various cycles that allow for its type and seat configuration. If a cycle only allows for one particular aircraft then it is treated in isolation. The two major reasons why aircraft are rotated on the cycles are: 1. Balance of f lying hours. The major maintenance checks have been scheduled based on average flying hours, and in general the weekly cycling patterns are not equal in flying hours. 2. Regular opportunities for minor maintenance. Minor maintenance periods have been scheduled onto only some of the weekly cycling patterns so rotating the equipment allows each to come in periodically. In general, for the wide-body equipment the requirement is that each come in for a 14-hour maintenance period every two weeks. 58 In general, this step in the process requires reproducing the ut i l i za t ion charts again and establishing several cycling patterns until one is decided upon. A . 1 . 3 Assigning Aircraft Tail Numbers In order to i n i t i a l i z e the assignment of aircraft to routes, the new schedule must be "phased-in", i . e . , the f i r s t f l ights of the new period adjusted so there is a smooth transition from the last scheduled flights of the previous period. Usually, several options for "phasing-in" the new schedule are developed and presented to Payload Control for a decision to be made. Other than the "phasing-in" decisions, aircraft are assigned arb i t rar i ly . The next step is to go through the schedule, sequentially assigning according to the operational cycling patterns developed, and adjusting for minor route restrictions and major maintenance checks. (See Figure A.2 for maintenance schedule.) This wil l involve aircraft substitutions where necessary. Again these cases are presented to other groups such as Payload Control for a decision to be made. The aircraft assignments are performed by linking the bars on the charts with colored lines, matching the ta i l numbers to the lines at the start and finish of each week. Part of the Ut i l izat ion chart is i l lustrated in Figure A . 3 . The above in i t i a l i za t ion process takes several weeks of manual work. A.2 Handling Requests for Extra Usage The above routing of the aircraft provides up-to-date visual avai labi l i ty of the aircraft downtime. This is necessary in order to provide equipment for a l l extra usage required during the l i f e of the schedule. Examples of extra usage being extra sections, charters, special stops, promotional f l ights , pi lot training, cabin attendant training, advertising requirements, etc. The f i r s t step upon i n i t i a l l y receiving a request is to identify how much time is needed. It then must be evaluated whether or not an aircraft is available for that length of time or can be made available by manipulating the routings to produce a larger downtime period. if an aircraft is available, this must be confirmed by maintenance. The cycling requirements-and f l ight itinerary are identified for the in i t i a l request. This information then goes back to the Sales Department for confirmation, and as well to each department. If there are any problems that would prohibit this request, then that department would notify Operations Planning, who would then try to make adjustments. When the request has been confirmed, a f l ight order is prepared and distributed. At this point the cycling requirements must be rechecked, and 59 appropriate changes are made to the routings. A.3 Co-ordinating/Reflecting Changes Operations Planning is the source of the planned aircraft routings, and thus any changes must be co-ordinated with them. As mentioned ear l ier , Operations Control is responsible for handling a l l short-term changes, in particular emergency situations that arise in daily operations. An example is when a plane has an engine breakdown and is unable to perform the next f l ight . Their approach is to find a solution that solves the immediate problem. Operations Planning wil l adjust the books to reflect that change and the consequences of i t . If the changes have affected-the routings beyond the next ten day period, Operations Planning must bring the aircraft back to cycle. The narrow-body aircraft are routed by Maintenance Planning, and there are generally no problems involved. This is because the aircraft return to Vancouver nightly, or at most every three nights, so they can be rerouted at any point to suit maintenance purposes. However, on occasions where Operations Planning is trying to extend downtime for extra f ly ing , they wil l change the routing to properly position the aircraft , and confirm this with Maintenance. Often Maintenance Planning wil l inform Operations Planning of necessary changes to the schedule and routings to accommodate for changes to the maintenance plan. If these are not satisfactory, then Operations Planning wi l l suggest alternate solutions. Thus, Operations Planning acts as the key focal point for decisions dealing with aircraft usage. They are often not the decision-maker, but rather a decision support system themselves in providing information and suggested solutions to others. Figure A . l Example of Cycling Chart 61 TTcflo IS ~ 3 i i 33 !U1 to' 0_ a) to to 3 -•r ro CD 1/1 • l A M To 1/3 9 0 3 . in 3~ 5J IS" in 4 ' 1 (A IA ! Figure A.2 Example of Maintenance Schedule ROUTE S U N D A Y " H * i! 8 1335 62 O R I E Mi?r r 1 pe 14b % 7 \ • \ R. ft! I \ \ ccio 02<*> 1 0 J o: iic -"i-u C.v y ; -wt. 1M, 212 AH'. Ms 5 g ? V%l ''gfr -fafc OUT' WM'-Di 3S j o ' l i s r f . a s f ' ' or*