 |
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
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 author’s surname.
|
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.
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 accross 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 - 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.
|
|
|
|
|
|
