Solving the Airline Tail Assignment Problem with Column Generation

Abstract

The airline industry there are a lot of planning problems. The first problem that is encountered in the process is the network planning. This problem determines which flights will be flown on which days. The decisions here are usually made with factors such as potential revenue or the hub and spoke system. The second problem is fleet assignment, where the various flights are divided between the different aircraft types. The third problem is aircraft routing or tail assignment. Here the result of the previous phase is used and the routes are then divided further between the various planes based on maintenance and other factors. The final phase in the initial planning is given by the crew scheduling and ground resources planning. These involve the division of the various resources such as ground and air crew between the different flights. The above problems determine the initial planning. It would of course be ideal to combine them in order to find an optimal planning, but this is often not possible due to the complexity of the individual problems. As such they are usually solved sequentially. There are however also a number of factors that only become clear during the operation which might cause the original planning to no longer be feasible or optimal. This mainly includes disturbances such as flights being delayed or cancelled and as such mean that planes are not where they are expected to be. The tail assignment problem is often solved during operations and modifies the original planning to take these factors into account. These factors often only become clear during the operation and as such the tail assignment problem is then solved every day to try to minimize the effect of the disturbances. We will mainly be focusing on the aircraft routing and tail assignment problem. For both we only consider one type of aircraft, which means that the only difference between the planes in our planning are factors such as maintenance. The main problem is to assign these planes to the various flights that have to be flown. For this we will use daily lines of flight (LOF) which contain a set of flights that can be flown by a single plane in a single day. In the tail assignment problem we will also have an initial planning to use as a base to improve. We generally do not want to change this planning more than necessary as that would also require significant changes to the crew scheduling and ground resource planning phases which are not considered here. For this we first go over the background that will be needed for this. We begin with the basics of linear programming. After that we prove the simplex algorithm that can be used to solve those linear programs. Then we discuss duality and its relation with the column generation technique which can significantly improve the efficiency with which we find our optimal solution. For this a knowledge base was created from a university course, while the more detailed aspects were taken from a book. After this we discuss the maintenance routing problem as it is described in a certain article as well as its expansion to the tail assignment problem. Here the purpose is to minimize delay in the planning. The second approach we take is to instead try to minimize changes from the original schedule as is common when solving the tail assignment problem. 2 In our final section we give a short summary of the two methods and show a few places where more research could be done