A dynamic approach for aircraft assignment and maintenance scheduling by airlines

The problems of assigning planes to flights and of fleet maintenance operations scheduling are considered in this paper. While recent approaches make use of artificial intelligence techniques running on main frame computers to solve combinatorial optimization problems for nominal operations, a dynamic approach is proposed here to face on-line operation conditions. The proposed solution mixes a Dynamic Programming approach (to cope with the fleet assignment problem) and a heuristic technique (to solve the embedded maintenance schedule problem). When applied to a medium charter airline, this approach shows acceptability characteristics for operational staffs, while providing efficient solutions. The proposed solution scheme can be considered as the basis for the development of an on-line decision support system for fleet operations management within airlines.     

Integrated recovery of aircraft and passengers after airline operation disruption based on a GRASP algorithm

This paper considers the integrated recovery of both aircraft routing and passengers. A mathematical model is proposed based on both the flight connection network and the passenger reassignment relationship. A heuristic based on a GRASP algorithm is adopted to solve the problem. A passenger reassignment solution is demonstrated to be optimal in each iteration for a special case. The effectiveness of the heuristic is illustrated through experiments based on synthetic and real-world datasets. It is shown that the integrated recovery of flights and passengers can decrease both the recovery cost and the number of disrupted passengers.     

Aircraft line maintenance scheduling and optimisation

With the advent of new technologies and more modern aircraft, many of the maintenance jobs traditionally scheduled for periodic block checks can now be performed in the ‘‘line maintenance” environment, i.e., during layovers between scheduled flights of an aircraft. This flexibility can be exploited to reduce maintenance costs and improve fleet utilisation of an airline. In this paper we introduce and study the Line Maintenance Scheduling Problem (LMSP). The LMSP assigns jobs to available maintenance opportunities, defined by aircraft routes, and sets the starting time for each job. Its objective is to minimise the deviation from this schedule with respect to given due dates for each task, without exceeding resource capacity at the airports at any moment. We formulate the LMSP as a mixed integer programming problem, and describe and compare two solution approaches for this problem: an integrated exact solution algorithm, which solves job assignment and timetabling simultaneously, and a sequential, heuristic approach. We tested our algorithms on a set of instances inspired on data provided by an industry partner. Our experiments show the applicability of both approaches on realistic settings: the exact approach was able to find the optimal solution for all instances, in less than 10 min on average. Our analysis also shows with an example that line maintenance can be more efficient when capacity is spatially spread, even if the total capacity is reduced.     

A robust optimization approach to the integrated berth allocation and quay crane assignment problem

This paper investigates the integrated berth allocation and quay crane assignment problem in container terminals. A deterministic model is formulated by considering the setup time of quay cranes. However, data uncertainties widely exist, and it may cause the deterministic solution to be infeasible. To handle the uncertainties, a robust optimization model is established. Furthermore, to control the level of conservativeness, another robust optimization model with the price constraints is proposed. A genetic algorithm and an insertion heuristic algorithm are suggested to obtain near optimal solutions. Computational experiments indicate that the presented models and algorithms are effective to solve the problems.     

A novel heuristic approach for solving aircraft landing problem with single runway

Nowadays, airlines administrations are more willing to utilize optimization tools to control air traffic due to considerable increases in volume of air transports. A challenging problem in the field of air traffic is how to optimally schedule landing time of aircrafts and assign them to different runways such that early and late landing costs are minimized. This problem is called aircraft landing problem (ALP). This paper proposes a novel decomposition based heuristic by solving two sub-problems for the ALP with single runway. In the first sub-problem, we apply the adaptive large neighborhood search (ALNS) algorithm to find a sequence of aircrafts. The solution found in the first sub-problem will be sent to the second sub-problem, to check for the feasibility of the solution using CPLEX solver. A set of benchmark problem are taken from the OR library for the purpose of comparison with other existing approaches. The computational results exhibit that the proposed algorithm is capable of finding the best known optimal solution for all the instances.     

Airline ground operations: Optimal schedule recovery with uncertain arrival times

Airline operations are subject to a number of stochastic influences which result into variable ground and block times for same flights on different days. Our research explores how airline operations control centers may benefit from an integrated decision support system for schedule recovery during aircraft ground operations. In this paper, we study the sensitivity of an optimal set of schedule recovery options towards uncertain arrival times. The calculation of recovery options is based upon an integrated and iterative scheduling and optimization algorithm, which incorporates uncertainties for arrival flights as a function of a given look-ahead time. Potential recovery options include stand re-allocation, quick-turnaround, quick passenger transfer, waiting for transfer passengers, cancellation of passenger or crew connections, and arrival prioritization. Within a case study setting at Frankfurt Airport, 20 aircraft turnarounds are analysed during a morning peak with their respective estimated arrival times (including potential arrival delays). The analysis of simulation results reveals an almost identical set of selected recovery options under high uncertainty circumstances and from post-operational point-of-view, which indicates high solution stability.     

From passenger growth to aircraft movements

Airlines are able to deal with passenger growth by either increasing the frequency or the aircraft size, which may entail different numbers of aircraft movements. Forecasting the latter is necessary for evaluating technologies, approaching future emissions or anticipating capacity constraints. Purpose of this paper is to forecast a typical fleet mix and the growth of aircraft movements on flight segments worldwide based on an assumed passenger growth. The methodology is implemented in a model called Forecast of Aircraft Movements. Basic approach is the assignment of each flight segment worldwide to a distance, passenger number and aircraft category. For each combination of distance and passenger numbers a typical fleet mix is defined. The forecasted worldwide growth of passenger demand and the empirically determined fleet mix is applied to all segments in order to derive a future scenario. Assuming a certain seat load factor, the frequency growth can be deduced from the aircraft movements generated for all segments. The paper includes a forecast for aircraft movements in a future scenario based on real schedule and passenger data and gives a detailed overview of the methodology and results considering airlines' behaviour.     

An effective genetic algorithm for the fleet size and mix vehicle routing problems

This paper studies the fleet size and mix vehicle routing problem (FSMVRP), in which the fleet is heterogeneous and its composition to be determined. We design and implement a genetic algorithm (GA) based heuristic. On a set of twenty benchmark problems it reaches the best-known solution 14 times and finds one new best solution. It also provides a competitive performance in terms of average solution.     

An adaptive memory programming metaheuristic for the heterogeneous fixed fleet vehicle routing problem

This paper studies the heterogeneous fixed fleet vehicle routing problem (HFFVRP), in which the fleet is composed of a fixed number of vehicles with different capacities, fixed costs, and variable costs. Given the fleet composition, the HFFVRP is to determine a vehicle scheduling strategy with the objective of minimizing the total transportation cost. We propose a multistart adaptive memory programming (MAMP) and path relinking algorithm to solve this problem. Through the search memory, MAMP at each iteration constructs multiple provisional solutions, which are further improved by a modified tabu search. As an intensification strategy, path relinking is integrated to enhance the performance of MAMP. We conduct a series of experiments to evaluate and demonstrate the effectiveness of the proposed algorithm.     

Three-stage airline fleet planning model

One of the main factors affecting airline success is bringing supply and demand as closely together as possible. In order to achieve this goal, an airline needs to adopt an appropriate methodological approach for the fleet planning process. Selection of an aircraft for operating a defined route network is a key element which has a direct impact on the increase of an airline's profitability and on the reduction of an airline's costs. The objective of this paper is to develop a robust model for fleet planning that deals with both fleet size and fleet composition problems for airlines operating on short haul and medium haul routes. The three-stage model for fleet planning involves approximate fleet composition, fleet sizing and aircraft type selection based on fuzzy logic, heuristic and analytic approaches, and multi-criteria decision making, respectively. This model is exemplified with a hypothetical airline based at Belgrade Airport.     

The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion

The green vehicle routing and scheduling problem (GVRSP) aims to minimize green-house gas emissions in logistics systems through better planning of deliveries/pickups made by a fleet of vehicles. We define a new mixed integer liner programming (MIP) model which considers heterogeneous vehicles, time-varying traffic congestion, customer/vehicle time window constraints, the impact of vehicle loads on emissions, and vehicle capacity/range constraints in the GVRSP. The proposed model allows vehicles to stop on arcs, which is shown to reduce emissions up to additional 8% on simulated data. A hybrid algorithm of MIP and iterated neighborhood search is proposed to solve the problem.     

Accounting for population exposure to vehicle-generated pollutants and environmental equity in the toll design problem

The emissions generated by motor vehicles remain a major source of air pollutants that affect public health and contribute to anthropogenic climate change. These negative externalities can be reduced, in part, with the implementation of environmentally oriented road pricing schemes, which can be designed using optimization-based approaches. In this paper, a toll design problem is proposed for determining toll locations and levels that minimize the expected human exposure to air pollutants and the related environmental inequalities, subject to constraints on pollutant concentration levels and implementation costs. The practical use of the proposed problem is hindered in most real-world applications by the computational costs associated with the evaluation of candidate solutions, as is common for network design problems. Furthermore, the problem cannot be expressed analytically given the multiple types of models (e.g., traffic assignment, emissions, air dispersion models) that would be required to evaluate a single design alternative. For these reasons, a derivative-free surrogate-based solution algorithm is proposed for mixed integer problems like the ones considered here. Numerical examples are used to illustrate possible applications of the proposed model and to test the performance of the surrogate-based algorithm. Relative to a joint simulated annealing-genetic algorithm heuristic and a genetic algorithm-based approach, the proposed algorithm found better solutions in fewer function evaluations.     

Aircraft routing under different business processes

Given a set of scheduled flights that must be operated by the same aircraft type, the aircraft routing problem consists of building anonymous aircraft routes that respect maintenance requirements and cover each flight exactly once. This paper looks at the nature of the problem and introduces a classification according to three business processes that are used to assign the anonymous routes to the specific aircraft tail numbers. Furthermore, we compare the aircraft routing problem variants resulting from these three processes with regard to their adaptability to different contexts, the difficulty of solving them, the cost of the computed solutions, and the robustness of these solutions.     

Grounded aircraft: An airfield operations perspective of the challenges of resuming flights post COVID

The global COVID pandemic, national lockdowns and unprecedented decline in passenger demand worldwide has led to airlines cancelling services, furloughing staff, applying for financial support and placing aircraft into temporary storage. However, with finite space available, and up to two-thirds of the world's total passenger fleet grounded for an indeterminate period of time, airlines have been forced to park their aircraft in unusual places, sometimes at airports they do not normally serve and in volumes never normally experienced. The aim of this paper is to investigate the extent of grounded aircraft at UK airports and explore the challenges, from an airfield operations perspective, of resuming flights post-COVID.     

Runway capacity management – An empirical study with application to Doha International Airport

This paper examines a three-faceted approach for runway capacity management, based on the runway configuration, a chosen scheduling approach, and an aircraft separation standard. These factors prompt alternative runway settings that are encapsulated using a classical mixed-integer formulation. The optimal solution for each runway setting is compared against our proposed optimization-based heuristic. This integrated approach is applied to investigating the transition from the (Old) Doha International Airport to the New Doha International Airport. Our empirical study based on historical data reveals that the proposed heuristic consistently yields optimal or near-optimal schedules, with considerable savings in fuel cost and reductions in delays, while preserving the spirit of an FCFS sequencing policy.     

Dynamic management of aircraft stand allocation

This paper aimed to present an original approach for solving the aircraft stand allocation (SA) problem dynamically when due to operational disturbances, the planned allocation cannot be accomplished. The proposed Multiple-criteria Dynamic Stand Allocation (MDSA) method uses fuzzy logic to support decision-making under uncertainty. The MDSA method provides effective solutions in a short time, necessary for traffic management in case of delays, emergency, and untypical cases. It considers partially conflicting points of view of different airport users (airport managers, air traffic controllers, airlines, handling agents, and passengers) and may significantly support managers on the SA problem. The approach proposed can also be used for creating an initial SA plan for a considerable number of aircraft.     

The simultaneous berth and quay crane allocation problem

This paper addresses efficient berth and crane allocation scheduling at a multi-user container terminal. First, we introduce a formulation for the simultaneous berth and crane allocation problem. Next, by employing genetic algorithm we develop a heuristic to find an approximate solution for the problem. The fitness value of a chromosome is obtained by crane transfer scheduling across berths, which is determined by a maximum flow problem-based algorithm based on a berth allocation problem solution defined by the chromosome. The results of numerical experiments show that the proposed heuristic is applicable to solve this difficult but essential terminal operation problem.     

A matheuristic approach to the air-cargo recovery problem under demand disruption

Air cargo transport is subject to unpredictable changes in expected demand, necessitating adjustments to itinerary planning to recover from such disruptions. We study a flight rescheduling problem to react to cargo demand disruptions in the short run. To increase flexibility, we consider two different cargo assignment policies. We propose a matheuristic approach to solve the problem that provides high-quality solutions in a short computational time, based on column generation in which each subproblem is solved using an ad-hoc heuristic. The approach is tested on demand disruption instances containing up to 75 air cargo orders with different penalty levels. The results show that the proposed method improves profit by 54% over the solution generated by a commercial MIP solver within a 1-h time limit, and by 15% over the solution with the routes fixed as in the original flight planning that only allows cargo to be re-routed. We also show that there exist incremental benefits in the range of 3–5% by allowing cargo for a given order to be transported by various aircraft.     

Stochastic optimization models for the airport gate assignment problem

Uncertainties inherent in the airport traffic may lead to the unavailability of gates for accommodating scheduled flights. Incorporating random disruptions is crucial in constructing effective flight-gate assignments. We consider the gate assignment problem under uncertainty in flight arrival and departure times and develop stochastic programming models incorporating robustness measures based on the number of conflicting flights, idle and buffer times. The proposed models are formulated as large-scale mixed-integer programming problems and tabu search algorithms are implemented to obtain assignments of reasonable quality. We conduct a computational study to analyze the proposed alternate models and show the effectiveness of the solution methods.     

A rolling planning horizon heuristic for scheduling agents with different qualifications

This paper presents an optimization model for the tour scheduling problem for agents with multiple skills and flexible contracts in check-in counters at airports. The objective is to minimize the total assignment costs subject to demand fulfillment and labor regulations. In order to solve this problem we develop a rolling planning horizon-based heuristic. Our heuristic is robust and provides near-optimal schedules within reasonable computation time for real-world cases, although the parameter selection is important to its performance. In addition, we discuss the impact of the skill distribution on the scheduling costs for several instances.