 Open Access
 Total Downloads : 1096
 Authors : Pardeep Kumar Mittal, Dr. Rakesh Kumar, Dr. P.K.Suri
 Paper ID : IJERTV2IS90734
 Volume & Issue : Volume 02, Issue 09 (September 2013)
 Published (First Online): 25092013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
A Genetic Simulator for Airline Yield Management
Pardeep Kumar Mittal 
Dr. Rakesh Kumar 
Dr. P.K.Suri 
Assistant Professor 
Professor 
Dean (R&D) 
Dept. of Computer Science 
Dept. of Computer Science 
Chairman & Professor 
& Applications 
& Applications 
(CSE/IT/MCA) 
K.U.Kurukshetra 
K.U.Kurukshetra 
H.C.T.M., Kaithal 
Abstract
Airline yield management nowadays has become a very important research area. As more and more companies are coming in the field of airlines, it has become very difficult to sustain for a company without incorporating yield management. Therefore most of the companies are trying to incorporate the yield management in their system. The basic purpose of the yield management is to maximize revenue within the specified constraints. This paper is an attempt to design a basic decisionsupport tool for airline yield management using genetic algorithm. The genetic simulator has been designed using Matlab.
1. Introduction
Yield management is the concept of identifying various strategies for optimizing yield (revenue) in various capacityconstrained services. The core concept of yield management is to provide the right service to the right customer at the right time for the right price.
A popular definition of yield management is given by Netessine as Yield management is the process of understanding, anticipating and reacting to consumer behaviour in order to maximize revenue or profits.[1]
The big question is when yield management should be applied. Are there any conditions under which it can be applied? The answer lies in the following three basic conditions:

There is a fixed amount of resources available for sale.

The resources sold are perishable.

Different customers are willing to pay a different price for using the same amount of resources.
Yield management can be applied in a number of industries, although it is more popular in airlines industry and hotel industry.
Although there are no specific guidelines for a yield management process, it may contain data collection,
segmentation, forecasting, optimization, and dynamic re evaluation
In mathematics, computer science, or management science, optimization is the selection of a best element (with regard to some criteria) from some set of available alternatives. In the simplest case, an optimization problem consists of maximizing or minimizing a real function by systematically choosing input values from within an allowed set and computing the value of the function. Generally, optimization includes finding "best available" values of some objective function given a defined domain, including a variety of different types of objective functions and different types of domains.
To solve various optimization problems, one may use algorithms that terminate in a finite number of steps, or iterative methods that converge to a solution (on some specified class of problems), or heuristics that may provide approximate solutions to some problems.

Literature Review
From a historical perspective, the interest in Yield (Revenue) Management practices started with the pioneering research of Rothstein [2] and Littlewood [3] on airline yield management. However, it was probably after the work of Belobaba ([4], [5] and [6]) and the American Airlines success [7] that the field really took off. The airline industry provided researchers with a concrete example of the tremendous impact that Revenue Management tools can have on the operations of a company (e.g. [7]). At this stage, however, much of the work was done on capacity management and overbooking with little discussion of dynamic pricing policies. In essence, prices (fares) in these original models were assumed to be fixed and managers were in charge of opening and closing different fare classes as demand evolved. During the 90s, the increasing interest in Revenue Management become evident in the different applications that were considered. Models became industry
specific (e.g. airlines, hotels, or retail stores) with a higher degree of complexity (e.g. multiclass and multiperiod stochastic formulations). Furthermore, it was in the last decade that pricing policies really became an active component of the Revenue Management literature (e.g.[8], [9], [10] and [11]).
Several authors report success stories on how effective Revenue Management has been done in practice ([12] and [13]). An example of successful Revenue Management system can be found in British Airways. Among the reported in 1992 reasons of company success were cost cutting and sophisticated Yield Management. The company attributed its success to being a lowcost and highrevenue carrier [12]. The next successful Revenue Management implementation example can be found within the Austrian Airlines company that has been one of the most consistently profitable airlines in Europe in the past decades. During the Gulf War that has caused profits of the most airlines to decline, the Austrian Airlines has experienced its twentyfirst consecutive year of profits [13]. This has proven the company capability to perform effectively during extremely cyclical periods. The company owes its success to smart investment choice into a Revenue Management and decisionsupport computer system. This system has helped to monitor all historical data on the company flights as well as has made it possible to perform flights forecasts up to a one year period with high precision. Moreover, the new Revenue Management system has allowed the company management to look for future business opportunities by supplying it with decision making tools to forecast future flights demand. In addition, the implementation of this system has enabled the company to keep her prices at stable level while other companies were trying to survive by lowering their flight prices [13]. Bitran and Caldentay in their paper examined the research and results of dynamic pricing policies and their relation to Revenue Management[14]. The survey is based on a generic Revenue Management problem in which a perishable and nonrenewable set of resources satisfy stochastic pricesensitive demand processes over a finite period of time.
Genetic algorithm in yield management
In a system proposed by Aloysius George et.al. , in order to maximize the revenue of airline, an optimized flight booking and transportation terminal open/close decision system has been presented using Genetic Algorithm[15]. In this system, the particular booking terminals historical booking data is observed. Consequently, its frequency is generated with linguistic variable and deviation of booking is interpreted. Using the observed data and genetic algorithm, the terminal open/close decision system is optimized.
In an article presented by Srinivas and Shashi [16], the focus is on developing a decisionsupport tool to estimate the number of seats to each fare class. Genetic algorithm is
used as a technique to solve this problem. The decision support tool considers the effect of timedependent demand, ticket cancellations and overbooking policies.

Problem Definition and Formulation
In this problem an assumption regarding a flight operating between a specified origin and destination has been made. The reservation for the flight starts fom the first date of expected reservation up to the date of departure. The period of reservation may be divided in a single or more than one time slices. Another assumption is to fix the fare of each class during each time slice and also assumed as known. Following notations has been assumed for this problem:
Ct = Total capacity of a flight
N, = Number of customers belonging to class during time slice .
F = Fare for class .
U, = Upper limit of demand for class during time slice .
L, = Upper limit of demand for class during time slice .
For finding the objective function, the purpose of which obviously is to maximize the revenue, one have to assume some constraints, which can be:
First assumption is that there will be no cancellations and noshows. The total number of passenger travelling should be less than or equal to the capacity of the flight.
The number of customers travelling in each class should be greater than or equal to lower bound and less than or equal to the upper bound.
On the basis of above assumptions, the objective function can be written as:
Max. N, F . (1)
Subject to the constraints
N, <= Ct & L, <= N, <= U, for all and , N, >= 0, which indicates that number of customers in each time slice can be positive only

Implementation using Genetic Algorithm The formulation specified in above section is basically a Linear Programming Problem with the variables being assumed as integers. Therefore the problem actually becomes an integer programming problem. This problem can easily be solved using any standard method to solve LPP. But the traditional LPP methods becomes complex when there is a presence of discrete integer variables. Also there is large amount of input information is required such as constraints, therefore necessitating complex modelling and simulation. Therefore instead of using the basic techniques, an attempt has been made to solve the problem using genetic algorithm.
The basic advantage of using GA lies in the fact that it starts searching for optimal solution from multiple points, while most of the other methods start from a single point in search space. Thus there is less chance of sticking at local maxima when GA is being used. Further, if someone
wishes to modify the model for the whole airlines, it can be easily implemented using GA. Additionally GA does not require gradient and derivative information and thus can be used to solve even complex real world problems with discontinuous functions. [17].
For solving the above formulated problem, a genetic simulator has been implemented using Matlab and is explained below:
Representation
To solve any problem using Genetic Algorithm, the very first issue is the selection of encoding scheme to represent the chromosomes. There are a number of encoding schemes available in literature such as binary, octal, hexadecimal, permutation and tree etc. Encoding scheme selected will further dictate what will be the crossover and mutation operators. There are two basic principles to select an encoding scheme: (i) Principle of minimal alphabet and
(ii) Principle of meaningful building blocks [17]. It has been observed that in the said problem, binary encoding scheme is the base option that also satisfies both criteria. While this technique is very commonly used, in present case the first thing is to decide the length of the binary string. The number of genes in the binary string in present case is based on number of classes and number of time slices that are considered in an airplane. The number of genes will be evaluated as
Numberofgenes = numberoftimeslices * numberofclasses * numberofbits . (2)
For example, if it is assumed that number of time slices are 1, number of classes are 4 and number of bits are 8, then the number of genes will be 32 and these genes will be represented with a binary sequence generated randomly.
Evaluation Function
Closely related to the representation, the issue of the evaluation function arises. This function associates a value to every individual in the population, and corresponds to the quality of that individual. Thus, different representations of the same problem may have different evaluation functions, since this is typically calculated from the values of the genes of each individual and through the genotypetophenotype mapping. The evaluation function is often referred to as fitness function in the Evolutionary Computation field. In proposed simulator, an evaluation function in Matlab has been designed to evaluate the chromosomes. The fitness value of each string (Chromosomes) is calculated by decoding the binary strings which represents the information about the number of passengers belonging to each fare class. However, the fitness value is bounded by the expected demand range for each fare class. The final parameter value for the number of customers belonging to a particular class can be evaluated as:
= Lb + ((Ub Lb) *d)/(2l 1),
where d is the decoded value and l is the length of the chromosome.
Initial Population
Once the representation is fixed, the first issue in developing the algorithm is that of the initial population. This is typically performed by randomly generating individuals so that the population can cover wider areas of the search space. Nonetheless, there are other more specialized methods. A very common approach is to generate the individuals in a greedy manner, which means that every individual is constructed in a way such that at every time, the next gene is given the value that optimizes the evaluation function for that individual. Occasionally, the solutions may be somehow seeded in areas where solutions are likely to be found. In proposed simulator the basic method of randomly generating individuals has been used.
GA parameters such as total number of generations, cross over probability, mutation probability, population size, total number of iterations are fed as input in this step. Here assumption is that the typical range for population is 50
500. The random numbers are generated assuming population is normally distributed.
Parent Selection
Selection is the method through which certain elements in the population are chosen to be combined. This selection mechanism tries, in general, to choose parents that are likely to produce a highquality descendant. Typically, two individuals are chosen to reproduce and yield descendants. Different kinds of selection mechanism are Roulette Wheel, Ranking, Tournament, Multiparent, etc. In proposed simulator, researchers have used two selection mechanisms: (i) RouletteWheel and (ii) Tournament selection and are explained below:
RouletteWheel Selection: In this method, a certain probability is to be chosen for every individual in the population. This probability depends directly on the absolute fitness of the individual [18]. The main drawback of this mechanism is that the best candidates are very likely to take over the whole population very quickly which may result in the loss of diversity sometimes. Diversity is one of the main causes for the genetic algorithm being used so widely. To maintain diversity a combination of roulette wheel selection with some other selection mechanism can be used.
Tournament Selection: This is one of the simplest mechanisms, and also the least timeconsuming. It consists of choosing k individuals completely at random, and then selecting the two individuals with highest fitness function. Obviously, the complexity of this method depends on the value of k. The probability for tournament selection is fixed as 0.75 in proposed simulator.
Reproduction
For the purpose of reproduction, the parents(individuals) are combined in such a way that a high quality individual (descendant) will be obtained. This mechanism is also known as crossover. In some GAs, this operator is able to generate ore than one descendant (usually two), but one
will assume from now on that only one descendant is going to be generated. Thus, different crossover operators are one point, multiple point, uniform, arithmetic, etc. In present case, one point, two point and uniform crossover has been used, and are explained as follows:
One point crossover: This is the most popular method. It consists of choosing a point randomly, and copying the genes of a parent, from the beginning until this point, to the descendant, and the genes of the other parent from that point till the end.
As an example, imagine two parents of the form:
First = ( 0 1 0 0 1 1 1 1 0 ), Second = ( 0 0 0 1 1 0 1 0 0 )
and k = 5 is the crossover point, the descendant would either be
( 0 1 0 0 1 / 0 1 0 0 ) or ( 0 0 0 1 1 / 1 1 1 0 )
Two point crossover: It is similar to the previous crossover, and the only difference is that instead of 1 point, two points are chosen randomly. Then, to generate a descendant it would copy the genes of each parent in turns after each crossover point.
Uniform crossover: It is slightly different than the previous one. It treats each gene independently and decides from which parent it is going to be inherited (typically with the same probability).
Mutation
This operator is the source of great diversity. It is based in the biological fact that some genes can mutate for different reasons, and thus, the descendant can acquire genes that are from neither of its parents. The most common ones are random bit modification, swap mutation, insert mutation, scramble mutation, etc. In this particular case, the random bit modification has been used which is explained below: Random bit modification: Consists on changing the value of some bits with a given probability. The operator changes the value of every bit in the sequence with a certain probability. If the representation is binary as in our case, the effect is that of flipping a bit, either from 0 to 1 or from 1 to 0.
Selection of the New Generation
This is the mechanism that replaces the last population by a new one. In order to do so, some algorithms completely replace the previous population for the new set of descendants or offspring. However, this is usually not a very effective technique, and GAs normally implements mechanism to generate the new population from both, the previous one and the offspring. Some of these mechanisms are fitness based, generation based, replace worst, etc. Derived forms of generational update are used like ( + )update and (, )update. This time from a parent population of size , a little of children is produced of size . Then the best individuals from either the offspring population or the combined parent and offspring populations (for (, ) and ( + )update respectively), form the next generation[19]. In proposed simulator the fitness based replacement has been used i.e. selection focuses on keeping the individuals with higher fitness for
the next generation. A technique associated with this operator (independent of the mechanism type) is to always maintain the highest quality individual in the population. This technique is usually referred to as elitism.
Termination
The termination condition indicates when it is time for the algorithm to stop. At this point, the algorithm will usually return the best individual according to its fitness function. One can distinguish two kinds of termination condition: Objective reached: when a GA is implemented to reach a certain goal (i.e., a solution of a certain quality), reaching that goal should be the indication for the algorithm to stop. External conditions: However, the previous case is very rarely achieved, due to the stochastic nature of these algorithms. Therefore, different criteria must be used. Different conditions include fixed number of generations reached, maximum time allowed reached, fitness improvement does not occur for a certain period of time/generations, manual inspection, a combination of the above. In proposed simulator, researchers have maintained a fixed number of iterations.
Genetic Simulator: SingleLeg Flight Yield Management
Init_pop = Randomly Generated population.
//Initialize Population with size n
curr_pop = Init_pop.
While ( !stop_criterion)
// Condition to stop with maximum iteration being fixed as max
Evaluate Fitness of curr_pop.
Create mating pool according to Roulettewheel Selection OR Tournament Selection.
// Selection
Apply Crossover like Onepoint, Twopoint & Uniform Crossovers on mating pool with probability 0.80.
Apply Mutation on mating pool with probability
0.03. // Mutation
Replace generation with ( + )update as curr_pop. // Replacement
End While
End

Results
Genetic algorithm is used as a solution technique for the singleleg airlines problem using various combinations of different operators.
In this case, a single flight is considered to operate between given origin and destination. The capacity of the flight is assumed to be 100. The following GA parameters are taken into considerations:
Population size = 75
Maximum number of iterations = 50
Crossover probability = 0.80 Mutation probability = 0.03
Tournament Selection parameter = 0.75 Number of simulations = 30
Using the above parameters and various combinations one can get the tables 1 and 2, which are shown at the end of the paper.
Results obtained for each combination of operators are shown below:


Using combination of Roulette Wheel selection and the three types of crossovers i.e. onepoint, twopoint and uniform, the following results were obtained:
Fig.1 : Lower Bound, Upper Bound, and Estimated Fitness
Fig.2: Average Fitness
Fig 3: Maximum Fitness

Using combination of Tournament selection and the three types of crossovers i.e. onepoint, twopoint and uniform, following results have been observed:
Fig.4 : Lower Bound, Upper Bound, and Estimated Fitness
Fig.5: Average Fitness
Fig 6: Maximum Fitness

Using combination of Roulette Wheel and Tournament selection along with onepoint crossover, following results have been obtained:
Fig.7 : Lower Bound, Upper Bound, and Estimated Fitness
Fig.8 : Maximum and Average Fitness

Using combination of Roulette Wheel and Tournament selection along with twopoint crossover, following results have been observed:
Fig.9 : Lower Bound, Upper Bound, and Estimated Fitness
Fig.10 : Maximum and Average Fitness

Using combination of Roulette Wheel and Tournament selection along with uniform crossover, following results have been observed:
Fig.11 : Lower Bound, Upper Bound, and Estimated Fitness
Fig.12 : Maximum and Average Fitness

Interpretation
Upon comparing the above results with [16], it has been observed that the solution found using GA is optimal and the results obtained are at par with [16]. Looking at the tables and graphs obtained by different combinations of various selection and crossover methods the following findings has also been observed:

The best estimation is obtained in most of the cases when tournament selection is used irrespective of the crossover operators, while when roulette wheel selection is used the best estimation is generally obtained in case of onepoint crossover.

There are three different combinations which can be considered as better combinations as compared to others. These are tournament selection along with uniform crossover or onepoint crossover and roulette wheel selection with onepoint crossover.

The combinations which should be discarded completely are roulette wheel selection and twopoint crossover, roulette wheel selection and uniform crossover as the results producd by these combinations are not found to be very useful.

Looking at various graphs for the average fitness of the population, it is clearly visible that onepoint cross over always yields not a very good average fitness, while when twopoint or uniform crossover is used the average fitness is quite good and almost same in each case.

Conclusion
In this paper, an attempt has been made to solve the problem of yield management using Genetic Algorithm, GA has been used in the said experiment with a number of variants in selection and crossover. It is inferred that GA can be successfully used in the problem of yield management. Yield management is a problem of optimization and GA has been used in past in a number of other problems of optimization. GA being an evolutionary algorithm is a good option for such type of problems where the result should evolve with passage of time. The particular case study which has been picked is airlines yield management. The various combinations of different operators were tried in an attempt to find the best possible combination for maximizing the profit for airlines. The combinations which proved to be best were tournament selection along with either uniform crossover or onepoint crossover. However, if one takes into account the improvement in the total population, then the onepoint crossover fails. In that case the only combination found to be very good is tournament selection along with uniform crossover.

Future Scope
In this paper a basic case of yield management in airlines has been taken into consideration with only a single decision period. The results obtained although can prove to be useful for airlines industry; still there are a number of things that can be considered for practical implementation. Some of them can be consideration of more than one decision period, overbooking and cancellation, arrival pattern of customers, etc. The concept of genetic algorithm can also be applied to other industry such as hotel industry, seacargo industry, etc.

References

Netessine, S. and R. Shumsky (2002), Introduction to the Theory and Practice of Yield Management,
INFORMS Transactions on Education, Vol. 3, No. 1

Rothstein, M. 1971. An Airline Overbooking Model.
Trans. Sci. 5, 180192.

Littlewood, K. 1972. Forecasting and Control of Passenger Bookings. AGIFORS 12th Annual Symposium Proceedings, 95128, Nathanya, Israel

Belobaba, P. (1987). Air Travel Demand and Airline Seat Inventory Management. Ph.D. Dissertation, MIT.

Belobaba,P. 1989. Application of a Probabilistic Decision Model to Airline Seat Inventory Control. Ops. Res. 37, 183197.

Belobaba, P. (1987), Airline Yield Management: An Overview of Seat Inventory Control, Transportation Science, 21, 6373.

Smith, B., J. Leimkuhler, R. Darrow, J. Samuels. 1992. Yield Management at American Airlines. Interfaces, 22, 831.

Gallego, G., G. van Ryzin G. 1994. Optimal Dynamic Pricing of inventories with Stochastic Demand over Finite Horizons. Mgmnt. Sci. 40, 9991020.

Bitran, G., S. Monschein. 1997. Periodic Pricing of Seasonal Product in Retailing. Mgmnt. Sci. 43, 427 443.

Feng, Y., G. Gallego. 1995. Optimal Starting Times for EndofSeason Sales and Optimal Stopping Times for Promotional Fares. Mgmnt. Sci. 41, 13711391.

Feng, Y., G. Gallego. 2000. Perishable Asset Revenue Management with Markovian Time Dependent Demand Intensities. Mgmnt. Sci. 46, 941956.

Unternehmen und Markte (1992) Unternehmen und Markte in Handelsblatt, 12 April 1992, p. 13.

Robert G Cross, Revenue Management: HardCore Tactics for Market Domination ,1997, Broadway Books, New York

Gabriel Bitran and Rene Caldentey, An Overview of Pricing Models for Revenue Management, December, 2002

Aloysius George, B.R.Rajakumar, D. Binu, Genetic Algorithm Based Airlines Booking Terminal Open/ Close Decision System, ICACCI12, August 35, 2012, Chennai, T Nadu, India.

Srinivas S. Pulugurtha & Shashi S. Nambisan, A DecisionSupport Tool for Airline Yield Management Using Genetic Algorithm, Computer Aided Civil and Infrastructure Engineering, 2003, 214233.

Goldberg, D.E.(1989), Genetic Algorithms in Search Optimization and Machine Learning, AddisonWesley, New York.

J.H. Holland, Adaption in Natural and Artificial Systems, MIT Press, 1975.

S.N.Sivanandam, S.N.Deepa, Introduction to Genetic Algorithm, SpringerVerlag Berlin Heidelberg 2008
TABLE1: LOWER, UPPER AND BEST ESTIMATED DEMANDS IN EACH ASSUMED FARE CLASS
Demand 

Fare Class 
Fare 
Lower Limit 
Upper Limit 
Best Estimation 
1 
100 
0 
63 
30 
2 
250 
30 
45 
45 
3 
500 
13 
20 
20 
4 
800 
2 
5 
5 
TABLE 2: NUMBER OF ITERATIONS FOR THE BEST ESTIMATES IN VARIOUS COMBINATIONS OF SELECTION AND CROSSOVER PARAMETERS
Parameters 
Iterations 
No. of simulation when max. is not achieved in specified iterations 

Selection 
Crossover 
Min. in all simulations 
Avg. of all simulation except when max is not achieved 

Roulette Wheel 
OnePoint 
4 
19 
9 
Roulette Wheel 
TwoPoint 
23 
27 
25 
Roulette Wheel 
Uniform 
17 
32 
24 
Tournament 
OnePoint 
2 
19 
6 
Tournament 
TwoPoint 
9 
23 
6 
Tournament 
Uniform 
5 
17 
2 