Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier

Flight retiming in airline scheduling consists in slightly modifying the scheduled departure time of some flights with the goal of providing a better service with a cheaper cost. In this research, the departure times must be selected from a small discrete set of options. The whole problem embeds flight retiming, fleet assignment, aircraft routing and crew pairing. Thus, the aim is to determine the departure times of the flights, the fleet assignment and the minimum cost aircraft and crew routes. The objective function takes into account a large cost associated with each crew member, a penalization for short or long connection times, a cost for crew members changing aircraft along their routes, and a minor penalty associated with the use of each aircraft. The constraints enforce aircraft maintenance and crew working rules. In this setting, flight retiming is allowed to potentially reduce the total costs and increase the robustness of the solution against delays by decreasing the number of aircraft changes.We propose and compare four heuristic algorithms based on a Mixed Integer Linear Programming model for the whole problem. The model contains path variables representing the crew pairings, and arc variables representing the aircraft routes. In the heuristic algorithms, column generation is applied on the path variables, and different flight retiming options are considered. The algorithms are tested on real-world instances of a regional carrier flying in the Canary Islands to evaluate their advantages and drawbacks. In particular, one of the algorithms, that uses the solution of the Linear Programming relaxation of the model to select promising options for the departure of the flights, turns out to be the most effective one. The obtained results show that costs can be significantly reduced through flight retiming while still keeping the computing times reasonably short. In addition, we perform a sensitivity analysis by including more retiming options and by using different aircraft and crew costs. Finally, we report the results on larger size instances obtained by combining real-world ones.     

GRASP with a New Local Search Scheme for Vehicle Routing Problems with Time Windows

The NP-Hard Vehicle Routing Problem with Time Windows (VRPTW) is one of the major transportation problems. In this paper, a Greedy Randomized Adaptive Search Procedure (GRASP) for VRPTW is discussed for minimizing the fleet size and the travel distance. There are two phases within each GRASP iteration: construction phase and local search phase. In the construction phase, the initial solution is computed by applying an adaptive randomized greedy function. In the local search phase, the search procedure is applied to the constructed initial solution obtained by the construction phase for an improvement. In this paper, we propose an improved solution technique by using new local search ideas and new lower bounding procedures. In addition, we report computational results and address some practical issues in this area.     

Pareto mimic algorithm: An approach to the team orienteering problem

The team orienteering problem is an important variant of the vehicle routing problem. In this paper, a new algorithm, called Pareto mimic algorithm, is proposed to deal with it. This algorithm maintains a population of incumbent solutions which are updated using Pareto dominance. It uses a new operator, called mimic operator, to generate a new solution by imitating an incumbent solution. Furthermore, to improve the quality of a solution, it employs an operator, called swallow operator which attempts to swallow (or insert) an infeasible node and then repair the resulting infeasible solution. A comparative study supports the effectiveness of the proposed algorithm, especially, our algorithm can quickly find new better results for several large-scale instances. We also demonstrate that Pareto mimic algorithm can be generalized to solve other routing problems, e.g., the capacitated vehicle routing problem.     

The simulation of industrial robot systems

This paper describes the GRASP computer aided design system for modelling and evaluating industrial robot workplaces. GRASP satisfies a range of simulation needs within the context of designing, implementing and operating industrial robotic systems. The GRASP software may be used to investigate robots operating by themselves or, more likely, as part of an integrated cell. Facilities within GRASP assist workplace layout, position and velocity evaluations, clash detection and co-ordination between items. A robot library exists and is being extended, and an embryo off-line programming facility has been used under restricted conditions. GRASP has been used to help solve a wide range of practical industrial robot problems and has proved itself technically, and also as an educational tool, by showing how a proposed system would operate. The paper describes the facilities within GRASP.     

Lower Cost Arrivals for Airlines: Optimal Policies for Managing Runway Operations under Optimized Profile Descent

Optimized profile descent (OPD) is an operating procedure being used by airlines to improve fuel and environmental efficiency during arrival operations at airports. In this study, we develop a stochastic dynamic programming framework to manage the sequencing and separation of flights during OPD operations. We find that simple calculation based measures can be used as optimal decision rules, and that the expected annual savings can be around $29 million if such implementations are adapted by major airports in the United States. Of these savings, $24 million are direct savings for airlines due to reduced fuel usage, corresponding to a potential savings of 10%–15% in fuel consumption over current practice. We also find that most of these savings will be due to the optimal spacing of OPD flights, as opposed to the optimal sequencing policies which contribute only 14% to the total savings. Hence, optimal spacing of OPD flights is much more important than optimal sequencing of these flights. We also conclude that there is not much difference between the environmental costs of fuel‐optimal and sustainably‐optimal spacing policies. Hence, an airline‐centric approach in improving OPD operations is likely to be not in conflict with objectives that might be prioritized by other stakeholders.     

An iterated local search with multiple perturbation operators and time varying perturbation strength for the aircraft landing problem

Landing aircraft safely is an important operation that air traffic controllers have to deal with on a daily basis. For each arriving aircraft a runway and a landing time must be allocated. If these allocations can be done in an efficient way, it could give the airport a competitive advantage. The Aircraft Landing Problem (ALP) aims to minimize the deviation from a preferred target time of each aircraft. It is an NP-hard problem, meaning that we may have to resort to heuristic methods as exact methods may not be suitable, especially as the problem size increases. This paper proposes an iterated local search (ILS) algorithm for the ALP. ILS is a single solution based search methodology that successively invokes a local search procedure to find a local optimum solution. A perturbation operator is used to modify the current solution in order to escape from the local optimum and to provide a new solution for the local search procedure. As different problems and/or instances have different characteristics, the success of the ILS is highly dependent on the local search, the perturbation operator(s) and the perturbation strength. To address these issues, we utilize four perturbation operators and a time varying perturbation strength which changes as the algorithm progresses. A variable neighborhood descent algorithm is used as our local search. The proposed ILS generates high quality solutions for the ALP benchmark instances taken from the scientific literature, demonstrating its efficiency in terms of both solution quality and computational time. Moreover, the proposed ILS produces new best results for some instances.     

Multiple phase neighborhood Search—GRASP based on Lagrangean relaxation, random backtracking Lin–Kernighan and path relinking for the TSP

In this paper, a new modified version of Greedy Randomized Adaptive Search Procedure (GRASP), called Multiple Phase Neighborhood Search—GRASP (MPNS-GRASP), is proposed for the solution of the Traveling Salesman Problem. In this method, some procedures have been included to the classical GRASP algorithm in order to improve its performance and to cope with the major disadvantage of GRASP which is that it does not have a stopping criterion that will prevent the algorithm from spending time in iterations that give minor, if any, improvement in the solution. Thus, in MPNS-GRASP a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is proposed. Also, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. A new variant of the Lin-Kernighan algorithm, called Random Backtracking Lin-Kernighan that helps the algorithm to diversify the search in non-promising regions of the search space is used in the Expanding Neighborhood Search phase of the algorithm. Finally, a Path Relinking Strategy is used in order to explore trajectories between elite solutions. The proposed algorithm is tested on numerous benchmark problems from TSPLIB with very satisfactory results.     

基于ASRank和MMAS的蚁群算法求解飞机指派问题

本文将航班串的飞机指派问题归结为车辆路径问题,考虑连续航班串之间衔接时间、衔接机场的约束、每架飞机的总飞行时间约束,建立了带有飞行时间约束的车辆路径问题的混合整数规划模型。构造了蚁群系统算法,引入基于排序的蚂蚁系统和最大最小蚂蚁系统算法的信息素更新策略。选取某航空公司7组初始航班串集合进行测试,并对算法中的重要参数进行了分析。实验结果表明,本文设计的模型和算法可以有效地减少连续航班串之间的总衔接时间,在可接受的计算时间内获得满意解。     

Robust gate assignment procedures from an airport management perspective

The assignment of aircraft arriving out of schedule to available stands at the terminal is a major issue with feasible solutions when stands are placed in the same zone, but it is very difficult to solve when candidate alternative stands are placed in different zones due to passenger movement through the terminal. In order to tackle arrival delays while preserving quality factor services to passengers and protecting turnaround aircraft times, most airports have modified their infrastructure by increasing the number of stands at the terminal. In this paper a simulation-based experimental approach that evaluates the minimum amount of stands at the terminal necessary to cope with arrival/departure pattern traffic under a time delay limit is presented. Emergent dynamics are analyzed when the number of stands is increased and a causal model to evaluate shortages and benefits of different policies and strategies for gate assignment to mitigate undesirable consequences is introduced.     

考虑延误因素的机组排班模型研究

机组排班是航空公司运营计划的重要环节。传统对机组排班问题的研究,通常不考虑延误对排班的影响,导致机组排班的鲁棒性较差。本文在传统机组排班模型的基础上考虑延误成本,以最小化各项任务成本和延误成本为目标,提出了考虑随机延误因素的机组排班数学规划模型。然后提出求解此模型的启发式列生成算法,该算法可有效缩小问题规模,减少求解过程中的迭代次数并提高求解质量。利用航空公司真实飞行数据进行测试,证明算法可在短时间内求解大规模机组排班问题。最后,通过仿真试验证实考虑延误的机组排班模型可有效提升排班的鲁棒性。     

A Heuristic Risk Assessment Technique for Birdstrike Management at Airports

Collisions between birds and aircraft (birdstrikes) have caused the loss of at least 88 aircraft and 243 lives in world civil aviation. Conservative estimates suggest that more routine damage and delays following birdstrikes cost the industry and its insurers US$1.2-1.5 billion per year. The majority of strikes happen close to airports and most countries have regulations that require airport managers to control the birdstrike risk on their property. Birdstrike prevention has, however, lagged behind other aspects of flight safety in the development and implementation of risk assessment protocols, possibly because of the inherent difficulty in quantifying the variability in the populations and behavior of the various bird species involved. This article presents a technique that uses both national and airport-specific data to evaluate risk by creating a simple probability-times-severity matrix. It uses the frequency of strikes reported for different bird species at a given airport over the preceding five years as a measure of strike probability, and the proportion of strikes with each species that result in damage to aircraft, in the national birdstrike database, as a measure of likely severity. Action thresholds for risk levels for particular bird species are then defined, above which the airport should take action to reduce the risk further. The assessment is designed for airports where the reporting and collation of birdstrike events is reasonably consistent over time and where a bird hazard management program of some sort is already in place. This risk assessment is designed to measure risk to the airport as a business rather than risk to the traveling passenger individually. It therefore takes no account of aircraft movement rate in the calculations and is aimed at minimizing the number of damaging incidents rather than concentrating on catastrophic events. Once set up at an airport, the technique is simple to implement for nonexperts, and it allows managers to focus bird control resources on the species causing the greatest risk, hence maximizing the return on investment. This protocol is now being successfully used at major airports in the United Kingdom and elsewhere in the world.     

Minimizing takeoff and landing risk in helicopter pickup and delivery operations

The problem of minimizing total helicopter passenger risk caused by takeoffs and landings is studied. There are passenger pickup and delivery demands to be satisfied at given points by flights starting and ending in the same heliport and visiting several points. For each point, the delivery demand is the number of passengers to be transported from the heliport to this point and the pickup demand is the number of different passengers to be transported from this point to the heliport. Each pickup and delivery demand must be satisfied in full by one flight. There are an upper bound on the number of flights and an upper bound on the helicopter passenger capacity. The objective function is a linear combination of the numbers of passengers involved in takeoffs and landings at visited points. A solution is characterized by the number of flights, sets of visited points and their sequences for all flights. Properties of optimal solutions are established. Several cases are proved NP-hard. A quadratic boolean programming formulation and two dynamic programming algorithms are suggested for the general case. Computer experiments demonstrated that they are able to solve real-life instances. Polynomial time algorithms are presented for special cases. Implementation of the suggested solutions into the real helicopter operations should decrease the number of fatalities.     

Revised GRASP with path-relinking for the linear ordering problem

The linear ordering problem (LOP) is an NP\mathcal{NP}-hard combinatorial optimization problem with a wide range of applications in economics, archaeology, the social sciences, scheduling, and biology. It has, however, drawn little attention compared to other closely related problems such as the quadratic assignment problem and the traveling salesman problem. Due to its computational complexity, it is essential in practice to develop solution approaches to rapidly search for solution of high-quality. In this paper we propose a new algorithm based on a greedy randomized adaptive search procedure (GRASP) to efficiently solve the LOP. The algorithm is integrated with a Path-Relinking (PR) procedure and a new local search scheme. We tested our implementation on the set of 49 real-world instances of input-output tables (LOLIB instances) proposed in Reinelt (Linear ordering library (LOLIB) 2002). In addition, we tested a set of 30 large randomly-generated instances proposed in Mitchell (Computational experience with an interior point cutting plane algorithm, Tech. rep., Mathematical Sciences, Rensellaer Polytechnic Institute, Troy, NY 12180-3590, USA 1997). Most of the LOLIB instances were solved to optimality within 0.87 seconds on average. The average gap for the randomly-generated instances was 0.0173% with an average running time of 21.98 seconds. The results indicate the efficiency and high-quality of the proposed heuristic procedure.     

Approaches to solve the fleet-assignment,aircraft-routing,crew-pairing and crew-rostering problems of a regional carrier

This paper presents the results of a research project funded by a regional carrier operating inter-island services within the Canary Islands (Spain) in addition to services to Morocco and Portugal. It operates between 100 and 150 flights a day using three airline operators. The main scope of the project was to solve fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems on real-world data. The special characteristics of the carrier, flying between 7 am and 11 pm every day, have motivated us to design models and algorithms that are different than the ones addressed in the literature, typically built for large airline companies. This paper shows a solution approach for an integrated fleet-assignment, aircraft-routing and crew-pairing problem covering the flights of a single day. This is a new combinatorial problem that can be considered as a 2-depot vehicle routing problem with driver changes, where the vehicles represent aircrafts and the drivers represent crews. Adapting approaches from the vehicle routing literature, this paper describes a heuristic algorithm based on an integer programming model. In a similar way, this paper also addresses the rostering problem. This problem can be decomposed in smaller problems taking into account operators, bases and crew groups. These problems admit a compact formulation through mixed integer linear programming models which can be tracked by modern general-purpose solvers. This paper illustrates the success of our solution approaches on real-world instances. The airline carrier is currently using these approaches.     

网络效应与多寡头市场技术许可竞争策略研究

考虑一个由一家在位许可企业与多家寡头企业组成的网络产品市场,分析当产品具有网络效应时在位许可企业在固定费许可下最优的许可证数问题,证明在位企业是否进行许可、进行独家还是多家许可受到网络效应强度、市场容量、市场集中度、研发效率的影响。当市场容量较小时,在位企业将垄断;当市场容量足够大时,许可总是最优的--若网络强度较小,无论市场集中度如何,多家许可均优于独家许可;若网络强度适中,对市场上具有研发潜力的企业都进行许可较优;若网络强度很大,在市场集中度较大时,多家许可优于独家许可;若市场集中度较小,则进行独家许可还是多家许可取决于发放许可证数。另外在许可企业不能实行价格歧视时,最优的固定费随着受许企业整体研发效率和许可证数的提高而减小。     

A flexible model for the pricing of perishable assets

We present a flexible and versatile model which addresses the problem of assigning optimal prices to assets whose value becomes zero after a fixed expiry date. (Such assets include the important example of seats on airline flights.) Our model is broad in scope, in particular encompassing the ability to deal with arrivals of customers in groups. It is highly adaptable and can be adjusted to deal with a very extensive set of circumstances.Our approach to the problem is based on elementary and intuitively appealing ideas. We model the arrival of customers (or groups of customers) according to an inhomogeneous Poisson process. We incorporate into the model time dependent price sensitivity (which may also be described as “time dependent elasticity of demand”). In this setting the solution to the asset pricing problem is achieved by setting up coupled systems of differential equations which are readily amenable to numerical solution via (for instance) a vectorised Runge-Kutta procedure. An attractive feature of our approach is that it unifies the treatment of discrete and continuous prices for the assets.     

A review on airport gate assignment problems: Single versus multi objective approaches

Assigning aircraft to gates is an important decision problem that airport professionals face every day. The solution of this problem has raised a significant research effort and many variants of this problem have been studied. In this paper, we review past work with a focus on identifying types of formulations, classifying objectives, and categorising solution methods. The review indicates that there is no standard formulation, that passenger oriented objectives are most common, and that more recent work are multi-objective. In terms of solution methods, heuristic and metaheuristic approaches are dominant which provides an opportunity to develop exact and approximate approaches both for the single and multi-objective problems.     

Scheduling Truck Arrivals at an Air Cargo Terminal

We consider the scheduling of truck arrivals at an air cargo terminal. By coordinating arrivals of cargo delivery trucks with outbound flight departure schedules, some of the shipments can be transferred directly to the departing flights, while others will be stored at the terminal's storage facility and incur extra handling and storage costs. The objective is to obtain a feasible schedule so as to minimize the total cost of operations. We formulate the problem as a time‐indexed integer program and show that, even with limited number of unloading docks at the terminal, the problem is non‐trivial (NP‐hard in the strong sense). Our solution method includes an exact solution procedure to determine an optimal unloading sequence for the shipments carried by each truck, together with a Lagrangian relaxation‐based heuristic for assigning trucks to truck docks and determining truck arrival times. We conducted computational experiments to test the performance of our solution method. Computational results show that our method can generate near‐optimal solutions efficiently. Our simulation results indicate that the scheduling approach proposed in this paper has the potential to generate significant cost savings over a first‐come, first‐served approach currently used at the air cargo terminal that we observed.     

Location optimization of strategic alert sites for homeland defense

This research uses a location analysis approach for selecting aircraft alert sites for the defense of important national areas of interest identified by the US Department of Defense. Solutions are generated in a two step approach where the minimum number of sites is first identified using the location set covering problem and then the result is improved by finding the minimum aggregate network distance or p-median solution from the alternate optimal solutions to the LSCP. This approach also identifies the p-center solution to the problem ensuring equitable response to all areas of interest. Sensitivity analysis is performed to determine the impact of altering aircraft launch and flying times on the number of required alert sites and the amount of coverage provided by selecting fewer locations. Results indicate a significant increase in the number of alert locations needed in comparison to original military estimates. The research points out significant implications about future military base closure decisions and the trade-offs between cost and required response times of aircraft in a defense emergency.     

Cost minimization of large-scale infrastructure for electricity generation and transmission

Electricity infrastructure confronts societies with immense costs as it must ensure the generation of power and its transmission to locations with consumption requirements. We minimize these costs by formulating an electricity generation and transmission problem that facilitates the design of electricity infrastructure on a macro level. Our problem specifies the capacity, type, and location of power plants and, at the same time, determines the appropriate arrangement of high-voltage transmission lines in order to fulfill the demand of individual cities. We specifically incorporate the non-linear nature of cost functions for power generation that are common in practice. This results in a mixed integer non-linear problem, for which the branch-and-reduce solver from GAMS exceeds runtime constraints, even for small instances with 25 locations. As a remedy, we develop heuristics based on the reduced variable neighborhood search and the greedy randomized adaptive search procedure (GRASP). Their performance enables us to address large-scale problems that arise in real-world applications. We demonstrate this with an actual, nationwide example that spans all 4537 municipalities in Germany.