Airline Schedule Planning Using Heuristic Search Method

Airlines are faced with some of the biggest and hardest scheduling problems known. For example, one major US carrier periodically schedules about 2700 flights per day to over 130 cities, using more than 400 aircrafts of 14 different kinds. Flight scheduling is one of the major problems for any airline company. This problem has been investigated as an optimization problem for many years. Usually, the flight scheduling problem is divided to a number of sub-problems, and fleet assignment is one of them. In this problem, given a flight time table and aircraft specifications, the type of aircraft is determined for each flight or the fleet assignment problem is the problem of assigning the right aircraft type to the rights in the timetable, while minimizing costs and satisfying various constraints. A lot of money can be saved if the right aircraft types are used. For example, in 1994, Delta Air Lines estimated that the use of a newly developed fleet assignment system would yield savings of up to $300 million over the following three years. The trade off between different aircraft types is that with a larger aircraft, more passengers can be serviced, and thus more income is generated. On the other hand, a larger aircraft consumes more fuel and is generally more expensive to operate. The fleet assignment problem (FAP) in air transportation consists of assigning fleet types to flights of a given flying schedule while respecting feasibility constraints and maximizing expected profit. Expected operational costs can be quite accurately expressed as a linear function of the FAP decision variables. The same cannot be said of expected revenues. Future revenues depend mainly on future travel demand. A particular fleet assignment (FA) then affects revenues through capacity limitations. Hence, when one expresses the expected profit as a linear function of the FAP decision variables, it is implicit that it is based on demand forecasts and that this linear function is only an approximation, a tool whose efficiency is to be judged on the profitability of the FAs found by the FAP solver. Because of this tight economic link, the fleet assignment problem is often connected to a revenue management system, which gives information about that is the best aircraft type for an individual flight, from a purely economic point of view, considering the booking situation and other things. But if the best aircraft type for each individual flight is already known, then what is the problem, you might ask. Just assign the best type to each flight, and the problem is solved. But this is obviously a typical example of a way in which one problem in a sequential solution procedure can ruin the possibilities for the following problems. It could for example mean that an aircraft would have to make a large amount of flights without passengers, so called deadheads, to operate its flights, because they are scattered geographically. This is likely not a very good solution. In recent studies, the fleet assignment problem has been modeled as a multi-commodity network flow problem with integer and real variables, and solved by conventional methods. In this research, we modify one of the existing models for domestic airline company and use Genetic Algorithm (GA), Simulated Annealing (SA) and Ant Colony Optimization (ACO) to solve it. These algorithms were implemented for the fleet assignment problem and used to solve a sample problem. Comparison of results of solving the sample problem by algorithms and GAMS software indicates that, GA, SA and ACO have good capability for solving the fleet assignment problem.