Analysis of Airline Planning

I NDIAN INSTITUTE OF MANAGEMENT CALCUTTA

WORKING PAPER SERIES

WPS No. 590/March 2006

Analysis of Airline Planning

by

Nitika

nitika@iimcal.ac.in

Doctoral student, IIM Calcutta, Diamond Harbour Road, Joka P.O., Kolkata 700 104

India

&

Manabendra N Pal

Professor, IIM Calcutta, Diamond Harbour Road, Joka P.O., Kolkata 700 104, India

Analysis of Airline Planning

Nitika*1, Manabendra N Pal1

1Operations Management Group, Indian Institute of Management Calcutta, India

Abstract

The paper tries to classify the problems and their solutions in airline planning, based on present literature and the corresponding gaps. Here the scope is not restricted to airline scheduling. The paper first presents the structure of the system, based on the components of the airline system and their interactions. It starts from the macro level relationships and in each step goes into more details. Then based on these structure and interactions, the problem classes have been defined. We have also done a classification of the literature based on the different ways these problems have been modeled and solved.

1. Introduction

"Start by being a billionaire and then buy an airline."

- Richard Branson, chairman of Virgin,

In answer to the question of how one becomes a millionaire ……

And then this quote can be quite true because of the competitive nature of the airline industry, which is one of the most competitive industries. So, it is very important to understand the various components, their interaction, corresponding problems and their existing or possible solutions.

The paper here tries to give a picture of the scenarios in the airline industry in terms of the problems at various stages and the existing and prospective solutions. It does it by defining the various pockets of problems based on the interactions and literature. It complements it with few references in each class of the problem. Also the paper tries to tell the gaps existing in the literature. It is not a state-of-art work. Rather it is a work which can be used as an introduction to the airline system, the interactions present and the classes of work done in these areas. The paper discusses some problems in more detail than the others, due to the space constraints. The reason for this is that, it is difficult to summarize the airline literature in a paper, as it is too vast. And it might clutter the classification by the details.

The contribution of this paper is in terms of providing a formal framework of the airline industry from problem solving point of view. All this knowledge might be present in bit and parts. But the work tries to put the pieces together and also show the interactions and then discusses the bridges between these parts.

The utility of this paper is that it can be used as a preliminary study for the introduction of the airline system. Also at the same time, while going for any strategic decisions, it can help in providing a framework for understanding interactions in the system, to analyze the effect of one part on other and present scenarios for these problems.

* Corresponding author. Email: nitika_cs@yahoo.co.in

2. Airline System

An airline offers a product – services for air travel and it consists of fleets, crew and other ground facilities as its resources. Airline needs to plan its resources such that its final short and long term profits are maximized. The objective of an airline like any other organization is to earn profit and gain customer share & loyalty. Short term profits consist of getting maximum profit by maximizing the revenue and minimizing the cost, which are more of the operations problems. The long term benefit among other things consists of customer retention, competitive strategies etc.

So, the main goals are to achieve the above stated objectives taking into account the constraints of resource availability, regulations and the interactions and behavior of the system.

There is some demand for the product (flight services) offered by airlines. This demand constitutes passengers who want to go from a place to the other. So, passengers want a product, i.e. schedule, for which they have to pay minimum price (fare + time) and get the maximum output – frequency, service, convenience etc. On the other hand, the airline tries to minimize its cost and earn the maximum profit, while using its resources efficiently. To achieve all this there are tradeoffs. For example, the minimum cost for an airline might mean higher cost for the passengers. Lowering the frequency in a market might increase passenger’s cost in terms of time. Also while the airline would like to keep the fare high, the customers would like it to be low. And all these factors affect the total (unconstrained) demand. Then competition aggravates the situation even more. Then the question becomes how to model all these factors. So, to provide this service what airline need to do it to decide the network (hence markets and the corresponding frequency along with departure time – from now on we will consider the network design including all these) and the fares, taking all these factors into account. These two map to the corresponding problems of network design and revenue management.

But to offer the flights, solving these two problems is not just enough. Airline need to plan the crew, fleet (which type for a flight and its route) etc. So, it is a total problem to provide a schedule, which consists of flights flown, their departure time, the fleet assigned to each flight, the route taken by a fleet and the crew assigned to each flight. These problems which might seem to be independent are related and some of the interactions have been explained in the following section. For example if one combines the fleet assignment and network design, the departure time can be changed little to incorporate some extra pairings

to check and include in the final schedule. Similarly the more crew pairing might have so many possible pairings, but if the routing of fleets is fixed, it gets reduced. So, as such it is one big problem, which can be defined as – to prepare a schedule which provides network design and fare along with the corresponding crew, fleet and routing. But to achieve this, the support of airport operations is required. And it spans a whole class of problems, called airport planning and scheduling.

So, to achieve the above said objectives, flight and airport scheduling are the major classes of the problems. These classes include various problems to solve. For example, network design and crew scheduling are the examples of the problems existing in this class. However some other problems, which are not directly related to providing service at any given point of time, also do exist in the airlines. Some of them are fleet procurement planning, airport facilities development. While flight and airport scheduling are more at the operational level, the latter problems mainly lie in the category of resource planning and are more related to long term planning.

These planning and scheduling steps while working at these different operational planning levels solve the particular problems. But they don’t provide any information about the structure and behaviour of the system. Also the long term goals require the knowledge and understanding of the system. For example how the different components of cost affect the network profitability. Other such behaviours might be the robustness in different kind of networks, interaction of utility function, cost and network structure. Such knowledge of the system interactions is always useful. It helps in operational decision making, future planning and policy making. For example recently so many low cost carriers have come up in different countries (2003 Southwest airlines was the largest low cost carrier in U.S.). Also some concepts of better service, shared chartered plane etc. are the new trend. So to evaluate the existing and new policies, creating a positioning in market etc. are some of the issues in which the better understanding of the system might be useful. Also at the

operational level it might be useful. The reason is that many of the parameters are used as input in these models. So understanding these parameters behaviour might be useful in developing models. It might even help in formulating assumptions etc. And practically these studies might be useful in say in determining the kind of fleets according to network, market etc.

We can say that analysis provides many insights for solving various scheduling problems. Some of the examples can be –

?Providing guidelines and insights in incremental scheduling

?Designing DSS in reactive scheduling

?In understanding different scenarios

So, the relation of analysis and scheduling can be shown as:

So the above said aspect is captured in the literature which covers the analysis of the airline system, its network and related aspects like utility function for a customer.

But to use these analyses in different parts of scheduling and planning, there are two kinds of things to understand. First is to – understand what affects the other, the interactions and what the nature of these relationships is. The next step it to use in appropriately. For example, analysis of cost structure might give the information about the cost aspect. But cost affects what and is affected by what is required to use it in the scheduling. And once it is done, it should be made compatible with the units and scale of other variables and parameters. These have been discussed in the interaction section along with an example. So, mainly the three classes of problems can be shown as:

Once all this has been done, the next step is to check how these planning & scheduling (along with the analysis) is performing. Performance metrics might be from industry point of view –like calculating financial & market performance from the ratios and all. As here the paper is about planning, its performance can be mainly seen from the point of view that how well it is performing with respect to the stated objectives. One such objective can be robustness of the schedule in the after math of some disruptions. But the paper does not go into the details of performance.

3. Details of classes and examples from Literature

After introducing the system and providing the basic interactions of the system, next the paper provides the details of these classes along with some examples from literature as follows:

There are not strict boundaries between the classes. But still this paper helps in providing a structure for the classes of problems and solution methodologies along with some work which covers more than one class. Considering the above framework, the three main classes are:

?Scheduling (Planning) – flight and airport

?Analysis of the system components and networks

?Interactions between the scheduling and analysis

3.1 Scheduling

3.1.1 Importance of Scheduling in Airlines

Airline scheduling is one of the most important aspects in airline industry. Then the competition and thin margins make it even more important. Planning literature mainly consists of airline flight scheduling and airport scheduling. While the paper explains the problem of flight scheduling in detail, it briefly summarizes the airport operations.

3.1.2. Flight Scheduling

Airline flight scheduling is required at two phases: initial scheduling and reactive scheduling. The first one is at the initial planning level to provide the service. Here initial scheduling means scheduling different steps and activities for the flights and crew to follow. And the reactive scheduling means the scheduling in the after-math of some disruptions. Here scheduling need to be done in such a way that it is as close to the planned one as possible and at the same time, it does affect the profitability at the minimum. At both the stage, issues might be same. But there importance might vary. For example, at the initial planning level, increase of 2-3 hours in the run time of model might not make much of a difference, if it is improving the solution quality in term of profitability or some other objective. But in case of reactive planning 3 hours might be a long time.

Airline flight scheduling, as told in the introduction part it consists of providing schedule and fare to the passengers. And to accomplish this, the problem consists of providing various direct and indirect services to the customers.

As explained in the introduction part, the problem of providing the service to customers is a one whole problem. But due to the scope and complexity of problem, it has been divided into the sequential stages. Planning of airline (flight) operations can be divided into four stages. The first stage, called the schedule design stage (network design stage), provides a list of flights along with origin & destination airports, arrival & departure times and the day of the week it operates. The second stage, called fleeting, decides the type of aircraft to be allocated to each flight, based on the number of aircraft available for each type and demand forecast. Once the fleeting is done, the next step is to decide which specific aircraft of a particular fleet type, out of many available for each type, to assign to each flight. This stage is called routing. Then the last stage assigns crew to each flight. The four stages can be shown as (Barnhart, 2004):

More information about airline operations can be found in Barnhart (2004). Sometimes the next stage, revenue management is considered as the next stage.

To solve these stages, there are two kinds of problems addressed at each stage of scheduling. The first issue is to model and formulate the problem. Then after formulation, because of the combinatorial nature of the problem, there is a need to provide a proper solution methodology for the proposed model.

The two modelling approaches for the above said scheduling different stages are - integrated and sequential. The integrated approach consists of combining a few of the above stages and modelling them together. This kind of modelling provides a more realistic picture and allows the model to capture the common factors and interactions across different stages. And it also helps in exploring all the options (i.e. all the combinations for various activities). But the complexity of this approach is comparatively more. Also one needs to check the integral constraints and the ways to handle these. The reason is that if the integrality is not taken care properly and some approximations are

made in the solution, then the advantage gained by the integrated approach can be offset by these. So above are the issues with respect to the integrated approach. Then the Sequential approach is supposed to be comparatively simpler. But it can’t capture all the interactions across stages. So, the choice between the integrated and sequential approach is made accordingly.

Whatever approach is taken for modelling, there are some issues to be considered. There are different kinds of the formulation issues to be addressed at various stages of scheduling. Some of these are listed below:

Objective – It can be cost minimization, profit or revenue maximization or may be robustness maximization etc. Here all the objectives except the last one are profitability objective. The last one is the reliability objective. Reliability objective might finally help in improving the other objectives. While profitability objectives are mainly influenced by the accuracy of forecasted parameters, proper formulation of the problems and the corresponding solution methodologies, the robustness objective has some special requirements. For example, it requires the points of robustness requirement, identifying and defining the metrics of robustness and proper integration of these metrics as objectives with other objectives. Going by the above classification, if we look at the profitability figures, there are two kinds of papers broadly. One class takes cost, profit figures as parameters and use the data values for them from the historical estimates. Some other papers deal with the components of the profit, cost, the distribution or nature of these and then incorporate them. These are more related to the analysis and interaction part, discussed later. Then for the robustness objective at the planning stage, the work done is in terms of defining the metrics and designing appropriate formulation & providing the respective solution methodology. Robustness, being one of the important aspects has been discussed in detail later.

Model can be single objective or the multi-objective, combining two or more of the above objectives. Here the issues might be compatibility of units of different objectives and combine these objectives properly. A few papers using multi objective model for scheduling are – Teodorovic & Emina (1989) and Hsu & Wen (2000).

Scheduling unit considered can be – flight leg, itinerary, string connections at the banks etc. There can be relative pros and cons of each approach. For example, string based approach might help in removing some of the infeasible pairings at string generation stage only.

Time horizon considered – daily, weekly, maintenance cycle etc.

Modelling approach – Network flow problem, Integer programming, set partitioning, multi-commodity flow problem, non-linear programming etc.

Assumptions – these define the scope of the formulation and the problem considered.

The issues considered above can be at any stage of scheduling. If one wants to look at one stage specifically then there can be some specific issues. For example, if we look at the routing stage, the issues have been discussed as following:

Some integrated models of routing along with schedule generation, fleeting and crew scheduling have been given in Barnhart et. al. (1998), Mercier et. al. (2005), Klabjan et. al. (2002), Ioachim et. al. (1999), Stojkovic & Soumis (2001) and Yan & Tseng (2002). Yan & Tseng (2002) combine routing with the schedule design. It considers the origin-destination (OD) pairs demand and supply constraints as the integrated model’s basic inputs. Ioachim et. al. (1999) gives an optimisation model for the fleet assignment and routing. In Mercier et. al. (2005) Routing has been integrated with the crew scheduling taking care of variable connection times. Klabjan et. al. (2002) solves the crew-scheduling problem; however it mentions the partial integration with the routing due to Plane-count constraints. The work also considers the time-window concept.

The second case, i.e., the independent routing models, has been discussed in Desaulniers et. al. (1997), Gopalan & Talluri (1998), Sriram & Haghani (2003), Talluri (1998). The work following the sequential approach, i.e. the routing stage separately has been given in Gopalan & Talluri (1998), Lal et. al. (2002), Mercier et. al. (2005) and Talluri (1998). Desaulniers et. al. (1997) addresses the DARSP (Daily Aircraft Routing and Scheduling Problem). The paper considers the one-day planning horizon and heterogeneous fleet. The two types of formulations given are – Set partitioning type formulation and Time constrained multi-commodity network flow formulation. Sriram & Haghani (2003) presents innovative mathematical formulation and a the aircraft maintenance-scheduling problem, while minimizing the maintenance cost. The paper considers seven days planning horizon and type B check. Talluri (1998) talks about the complexity of the four day maintenance routing problem and tells about the heuristic to solve it using the three days planning algorithm & other algorithms.

Some important classification criterion on the routing stage can be shown on the following basis:

Routing Maintenance DARSP

Scheduling unit Flight based Connection based String based

Objective Revenue Cost Robustness

Robustness measure Propagated delay Overlapping Short

connection

&

others

Then the next point might in formulation is to decide the parameters and variables in the model. Some of the aspects like demand, fare, fleet assigned etc. can be taken as both variable and parameter, based on the assumptions. Generally for the scheduling problems the demand, fare etc. are considered to be parameter. But there might be interactions like schedule offered affects the demand and which in turn affects fare and these might be taken as variables. Studies to capture this have been covered in interaction part.

On the solution methodology side, usually the attempt it made to take the help of domain knowledge, various O.R. (column generation, decomposition etc) and computer techniques because of the size and complexity of the problem. All this knowledge can be used either in developing heuristics, improving the optimal methods or a combination of the both. One example of the combination of both can be developing strategies for branch and bound. Without going into the details of all these combinations, i.e. domain knowledge and optimal methods, computer techniques and heuristics, the paper provides the examples a few of them. If we talk about the domain knowledge being used in the optimal methods, examples can be various techniques of problem-size reduction methods, as suggested by Barnhart (2004). Similarly the example of use of O.R. techniques in optimal methods might be to use Branch and Price (Barnhart, 2004). Some other examples, form the literature, are the following. The solution approach, in Ioachim et. al. (1999), is based on Dantzig-Wolfe decomposition and then the dynamic programming has been used to solve the sub-problem. Desaulniers et. al. (1997) has two formulations for the routing problem. The former is a kind of string model and branch & bound has been used to solve it. The second one is similar to leg-based model and Lagrangian relaxation has been used for the solution. Yan & Tseng (2002) use Lagrangian relaxation and heuristics to solve the integrated model. Sriram and Haghani (2003) use a heuristic, using Depth First Search and Random Search to solve the maintenance routing problem. Talluri (1998) tells about the heuristic to solve the maintenance routing problem using the three days planning algorithm & other algorithms.

The next stage, revenue management side, has different issues. Classes of problems at this stage have been discussed in Barnhart (2003), which also gives reference of McGill & Ryzin (1999) – survey paper on revenue management. One other survey paper, Elmaghraby & Keskinocak (2003), provides the details about dynamic pricing. This is one of the most important areas of revenue management. Some of the main problems in this class are – handling overbooking problem, differential fares, dynamic pricing etc. Examples of few papers in revenue management are – Belobaba & Gorin (2004), Bertsimas & Boer (2005), Bodily & Weatherford (1994) and Boyd & Bilegan (2003). While Belobaba & Gorin (2004) discuss the importance of revenue management, others tell the ways to solve the specific problems under the domain of revenue management.

Other than these full scale scheduling problems, there are some papers which talk about making changes to the existing schedules. One such example is Lohatepanont & Barnhart (2004). The approach in the paper is called the incremental approach. It takes the existing schedule and possible addition & deletion of flight. Then the set of flights obtained is called master flight list and the decision problem is to select flights from it satisfying the various constraints.

If one includes the revenue management, then other than these 5 stages of scheduling, there are some aspects whose study helps in supporting the study and development of these scheduling problems. Some of the examples of such developments are – time-window concept, Passenger Mix Model etc. Time-window concept has been used to increase the number of possible pairings, which might help in improving the objective function value. It has been used in Rexing et. al. (2000) and Klabjan et. al. (2002). Passenger Mix Model was used by Kniker (1992).

Next, if one looks at the reactive planning, as discussed problems might be same, i.e. crew scheduling, fleet assignment etc. But here the time taken to solve might be more important and also the human intervention might be required. Many times at reactive level a DSS (Decision Support System) is also provided to give the user an option and accordingly the system is optimised. So, many times a decision support system is used for it. Also the nature of constraints might be required. One survey paper in this category is Cavanagh (1998). Some other papers in this area are Stojkovic (2002), Stojkovic (2001), Mathaisel (1996) and Yan & Yang. Stojkovic (2001) is also an integrated optimisation model and uses Dantzig-Wolfe decomposition for the solution. Mathaisel (1996) provides the decision support system for irregular operations.

3.1.3 Airport Operations

The problems here have been explained in Barnhart (2003). The summary of it is as follows. The problems here are mainly divided into two classes: airport operations and air traffic management. On the airport operations side again there are two classes: airside facilities (includes runways, taxiways, aircraft stands,

aprons etc.) and landside facilities (includes passenger and cargo buildings, curbside, check-in etc.). Air traffic management also consists of: air traffic control and air traffic flow management. Then within these classes, the problems consist of – operational (day-to-day) planning, infrastructure planning and performance measure of these.

3.2 Analysis of the system and networks

When we consider analysis, it consists on many problems like demand and market share for an itinerary and an airline, network structure and the behavior of various parameters (e.g. cost), competition and equilibrium in various situations, study of tools for the various problems. The list presented here is not an exhaustive list of problems or classes of problems. These are a few of the main problems. The paper mainly concentrates on the demand and network structure side. Also it provides some insights into competition side.

3.2.1 Demand

Demand is one of the most important parameters in the study of airline planning. It is done in two steps:

a) Demand Forecast

b) Itinerary/flight share models – tell share and also help in sensitivity/elasticity study

Going into the details of the share models, there are two classes of models – QSI (Quality Service Index) based and logit based (Discrete choice models/Random utility models, based on some defined utility). These models are based on the work provided by McFadden (1978). In the recent times, there are many developments in the study of these discrete choice models (Wen & Koppelman, 2001; Moshe & Bierlaire, 1999, Greene 19; Swait, 2001) and also in their applications to the airline industry (Coldren, 2005; Carrier 2003).

Then coming to the elasticity study part, there are comparatively less work. Going by approaches, there are two kinds of approaches. One is to obtain closed form expression (may be a function of the parameters of the model) for the elasticity. The other one is to model these parameters in the model and then find them out while solving for other parameters. Then going by any of the above said approaches, the objective might be to find attribute elasticity (Greene 19; Coldren 2005) and availability cross-effects (Anderson &Wiley, 1992; Lazari & Anderson, 1994).

Here the gaps exist in terms of a comprehensive study of tools and finding out which tool is more useful in which scenario. Also the gaps are present in terms of finding elasiticies, where not much work is present.

3.2.2 Networks

Lederer (1998) classifies the literature into three classes. The study about airline system and network can be obtained by different kinds of analysis like – economic, operations research and transportation engineer.

Economics – Here studies are mainly related with competition, non-cooperative games, and equilibrium in different kinds of markets, economies of scale and public welfare effects of competition between airlines. Both the analytical and empirical economics studies have been conducted to study these factors. A few examples in this class are Lederer (1993), Brueckner (2004) and Trapani (1982). The former one takes the domain of network design in an oligopoly, but the findings can be quite useful in general. The paper shows when do Nash equilibrium prices and also finds out the relation between the lower bound of profit and the network designs chosen. But the problem, here, is that it assumptions it makes might not represent the real case. For example, it assumes that the – if two firms have the same least total price, the firm with the least cost will serve all of the demand. But it might not be the case. Say airline i has capacity of 200 and airline j has a capacity of 150. Assuming the i has least p And the total demand is

320. Then the minimum demand which will be there for j is 120. And then the factors of departure time etc. can come into play.

Brueckner (2004) goes for utility side and also compares Hub and Spoke network with fully connected network. But the problem here is that it takes the monopoly assumption. So many of the related assumptions don’t hold in general and also the findings are accordingly specific for such scenario. For example, at one point it says that customers don’t mind increase in fare, if service (here means frequency) increases. And the whole analysis is done accordingly. But this is not actually the case. That is even if the competition is not considered explicitly in all aspects, such assumptions still don’t hold. For example the whole utility function and then the subsequent analysis will change with change in such assumptions. Also the analysis of different types of utility function, corresponding cost and network structure is not done here. So taking proper care of such assumptions might be quite useful. Also one more restriction is that the assumption about the structure of the network (only 3 cities considered). However in the conclusion it says that this assumption has been taken to simplify. It says it should be easy to generalize and provide results on similar lines. But still it needs to be studied and checked.

OR – Papers, in this class, present the models to study the behavior of airline costs and related aspects in different types of networks. The Lederer (1998) paper itself falls in this category. Examples of other papers in this class are Gunn (1964), Soumis (1993) and Gastner & Newman (2004). One other example is Bhadra & Texter (2004), which empirically studies U.S. networks.

Lederer (1998) studies the network structure with respect to different parameters (cost etc.) and frequency. It first assumes that the total utility offered (measured in the terms of price, frequency etc.) to the customer by the airline is constant and the demand vector is constant. It takes the case of a profit maximizing airline and then tells that keeping the utility constant, makes the profit maximization equivalent to cost minimization. Then it studies the behavior of the cost components and total cost. Later it goes to find the optimal frequency w.r.t. cost minimization. In the end also studies the effect of congestion at hub and reliability in terms of probability of delay etc. But a few gaps here are in forms of assumption regarding constant utility and assumption regarding circular shape of network. Also if one wants to look at holistic behavior of the system, it tells about the optimal frequency in different kinds of networks under all assumptions, some of which I have told above. But it does not provide the full picture of the system in general, as only four standard types of networks have been considered. Also the robustness aspect as such is not considered. The only consideration of schedule reliability is in terms of optimal choice of probability of delay across various networks.

Other paper in this class is by Gunn (1964), which uses simulation to study the airline system. However at that time, the computational facilities available were limited. So, many of the issues are not there. But then being a simulation model it

can’t capture all scenarios and there is a need to support the simulation results with analytical studies (To whatever complexities possible).

Soumis (1993) finds out the arcs flows, find out flow conservation equation for each market and show that these systems of equation converge under some assumptions. Also it provides an algorithm to solve the system of equations (which are non-linear). Also it says that it can be used for scenario analysis and re-optimization. But it does not talk about the parameters being affected by change. So, the parameter behavior changes, then it might be required to check convergence and if it is convergent, then accordingly find the solution.

The papers discussed in this section are just a few examples of the work present in the literature. But the general gaps present are as follows: most of the papers discuss the issues in isolation from other perspective. Also in many papers, the assumptions are quite restrictive. So work can be extended in these areas.

Transportation Engineers – Predict consumer choice using random utility model. Studies also include the choice of proper tool for such models. These have been discussed in demand section.

One other class of problems, which can be included in the networks, is the hub location problem and its analysis. There are different kinds of problems in this class. For example, it can be a single allocation p-hub median or multiple allocation one, which is based on the fact whether each spoke can be connected to only one or multiple hub. Also other issue can be network policies, which take care of strict and non-strict hubbing. It takes care of channeling flows through hubs. Some of the examples in this class are O’Kelly (1994, 1995) and Jaillet et. al. (1996).

3.2.3 Study of Tools

The most commonly used methodologies and techniques for the analysis, among the various other, are -analytical modelling, empirical study or simulation.

Analytical Derivations – Utility of analytical studies is in terms of analyzing the behavior of various parameters and variables with respect to change in one or more parameters. However this kind of study might need a base (assumptions). For example, it might be done for network design with profit maximization as objective. Then the approach might be start with such studies and go towards the generalizations. would try to start with a model, then may be the first say with the help of Lagrange relaxation make it a unconstrained one and finally go for numerical approximation to a get a solution and study the behavior.

Simulation – The different kinds of distribution and parameters. Also it might be useful for the scenario analysis or to design a benchmark set of problems, which

can be used for study and analysis of different models. For example, Kingman et. al. (1974) generates a variety of network problems and also a set of benchmarked problems. However these are for transportation, assignment etc. But such a set can be quite useful for airline industry. For example many times the newer models are proposed with the different assumptions relaxed and shown to perform better on one of the airlines. But a benchmark set might help in standardizing the comparison and also might help in the rationale behind the different models performing differently for different problems. Here the literature and domain knowledge can be quite useful for designing such a set.

Empirical Studies – These studies might be useful in studying the scenarios in a particular market, for example U.S. airline industry. There is a lot of work, which uses these techniques. Later these studies can be combined to find out the generalizations, if any. A few examples of work in this class are Swan & Adler (2005) and Chiou & Chen (2006). These studies might be useful in many simulation designs, as they might help in providing parameter values and range. Other Tools - Then the other approach might be to check if the airline networks can be mapped to theories already existing and use the properties of those in the future studies. For example, Daganzo (2004) was used for vehicle reposition problem. The benefit of such mappings is that these theories might have a huge number of results, which might be useful for the analysis purpose. Some of these can be: The general networks, Use of Complex Adaptive Systems (CAS), Scale free networks, Robust optimization, fuzzy theory. However the usage of these tools requires the proper mapping and even might need defining an appropriate dictionary for the same. Some examples of the efforts in the direction of mapping these tools or using them in the airlines are – Conway (2004), Kuby et. al. (2005), Kincaid (2003), Teodorovic et. al. (1994) and Alexandrov (2004). These tools can be quite useful to study the network behavior. Also these might be useful when there is an incremental approach – taking a base schedule and making changes, rather than starting from the scratch, as is done in many practical cases. But such possibilities need to be explored.

3.3 Interaction between scheduling and analysis

3.3.1 Importance of capturing interactions and an example

While working at the operational level, whatever be the level or horizon of planning, there are some basic interactions in the airline system. For example, to solve a particular problem whether one wants to take profit, revenue or cost as the objective function, might depend on various factors. But the fact that the profit is a function of revenue and cost still remains same. And it is important to capture these interactions/bridges to get the more realistic picture in scheduling. Some of these interactions have been shown as following.

Figure 1 shows that the profit is a function of revenue and cost. Now the factors affecting revenue are - demand realized (DR) and the fare. The DR is a function of capacity offered and unconstrained demand, shown as:

Demand realized = min (capacity, unconstrained demand after all the corrections)

The next level relationship can be shown as:

In figure 2, the demand realized shows the demand side and the capacity shows the supply. The supply, which is finally related to the fleet assignment, is decided based on demand and other things. But as shown, the supply itself affects the final demand realized. So it becomes a kind of cycle. And we need to handle it.

Now when we talk about the supply, it does not contain only the fleet assignment (capacity). It also includes the things like – network structure and its results like frequency, fares, robustness/reliability etc.

So, what the customers see is the supply (defined as frequency, departure time, capacity, fare etc.). While this supply is provided in a way that it provides maximum demand, revenue etc., there is a cost associated with providing all these. So the airline would try to find the point where the revenue and cost converge to provide the optimum profit.

But to provide this supply, airline need to plan its resources and scheduling comes into the picture. So, a better formulation can be done by understanding and taking into account all the relevant interactions.

This is just a simple snap-shot of the overall much complex picture. And there might be other issues also. For example when we talk about economies of scale, it is quite related to one or the other form of fixed cost. One example of these fixed costs is acquiring runways etc. on the airport. For example, for an airline operating two flights such fixed cost would be much lesser if it operates in one O-D pair than two. Other fixed costs are cost of acquiring a fleet, cost of operating the fleet and even the network structure affects these costs.

Capturing all these in the scheduling and other problems might require understanding these relations and also the right approach to use these. Some work is present in literature covering the bridges between these scheduling and analysis literature. The references have been given in the next section, which provide the example that explains the exact nature and behavior of these interactions and also how to incorporate them in some selected problems the various problems.

3.3.2 Papers capturing interactions

There is a major gap existing in literature in the form of using the analysis part along with scheduling formulations and present an overall picture of the scheduling problems. It means that say, rather than just taking cost as parameter c j, if its components and behavior is studied and taken into consideration while formulating the scheduling problem, it might be able to provide the better picture. Some of the examples existing in the literature are – Teodorovic & Nozic (1989), Hsu & Wen (2003) and Adler & Berechman (2001). Hsu & Wen (2003) use Grey theory, construct a polyfactor model for OD-pair market-size estimation and capture demand-supply interactions. These interactions are captured at flight frequency determination and network design stage. Teodorovic & Nozic (1989) use the market share models to capture competition during network design stage. Though some work has been done on this side, still there is need to apply it in different problems and to capture more interactions. For example one such scenario might be to capture the dynamic interactions between costs, utility offered and network design. One another example can be to capture demand interactions during network design and fleet assignment stages.

3.4 Snap-shot of the classes of Problems

The figure below shows the broad the classification of the classes of problems. However due to space constraints, all the classes have not been shown. So, the literature can be broadly classified as following: