En Route Speed Change Optimization for Spacing Continuous Descent Arrivals  
Marcus Lowther (Master student at Georgia Institute of Technology, United States of America)

Abstract: Continuous Descent Arrival (CDA) procedures have been shown to minimize the thrust required during landing, reducing noise, emissions, and fuel usage for commercial aircraft. Widespread implementation of CDA would result in significant reductions in environmental impact and airline operating costs. However, a significant barrier to system wide CDA implementation is the ability to merge and space CDA aircraft with required spacing so that the CDA is flown safely and the spacing of the aircraft does not incur significant additional fuel use from heading and speed changes. Thus, a method was developed to determine adjustments to cruise speeds while aircraft are en route, while achieving the spacing targets calculated by the Tool for Analysis of Separation and Throughput, and to optimize fleet wide fuel burn increase. The En route Speed Change Optimization Relay Tool solves the speed change problem quickly, while dividing the speed changes fairly across multiple airlines.

 

Integration of gate assignment and platform bus planning  
Guido Diepen (Ph.D. student at University of Utrecht, The Netherlands)

Abstract: In this paper we look at the gate assignment problem and the bus planning problem as they appear at Amsterdam Airport Schiphol (AAS). Furthermore, we consider the integrated version of these problems. Given the expected arrivals and departures for the next day, we aim at finding a robust solution, such that the amount of replanning due to deviations from the expected arrival and departure times is minimum. For the separate problems we present two similar integer linear programs (ILP) and solve the LP-relaxations through column generation. The generated columns and a set of additional columns are then used to solve the ILP. For the integrated approach we show how to link the models of the separate problems to form one large model. Computational results with real life data provided by AAS are promising and indicate that the algorithm is able to solve real-life instances within acceptable running times.

 

Airline Passengers’ Online Search and Purchase Behavior: New Insights from an Interactive Price Response Model  
Misuk Lee (Ph.D. student at Georgia Institute of Technology, United States of America)

Abstract: This paper develops a model of airline customers’ on-line search and purchase behavior using page-by-page clickstream data collected from a web-based Interactive Pricing Response (IPR) system that was implemented by Freedom Air, a former low cost subsidiary of Air New Zealand. The IPR system represents a new business model designed to stimulate demand by dynamically offering discounts to highly time-flexible travelers in a way that does not trigger price responses from competitors. A new model based on Markov-methods that incorporates reference price effects is proposed to capture the dynamics of customer search and purchase behaviors of these highly time-flexible leisure travelers. Empirical results show that higher search intensities and purchase conversions occur as the relative discounts increase. In addition, while product attributes displayed on the previous screen are highly correlated with product attributes displayed on the current screen, fundamental customer choices related to whether to continue shopping, to purchase, or not to purchase are driven predominately by the relative discount level displayed on the current screen. Simulations are used to illustrate how these highly-predictable search and purchase behaviors can be integrated back into the IPR system, effectively enabling firms to control conversion rates and the relative discount rate ranges offered in the market.

 

Block Time Estimation and Robust Airline Scheduling  
Yu-Ching Lee (Master student at University of Illinois, United States of America)

Abstract: Airline schedule development continues to remain one of the most challenging planning activity for any airline. An airline schedule comprises a list of flights and specifies the origin, destination, scheduled departure, and arrival time of each flight in the airline’s network. A critical component of the schedule development activity is the estimation of flight block-times, which depend on several factors. Many airlines estimate these block-times simply by using limited historical data, however, such techniques have not resulted in significantly improved on-time performance of the schedule during operations. Thus, from a passenger’s perspective, the service level guarantee of an airline’s network continues to be low. We first define two service level metrics for an airline schedule. The first one is similar to the on-time performance measure of the U.S. Department of Transportation and we define it as the flight service level. The second metric, called the network service level, is geared towards completion of passenger itineraries. We then develop a stochastic integer programming formulation that optimally perturbs a given schedule to maximize expected profit while ensuring the two service levels. We also develop a variant of this model that maximizes service levels while achieving desired network profitability. To solve these models we develop an efficient algorithm that guarantees optimality. Through extensive computational experiments, using real-world data, we demonstrate that our models and algorithms are efficient and achieve the desired trade-off between service level and profitability.

 

The Application of Semidefinite Programming to the Aircrew Scheduling Problem  
Leander Quiring (Master student at University of Waterloo, Canada)

Abstract: It is said that the world is shrinking every day. Passenger air travel, along with electronic communication, is undoubtedly one of the key factors responsible for this shrinking. To allow air traffic in the volumes we see today, quite a few extremely difficult problems had to be solved in the fields of structural engineering, aerodynamics, even marketing. In this paper, we examine one such problem, the aircrew scheduling problem, and how it is has been solved in industry. We then examine a Semi-Definite Programming (SDP) relaxation for the two phases of this problem and test it on three test cases. The results of these test cases are promising, and suggest that further research in this area might be very rewarding. We also suggest several practical areas in which this research might be directed and where SDP could be used in the airline industry.

 

Fairness in the Aircraft Landing Problem  
Maarten Soomer (Ph.D. student at VU University of Amsterdam, The Netherlands)

Abstract: The last few decades a lot of attention has been paid to Collaborative Decision Making (CDM) in Air Traffic Management. A lot of models are proposed in which information of stakeholders (mainly airlines) is used in some way to improve the decision process. When doing this, fairness becomes an important issue. However, it is not always clear what will be considered fair by the airlines involved. In this paper we will use the aircraft landing problem to illustrate various definitions of fairness, that stem from the use of airline preferences. In this problem, a landing order and feasible landing times have to be determined for a set of flights at a runway. The airlines cost and the various definitions of fairness are used as objective for the problem. Local search heuristics are introduced to solve these formulations. Numerical experiments using schedule data from a large European airport are used to evaluate how the fairness definitions and heuristics behave for real life problems. The results show that it is possible to achieve more fairness, while still obtaining considerable cost savings compared to the First Come First Served schedule. The heuristics obtain reductions of up to 26% in the root mean square deviation of the average cost per airline. The different heuristics show that schedules with different trade-offs between efficiency, cost, delay and fairness can be obtained. Hopefully, these results can be a starting point for discussing the fairness issues related to the introduction of CDM processes among air traffic stakeholders.

 

A Mixed Integer Programming Approach to the Aircraft Weight and Balance Problem  
Wouter Souffriau (Ph.D. student at KaHo Sint-Lieven, Belgium)

Abstract: The Aircraft Weight and Balance Problem (AWBP) is a real-world combinatorial optimisation problem in which an aircraft should be loaded with containers in such a way that the total cargo value is maximised. At the same time the centre of gravity should approach an optimal point. Flying optimally reduces fuel consumption and thus results in a financial and environmental gain. This paper introduces a mixed integer programming approach to solve the AWBP. Experimental results show that the model enables an increase of the cargo value compared to the result obtained by an experienced planner. Moreover, the mixed integer programming approach achieves better balanced solutions in only a few seconds.

 

Solving the Robust and Integrated Aircraft Routing and Crew Pairing Problem in Practice  
Oliver Weide (Ph.D. student at University of Auckland, New Zealand)

Abstract: We formulate an integrated aircraft routing and crew pairing model that yields solutions for both problems that incur small costs and are robust to typical stochastic variability in airline operations, i.e. effects of delays occurring in operations are minimised. We propose two new solution methods to solve the integrated model. The first approach is an optimisation based heuristic that is capable of generating good quality solutions quickly, the second approach utilises Dantzig-Wolfe decomposition to solve the integrated model to optimality. Using data from domestic Air New Zealand schedules, we evaluate the benefits of solving the integrated model on real world problem instances. Our solutions satisfy all rules imposed on aircraft routings and crew pairings and are ready to be implemented in practice. We obtain solutions that dramatically improve costs and robustness of solutions obtained by traditional methods. We also compare our approaches with an existing Benders decomposition approach.

 

Schedule Design and fleet Assignment with Demand-Supply Interactions: an Alternative Approach  
Nitika Budhiraja (Ph.D. student at Indian Institute of Management Calcutta)

Abstract: The paper solves schedule design and fleet assignment problem while taking care of various demand-sypply interactions. Scope of the paper includes both unconstrained and constrained demand. Paper provides a method to incorporate the change in unconstrained itenary demand as a function of supply and the approach is less subjective and hence more scalable as compared to existing methods. Paper also discusses a new approach to handle spill and recapture. The resultant model is a mixed integer non-linear model, that has been converted into a mixed integer linear problem. The paper illustrates the utility of approach with the help of examples.

Robust Flight Scheduling - An Analytic Approach to Performance Evaluation and Optimization  
Brigitte Fuhr (Ph.D. student at Clausthal University of Technology and Lufthansa Airlines)

Abstract: The flight scheduling process of most major airlines is mainly based on deterministic rules disregarding the stochastic nature of airline operations. Creating schedules which are robust against daily disruptions and at the same time follow aircraft productivity goals requires a stochastic model. Often the model is formulated in terms of a Monte Carlo simulation which forecasts the operational schedule performance. This paper focuses on an analytic modeling approach that can be used for punctuality evaluation and moreover provides an algorithm to calculate the optimal basic planning parameters in terms of block times and ground times.

Integrated Airline Fleet and Crew Robust Planning  
Chunhua Gao (Ph.D. student at Georgia Institute of Technology)

Abstract: The airline fleet assignment problem involves assigning aircrafts to flights to maximize profit. Different fleet assignment solutions cause dramatically different performance in subsequent crew planning and operational processes. We have developed an integrated fleet and crew robust planning method to provide fleet assignment solutions that are both friendly to crew planning and robust to real time operations. The three challenges of this work are 1) to understand the influence of fleet assignment on crew scheduling; 2) to address crew scheduling in a tractable way in the integrated model; and 3) to achieve robustness. We address these challenges by developing a new approach that integrates crew connections within the fleet assignment model and imposes station purity by limiting the number of fleet types and crew bases allowed to serve each airport. Computational results demonstrate that the proposed approach can reduce crew planning cost, improve robustness, and solve industrial size problems with good computational efficiency.

Designing Allocation Mechanisms for Carrier Alliances  
Lori Houghtalen (Ph.D. student at Georgia Institute of Technology)

Abstract: When cargo carriers form an alliance, a key issue to resolve is how to provide incentive for carriers to make decisions that are optimal for the alliance as a whole. We propose a mechanism that utilizes capacity exchange prices to influence carrier behavior, and analyze two approaches to modeling the impact of these prices on the behavior of an individual carrier. We find that the model used can significantly impact alliance recommendations; one proposed model always finds capacity exchange prices that yield an allocation that is budget-balanced and stable, yet cannot guarantee centralized feasibility. The second model uses more realistic control parameters and does in fact guarantee centralized feasibility. Finally, experimental results for two and three-carrier alliances are analyzed; it is determined that the benefit associated with collaborating increases with network size and fleet capacity, and depending on the characteristics of demand, fleet capacity is a more important factor.

Dynamic Pricing of Perishable Assets under Competition  
Ming Hu (Ph.D. student at Columbia University)

Abstract: Legacy carriers in the airline industry are facing fierce competition from low cost providers that impose few or no fare restrictions. In addition, the Internet has provided customers with instant fare transparency. As a result, existing revenue management solutions based on allocating capacity to different fare classes are becoming less effective. To avoid revenue erosion from inadequate solutions, carriers need to develop new systems based on how consumers behave given the information available to them. This requires a choice-based, multi-player, game theoretic formulation of dynamically pricing perishable inventories over finite-horizons. Here we present such a formulation as a stochastic control problem in continuous time and provide sufficient conditions for the existence and uniqueness of open-loop Nash equilibria of the corresponding differential game. We show that pricing heuristics suggested by the open-loop Nash equilibria are asymptotically ε-Nash equilibria for the stochastic game. The robust stability of the unique open-loop Nash equilibrium and repeated versions of the single-stage pricing game are also studied. Asymptotic results are extended to network models, to sales over different channels and to account for quality attributes.

Seat Inventory Control with Limited Demand Information  
Yingjie Lan & Huina Gao (Ph.D. students at University of Maryland)
 
Abstract: In this paper, we consider the classical single resource (leg) problem in revenue management for the case where demand information is limited. Our approach employs a competitive analysis, which guarantees a certain performance level under all possible input sequences where the only information available consists of lower and/or upper bounds on demand. We consider both competitive ratio and absolute regret performance criteria. We derive the best possible static policies whose booking limits remain constant throughout the booking horizon, under the various models we analyze. We prove that the optimal policies have the form of nested protection levels. We also show how dynamic policies, whose booking limits may be adjusted at any time based on the history of bookings, can be obtained. We provide extensive computational experiments and compare our methods to existing ones. The results of the experiments demonstrate the effectiveness of these new robust methods.

Noise Load Management at Amsterdam Airport Schiphol  
Tristan Meerburg (Student at University of Twente)

Abstract: Amsterdam Airport Schiphol is one of the five primary hub-airports in Europe. All flight movements are controlled by Air Traffic Control the Netherlands (LVNL), whose main objective is to guarantee safety, efficiency, and protection of the environment, that includes noise load. To this end, a number of enforcement points is located in the vicinity of Schiphol. Each aircraft movement contributes to the noise load at these points. If the cumulative load in an aviation year at an enforcement point exceeds its maximum, the civil aviation authority may impose severe sanctions, such as fines, or a reduction in the number of aircraft movements. The latter is a typical restriction for Schiphol. Runway selection is carried out via the preference list, an ordered set of runway combinations such that the higher on the list a runway combination, the better this combination is for maintaining the noise load limit. The highest safe runway combination in the list will actually be used. This paper has formulated the preference list selection process in the mathematical framework of Stochastic Dynamic Programming that enables determining an optimal strategy for preference list selection taking into account future and unpredictable weather conditions, as well as safety and efficiency restrictions. The size of the problem is determined by the number of enforcement points. The work described in this paper is intended as a feasibility study. Numerical results indicate that, although our algorithm in Matlab on a regular PC has a running time that is not practical for direct implementation in the decision process, our algorithm is capable of describing optimal decisions for a smaller set of enforcement points, and therefore that the approach followed in this paper is a feasible solution for the optimal preference list problem.

 

Rethinking the Airline Crew Scheduling Process  
Chunhua Gao (Ph.D. student at Georgia Institute of Technology)

Abstract: This research on the airline crew scheduling problem focuses on more efficient solution approaches as well as integrating the crew problem with other airline scheduling problems. It is known that for some schedules there are very good pairing solutions with low pay and credit, while for other schedules the pairing solutions are poor and may be impossible to improve by more computational effort. We explore the reasons intrinsic to schedules that prevent getting good pairing solutions. In this paper, two schedule analysis methods are proposed to evaluate the crew friendliness of a given schedule, and guidelines are given for making small modifications of the schedule when analysis indicates problems. Based on the result and methodology of schedule analysis, application areas such as a new duty partition formulation for crew pairing problem, integrated planning, and integrated recovery are discussed.

Analysis of U.S. Airline Passengers' Refund and Exchange Behavior across Multiple Airlines  
Dan Iliescu (Ph.D. student at Georgia Institute of Technology)

Abstract: This paper uses individual ticket data from the Airline Reporting Corporation to model customer refund and exchange behavior across multiple U.S. airlines. A conceptual model describing how ticketing data relates to and can be integrated into traditional no-show and cancellation models is outlined. Survival models are used to predict the number and timing of cancellation (defined as ticketing refunds and exchanges). Distinct from other cancellation models, time is modeled “backwards” relative to the outbound departure date to provide a clearer interpretation of cancellation effects occurring as a function of days from flight departure. Empirical results provide new insights into airline passenger behavior and constitute one of the first published studies to be based on ticket clearinghouse data. This is of interest to airlines because as the use of the Internet has increased, traditional data sources (such as booking reservations made through travel agencies) are becoming less reliable.

Integrated Airline Scheduling: Decomposition and Acceleration Techniques  
Nikolaos Papadakos (Ph.D. Student at IC-PARC (centre for Planning And Resource Control))

September 2007: Paper published in Computers and Operations Research (2007) doi: 10.1016/j.cor.2007.08.002
Abstract: Airline scheduling is composed of fleet, maintenance, and crew decision subproblems. It is believed that the full problem is computationally intractable, and hence the constituent subproblems are solved sequentially so that the output of one is the input of the next. The sequential approach, however, provides suboptimal solutions and can also fail to satisfy the maintenance constraints of an otherwise feasible full problem. In this paper an integrated airline scheduling model is introduced, and its size is reduced by applying Benders decomposition combined with column generation. Several techniques are introduced to accelerate these decomposition algorithms. These techniques are generic enough to be applied to other airline problems. Solutions of several realistic data sets are computed using the integrated approaches, which are compared with solutions of the best known approaches from the literature. As a result, the integrated approach significantly reduces airlines costs, and the chosen formulation proves be better than alternative integrations attempted.

Capacity Planning at Airport Terminals using Delay Time Approximations and Multistage Stochastic Programming  
Senay Solak (Ph.D. student at Georgia Institute of Technology)

Abstract: An important part of the airport terminal design process is the determination of the optimal design capacity levels for different areas of the terminal under the uncertainty of future demand levels and expansion costs. Due to the difficulty of this task, most studies in this area either do not account for expandability or focus only on one particular area of the terminal. Furthermore, modeling the transient demand patterns is usually difficult due to the complex structure of an airport terminal. In this study, we aim to remedy this shortcoming first by developing functions to approximate maximum delay in passageways and processing stations during peak periods. We then propose a multistage stochastic programming approach based on a multicommodity flow network representation of the whole airport terminal. The level of service structure assumed in the model is based on time spent in the terminal by different types of passengers. Solution of the proposed model provides optimal capacity requirements for each area in an airport terminal during the initial building phase, as well as the optimal expansion policy under stochastic future demand.

 

Solving large scale linear multicommodity flow problems with an active set strategy and Proximal-ACCPM  
Frederic Babonneau
Doctoral Student at the University of Geneva

 

A Multi Objective Model for the Robust Aircraft Routing
Nitika Budhiraja
Doctoral Student at Indian Institute of Management, Calcutta
 

Modeling The Competitive Dynamic Among Air-Travel Itineraries With Generalized Extreme Value Models  
Greg Coldren (Winner, 2005 AGIFORS Anna Valicek Medal)
Doctoral Student at Northwestern University
 

A New Approach To Solve The Probabilistic Nonlinear Seat Inventory Control Problem  
Andreea Popescu (runner-up, 2005 AGIFORS Anna Valicek Medal)
Doctoral Student at Georgia Institute of Technology