The airline perturbation problem: considering disrupted passengers

Abstract

When airlines are faced with some unforeseen short-term events, they have to reconstruct their flight schedules. Although aircraft recovery decisions affect passengers, these disrupted passengers and recovering them have not been explicitly considered in most previous aircraft recovery models. This paper presents an assignment model for airline schedule recovery which recovers both aircraft and disrupted passengers simultaneously, using a rolling horizon time framework. Our model examines possible flight retiming, aircraft swapping, over-flying, ferrying, utilization of reserve aircraft, cancellation and passenger reassignment to generate an efficient schedule recovery plan. The model ensures that the schedule returns to normal within a certain time and the objective is to minimize operational recovery aircraft cost, cancellation and delay cost as well as disrupted passenger cost. The model is tested using a data-set with two disruption scenarios. The computational results show that it is capable of handling the integrated aircraft and passenger recovery problem successfully.     

A math-heuristic algorithm for the integrated air service recovery

A sophisticated flight schedule might be easily disrupted due to adverse weather, aircraft mechanical failures, crew absences, etc. Airlines incur huge costs stemming from such flight schedule disruptions in addition to the serious inconveniences experienced by passengers. Therefore, an efficient recovery solution that simultaneously decreases an airline's recovery cost while simultaneously mitigating passenger dissatisfaction is of great importance to the airline industry. In this paper, we study the integrated airline service recovery problem in which the aircraft and passenger schedule recovery problems are simultaneously addressed, with the objective of minimizing aircraft recovery and operating costs, passenger itinerary delay cost, and passenger itinerary cancellation cost.Recognizing the inherent difficulty in modeling the integrated airline service recovery problem within a single formulation (due to its huge solution space and quick response requirement), we propose a three-stage sequential math-heuristic framework to efficiently solve this problem, wherein the flight schedules and aircraft rotations are recovered in the first stage, Then, a flight rescheduling problem and passenger schedule recovery problems are iteratively solved in the next two stages. Time-space network flow representations, along with mixed-integer programming formulations, and algorithms that take advantages of the underlying problem structures, are proposed for each of three stages. This algorithm was tested on realistic data provided by the ROADEF 2009 challenge and the computational results reveal that our algorithm generated the best solution in nearly 72% of the test instances, and a near-optimal solution was achieved in the remaining instances within an acceptable timeframe. Furthermore, we also ran additional computational runs to explore the underlying characteristics of the proposed algorithm, and the recorded insights can serve as a useful guide during practical implementations of this algorithm.     

A stochastic passenger loading model of airline schedule performance

The passenger loading problem is defined as that of determining the distribution of passengers that will be carried on each flight in a given market over the course of the day. This problem is stochastic in nature, and must take into account the fact that as some flights become booked up, passengers may spill to adjacent flights, or may choose not to fly on that airline. A precise model of the loading process is developed and solved using an efficient numerical procedure. Several approximations are introduced and tested which further improve the overall efficiency. The model represents a more rigorous solution approach than has appeared previously in the literature, and as such could be used to evaluate simpler approximations. It is fast enough, however, to be used as an interactive schedule evaluation and design tool.     

A hybrid optimization-simulation approach for robust weekly aircraft routing and retiming

We address the robust weekly aircraft routing and retiming problem, which requires determining weekly schedules for a heterogeneous fleet that maximizes the aircraft on-time performance, minimizes the total delay, and minimizes the number of delayed passengers. The fleet is required to serve a set of flights having known departure time windows while satisfying maintenance constraints. All flights are subject to random delays that may propagate through the network. We propose to solve this problem using a hybrid optimization-simulation approach based on a novel mixed-integer nonlinear programming model for the robust weekly aircraft maintenance routing problem. For this model, we provide an equivalent mixed-integer linear programming formulation that can be solved using a commercial solver. Furthermore, we describe a Monte-Carlo-based procedure for sequentially adjusting the flight departure times. We perform an extensive computational study using instances obtained from a major international airline, having up to 3387 flights and 164 aircraft, which demonstrates the efficacy of the proposed approach. Using the simulation software SimAir to assess the robustness of the solutions produced by our approach in comparison with that for the original solutions implemented by the airline, we found that on-time performance was improved by 9.8–16.0%, cumulative delay was reduced by 25.4–33.1%, and the number of delayed passengers was reduced by 8.2–51.6%.     

Monitoring Aircraft Turnaround Operations – Framework Development,Application and Implications for Airline Operations

Abstract

A real-time operation monitoring system – Aircraft Turnaround Monitoring System – is developed based on a system framework to monitor aircraft turnaround operations at an airport. Mobile computing devices (PDAs) and wireless network technology General Packet Radio Service (GPRS) are used to implement the real-time monitoring system for an airline. System implementation and test results indicate that real-time operation monitoring can potentially reduce delays occurring from airline operations. Proactive measures can be taken immediately by ground handling staff to reduce delays, once the risk of delays and potential delay propagation is identified. The availability of detailed operating data can help airlines identify the root delay causes from complex connections among aircraft, flight/cabin crew and passengers. In addition, these operating data also shed some light on the future development of aircraft routing algorithms in order to consider explicitly stochastic disruptions and delay propagation in airline schedule planning.     

Analysis of airline operating strategies under stochastic demand

Variability in the demand for air travel is studied with respect to stochastic and time varying components which affect the distribution of passengers who will want to travel on a particular day. The problem is then cast as one of optimizing the total capacity offered in a given time period using operating net revenues as the objective. The distribution of demand is assumed to be normal, and passengers lost on those days when demand is high are assumed to travel on another airline or a different mode. An airline must therefore balance the costs of increased capacity against the benefits of carrying more people. Tradeoffs are studied parametrically, with particular emphasis on the effect the variance of the distribution of demand has on different relationships. Also shown is a simple procedure for estimating actual market mean and variance given the mean and variance of the number of passengers actually flown, which has a truncated distribution.     

A multiobjective planning model for intercity train seat allocation

This paper presents a multiobjective planning model for generating optimal train seat allocation plans on an intercity rail line serving passengers with many‐to‐many origin‐destination pairs. Two planning objectives of the model are to maximise the operator's total passenger revenue and to minimise the passenger's total discomfort level. For a given set of travel demand, train capacity, and train stop‐schedules, the model is solved by fuzzy mathematical programming to generate a best‐compromise train seat allocation plan. The plan determines how many reserved and non‐reserved seats are to be allocated at each origin station for all subsequent destination stations on each train run operated within a specified operating period. An empirical study on the to‐be‐built Taiwan's high‐speed rail system is conducted to demonstrate the effectiveness of the model. The model can be used for any setting of travel demand and stop‐schedules with various train seating capacities.     

Disruption Management of an Inequality-Based Multi-Fleet Airline Schedule by a Multi-Objective Genetic Algorithm

Abstract

This paper presents a novel application of a Method of Inequality-based Multi-objective Genetic Algorithm (MMGA) to generate an efficient time-effective multi-fleet aircraft routing algorithm in response to the schedule disruption of short-haul flights. It attempts to optimize objective functions involving ground turn-around times, flight connections, flight swaps, total flight delay time and a 30-minute maximum delay time of original schedules. The MMGA approach, which combines a traditional Genetic Algorithm (GA) with a multi-objective optimization method, can address multiple objectives at the same time, then explore the optimal solution. The airline schedule disruption management problem is traditionally solved by Operations Research (OR) techniques that always require a precise mathematical model. However, airline operations involve too many factors that must be considered dynamically, making a precise mathematical model difficult to define. Experimental results based on a real airline flight schedule demonstrate that the proposed method, Multi-objective Optimization Airline Disruption Management by GA, can recover the perturbation efficiently within a very short time. Our results further demonstrate that the application can yield high quality solutions quickly and, consequently, has potential to be employed as a real-time decision support tool for practical complex airline operations.     

Heuristic approach to the airline schedule disturbances problem

Abstract

When disturbances make it impossible to realise the planned flight schedule, the dispatcher at the airline operational centre defines a new flight schedule based on airline policy, in order to reduce the negative effects of these perturbations. Depending on airline policy, when designing the new flight schedule, the dispatcher delays or cancels some flights and reassigns some flights to available aircraft. In this paper, a decision support system (DSS) for solving the airline schedule disturbances problem is developed aiming to assist decision makers in handling disturbances in real-time. The system is based on a heuristic algorithm, which generates a list of different feasible schedules ordered according to the value of an objective function. The dispatcher can thus select and implement one of them. In this paper, the possibilities of DSS are illustrated by real numerical examples that concern JAT Airways' flight schedule disturbances.     

A heuristic model for frequency planning and aircraft routing in small size airlines

The flight schedule of an airline is the primary factor in finding the most effective and efficient deployment of the airline's resources. The flight schedule process aims at finding a set of routes with associated aircraft type, frequency of service and times of departures and arrivals in order to satisfy a specific objective such as profit maximization. In this paper, we develop a two‐phase heuristic model for airline frequency planning and aircraft routing for small size airlines. The first phase develops a frequency plan using an economic equilibrium model between passenger demand for flying a particular route and aircraft operating characteristics. The second phase uses a time‐of‐day model to develop an assignment algorithm for aircraft routing.     

The flight perturbation problem

Airlines spend considerable time, effort and financial resources on planning. It is essential to create a competitive timetable and construct a fleet and a crew schedule that utilizes these resources to the maximum. Unfortunately, it is all too common that an airline is faced with the necessity of reconstructing their schedules due to some unforeseen event, for example an aircraft breakdown or a crew member that is indisposed. In this paper, an application that can help airlines solve the complex problem of reconstructing aircraft schedules is presented. A mixed integer multicommodity flow model with side constraints is developed and further reformulated into a set packing model using the Dantzig—Wolfe decomposition. Cancellations, delays and aircraft swaps are used to resolve the perturbation, and the model ensures that the schedule returns to normal within a certain time. Two column generation schemes for heuristically solving the model are tested on real problem data obtained from a Swedish domestic airline. The computational tests show that the application is capable of presenting high quality solutions in a few seconds and therefore can be used as a dynamic decision support tool by the airlines.     

Robust supply vessel routing and scheduling

We solve the problem of tactical supply vessel planning arising in the upstream offshore petroleum logistics. Supply vessels deliver all the necessary materials and equipment to offshore installations from an onshore supply base according to a delivery schedule. The planning of supply vessels should be done so that their number is minimized and at the same time provide a reliable flow of supplies from the base. The execution of a weekly sailing plan is affected by weather conditions, especially in winter time. Harsh weather conditions increase the number of vessels required to perform the operations as well as the service times at the installations, and thus disrupt the schedule, leading to additional costs and reduced service level. We present a methodology for robust supply vessel planning enabling a trade-off analysis to be made between the schedules’ service level and vessels’ cost. The methodology involves the generation of multiple vessel schedules with different level of robustness using an adaptive large neighbourhood search metaheuristic and a subsequent discrete event simulation procedure for the assessment of the service level. To control the level of robustness we developed a concept of slacks and incorporated it into the metaheuristic algorithm.     

Passenger Perspectives in Railway Timetabling: A Literature Review

When looking at railway planning, a discrepancy exists between planners who focus on the train operations and publish fixed railway schedules, and passengers who look not only at the schedules but also at the entirety of their trip, from access to waiting to on-board travel and egress. Looking into this discrepancy is essential, as assessing railway performances by merely measuring train punctuality would provide an unfair picture of the level of service experienced by passengers. Firstly, passengers’ delays are often significantly larger than the train delays responsible for the passengers to be late. Secondly, trains’ punctuality is often strictly related to too tight schedules that in turn might translate into knock-on delays for longer dwelling times at stations, trip delays for increased risk of missing transfer connections, and uncertain assessment of the level of service experienced, especially with fluctuating passenger demand. A key aspect is the robustness of railway timetables. Empirical evidence indicates that passengers give more importance to travel time certainty than travel time reductions, as passengers associate an inherent disutility with travel time uncertainty. This disutility may be broadly interpreted as an anxiety cost for the need for having contingency plans in case of disruptions, and may be looked at as the motivator for the need for delay-robust railway timetables. Interestingly, passenger-oriented optimisation studies considering robustness in railway planning typically limit their emphasis on passengers to the consideration of transfer maintenance. Clearly, passengers’ travel behaviour is far more complex and multi-faceted and thus several other aspects should be considered, as becoming more and more evident from passenger surveys. The current literature review starts by looking at the parameters that railway optimisation/planning studies are focused on and the key performance indicators that impact railway planning. The attention then turns to the parameters influencing passengers’ perceptions and travel experiences. Finally, the review proposes guidelines on how to reduce the gap between the operators’ railway planning and performance measurement on the one hand and the passengers’ perception of the railway performance on the other hand. Thereby, the conclusions create a foundation for a more passenger-oriented railway timetabling ensuring that passengers are provided with the best service possible with the resources available.     

Effective aircraft maintenance schedule adjustment following incidents

In the real world, planned aircraft maintenance schedules are often affected by incidents. Airlines may thus need to adjust their aircraft maintenance schedules following the incidents that occur during routine operations. In tradition, such aircraft maintenance schedule adjustment has been performed manually, a process which is neither effective nor efficient, especially when the problem scale is large. In this study, an aircraft maintenance schedule adjustment model is developed, with the objective of minimizing the total system cost, subject to the related operating constraints. The model is formulated as a zero-one integer program and is solved using a mathematical programing solver. The effectiveness of the model is evaluated by application to a case study using data from an aircraft maintenance center in Taiwan. The test results show the proposed model, as well as the scheduling rules abstracted from the results are useful for the decision maker to adjust good maintenance schedules.     

Transit network design based on travel time reliability

This paper presents a transit network optimization method, in which travel time reliability on road is considered. A robust optimization model, taking into account the stochastic travel time, is formulated to satisfy the demand of passengers and provide reliable transit service. The optimization model aims to maximize the efficiency of passenger trips in the optimized transit network. Tabu search algorithm is defined and implemented to solve the problem. Then, transit network optimization method proposed in this paper is tested with two numerical examples: a simple route and a medium-size network. The results show the proposed method can effectively improve the reliability of a transit network and reduce the travel time of passengers in general.     

An optimization model for a real-time flight scheduling problem

Although airlines plan aircraft routes and crew schedules in advance, perturbations occur everyday. As a result, flight schedules may become infeasible and would need to be updated. This Day of Operations Scheduling problem impacts the entire system of an airline as the decisions enforced are final. When perturbations are relatively small, the airline may be able to at least preserve the planned aircraft and crew itineraries. We propose a model that determines new flight schedules based on planned crew transfers, rest periods, passenger connections, and maintenance. Its dual is shown to be a network model, hence solvable in a real-time environment. In addition, it can be used in more sophisticated operational and planning systems.     

Intermodal Transit System Coordination

In urban areas where transit demand is widely spread, passengers may be served by an intermodal transit system, consisting of a rail transit line (or a bus rapid transit route) and a number of feeder routes connecting at different transfer stations. In such a system, passengers may need one or more transfers to complete their journey. Therefore, scheduling vehicles operating in the system with special attention to reduce transfer time can contribute significantly to service quality improvements. Schedule synchronization may significantly reduce transfer delays at transfer stations where various routes interconnect. Since vehicle arrivals are stochastic, slack time allowances in vehicle schedules may be desirable to reduce the probability of missed connections. An objective total cost function, including supplier and user costs, is formulated for optimizing the coordination of a general intermodal transit network. A four-stage procedure is developed for determining the optimal coordination status among routes at every transfer station. Considering stochastic feeder vehicle arrivals at transfer stations, the slack times of coordinated routes are optimized, by balancing the savings from transfer delays and additional cost from slack delays and operating costs. The model thus developed is used to optimize the coordination of an intermodal transit network, while the impact of a range of factors on coordination (e.g., demand, standard deviation of vehicle arrival times, etc) is examined.     

Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: An approximate dynamic programming approach

In a heavily congested metro line, unexpected disturbances often occur to cause the delay of the traveling passengers, infeasibility of the current timetable and reduction of the operational efficiency. Due to the uncertain and dynamic characteristics of passenger demands, the commonly used method to recover from disturbances in practice is to change the timetable and rolling stock manually based on the experiences and professional judgements. In this paper, we develop a stochastic programming model for metro train rescheduling problem in order to jointly reduce the time delay of affected passengers, their total traveling time and operational costs of trains. To capture the complexity of passenger traveling characteristics, the arriving ratio of passengers at each station is modeled as a non-homogeneous poisson distribution, in which the intensity function is treated as time-varying origin-to-destination passenger demand matrices. By considering the number of on-board passengers, the total energy usage is modeled as the difference between the tractive energy consumption and the regenerative energy. Then, we design an approximate dynamic programming based algorithm to solve the proposed model, which can obtain a high-quality solution in a short time. Finally, numerical examples with real-world data sets are implemented to verify the effectiveness and robustness of the proposed approaches.     

A new schedule-based transit assignment model with travel strategies and supply uncertainties

This paper proposes a new scheduled-based transit assignment model. Unlike other schedule-based models in the literature, we consider supply uncertainties and assume that users adopt strategies to travel from their origins to their destinations. We present an analytical formulation to ensure that on-board passengers continuing to the next stop have priority and waiting passengers are loaded on a first-come-first-serve basis. We propose an analytical model that captures the stochastic nature of the transit schedules and in-vehicle travel times due to road conditions, incidents, or adverse weather. We adopt a mean variance approach that can consider the covariance of travel time between links in a space–time graph but still lead to a robust transit network loading procedure when optimal strategies are adopted. The proposed model is formulated as a user equilibrium problem and solved by an MSA-type algorithm. Numerical results are reported to show the effects of supply uncertainties on the travel strategies and departure times of passengers.     

A probabilistic model for vehicle scheduling based on stochastic trip times

Vehicle scheduling plays a profound role in public transit planning. Traditional approaches for the Vehicle Scheduling Problem (VSP) are based on a set of predetermined trips in a given timetable. Each trip contains a departure point/time and an arrival point/time whilst the trip time (i.e. the time duration of a trip) is fixed. Based on fixed durations, the resulting schedule is hard to comply with in practice due to the variability of traffic and driving conditions. To enhance the robustness of the schedule to be compiled, the VSP based on stochastic trip times instead of fixed ones is studied. The trip times follow the probability distributions obtained from the data captured by Automatic Vehicle Locating (AVL) systems. A network flow model featuring the stochastic trips is devised to better represent this problem, meanwhile the compatibility of any pair of trips is redefined based on trip time distributions instead of fixed values as traditionally done. A novel probabilistic model of the VSP is proposed with the objectives of minimizing the total cost and maximizing the on-time performance. Experiments show that the probabilistic model may lead to more robust schedules without increasing fleet size.