Chapter 1
Introduction
Introduction
The United States Airline Deregulation Act of 1978 paved the way for major structural changes in the US airline industry. Airlines were allowed to select their network as well as their fares. This prompted a rush of new startup airlines to the market. After deregulation, the competition was not only between the pre-deregulation airlines, but also from the new entrants. Airlines were no longer protected, and if they wanted to be profitable, they had to manage their operations more efficiently.
Airlines use numerous resources to provide transportation services for their passengers. It is the planning and efficient management of these resources that determines the survival or demise of an airline. The airline industry is an excellent example of the ‘survival of the fittest concept.’ Table 1.1 shows the number of certificated airlines from 1976–2007 in the United States. The table also presents the number of airlines that were closed or merged with other airlines, and the number of newly established airlines. As the table implies, the airline industry operates in a very dynamic and uncertain environment. Furthermore, low flexibility to respond to changes, tightly coupled resources and limiting FAA regulations make the airline industry a complex environment (Yu 1998). To handle the complexity, robust and efficient planning tools and techniques are required. Operations research tools and techniques have played an important role in handling such complexities.
Operations Research and Airlines
Airlines have been using operations research techniques since the 1950s (Barnhart and Talluri 1997). Operations research models have had a tremendous impact on planning and managing operations within the airlines. The advances in computer technology and optimization models have enabled airlines to tackle more complex problems and solve them in a much shorter span of time. The vast contribution of these models has led to the establishment of operations research departments in many airlines, which help save millions of dollars. These departments have helped create an important professional society within the field of operations research, the Airline Group of the International Federation of Operational Research Societies (AGIFORS). AGIFORS is a professional society that seeks to advance, promote, and apply operations research within the airline industry (see www.agifors.org). A brief look at their website shows that Operations Research techniques have been successfully applied to many diverse problems such as revenue management, crew scheduling, aircraft routing, fleet planning, maintenance, and so on, within the airline industry. Barnhart (2008) discusses the accomplishment, opportunities and challenges of Operations Research in airline scheduling.
Table 1.1 Number of US certificated (DOT) airlines in the years 1976–2007
Outline of this Book
This book explores a variety of optimization models adopted by the airlines for scheduling and planning. The chapters discussing these models start with an example and then explain the process of developing a mathematical model. At the end of the chapter the general mathematical model is presented. The contents of this book are divided into three parts as follows:
Part 1 – Planning Optimization
• Chapter 2 – Network Flows and Integer Programming Models: This chapter is intended as a review of the basic concepts in network flows and integer programming models. These models are adopted later on in the following chapters.
• Chapter 3 – Flight Scheduling: Construction of flight schedules is the starting point for all other airline optimization problems. This chapter discusses the construction of flight schedules for a fictitious airline. This schedule is then used in the following chapters to address fleet assignment, aircraft routing, crew scheduling, and manpower planning.
• Chapter 4 – Fleet Assignment: Airlines typically operate a number of different aircraft, each having different characteristics, seating capacity, landing weights, and crew and fuel costs. This chapter introduces the basic fleet assignment model and its application to the fictitious airline.
• Chapter 5 – Aircraft Routing: This chapter presents the process of assigning individual aircraft to fly each flight segment assigned to the fleet. The chapter discusses mathematical models and their applications to the fictitious airline.
• Chapter 6 – Crew Scheduling: This chapter discusses the process of assigning crew to flight segments in two phases. First, crew pairing is introduced to determine which flight segments should be paired. The second phase, crew rostering, discusses how these pairings are assigned to the crew incorporating various rules and regulations.
• Chapter 7 – Manpower Planning: This chapter discusses manpower planning for ground crew through the fictitious airline case.
Part 2 – Operations and Dispatch Optimization
• Chapter 8 – Revenue Management: This chapter introduces revenue management, probabilistic models, and case studies.
• Chapter 9 – Fuel Management Systems: This chapter introduces jet fuel cost, hedging strategies, case study, and a mathematical model for fuel tankering.
• Chapter 10 – Airline Irregular Operations: When faced with a lack of resources and/or disruptions caused by various internal and external factors, airlines often are not able to fly their published flight schedule. This chapter provides an introduction to irregular operations, delays, cancellations, a mathematical model for irregular operations, and a case study.
• Chapter 11 – Gate Assignment: This chapter introduces the gate assignment mathematical model through a case study.
• Chapter 12 – Aircraft Boarding Strategy: This chapter explores various aircraft boarding strategies adopted by the airlines. It introduces a mathematical approach for an efficient aircraft boarding strategy applied to an Airbus A-320.
Part 3 – Computation Complexity and Simulation
• Chapter 13 – Computational Complexity, Heuristics, and Software: This chapter discusses inherent computational complexity with the airline problems and how heuristics are implanted to solve large scale problems. It also highlights some of the software vendors who provide solution suites for different airline problems.
• Chapters 14–18: These chapters introduce case studies on a start-up airline, and simulation modeling for airlines and airports. Simulation studies have become an alternative and/or integrated part of mathematical models when faced with complex problems.
• Appendix: provides the full name of the airports presented as their three/four letter codes in this book.
Software
Throughout this book references are made to software for solving linear/integer program models. Many of these models can be solved using student/trial versions of optimization software, which are typically available at colleges, universities, and airlines. There are many software vendors who provide these student/trial versions free to download on their websites (see, for example, www.lindo.com or www.maximal-usa.com). For larger problems, which exceed the student/trial version limits, we used full version of MPL software (www.maximal-usa.com) with CPLEX solver (www.ilog.com).
References
Barnhart, C. and Talluri, K.T. (1997). Airline operations research in design and operation of civil and environmental engineering system, in C. Revelle and A. McGarity. Wiley, 435–69.
Barnhart, C. (ed.). (2008). Proceedings from CPAIOR ‘08: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems – 5th International Conference.
Yu, G. (1998). Operations Research in the Airline Industry. Kluwer Academic Publishers.
PART I
Planning Optimization Chapter 2
Network Flows and Integer Programming Models
Introduction
A large part of the problems that airlines face can be translated into network and integer programming models. These models are mentioned and used throughout this book. This chapter attempts to provide a review of some of the optimization models discussed in this book. It should be noted that these topics only represent a small selection of models from the vast area of network and integer programming techniques. For a complete discussion of various network models, interested readers are referred to the list of books referenced in this chapter.
Networks
A network (also referred to as a graph) is defined as a collection of points and lines joining these points. There is normally some flow along these lines, going from one point to another. Figure 2.1 represents a network.
Figure 2.1 Basic elements of a network
Network Terminology
Before explaining the models, some terminologies commonly used in network study are described.
Nodes and Arcs: In a network, the points (circles) are called nodes and the lines are referred to as arcs, links or arrows (see Figure 2.1).
Flow: The amount of goods, vehicles, flights, passengers and so on that move from one node to another (see Figure 2.2).
Figure 2.2 Flow between two nodes
Directed Arc: If the flow through an arc is allowed only in one direction, then the arc is said to be a directed arc. Directed arcs are graphically represented with arrows in the direction of the flow (see Figure 2.3).
Figure 2.3 Directed flow
Undirected Arc: When the flow on an arc (between two nodes) can move in either direction, it is called an undirected arc. Undirected arcs are graphically represented by a single line (without arrows) connecting the two nodes (see Figure 2.4).
Figure 2.4 Undirected flow
Arc Capacity: The maximum amount of flow that can be sent through an arc. Examples include restrictions on the...