Anna Valicek Medal

History of the Anna Valicek Medal

Anna Valicek Medal – 2010

The AGIFORS council received 23 submissions for Anna Valicek Medal in 2010.

Winner Anna Valicek Medal 2010

Ivan Dovica (Doctoral student at Charles University, Czech Republic)

Robust Tail Assignment

Abstract: We propose an efficient column generation method to minimize the probability of delay propagations along aircraft rotations. In this way, delay resistant schedules can be constructed. Computational results for large-scale real-world problems demonstrate substantial punctuality improvements. The method can be generalized to crew and integrated scheduling

problems.

Runner-Up Anna Valicek Medal 2009
Masoud Talebian (Doctoral student at Columbia University, United States of America)

Requiring Minimum Sales Volumes to Trigger a Commission Increase under Competition

Abstract: We consider a game between two airlines with fixed capacities that compete for customers through a travel agent. The agent works on commission margins and can influence customer choices. We study the effects of requiring minimum sale volumes, or thresholds, to trigger an increase in commissions when commission margins are fixed, and also when commission margins are decision variables. With fixed commission margins, the airline with a higher commission margin gets priority. However, at least one airline has an incentive to impose minimum sale volumes to trigger commissions, usually at the expense of the agent. In equilibrium, the airline with a higher total commission on sellable capacity gets priority and there are cases where the agent is forced to discard items that he cannot sell. If commission margins are also decision variables, the equilibrium results in less revenue for the smaller airline and more revenue for the agent, with the revenue for the larger airline remaining unchanged.

Honorable Mention - Anna Valicek Medal 2010:

Vikrant Vaze (Doctoral student at Massachusetts Institute of Technology, United States of America)

Competitive Airline Scheduling under Airport Demand Management Strategies

Abstract: Demand often exceeds capacity at the congested airports. Various strategic slot control mechanisms are used to bring demand and supply in balance. Given a slot allocation strategy, the profitability of an airline depends not only on its own schedule but also on competitors schedules. We propose a game-theoretic model of airline frequency competition under slot constraints. The model is solved to obtain a Nash equilibrium using a successive optimizations approach, wherein individual optimizations are performed using a dynamic programming-based technique. The model predictions are validated against actual frequency data which indicates a close fit to reality. We use the model to evaluate different slot allocation strategies from the perspectives of the various stakeholders. The most significant result of this research shows that a small reduction in total number of slots translates into not only a substantial reduction in airport congestion and delays, but also a considerable improvement in airlines profitability.

Other Submissions – 2010

We thank the other submitters for sharing their Operations Research work with the AGIFORS community. We recognize the authors for their innovative contributions relevant to the airline industry. Submissions are in alphabetical order of the paper title.

Allocate the Right Aircraft Capacity

Mohammed Salem Awad (Felix Airways)

A Dynamic Programming Framework for Aircraft Design and Airline Network Design Incorporating Passenger Demand Models

Navindran Davendralingam (Purdue University)

An Optimization Approach to Airline Integrated Recovery

Jon D. Petersen (Georgia Institute of Technology)

A proposal for network air traffic flow management incorporating fairness and airline collaboration

SHUBHAM GUPTA (Massachusetts Institute of Technology)

A Runway Configuration Management (RCM) Model with Marginally Decreasing Transition Capacities

Christopher Weld (College of William & Mary)

Assessing the Efficacy of Adaptive Airport Strategic Planning: Results from Computational Experiments

J.H. Kwakkel (Delft University of Technology)

Building Reliable Air-Travel Infrastructure Using Stochastic Models of Airline Networks

Mazhar Arikan (Purdue University)

Collision Avoidance in the Air Traffic Management: A Mixed Integer Linear Optimization Approach

Javier Martin-Campo (University Rey Juan Carlos)

Conflict Avoidance: 0-1 linear models for Conflict Detection & Resolution

Pablo Olaso (University Rey Juan Carlos)

Dynamic optimization of codeshare flight selection for an airline company

Marc-Alexandre LaRoche (Ecole Polytechnique de Montreal)

Decoupling Airline Alliances: A Bid-Price Approach to the Game of Incomplete Information

Christopher P. Wright (University of Rochester)

Estimating unconstrained demand rate functions using customer choice sets

Alwin Haensel (VU University Amsterdam)

Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods

Mohammed Saddoune (Ecole Polytechnique de Montreal)

Logical analysis of data for estimating passenger show rates in the airline industry

Christine Dupuis (Ecole Polytechnique de Montreal)

Optimal sequencing of aircrafts take-off and landing at a busy airport

Paolo D'Urgolo (Universit`a degli Studi Roma Tre)

Profit Maximization of Multi-Stops Operating Model

Mohammed Salem Awad (Felix Airways)

Robust Airline Schedule Planning: Minimizing Propagated Delay in an Integrated Routing and Crewing Framework

Michelle Dunbar (University of New South Wales)

Robust Optimization: Lessons Learned from Aircraft Routing

Lavanya Marla (Massachusetts Institute of Technology)

Short-term Allocation of Time Windows to Flights through a Distributed Market-based Mechanism

Andrea RANIERI (University of Trieste)

Variable opaque products in the airline industry: A tool to fill the gaps and increase revenues

David Post (SigmaZen GmbH)

Anna Valicek Medal - 2009

This year's competition was one of the best (and closest) ever in terms of the overall quality of the submissions. Although it was a difficult decision, the AGIFORS council is pleased to have selected two excellent papers as finalists for the Anna Valicek Medal. The authors have been invited to present their work on the 49th annual symposium to be held in Atlanta, Georgia, United States of America, between 28 September and 2 October 2009 (air transportation, accommodations and symposium fees are sponsored). The two finalists were:

	Winner Anna Valicek Medal 2009 Douglas Fearing (Ph.D. student at Massachusetts Institute of Technology, United States of America) Equitable and Efficient Coordination of Traffic Flow Management Programs
Abstract: When air traffic demand is projected to exceed capacity, the FAA implements Traffic Flow Management programs. Independently, these programs maintain a first-scheduled, first-served invariant, which is the accepted standard of fairness within the industry. Coordinating multiple programs requires a careful balance between equity and efficiency. In our work, we first develop a fairness metric to measure deviation from first-scheduled, first-served. Next, we develop an IP formulation that attempts to directly minimize this metric. We further develop an exponential penalty approach and show that its computational performance is far superior and its trade-off between delay and fairness compares favorably. In our results, we demonstrate the effectiveness of these models using regional and national scenarios. Additionally, we demonstrate that the exponential penalty approach exhibits exceptional computational performance, implying practical viability. Our tests suggest that this approach could lead to system-wide savings on the order of $100 million per year.
	Runner-Up Anna Valicek Medal 2009 Gizem Keysan (Doctoral student at Georgia Institute of Technology, United States of America) Tactical and Operational Planning of Scheduled Maintenance for Per-Seat, On-Demand Air Transportation
Abstract: Advances in aviation technology including the development of relatively cheap, very light jets and the possibility of free-flight have led to the realization of a per-seat, on-demand (PSOD) air transportation business that operates without a published flight schedule. An important aspect of daily operations for PSOD air transportation is managing the scheduled maintenance of the jets in the fleet. In this paper, we consider types of scheduled maintenance that require a visit to a maintenance facility and have to be performed frequently enough to pose planning challenges. Due to physical space limitations or the availability of labor, there is an upper bound on the number of jets that can be maintained on a given day. This is referred to as the maintenance capacity. Operational level planning is concerned with assigning itineraries to jets and determining the specific jets that have to go to maintenance on a daily basis given a certain maintenance capacity. We develop a two-phase approach. In the first phase, a multi-commodity network flow model is used to assign itineraries to critical jets, i.e. jets with high accumulated flying hours, and to decide which of these critical jets to send to maintenance. In the second phase, an integer programming model is used to assign itineraries to non-critical jets in such a way that the number of critical jets on subsequent days does not vary too much. There is a strong interaction between the operational level maintenance decisions and flight scheduling. Maintenance decisions affect flight scheduling as jets that undergo maintenance cannot be used to transport passengers. Conversely, flight scheduling impacts maintenance decisions as it may be necessary to revise preferred maintenance decisions if the set of accepted transportation requests can no longer be accommodated when the preferred maintenance decisions are implemented. In order to capture this interaction, we develop a framework in which operational maintenance planning and daily flight scheduling receive feedback from each other. The framework is tested in a simulation environment where travel requests are generated using an agent-based model, and flight scheduling and operational maintenance planning are performed in real-time. Although motivated by the operations of PSOD air transportation, the models and solution approaches introduced in this paper can be used more generally for dynamic scheduling problems in which resources need to undergo periodic maintenance and the arrival and the length of the tasks that need to be performed by the resources are non-deterministic.

Honorable Mention - Anna Valicek Medal 2009:

Computing Bid-Prices for Revenue Management under Customer Choice Behavior
Juan M. Chaneton (Doctoral student at Departamento de Computacion, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina)

Abstract: We consider a choice-based, network revenue management (RM) problem in a setting where heterogeneous customers consider various products offered by a firm (e.g., different flight times, fare classes and/or routings). Customers may therefore substitute if their preferred products are not offered. These individual customer choice decisions are modeled as a very general stochastic sequence of customers, each of whom has an ordered list of preferences. Minimal assumptions are made about the statistical properties of this demand sequence. The firm manages the availability of products using a bid-price control strategy, and would like to optimize the control parameters accounting for the (potentially quite complex) choice behavior of its customers. We formulate a continuous demand and capacity approximation for this problem which allows for the partial acceptance of requests for products. The model admits a simple calculation of the sample path gradient of the network revenue function. This gradient is then used to construct a stochastic steepest ascent algorithm. We show that the algorithm converges (w.p.1) to a stationary point of the expected revenue function under mild conditions. The algorithm is relatively efficient from a computational point of view, and in our simulation experiments it produces significant revenue increases relative to the results obtained using bid-prices under the traditional independent demand assumption. The performance is generally improved when the bid-prices are re-optimized along the booking horizon, which is actually the case in practical applications. Moreover, one of the main implementation advantages of our proposal is that it can be built-in as an extra layer on current RM systems that use bid-price controls. These features make it a serious candidate for real world applications.

Network Revenue Management with Inventory-Sensitive Bid Prices and Customer Choice
Arne K. Strauss (Doctoral student at Department of Management Science, Lancaster University Management School, Lancaster, United Kingdom)

Abstract: We develop a new approximate dynamic programming approach to network revenue management models with customer choice that approximates the value function of the Markov decision process with a concave function which is separable across resource inventory levels. This approach reflects the intuitive interpretation of diminishing marginal utility of inventory levels and allows for significantly improved accuracy compared to currently available methods. The model allows for arbitrary aggregation of inventory units and thereby reduction of computational workload, yields upper bounds on the optimal expected revenue that are provably at least as tight as those obtained from previous approaches, and is asymptotically optimal under fluid scaling. Computational experiments for the multinomial logit choice model with distinct consideration sets show that policies derived from our approach outperform available alternatives, and we demonstrate how aggregation can be used to balance solution quality and runtime.

Other Submissions - 2009

Rescheduling Flights, Aircraft, and Passengers Simultaneously under Disrupted Operations - A Mathematical Programming Approach based on Statistical Analysis
Rodrigo Acuna-Agost (Doctoral student at Universit´e d’Avignon et des Pays de Vaucluse, Laboratoire Informatique d’Avignon, Avignon, France)

Abstract: This article studies the problem of recovering a perturbed flight schedule considering flights, aircraft, and passengers simultaneously. This integration involves a big challenge in both modeling and solving. We propose a Mixed Integer Programming (MIP) formulation and a solution method that uses a statistical analysis for concentrating the search on probable good solutions. The method was evaluated in the context of the competition ROADEF challenge 2009: Disruption Management for Commercial Aviation proposed by AMADEUS, obtaining very good results and showing to be quite effective and viable in practice.

Integrating the Fleet Assignment Model with Uncertain Demand
Anwar H. Ahmed (Doctoral student at Centre for the analysis of Risk and optimisation modelling applications (CARISMA), School of Information Systems, Computing and Mathematics, Brunel University, London, United Kingdom)

Abstract: Fleet assignment models (FAM) are used by many airlines to assign aircraft to flights in a schedule to maximize profit. We first state the basic FAM before proposing new FAMs (i.e. DFAM1 and DFAM2) that tackles the common problem associated with aircraft utilization. Through the use of a two-stage Stochastic Programming (SP) with recourse technique, the DFAMs are extended to SP-FAMs. In generating the demand scenarios, we use a network-simulation model embedded with a time-series engine that gives a snapshot of one week that is representative of any other week of the scheduling season. We outline the SP-FAM solution process and give a proof of concept using real data from a Middle East airline. Our investigations establish clear benefits of the recourse FAM compared to alternative models. Finally, we propose areas of future research to improve SP-FAM robustness through solution algorithms, revenue management (RM) effects, calibration of network-simulation models and system integration.

Statistical Analysis and Forecasting of KLM Royal Dutch Airlines Ground Handling Process Durations
Evrim Akar (Masters student at Department of Mathematics, Utrecht University, The Netherlands)

Abstract: It is crucial for organizations of all sizes to make future forecasts in order to decrease the uncertainty of the environment and to take the advantage of opportunities available to the organization. As each data set has its specific properties, not every method results in accurate forecasts for a given data set. Therefore, a variety of techniques have been developed for effective and efficient predictions. In this study, the analysis of random processes and time-series are examined. Moreover, a brief description about the major forecasting methods are given and a nonparametric curve estimation method is introduced for future predictions. In order to increase the forecast accuracy, ”comparison and combination method” is applied. We focus on the quantile values of Royal Dutch Airlines (KLM) Ground Handling Process Times Data.

A Mathematical Programming Approach to Airline Crew Pairing Optimization
Diana C. Flórez (Masters student at Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Columbia)

Abstract: In the ever increasing competitive environment of the airline industry, efficient personnel’s planning is among the most challenging tasks and solely responsible for the largest impact on an airline’s cost structure. The problem is theoretically appealing because it is computationally difficult due to the huge number of possibilities, and the amount of rules that determine crew planning. This work proposes a methodology to determine the most efficient and least costly way to serve the flights in an airline schedule during a weekly planning horizon considering layovers and deadheads. The strategy is composed of three optimization models: a binary programming model, a model based on the set partitioning problem, and a third model based on the set covering problem, the two latter solved via column generation. Computational results for the three models are presented using test instances built from a mid-sized Colombian airline.

The Impact of Aviation Checkpoint Queues on Security Screening Effectiveness
Adrian J. Lee (Doctoral student at Department of Mechanical Science and Engineering, University of Illinois at Urbana-Champaign, United States of America)

Abstract: Passenger screening at aviation security checkpoints is a critical component in protecting airports and aircraft from terrorist threats. Recent developments in technology have increased the ability to detect these threats. However, the average amount of time it takes to screen a passenger still remains a concern. This paper models the queuing process for a multi-level airport checkpoint security system, where multiple security classes are formed through subsets of specialized screening devices. An optimal static assignment policy is obtained which minimizes the steady-state expected amount of time a passenger spends in the security system. Then, an optimal dynamic assignment policy is obtained that maximizes the number of true alarms while maximizing passenger throughput. Performance of a two-class system is compared to that of a selective security system. The key contribution is that the resulting optimal assignment policies increase security and passenger throughput by efficiently and effectively utilizing available screening resources.

Anna Valicek Medal - 2008

The AGIFORS council received 10 submissions for Anna Valicek Medal in 2008.

The council selected two finalists for the Anna Valicek Medal. The authors were invited to present their work on the 48th annual symposium in Montreal Canada, 21-26 September 2008 (air transportation, accommodations and symposium fees were sponsored). Finally the AGIFORS council acted as a jury and determined the winner and runner-up. The AGIFORS council came to the following decision:

	Winner Anna Valicek Medal 2008 Emmanuel Carrier (Ph.D. student at Massachusetts Institute of Technology, United States of America) Modeling the Choice of an Airline Itinerary and Fare Product Using Booking and Seat Availability Data
Abstract: In this research, we develop a methodology to analyze the choice of an airline itinerary and fare product based on booking data. Since non-booked travel alternatives are not recorded in airline bookings, booking data was combined with fare rules and seat availability data to incorporate the impact of airline pricing and revenue management and reconstitute the choice set of each booking. In addition, characteristics of the traveler and the trip were retrieved from the booking records and replaced trip purpose that is traditionally used to segment demand in airline markets. They were included as explanatory variables of a latent class choice model in which several factors can be used simultaneously to segment the market without necessarily dividing the bookings into many small sub-segments. In addition to an improvement in fit over previous models based on a deterministic segmentation of the market, the latent class choice model was found to provide a more intuitive segmentation of the demand between a core of time-sensitive business travelers and a mixed class of price-conscious leisure and business travelers. This model extends the range of applications of passenger choice models to additional airline planning decisions such as pricing and revenue management.
	Runner-up Anna Valicek Medal 2008 Shervin AhmadBeygi (Ph.D. student at University of Michigan, United States of America) Decreasing Airline Delay Propagation By Re-Allocating Scheduled Slack
Abstract: Passenger airline delays have received increasing attention over the past several years as airspace congestion, severe weather, mechanical problems, and other sources cause substantial disruptions to a planned flight schedule. Adding to this challenge is the fact that each flight delay can propagate to disrupt subsequent downstream flights that await the delayed flights’ aircraft and crew. This potential for delays to propagate is exacerbated by a fundamental conflict: slack in the planned schedule is often viewed as undesirable, as it implies missed opportunities to utilize costly perishable resources, whereas slack is critical in operations as a means for absorbing disruption. In this paper, we show how delay propagation can be reduced by redistributing existing slack in the planning process, making minor modifications to the flight schedule while leaving the original fleeting and crew scheduling decisions unchanged. We present computational results based on data from a major U.S. carrier, showing that significant improvements in operational performance can be achieved without increasing planned costs.

Honorable Mention - Anna Valicek Medal 2008:

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.

Other Submissions - 2008

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.

Anna Valicek Medal - 2007

The AGIFORS council has received 9 submissions for Anna Valicek Medal 2007. The council has selected two papers as candidates for the Anna Valicek Medal. The authors were invited to present their work on the 47th annual symposium in Bangkok. Finally the AGIFORS council came to the following decision:

	Winner Anna Valicek Medal 2007 Juan José Miranda Bront (Student at University of Buenos Aires) A column generation algorithm for choice-based network revenue management
Abstract: In the last few years, there has been a trend to enrich traditional revenue management models built upon the independent demand paradigm by accounting for customer choice behavior. This extension involves both modeling and computational challenges. One way to describe choice behavior is to assume that each customer belongs to a segment, which is characterized by a consideration set, i.e., a subset of the products provided by the firm that a customer views as options. Customers choose a particular product according to a multinomial-logit criterion, a model widely used in the marketing literature. In this paper, we consider the choice-based, deterministic, linear programming model (CDLP) of Gallego et al., and the follow-up dynamic programming (DP) decomposition heuristic of van Ryzin and Liu, and focus on the more general version of these models, where customers belong to overlapping segments. To solve the CDLP for real-size networks, we need to develop a column generation algorithm. We prove that the associated column generation subproblem is indeed NP-Complete, and propose a simple, greedy heuristic to overcome the complexity of an exact algorithm. Our computational results show that the heuristic is quite effective, and that the overall approach has good practical potential and leads to high quality solutions.
	Finalist Anna Valicek Medal 2007 Geert De Maere (Ph.D. student at University of Nottingham) Multi-objective approaches for robust airline scheduling
Abstract: The operational performance of an airline schedule is the result of a complex interaction between the schedule and its operating environment. A robust schedule is one that anticipates the stochastic nature of the operating environment and reduces the influence of disturbances on its operation. Evidence in the literature shows that the robustness of airline schedules is influenced by multiple features in the schedule, defined as robustness objectives. The construction of robust airline schedules should therefore be considered as a multi-objective optimisation problem that generates schedules with a good balance between the individual robustness objectives that maximise the operational performance of the schedule. We present time window approaches for incremental and integrated multi-objective improvement of robustness objectives in airline schedules. We applied single- and multi-meme memetic solution approaches enabling us to generate diverse sets of high quality trade-off schedules that balance the individual objectives. A large scale simulation was carried out to estimate the operational performance of the individual trade-off schedules. A sensitivity analysis of the simulation results was undertaken to estimate the individual and simultaneous influence of the robustness objectives and the impact upon the operational performance. Our work has enabled us to better understand the mutual interaction of robustness objectives and their individual and simultaneous influence on the schedules' operational performance.

Other Submissions - 2007

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.

Anna Valicek Medal - 2006

In total 6 very interesting high quality papers were received in 2006. We would like to thank all submitters for submitting their work. Also we would like to thank all reviewers for reviewing the papers and giving feedback to the authors. In 2006 the council has come to the following decision:

	Winner Anna Valicek Medal 2006 Hai Jiang, Ph.D. student at Massachesetts Institute of Technology Dynamic Airline Scheduling: Models, Algorithms and Experiments
Abstract: Even with an optimized schedule, many flights upon departure have empty seats, while others suffer a lack of seats to accommodate passengers who desire to travel. Demand stochasticity is a major challenge for the airlines in the quest to produce profit maximizing schedules. We approach this challenge, recognizing that demand forecast quality for a particular date improves as the date approaches, by developing a dynamic scheduling approach that re-optimizes elements of the flight schedule during the passenger booking process. The goal is to match capacity to demand, given the many operational constraints that restrict possible assignments. We introduce flight re-timing as a dynamic scheduling mechanism and develop re-optimization models that integrate both flight re-timing and flight re-fleeting. Our re-optimization approach, re-designing the flight schedule at regular intervals, utilizes information from both revealed booking data and improved forecasts with later re-optimizations. Experiments are conducted using data from a major airline in the United States. We investigate properties of our model and demonstrate that significant potential profitability improvements are achievable using our dynamic scheduling approach.
	Runner-up Anna Valicek Medal 2006 Ozge Sahin, Ph.D. student at Columbia University Inter-temporal Valuations, Product Design and Revenue Management
Abstract: We study booking processes over finite horizons that culminate with the delivery of a good or service. We develop an inter-temporal choice model where the consumers choose the product they purchase among the current and the future alternatives taking into account the evolution of their valuations over time. We show that for all capacity levels likely to arise in practice, selling call options on capacity results in significantly higher expected revenues than low-to-high pricing. We analyze a two-period fluid model in detail, and obtain structural results on the optimal revenue function, closed-form distribution-free bounds on the option price and the optimal revenue. Moreover, we show that using options improve the social benefits over low-to-high pricing. Next, we show that the solution to the fluid model is asymptotically optimal heuristic for the stochastic model and extend the model to multiple periods and study the optimal time to issue and exercise call options.

Other Submissions - 2006

Besides the submissions of the winner and runner-up, four other papers were submitted. Submissions are working papers or completed works. Papers have been posted for comment from AGIFORS members. Please assist the authors by providing your constructive feedback. Submissions are in alphabetical order of the author’s surname.

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.

Anna Valicek Medal - 2005

In 2005 a total of 4 interesting high quality papers were received. All of these submissions are working papers, and these draft versions have been posted for comment from AGIFORS members. Please assist the authors by providing your constructive feedback.

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

AGIFORS president Tim Jacobs awards Greg Coldren the 2005 AGIFORS Anna Valicek Medal

Anna Valicek Medal - 2004

Winner

Congratulations to Rivi Sandhu for winning the 2004 Anna Valicek Medal. She completed her master's degree at the University of Illinois at Urbana-Champaign and is now working at United Airlines. Please click here for a copy of the working paper by Ms. Sandhu and Prof. Diego Klabjan.