Technical Program

Submitted abstracts will be conditionally accepted for inclusion in the AGIFORS Symposium agenda. Final acceptance is contingent on 1) receipt of complete presentation on/before 05 September 2010, and 2) approval of presentation content by the AGIFORS technical committee.

Air Cargo Schedule Planning
Ulrich Derigs and Stefan Friederichs - University of Cologne

We present a new approach and Decision Support System for air cargo schedule planning (ACSP). Following this approach, planning is based on predefined fixed and optional flights instead of single legs and the planning goal is to allow the analysis and adaption of a flight schedule to a changing environment. Planning is based on integrated models which support several relevant planning aspects such as maintenance requirements, equal aircraft usage, and the evaluation of RFS or alliances. A sophisticated branch & price & cut-procedure has been developed which is capable of solving problem instances of realistic sizes for different problem scenarios and airline types.

Air Travel Market Simulator in Amadeus
Francois Laburthe - Amadeus

A market simulation tool is often used in the airline industry to estimate the impact of different business processes that are often too complex to be measured directly. To be able to obtain reliable answers, a simulator needs to have certain qualities, in particular, reality, scalability, versatility, and usability. In the talk, we will present how we obtained the aforementioned features for our air travel market simulator and where the simulator has been used so far. The presentation will include calibration of simulation based on air travel market data for achieving the reality feature, distributed computing and sequential generation of simulated travel demand for scalability, modularized modeling of each airline business process and simulation of various combinations of modules for versatility, and integration of an simulation analysis tool for usability. The simulator has been used for validating the value of a new inventory control algorithm, which is in the process of being implemented in an industrialized airline IT system. Also, it is used to help an airline decide between two IT systems in the area of distribution and revenue management.

Airline Service Network Design under the EU Emissions Trading Scheme
Cornelia Schoen - Leibniz University Hannover

In an effort to help reduce CO2 emissions and mitigate the climate impacts, the EU recently announced that as from 2012 the aviation sector will be included in the EU Emissions Trading Scheme (ETS). In particular, all flights starting and landing in the EU will be subject to a cap on their CO2 emissions. In preparation of this regulation, airlines are spurred to explore how they can improve their offering and operations under economic and ecologic considerations. We present a market-oriented optimization model for airline service design that integrates flight schedule design, fleet assignment and demand management under the ETS.

A New Formulation for Choice Based RM under a General Attraction Model
Richard Ratliff - Sabre Holdings

This presentation makes two important contributions, one to discrete choice modeling and the other to revenue management with dependent demands. A new variation of the basic choice model is proposed in which the re-attraction rates of specific alternatives in the choice set can be varied for both dependent and independent demand applications. Also, a new, polynomial-sized formulation of the origin-destination network revenue management fluid model is presented which handles both class and flight-level recapture effects. Taken together, these techniques provide a general and computationally efficient framework for solving the deterministic RM optimization problem. A wide range of effects are considered including variable demand dependencies with corresponding up-sell and recapture rates, multiple cabins, multiple time periods, and competition.

An Optimization Approach to Airline Integrated Recovery
Jon Petersen - Georgia Institute of Technology

 

While the airline industry has been a considerable benefactor of the use of advanced optimization methods, most of the successes have been in the frictionless planning environment. Clearly disruptions are inevitable as airlines must repair their schedule, aircraft, crew, and passengers in a timely manner. Rescheduling each of these components in isolation may be a substantial challenge, so early research on irregular operations has studied these problems sequentially. By using heuristic methods to reduce the problem size, we present an optimization approach that solves the fully integrated problem. Computational results are presented showing considerable improvements in the integrated model.

Cluster based Fleet Assignment
Mourad Boudia and Semi Gabteni - Amadeus

Itinerary or O&D Based Fleet Assignment models have proven effective at capturing so called "network effects". However, the granularity of O&D based forecasts, with low demand averages and high deviations, results in a lack of robustness considering demand volatility. The larger the hubs and the connection possibilities, the more severe these effects. We propose to group itineraries while still capturing the network effects. This novel approach relies on a novel itinerary Cluster Based Fleet Assignment model. A simulation framework is developed to benchmark the approach. A number of issues must then be sorted out, starting with the clustering method and the cluster fare computation.

Decomposition Techniques in Market Sensitive Revenue Optimization
Thomas Winter and Arne Strauss - Lufthansa Systems

In airline revenue management, recent forecast and optimization models include the impact of customer choice behavior on demand forecasts and optimal control policies. The task is to find the best capacity allocation of number of seats to aircraft compartments and to find the best inventory control parameters. Deriving the best possible control parameters for airline capacity control can be done by solving a huge dynamic program or a huge mixed-integer program. Both options are infeasible due to curse of dimensionality of the state space or due to the number of possible control options and variables. Recent solution approaches consists of decomposition techniques where the overall network problem is split into smaller leg-based problems. We present a mathematical programming formulation for modeling the customer choice options and introduce a (deterministic) mixed integer program for solving the problem of optimizing the total network revenue for the given implied OD demand including adaptation of compartment capacities. Based on the result of this MIP, decomposition into leg based problems takes places. We discuss further options for speeding up the solution of the dynamic programs and conclude with the discussion of numerical results for real-world problems.

Economic Trends and Their Likely Effect on the Airline Industry
Jeffery Oboy - m2p

Where all airlines have been affected by the economic downturn now lasting since over 3 years, some worse than others, the industry as a whole is beginning to look for the light at the end of the tunnel. Which regions are heading upward, and which ones are not? What is the industry outlook in terms of passenger & cargo traffic growth, and what can we expect from the still volatile fuel situation? How will the effect of the current & forecasted economic situation differ between airlines in the Americas, EMEA & Asia-Pacific with respect to profitability and future trends in general?

Enhancing airline customer data by identifying passenger relationships
Michael Farrugia - UCD, Dublin

In the airline industry, customer data is predominantly based on quantitative data. In this presentation we explore the possibility of augmenting this quantitative data with relational data by identifying links between passengers. These links can represent different relationships such as travelled-with, sat-near or lives-in-same-city. The main topics of this presentation include:- * How to identify all airline customers even if they are not frequent fliers * What type of passenger relationships can be extracted from booking data * What is the business benefit of identifying passenger relationships and how can this information be used

Evaluating Alerting Mechanism in Crew Tracking System
Xianchang Wang - Chengdu Soft-intelligent Technology

In a crew tracking system, situation always changes; its alerting or warning mechanism should automatically trigger and notify crew scheduler what’s going on as well as what’s going wrong. Alerts guide crew controller try to fix the abnormal issues. For example, once a flight delays, the alerting mechanism should immediately trace out if a crew cannot execute the next flying task once the crew’s rest time is not enough. In practice, a crew controller may only need alerts they really need. Else they may lose in the mass of alerting messages. So the question of how the alerting mechanism can help crew controller efficiently and properly handle their daily operation becomes an important issue in a crew tracking system. In this paper, we present three function requirements for the alerting mechanism. Firstly, an alerting mechanism should capture all the daily operation problems. The alerting mechanism shouldn’t miss any existing problems or rule conflicts. Only a crew tracking system satisfy this functionality, the crew controller can be safe to believe your alerting mechanism and he can look upon your alerts to take actions instead of fingering out hidden conflicts by himself. We call this functionality a “Maximal” requirement. Secondly, an alerting mechanism should only alert real problem in real-time. If the problem doesn’t exist, or the problem was already fixed, the alerting mechanism should automatically clean up these non-existed alerts. So the life cycle of an alert should go to end when the problem is gone. This requirement for alerting mechanism, we call it “Minimal” requirement. The third functionality requirement is that the alerting mechanism should smartly tell the crew controller the related objects that cause the alert. In another word, alert should clearly tell the crew controller the problem’s scope and can quickly guide the crew controller to a solution by these objects. We call it “Supportive” requirement. In conclusion, we think that an advanced alerting mechanism should meet these three function requirements: the Maximal, the Minimal and the Supportive.

How robust are robust schedules in reality
Niklaus Eggenberg - APM Technologies

Due to economic pressure industries, when planning, tend to focus on optimizing the expected profit or the yield. The consequence of highly optimized solutions is an increased sensitivity to uncertainty. This generates additional "operational" costs, incurred by possible modifications of the original plan to be performed when reality does not reflect what was expected in the planning phase. The modern research trend focuses on "robustness" of solutions instead of yield or profit. Although robust solutions have a lower expected profit, they are less sensitive to noisy data and hence generate less operational costs. In this talk, we focus on the robustness of airline schedules. We compare different existing methods for "robust scheduling" on simulated data in order to analyze their performance. In particular, we analyze the consequences of erroneous prediction models on the performance of robust solutions. Simulations are based on the public data of the ROADEF Challenge 2009 (http://challenge.roadef.org/2009).

Maintenance Management at PGA Portugália Airlines

Miguel Vaz Pinto - PGA Portugália Airlines

Small is beautiful: Maintenance Program Optimization. Providing maintenance operations for a 14 aircraft fleet, we thrive to optimize Maintenance program cost using practical constraints: Escalation of critical tasks, integration with schedule "peak" timeframe when no Maintenance slot is allowed, grouping of critical tasks and hangar operations. PGA started with a model that potentially reduces Schedule maintenance cost, minimizing schedule downtime. Unit costs are "No-Fly" time and MH impact.

Measuring Schedule Robustness using Stochastic Models of Delay Propagation
Vinayak Deshpande - Purdue University

The goal of this research is to build stochastic models of airline networks and utilize publicly available data to answer policy questions related to schedule robustness, bottleneck flights in an aircraft rotation, bottleneck airports in the US air-travel infrastructure (airports that cause most delay propagation), and network based passenger-centric measures of on-time performance and schedule robustness. First, we develop stochastic models to analyze the propagation of delays through air-transportation networks. Second, our models allow us to develop three important robustness measures for airline networks. Finally, our analysis enables us to make recommendations regarding managing bottleneck resources in the air-travel infrastructure.

Model formulation and interface design choices for aircraft routing
Susanne Heipcke - FICO

Working with the example of aircraft routing with maintenance constraints, this talk discusses step-by-step the design choices for an optimization application: after the initial choice among different types of modeling systems and architectural issues, we shortly review possibilities for problem decomposition and concurrent solving with hints at their ease of implementation. We further comment on the role of visualization of input data and intermediate results during development, and user interaction with the application, including during the solving process.

Models, Mindsets and the Meaning of Life

David Post - SigmaZen

 

Individuals, groups and particularly societies through the ages have shown a high level of inertia when it comes to approaching a problem from a new perspective. The result is that new ideas are often stifled and a large amount of effort and luck is required by individuals to bring about anything more than incremental change.  This paper presents a case study of an attempt to perceive airline pricing from an alternative perspective: where price is based on the need an individual has to fly on a particular flight. It then discusses the revenue impact of such a pricing policy when it was applied to distressed inventory of a European low-cost airline and why such a policy might be even more beneficial for traditional full-service airlines.  The paper finishes with the author's vision of encouraging interactivity with consumers not only in the product-price specification but also in the post-transaction cash flow and how this could possibly be used as a novel approach to improving customer loyalty with the airline.

Multi-resource Revenue Management with Upgrades: A Comparison of
EMSR-Based and Choice-Based Algorithms

Mark Fergusun - Georgia Institute of Technology (GA Tech)

 

     We investigate EMSR-based and choice-based revenue management control policies for multi-resource industries. We define multi-resource to represent scenarios where the physical characteristics of the product being sold are different and not universally substitutable.  Applications in the airline industry include cases when customers have the option of purchasing different seats, such as first class, exit row, window, and aisle.  Although the literature provides promising insights for single-resource applications, our results show that neither the methodology nor the findings can be directly applied to multi-resource industries.  We develop several new methodologies and extensions to existing ones to incorporate product substitutability (defined as the case where only a subset of products are substitutes for other products). We compare the performance of these models against traditional single-resource techniques using actual booking data from a publicly available data source.  We provide several key contributions. In the context of EMSR-based methods, we propose a max flow sub-problem to account for product substitutability. Results indicate that it is critically important to consider the multi-resource nature of the problem, as a simple application of the traditional single-resource version of EMSR-b with ad hoc adjustments can lead to serious degradation in revenue performance – upwards of 10% in some cases. In the context of choice-based methods, we propose a new estimation method that is based on redefining arrival rates to include only those customers who purchase from either our firm or a competitor. We obtain choice-based parameters and arrival rates using a method that uses the firm’s historical market share and reduces computational times, compared against existing estimation techniques, from hours to seconds. We show that our method is robust to market share and underlying customer behavior assumptions. Further, we show that choice-based methods perform better than multi-resource EMSR methods in the majority of cases.

 

Multi-choice threshold models: Destination choice for opaque products.

Laurie Garrow -  Georgia Institute of Technology

 

We develop a new discrete choice model based on the concept of minimum thresholds, i.e., we assume that alternatives that do not meet a minimum desirable threshold are excluded from choice sets.  We use this model to predict destination exclusion probabilities data from an opaque product offered by a European airline. Customers are willing to accept uncertainty in their final travel destination, but for a fee may exclude one or more destinations.  Results show destination exclusion probabilities are sensitive to distance and geographic boundaries.

 

Research and Development of Next Generation RM system at United Airlines
Wen Zhao - United Airlines

Traditional RM models assume independent demand. With fare fences broken, these models become ineffective and cause spiral down of yield. RM users rely heavily on manual adjustments to counter spiral down. United Airlines has been investing in an automated, robust, and improvable solution during the past several years. Key components are a conditional demand forecaster and an optimizer that leverages new insights about demand behavior. Several forecast and optimization models have been tested and are being evaluated. Next Generation Demand Forecaster predicts constrained demand conditioning on the booking control. The optimizers feature integrated overbooking, and separate control of local/connection markets.

Seasonal Manpower Planning at a Low Cost Airline
Alexandre Feray - Open Airlines

When you speak to airlines, manpower planning is always a complicated subject with lots of experience and intuition involved.  The subject becomes even more complex in a low-cost airline environment which often combines high growth, rapid changes in the network as well as strong seasonal variations in the activity due to a more leisure-oriented market. In this presentation, we’ll show how we took an original approach based on crew costs modeling and operational research to optimize the crew manpower planning process and reduce crew costs.

SIGLA An Integrated System for Airline Management
Eduardo Soares - LATOP

The aim of this paper is to present the complete process of controlling and managing the flights in an airline company. Airline planning consists of several problems that are currently solved separately: fleet assignment, rostering, crew planning, fuel control, airport taxes, etc. A system was developed to handling with all the process and provides a series of tools. Some of these tools use mathematical programming to solve the problems and this paper will describe each one. This system is being utilizing in almost all regional airlines companies in Brazil and it takes advantage of integrations between the sectors so the planning people can use information from the operational one, the crew schedule assemble the pairing according to the fleet assignment and so on. Another feature of the system is the creation of scenarios. If the solution time is reasonable, several different scenarios of the same problem may be solved and choosing the one whose solution is the best in the given situation.
Keywords : Crew Scheduling, Information Technology, Schedule Planning

Solving the Airline Crew Pairing Problem using Subsequence Generation
Matias Sevel Rasmussen - Technical University of Denmark

The crew pairing problem is typically modelled as a set partitioning problem and solved by column generation. In this work in progress we severely limit the number of allowed subsequent flights, thereby significantly decreasing the number of possible columns. Set partitioning problems with limited subsequence counts are known to be easier to solve. The problem though, is that a small number of deep subsequences might be needed for an optimal or near-optimal solution and these might not have been included by the subsequence limitation. Therefore, we try to identify or generate such subsequences that potentially can improve the solution value.

Inquiries about Technical Program

Tim Jacobs
AGIFORS Technical Director
Phone: +1 480-872-3228
E-mail: tim.jacobs@usairways.com