The current airline practice is to assign aircraft capacity to scheduled flights well in advance of departure. At such an early stage in this process, the high uncertainty of demand poses a major impediment for airlines to best match the airplane capacities with the final demand. However, the accuracy of the demand forecast improves markedly over time, and revisions to the initial fleet assignment become naturally pertinent when the observed demand considerably differs from the assigned aircraft capacity. The Demand Driven Re-fleeting (DDR) approach proposed in this thesis offers a dynamic re-assignment of aircraft capacity to the flight network, as and when improved demand forecasts become available, so as to maximize the total revenue. Because of the need to preserve the initial crew schedule, this re-assignment approach is limited within a single family of aircraft and to the flights assigned to this particular family. This restriction significantly reduces the problem size. As a result, it becomes computationally tractable to include path level demand information into the DDR model, although the problem size can then get very large because of the numerous combinations of composing paths from legs. As an extension, models considering path-class level differences, day-of-week demand variations, and re-capture effects are also presented. The DDR model for a single family with path level demand considerations is formulated as a mixed-integer programming problem. The model's polyhedral structure is studied to explore ways for tightening its representation and for deriving certain classes of valid inequalities. Various approaches for implementing such reformulation techniques are investigated and tested. The best of these procedures for solving large-scale challenging instances of the problem turns out to be an integrated approach that uses certain selected model augmentations and valid inequalities generated via a suitable separation routine and a partial convex hull construction process. Using this strategy in concert with properly selected CPLEX options reduces the CPU time by an average factor of 7.48 over an initial model for a test-bed of problems each having 200 flights in total. Prompted by this integrated heuristic approach, a procedure for finding solutions within a prescribed limit of optimality is suggested. To demonstrate the effectiveness of these developed methodologies, we also solved two large-scale practical-sized networks that respectively involve 800 and 1060 flights, and 18196 and 33105 paths in total, with 300 and 396 flights belonging to the designated family. These problems were typically solved within 6 hours on a SUN Ultra 1 Workstation having 260 MB RAM and a clock-speed of 167 MHz, with one exception that required 14 hours of CPU time. This level of computational effort is acceptable considering that such models are solved at a planning stage in the decision process. / Master of Science

Air transportation offers both passenger and freight services that are essential for economic growth and development. In a highly competitive environment, airline companies have to control their operating costs by managing their flights, aircraft, and crews effectively. This motivates the extensive use of analytical techniques to solve complex problems related to airline operations planning, which includes schedule design, fleet assignment, aircraft routing, and crew scheduling. The initial problem addressed by airlines is that of schedule design, whereby a set of flights having specific origin and destination cities as well as departure and arrival times is determined. Then, a fleet assignment problem is solved to assign an aircraft type to each flight so as to maximize anticipated profits. This enables a decomposition of subsequent problems according to the different aircraft types belonging to a common family, for each of which an aircraft routing problem and a crew scheduling or pairing problem are solved. Here, in the aircraft routing problem, a flight sequence or route is built for each individual aircraft so as to cover each flight exactly once at a minimum cost while satisfying maintenance requirements. Finally, in the crew scheduling or pairing optimization problem, a minimum cost set of crew rotations or pairings is constructed such that every flight is assigned a qualified crew and that work rules and collective agreements are satisfied. In practice, most airline companies solve these problems in a sequential manner to plan their operations, although recently, an increasing effort is being made to develop novel approaches for integrating some of the airline operations planning problems while retaining tractability. This dissertation formulates and analyzes three different models, each of which examines a composition of certain pertinent airline operational planning problems. A comprehensive fourth model is also proposed, but is relegated for future research. In the first model, we integrate fleet assignment and schedule design by simultaneously considering optional flight legs to select along with the assignment of aircraft types to all scheduled legs. In addition, we consider itinerary-based demands pertaining to multiple fare-classes. A polyhedral analysis of the proposed mixed-integer programming model is used to derive several classes of valid inequalities for tightening its representation. Solution approaches are developed by applying Benders decomposition method to the resulting lifted model, and computational experiments are conducted using real data obtained from a major U.S. airline (United Airlines) to demonstrate the efficacy of the proposed procedures as well as the benefits of integration. A comparison of the experimental results obtained for the basic integrated model and for its different enhanced representations reveals that the best modeling strategy among those tested is the one that utilizes a variety of five types of valid inequalities for moderately sized problems, and further implements a Benders decomposition approach for relatively larger problems. In addition, when a heuristic sequential fixing step is incorporated within the algorithm for even larger sized problems, the computational results demonstrate a less than 2% deterioration in solution quality, while reducing the effort by about 21%. We also performed an experiment to assess the impact of integration by comparing the proposed integrated model with a sequential implementation in which the schedule design is implemented separately before the fleet assignment stage based on two alternative profit maximizing submodels. The results obtained demonstrate a clear advantage of utilizing the integrated model, yielding an 11.4% and 5.5% increase in profits in comparison with using the latter two sequential models, which translates to an increase in annual profits by about $28.3 million and $13.7 million, respectively. The second proposed model augments the first model with additional features such as flexible flight times (i.e., departure time-windows), schedule balance, and demand recapture considerations. Optional flight legs are incorporated to facilitate the construction of a profitable schedule by optimally selecting among such alternatives in concert with assigning the available aircraft fleet to all the scheduled legs. Moreover, network effects and realistic demand patterns are effectively represented by examining itinerary-based demands as well as multiple fare-classes. Allowing flexibility on the departure times of scheduled flight legs within the framework of an integrated model increases connection opportunities for passengers, hence yielding robust schedules while saving fleet assignment costs. A provision is also made for airlines to capture an adequate market share by balancing flight schedules throughout the day. Furthermore, demand recapture considerations are modeled to more realistically represent revenue realizations. For this proposed mixed-integer programming model, which integrates the schedule design and fleet assignment processes while considering flexible flight times, schedule balance, and recapture issues, along with optional legs, itinerary-based demands, and multiple fare-classes, we perform a polyhedral analysis and utilize the Reformulation-Linearization Technique in concert with suitable separation routines to generate valid inequalities for tightening the model representation. Effective solution approaches are designed by applying Benders decomposition method to the resulting tightened model, and computational results are presented to demonstrate the efficacy of the proposed procedures. Using real data obtained from United Airlines, when flight times were permitted to shift by up to 10 minutes, the estimated increase in profits was about $14.9M/year over the baseline case where only original flight legs were used. Also, the computational results indicated a 1.52% and 0.49% increase in profits, respectively, over the baseline case, while considering two levels of schedule balance restrictions, which can evidently also enhance market shares. In addition, we measured the effect of recaptured demand with respect to the parameter that penalizes switches in itineraries. Using values of the parameter that reflect 1, 50, 100, or 200 dollars per switched passenger, this yielded increases in recaptured demand that induced additional profits of 2.10%, 2.09%, 2.02%, and 1.92%, respectively, over the baseline case. Overall, the results obtained from the two schedule balance variants of the proposed integrated model that accommodate all the features of flight retiming, schedule balance, and demand recapture simultaneously, demonstrated a clear advantage by way of $35.1 and $31.8 million increases in annual profits, respectively, over the baseline case in which none of these additional features is considered. In the third model, we integrate the schedule design, fleet assignment, and aircraft maintenance routing decisions, while considering optional legs, itinerary-based demands, flexible flight retimings, recapture, and multiple fare-classes. Instead of utilizing the traditional time-space network (TSN), we formulate this model based on a flight network (FN) that provides greater flexibility in accommodating integrated operational considerations. In order to consider through-flights (i.e., a sequence of flight legs served by the same aircraft), we append a set of constraints that matches aircraft assignments on certain inbound legs into a station with that on appropriate outbound legs at the same station. Through-flights can generate greater revenue because passengers are willing to pay a premium for not having to change aircraft on connecting flights, thereby reducing the possibility of delays and missed baggage. In order to tighten the model representation and reduce its complexity, we apply the Reformulation-Linearization Technique (RLT) and also generate other classes of valid inequalities. In addition, since the model possesses many equivalent feasible solutions that can be obtained by simply reindexing the aircraft of the same type that depart from the same station, we introduce a set of suitable hierarchical symmetry-breaking constraints to enhance the model solvability by distinguishing among aircraft of the same type. For the resulting large-scale augmented model formulation, we design a Benders decomposition-based solution methodology and present extensive computational results to demonstrate the efficacy of the proposed approach. We explored four different algorithmic variants, among which the best performing procedure (Algorithm A1) adopted two sequential levels of Benders partitioning method. We then applied Algorithm A1 to perform several experiments to study the effects of different modeling features and algorithmic strategies. A summary of the results obtained is as follows. First, the case that accommodated both mandatory and optional through-flight leg pairs in the model based on their relative effects on demands and enhanced revenues achieved the most profitable strategy, with an estimated increase in expected annual profits of $2.4 million over the baseline case. Second, utilizing symmetry-breaking constraints in concert with compatible objective perturbation terms greatly enhanced problem solvability and thus promoted the detection of improved solutions, resulting in a $5.8 million increase in estimated annual profits over the baseline case. Third, in the experiment that considers recapture of spilled demand from primary itineraries to other compatible itineraries, the different penalty parameter values (100, 50, and 1 dollars per re-routed passenger) induced average respective proportions of 3.2%, 3.4%, and 3.7% in recaptured demand, resulting in additional estimated annual profits of $3.7 million, $3.8 million, and $4.0 million over the baseline case. Finally, incorporating the proposed valid inequalities within the model to tighten its representation helped reduce the computational effort by 11% on average, while achieving better solutions that yielded on average an increase in estimated annual profits of $1.4 million. In closing, we propose a fourth more comprehensive model in which the crew scheduling problem is additionally integrated with fleet assignment and aircraft routing. This integration is important for airlines because crew costs are the second largest component of airline operating expenses (after fuel costs), and the assignment and routing of aircraft plus the assignment of crews are two closely interacting components of the planning process. Since crews are qualified to typically serve a single aircraft family that is comprised of aircraft types having a common cockpit configuration and crew rating, the aircraft fleeting and routing decisions significantly impact the ensuing assignment of cockpit crews to flights. Therefore it is worthwhile to investigate new models and solution approaches for the integrated fleeting, aircraft routing, and crew scheduling problem, where all of these important inter-dependent processes are handled simultaneously, and where the model can directly accommodate various work rules such as imposing a specified minimum and maximum number of flying hours for crews on any given pairing, and a minimum number of departures at a given crew base for each fleet group. However, given that the crew scheduling problem itself is highly complex because of the restrictive work rules that must be heeded while constructing viable duties and pairings, the formulated integrated model would require further manipulation and enhancements along with the design of sophisticated algorithms to render it solvable. We therefore recommend this study for future research, and we hope that the modeling, analysis, and algorithmic development and implementation work performed in this dissertation will lend methodological insights into achieving further advances along these lines. / Ph. D.

This paper examines the determinants of profitability using operations strategy, productivity, and service measures in the context of the U.S. domestic airline industry. Data on ten carriers was collected on a quarterly basis between 1995 and 2007. An analysis is performed separately on data prior and post 9/11 attack. It is found that operations strategy and productivity measures are significant both before and after the 9/11 attack, whereas service measures are only significant before 9/11. Some managerial implications are provided. Additionally, it is found that the profitability of full-service carriers is improving faster than low-cost carriers after 9/11.

This paper examines the determinants of profitability using operations strategy, productivity, and service measures in the context of the U.S. domestic airline industry. Data on ten carriers was collected on a quarterly basis between 1995 and 2007. An analysis is performed separately on data prior and post 9/11 attack. It is found that operations strategy and productivity measures are significant both before and after the 9/11 attack, whereas service measures are only significant before 9/11. Some managerial implications are provided. Additionally, it is found that the profitability of full-service carriers is improving faster than low-cost carriers after 9/11.

This dissertation describes a model that predicts airline flight network, frequency and fleet changes in response to policy measures that aim to reduce the environmental impact of aviation. Such airline operational responses to policy measures are not considered by existing integrated aviation-environment modelling tools. By not modelling these effects the capability of the air transport system to adjust under changing conditions is neglected, resulting in the forecasting of potentially misleading system and local responses to constraints. The model developed follows the overriding principle of airline strategic decision making, i.e., airline profit maximisation within a competitive environment. It consists of several components describing different aspects of the air transport system, including passenger demand forecasting, flight delay modelling, estimation of airline costs and airfares, and network optimisation. These components are integrated into a framework that allows the relationships between fares, passenger demand, infrastructure capacity constraints, flight delays, flight frequencies, and the flight network to be simulated. Airline competition is modeled by simulating a strategic game between airlines competing for market share, each of which maximizes its own profit. The model is validated by reproducing historical passenger flows and flight frequencies for a network of 22 airports serving 14 of the largest cities in the United States, using 2005 population, per capita income and airport capacities as inputs. The estimated passenger flows and flight frequencies compare well to observed data for the same network (the R2 value comparing flight segment frequencies is 0.62). After validation, the model is applied to simulate traffic growth and carbon dioxide and nitrogen oxide emissions within the same network from 2005 to 2030 under a series of scenarios. These scenarios investigate airline responses to (i) airport capacity constraints, (ii) regional increases in costs in the form of landing fees, and (iii) major reductions in aircraft fuel burn, as would be achieved through the introduction of radically new technology such as a blended wing body aircraft or advanced open rotor engines. The simulation results indicate that, while airport capacity constraints may have significant system-wide effects, they are the result of local airport effects which are much greater. In particular, airport capacity constraints can have a significant impact on flight delays, passenger demand, aircraft operations, and emissions, especially at congested hub airports. If capacity is available at other airports, capacity constraints may also induce changes in the flight network, including changes in the distribution of connecting traffic between hubs and the distribution of true origin-ultimate destination traffic between airports in multi-airport systems. Airport capacity constraints are less likely to induce any significant increase in the size of aircraft operated, however, because of frequency competition effects, which maintain high flight frequencies despite reductions in demand in response to increased flight delays. The simulation results also indicate that, if sufficiently large, regional increases in landing fees may induce significant reductions in aircraft operations by increasing average aircraft size and inducing a shift in connecting traffic away from the region. The simulation results also indicate that the introduction of radically new technology that reduces aircraft fuel burn may have only limited impact on reducing system CO2 emissions, and only in the case where the new technology can be taken up by the majority of the fleet. The reason for this is that the reduced operating costs of the new technology may result in an increase in frequency competition and thus aircraft operations. In conclusion, the modelling of airline operational responses to environmental constraints is important when studying both the system and local effects of environmental policy measures, because it captures the capability of the air transport system to adjust under changing conditions.

abstract: Revenue management is at the core of airline operations today; proprietary algorithms and heuristics are used to determine prices and availability of tickets on an almost-continuous basis. While initial developments in revenue management were motivated by industry practice, later developments overcoming fundamental omissions from earlier models show significant improvement, despite their focus on relatively esoteric aspects of the problem, and have limited potential for practical use due to computational requirements. This dissertation attempts to address various modeling and computational issues, introducing realistic choice-based demand revenue management models. In particular, this work introduces two optimization formulations alongside a choice-based demand modeling framework, improving on the methods that choice-based revenue management literature has created to date, by providing sensible models for airline implementation. The first model offers an alternative formulation to the traditional choice-based revenue management problem presented in the literature, and provides substantial gains in expected revenue while limiting the problem’s computational complexity. Making assumptions on passenger demand, the Choice-based Mixed Integer Program (CMIP) provides a significantly more compact formulation when compared to other choice-based revenue management models, and consistently outperforms previous models. Despite the prevalence of choice-based revenue management models in literature, the assumptions made on purchasing behavior inhibit researchers to create models that properly reflect passenger sensitivities to various ticket attributes, such as price, number of stops, and flexibility options. This dissertation introduces a general framework for airline choice-based demand modeling that takes into account various ticket attributes in addition to price, providing a framework for revenue management models to relate airline companies’ product design strategies to the practice of revenue management through decisions on ticket availability and price. Finally, this dissertation introduces a mixed integer non-linear programming formulation for airline revenue management that accommodates the possibility of simultaneously setting prices and availabilities on a network. Traditional revenue management models primarily focus on availability, only, forcing secondary models to optimize prices. The Price-dynamic Choice-based Mixed Integer Program (PCMIP) eliminates this two-step process, aligning passenger purchase behavior with revenue management policies, and is shown to outperform previously developed models, providing a new frontier of research in airline revenue management. / Dissertation/Thesis / Doctoral Dissertation Industrial Engineering 2016

The thesis begins by examining the evolution of human performance modeling from the initial stimulus-response methods introduced during the industrial revolution to model factory worker productivity, continues with a discussion of the information processing model where human cognition was modeled as a series of actions carried out in a predefined order, and ends with the concept of cognitive control whereby cognition is not considered a context-free mental process but modeled as an individual's ability to maintain control under varying contexts and to counter the effects of disturbances. The results from a preliminary evaluation conducted to determine if CCMs could be measured and if they provided any additional insight cognitive work are presented, and reveal that CCMs could be measured and the self-assessed CCM varied as predicted. A design process is developed which utilizes the CCMs as representing specific patterns of activity, thus specifying the design requirements. Following this design process, a prototype is created and evaluated using a controlled experiment to examine the effectiveness of the CWSS. The experiment examines performance, workload, and patterns of activity, and has several interesting findings. The first is that performance was independent of the almost all of the predictors and covariates including participant's Self-assessed CCM, with the exception of CCM transitions. As in the preliminary study, participants who reported transitioning between CCMs also reported decreased performance, increased frustration and actually performed worse. Second, perceived performance varied linearly with a participant's self-assessed CCM, but not with the actual performance. Third, participants report lower levels of effort when using a CWSS DM that matched their operational CCM. Finally, the design process successfully created a CWSS with DMs which support strategic and tactical CCMs. Unfortunately, no specific performance improvements were found for cases where the participant's CCM matched the DM as hypothesized, calling into question the effectiveness of creating different design modes for performance improvement. This thesis presents two methods for measuring CCMs: one direct single scale and one indirect composite scale. The measurements correlate highly. Both have a high degree of face validity and user acceptance. In the end, the composite measure may be a more robust measure of CCM because it provides a greater degree of diagnosticity by specifically inquiring after different aspects of CCM and is less susceptible to an individual's interpretation of the relative importance of the multiple dimensions of CCMs included in the definitions.

Route planning forms an important aspect of airline operations for them to sustain the effects of deregulation and fierce competition. The Indian economic liberalization in 1991 has seen diminishing monopoly of Air India and dynamic demand splits amongst the service providers. Our research focuses on developing an aggregate route traffic demand forecasting (RTDF) model specifically for international carriers operating from India. The model is an econometric model that combines concepts of the traditional Gravity model of Physics and the Micro-economic theoretic model that links demand to price. In other words, the RTDF model is a fusion of the behavioral and gravity models. While developing the model, Becker’s approach of utility maximization has been made use of, thereby combining time and other inputs required to produce travel. The model is developed for the existing international routes from India with 2005 aggregative data provided by International Civil Aviation Organization (ICAO), which spanned 15 countries in Europe, Asia, Canada, and North America. The model has been validated and tested for its predictive power on a few intentionally left out routes from the original sample. The model explains about 70% of the variance, which is well above the acceptable zone for cross-sectional data. The model is then estimated for 2007 data on a few randomly selected high demand routes; the prediction error ranging from a minimum of 3.5% to a maximum of 13%, a range well within the acceptable error limits. We derive a sector-cost-model (SCM) by applying the concept of break-even analysis on the RTDF model. The SCM provides cost estimates on a particular route at various levels of airfare. The SCM helps us gain further insights into the business nature prevailing in the airline sector. On the viability of operations, we propose the sector-operation-fare (SOF) to be charged on a respective route, given the load factor, if the airline wishes to continue operations. For arriving at the SOF, we follow a demand oriented framework that comprises of two demand curves: the airline curve and the traffic curve. The numerical analyses provide room for policy formulations that help airlines in refining, redefining, and revitalizing the decision-making process in their operations. Airlines can use this model to forecast demand for a newly contemplated route and obtain a fair idea of the price they can charge the customer. In other words, airlines can estimate the economic viability of operations on a respective route.

The air transportation market has been growing steadily for the past three decades since the airline deregulation in 1978. With competition also becoming more intense, airline companies have been trying to enhance their market shares and profit margins by composing favorable flight schedules and by efficiently allocating their resources of aircraft and crews so as to reduce operational costs. In practice, this is achieved based on demand forecasts and resource availabilities through a structured airline scheduling process that is comprised of four decision stages: schedule planning, fleet assignment, aircraft routing, and crew scheduling. The outputs of this process are flight schedules along with associated assignments of aircraft and crews that maximize the total expected profit. Traditionally, airlines deal with these four operational scheduling stages in a sequential manner. However, there exist obvious interdependencies among these stages so that restrictive solutions from preceding stages are likely to limit the scope of decisions for succeeding stages, thus leading to suboptimal results and even infeasibilities. To overcome this drawback, we first study the aircraft routing problem, and develop some novel modeling foundations based on which we construct and analyze an integrated model that incorporates fleet assignment, aircraft routing, and crew pairing within a single framework. Given a set of flights to be covered by a specific fleet type, the aircraft routing problem (ARP) determines a flight sequence for each individual aircraft in this fleet, while incorporating specific considerations of minimum turn-time and maintenance checks, as well as restrictions on the total accumulated flying time, the total number of takeoffs, and the total number of days between two consecutive maintenance operations. This stage is significant to airline companies as it directly assigns routes and maintenance breaks for each aircraft in service. Most approaches for solving this problem adopt set partitioning formulations that include exponentially many variables, thus requiring the design of specialized column generation or branch-and-price algorithms. In this dissertation, however, we present a novel compact polynomially sized representation for the ARP, which is then linearized and lifted using the Reformulation-Linearization Technique (RLT). The resulting formulation remains polynomial in size, and we show that it can be solved very efficiently by commercial software without complicated algorithmic implementations. Our numerical experiments using real data obtained from United Airlines demonstrate significant savings in computational effort; for example, for a daily network involving 344 flights, our approach required only about 10 CPU seconds for deriving an optimal solution. We next extend Model ARP to incorporate its preceding and succeeding decision stages, i.e., fleet assignment and crew pairing, within an integrated framework. We formulate a suitable representation for the integrated fleeting, routing, and crew pairing problem (FRC), which accommodates a set of fleet types in a compact manner similar to that used for constructing the aforementioned aircraft routing model, and we generate eligible crew pairings on-the-fly within a set partitioning framework. Furthermore, to better represent industrial practice, we incorporate itinerary-based passenger demands for different fare-classes. The large size of the resulting model obviates a direct solution using off-the-shelf software; hence, we design a solution approach based on Benders decomposition and column generation using several acceleration techniques along with a branch-and-price heuristic for effectively deriving a solution to this model. In order to demonstrate the efficacy of the proposed model and solution approach and to provide insights for the airline industry, we generated several test instances using historical data obtained from United Airlines. Computational results reveal that the massively-sized integrated model can be effectively solved in reasonable times ranging from several minutes to about ten hours, depending on the size and structure of the instance. Moreover, our benchmark results demonstrate an average of 2.73% improvement in total profit (which translates to about 43 million dollars per year) over a partially integrated approach that combines the fleeting and routing decisions, but solves the crew pairing problem sequentially. This improvement is observed to accrue due to the fact that the fully integrated model effectively explores alternative fleet assignment decisions that better utilize available resources and yield significantly lower crew costs. / Ph. D.