Network design: taxi planning

The effect of managing aircraft movements on the airport’s ground is an important tool that can alleviate the delays of flights, specially in peak hours or congested situations. Although some strategic design decisions regarding aeronautical and safety aspects have a main impact on the airport’s topology, there exists a number of other additional factors that must be evaluated according to the on ground operations, i.e. previous to the taking-off or after landing. Among these factors one can consider capacities at waiting points and directions of some corridors. These factors are related to the demand situation of a given period and influence the aircraft’s routing on the ground or short term Taxi Planning problem (or TP-S). While the TP-S problem studies the aircraft routing and scheduling on the airport’s ground under a dynamic point of view, this paper presents a Taxi Planning network design model (or TPND), attending to these additional factors of the airport’s topology and the conflicting movements of the aircraft on them with the same modelling approach used in the TP-S problem. The TPND model is formulated as a binary multicommodity network flow problem with additional side constraints under a multiobjective approach. The side constraints included are the classical limitations due to capacity and also as a distinctive approach, constraints that restrict the interference of aircraft in order to decrease the intervention of human controllers during the operations or increase their safety margins. The multiobjective approach adopted for the TPND model balances conflicting objectives: airport’s throughput, travel times, safety of operations and costs. In the paper computational results are included on two test airports solving the TPND model by “Branch and Bound” showing the effect of the conflicting objectives in the design decisions. Research supported under Research Project TRA-2005-09068-C03-01/MODAL from the “Ministerio de Educación y Ciencia”.     

A simple expression for the nucleolus in a special case

We present a simple algorithm for calculating the nucleolus of a game whenever (a) the characteristic function is non-positive, ie. a “cost” function, and (b) the players can be ordered by “size” in such a way that the cost of any coalition is equal to the cost of the largest player in that coalition. The cumulative nucleolus is approximately equal to the convex envelope of this cost function. A numerical and geometric illustration is given for a game based upon Birmingham airport runway costs, where there are over 13,000 players (aircraft movements) of 11 distinct (aircraft) types.     

Column generation for vehicle routing problems with multiple synchronization constraints

Synchronization of workers and vehicles plays a major role in many industries such as logistics, healthcare or airport ground handling. In this paper, we focus on operational ground handling planning and model it as an archetype of vehicle routing problems with multiple synchronization constraints, coined as “abstract vehicle routing problem with worker and vehicle synchronization” (AVRPWVS). The AVRPWVS deals with routing workers to ground handling jobs such as unloading baggage or refuelling an aircraft, while meeting each job’s time window. Moreover, each job can be performed by a variable number of workers. As airports span vast distances and due to security regulations, workers use vehicles to travel between locations. Furthermore, each vehicle, moved by a driver, can carry several workers. We propose two mathematical multi-commodity flow formulations based on time-space networks to efficiently model five synchronization types including movement and load synchronization. Moreover, we develop a branch-and-price heuristic that employs both conventional variable branching and a novel variable fixing strategy. We demonstrate that the procedure achieves results close to the optimal solution in short time when compared to the two integer models.     

Some effects of aircraft arrival sequence algorithms

Although various airport landing sequencing algorithms have been considered in the literature, little work has been done in comparing their effects on Air Traffic Control, especially against first-come first-served (FCFS) runway sequences, the method most widely used in practice. This paper compares a number of such algorithms using a discrete-event simulation model of an airport with a single landing runway. Statistical methods are used to test for effects of sequencing algorithm, delay-sharing strategy, arrival rate and wake-vortex mix. Little benefit to delay, or stability of sequencing advice, is found from advanced sequencing when small changes are made to inputs calibrated to a specific airspace. Advanced sequencing improves landing rate, compared with FCFS sequencing, only when aircraft arrival rate is greater than maximum runway landing rate, and wake-vortex mix is sufficiently varied. Constrained position shifting constraints limit these improvements and it is shown that deterministic optimal techniques may actually be sub-optimal in a dynamic environment. Our main conclusion is that FCFS is a robust method under many conditions.     

Demand estimation with failure and capacity constraints: An application to prisons

A stochastic model for projecting demand for a population-driven, input-output facility that incorporates demographic changes, facility returns representing “failures”, and capacity constraints is proposed and demonstrated. The model is applied to the problem of prison population projection. The approach models the flow of inmates through the prison system, exploits the differences in the incarceration hazard rates of individuals in the general population and those who have been incarcerated previously, and explicitly considers the impact of constrained prison capacity on release policy and future admissions. First-time arrivals to prison are modeled as a Poisson process arising from the general population; recidivist arrivals are modeled using a failure model, where the reincarceration hazard rate is a function of age and race. The model is demonstrated for the State of North Carolina. The effect of limited prison capacity on the average time served is shown. Further, the results demonstrate that an early release policy will generate an increase in prison admissions through t'he return to prison of former inmates. The implications for current “get tough” sentencing policy initiatives relative to the prison crowding problem, the length of stay for offenders not included in the new policies, and the recursive effect of these policies on the input-output dynamics are considered. The results suggest the tradeoffs that exist between early release policies and capacity limitations.     

A Simulation Model for Calculating Annual Congestion Delay Arising from Airport Runway Operations

This paper describes a simulation model of delays to aircraft caused by airport runway congestion. It was developed for the Australian Government as part of the Sydney Airport Project. Subsequently, it was used in a traffic management study of the airport which examined the scope of deferring the need for additional runway capacity by adopting administrative measures affecting runway utilization.     

Airport noise modelling and aircraft scheduling so as to minimize community annoyance

A mathematical model of the annoyance created at an airport by aircraft operations is developed. The model incorporates population distribution considerations around an airport and the annoyance caused by aircraft noise. The objective function of this model corresponds to seeking to minimize total population annoyance created by all aircraft operations in a 24-hour period. Several factors are included in this model as constraint relationships. Aircraft operations by type and time period are upper bounded. Demand for flight services is incorporated by including lower bounds on the number of operations by type of aircraft, runway used and time period. Also upper bounds on the number of operations for each runway are included. The mathematical model as formulated is recognized as corresponding to a nonlinear integer mathematical programming problem.The solution technique selected makes use of a successive linear approximation optimization algorithm. An especially attractive feature of this solution algorithm is that it is capable of obtaining solutions to large problems. For example, it would be feasible to attempt the solution of problems involving several thousand variables and over 500 linear constraints. This suggested solution algorithm was implemented on a computer and computational results obtained for example problems.     

A further note on the nucleoous of the “airport game”

This paper represents a generalization of a previous paper on an “airport cost game” to the case of an “airport profit game”. A fee schedule in the airport profit game is obtained by subtracting the payoff vector from the vector of revenues. It is proved that the fee schedule corresponding to the nucleolus is independent of the revenue vector.     

Scheduling aircraft landings at London Heathrow using a population heuristic

With increasing levels of air traffic, making effective use of limited airport capacity is obviously important. This paper reports on an investigation undertaken by National Air Traffic Services in the UK into improving runway utilisation at London Heathrow. This investigation centred on developing an algorithm for improving the scheduling of aircraft waiting to land. The heuristic algorithm developed (a population heuristic) is discussed and results presented using actual operational data relating to aircraft landings at London Heathrow. This data indicates that our algorithm could have improved on air traffic control decisions in such cases by between 2–5?% in terms of reducing the timespan required to land all of the aircraft considered.     

On air traffic flow management with rerouting. Part II: Stochastic case

We present a framework for modeling multistage mixed 0-1 problems for the air traffic flow management problem with rerouting (ATFMRP) under uncertainty in the airport arrival and departure capacity, the air sector capacity and the flight demand. The model allows for flight cancelation, if necessary. It considers several types of objective functions to minimize, namely, total ground and air holding cost, penalization of the alternative routes to the scheduled one for each flight, delay cost for the flights to arrive to the airports and the air sector nodes, and penalization for advancing the arrival of the flights to the airport over the scheduled period. A scenario tree based scheme is used to represent the Deterministic Equivalent Model (DEM) of the stochastic mixed 0-1 program with full recourse. The nonanticipativity constraints that equate the so named common 0-1 and continuous variables from the same group of scenarios in each period are implicitly satisfied in the compact representation of DEM. Some computational experience is reported for medium-scale instances. The model is so tight that none of the instances of the testbed but two of them requires to execute the branch-and-cut phase of the MIP optimization engine of choice.     

Nonparametric Estimation of Hazard Rate Under the Constraint of Monotonicity

This article shows how to smoothly “monotonize” standard kernel estimators of hazard rate, using bootstrap weights. Our method takes a variety of forms, depending on choice of kernel estimator and on the distance function used to define a certain constrained optimization problem. We confine attention to a particularly simple kernel approach and explore a range of distance functions. It is straightforward to reduce “quadratic” inequality constraints to “linear” equality constraints, and so our method may be implemented using little more than conventional Newton–Raphson iteration. Thus, the necessary computational techniques are very familiar to statisticians. We show both numerically and theoretically that monotonicity, in either direction, can generally be imposed on a kernel hazard rate estimator regardless of the monotonicity or otherwise of the true hazard rate. The case of censored data is easily accommodated. Our methods have straightforward extension to the problem of testing for monotonicity of hazard rate, where the distance function plays the role of a test statistic.     

Operational extended model formulations for Advanced Planning and Scheduling systems

Since the basic reasoning of Manufacturing Resources Planning (MRPII) systems is flawed, a new breed of concepts called Advanced Planning and Scheduling systems (APS) have recently emerged to overcome the problems occurring on the shop floor. In this study, we develop improved and extended mixed integer programming formulations for APS systems at the factory planning level. First, we develop a basic model which explicitly considers capacity constraints, operation sequences, processing times, and due dates in a multi-machine, multi-order, multi-item environment where an item can be processed on a given set of eligible machines. The extensions to the basic model include sequence dependent setups, and transfer times between machines. We also show that our model with a little modification could be used to quote delivery times for customer orders in case due dates are not specified. We provide numerical examples and our conclusions along with future research directions.     

A set packing model for the ground holding problem in congested networks

Air traffic flow management (ATFM) consists of several activities performed by control authorities in order to reduce delays due to traffic congestion. Ground holding decisions restrict certain flights from tacking off at the scheduled departure time if congestion is expected at the destination airport. They are motivated by the fact that it is safer to hold an aircraft on the ground than in the air. Several integer linear programming models have been proposed to efficiently solve the ground holding problem (GHP). In this paper we investigate a set packing formulation of the GHP and design a branch-and-cut algorithm to solve the problem in high congestion scenarios, i.e., when lack of capacity induces flights cancellation. The constraint generation is carried out by heuristically solving the separation problem associated with a large class of rank inequalities. This procedure exploits the special structure of the GHP's intersection graphs. The computational results indicate that the proposed algorithm outperforms other algorithms in which flight cancellation has been allowed.     

One-way flow network formation under constraints

We study the effects of institutional constraints on stability and efficiency in the “one-way flow” model of network formation. In this model the information that flows through a link between two players runs only towards the player that initiates and supports the link, so in order for it to flow in both directions, both players must pay whatever the unit cost of a directional link is. We assume that an exogenous “societal cover” consisting of a collection of possibly overlapping subsets covering the set of players specifies the social organization in different groups or “societies,” so that a player may initiate links only with players that belong to at least one society that he/she also belongs to, thus restricting the feasible strategies and networks. In this setting, we examine the impact of such societal constraints on stable/efficient architectures and on dynamics.     

A genetic local search algorithm with a threshold accepting mechanism for solving the runway dependent aircraft landing problem

As the demand for air transportation continues to grow, some flights cannot land at their preferred landing times because the airport is near its runway capacity. Extra fuel consumption and air pollution are then caused by the landing delays. Moreover, such delays may possibly yield extra costs for both passengers and airline companies that result from rescheduling transfer passengers and crew members. Consequently, how to increase the handling efficiency of congested airports is a crucial management issue. Building new runways at existing airports is often not feasible due to environmental, financial and geographical constraints. Therefore, devising a method for tackling the aircraft landing problem (ALP) in order to optimize the usage of existing runways at airports is the focus of this paper. This paper aims to develop a solution procedure based on a genetic local search (GLS) algorithm for solving the ALP with runway dependent attributes. A set of numerical experiments were conducted to test the validity of the proposed algorithm based on five test instances created and investigated by previous studies. The numerical results showed that the proposed GLS algorithm can effectively and efficiently determine the runway allocation, sequence and landing time for arriving aircraft for the five test cases by minimizing total delays under the separation constraints in comparison with the outcomes yielded by previous studies.     

Models for single-sector stochastic air traffic flow management under reduced airspace capacity

Air traffic efficiency is heavily influenced by unanticipated factors that result in capacity reduction. Of these factors, weather is the most significant cause of delays in airport and airspace operations. Considering weather-related uncertainty, air traffic flow management involves controlling air traffic through allocation of available airspace capacity to flights. The corresponding decision process results in a stochastic dynamic problem where aircraft on the ground and in the air are controlled based on the evolution of weather uncertainty. We focus on the single-sector version of the problem that is applicable to a majority of cases where a volume of airspace has reduced capacity due to convective weather. We model the decision process through stochastic integer programming formulations and computationally analyse it for tractability. We then demonstrate through actual flight schedule data that a simplistic but practically implementable approximation procedure is a generally effective solution approach for these models.     

PREDICTING GULL/HUMAN CONFLICTS WITH MATHEMATICAL MODELS: A TOOL FOR MANAGEMENT

Abstract Gulls are highly adaptable animals that thrive in proximity to humans. Although gulls enjoy legal protection in North America, England, and Europe, they often conflict with human interests by spreading disease, transporting contaminants, fouling public areas with droppings, and colliding with aircraft. Of particular concern are aggregates of “loafing” gulls that gather on parking lots, rooftops, and airport runways. Loafing in birds is a general state of immobility that involves behaviors such as sleeping, sitting, standing, resting, preening, and defecating. The ability to predict the incidence of aggregated loafing provides a first step toward the amelioration of bird/human conflicts. We used mathematical models to predict the aggregate loafing behavior of gulls as a function of environmental conditions and tested model portability across years, phase of breeding cycle, loafing location, and species. Because groups of loafing birds quickly reassemble after disturbance, algebraic models for the steady‐state dynamics can be obtained from the differential equations using time‐scale analysis. The accessible management tool requires data collection on an appropriate time scale and information‐theoretic model selection from a suite of alternative algebraic models.     

Towards Washout Filter Concepts for Motion Simulators on the Base of a Stewart Platform

In this paper we present a pneumatically driven Stewart platform as a basis for motion simulators. Motion platforms, that simulate perceived situations in aeroplanes, cars or ships, have workspace constraints in every degree of freedom. Therefore it is necessary to adapt the accelerations and angular rates in order to stay within the physical restrictions. For realizing a flight or ride simulator on the basis of the Stewart platform, “ Washout Filters” are used to change the signals of the open source software FlightGearand to minimize the sensation error between simulator and aircraft. Different filter concepts are implemented and evaluated. The platform presented in this document is a parallel kinematic robot, driven by fluidic muscles. The pneumatically actuated muscles are only able to produce tensile forces. Therefore a spiral spring from a passenger car is used to apply the compressive forces and torques. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Dynamic decentralization of harvesting constraints in the management of tychastic evolution of renewable resources

This study proposes a new framework to tackle the uncertainty that prevails in the exploitation of renewable resources. It deals with the question of how to guarantee both a minimum multi-species harvest and the renewal of resources when their evolutions are uncertain. The problem is twofold: to decentralize a global constraint (on a multi-species harvest) into local constraints (on the resources of the different species) and, then, to use a “tychastic” approach necessitating only the forecasts of the lowers bounds of the resource growth rates. This study, formulated as a “tychastic” regulated system with viability constraints, departs from stochastic approaches generally used to deal with uncertain situations. It provides the time dependent harvesting rule allowing to always comply with a minimum harvest objective and resources replenishment thresholds whatever happens and a tychastic measure of risk viability in terms of minimum resources initially required. To solve this problem involving global and local constraints a new method that decentralizes the constraints has been devised. An example is presented whose numerical results are obtained thanks to a dedicated software using mathematical and algorithmic tools of viability theory.     

Topology of the Italian airport network: A scale-free small-world network with a fractal structure?

In this paper, for the first time we analyze the structure of the Italian Airport Network (IAN) looking at it as a mathematical graph and investigate its topological properties. We find that it has very remarkable features, being like a scale-free network, since both the degree and the “betweenness centrality” distributions follow a typical power-law known in literature as a Double Pareto Law. From a careful analysis of the data, the Italian Airport Network turns out to have a self-similar structure. In short, it is characterized by a fractal nature, whose typical dimensions can be easily determined from the values of the power-law scaling exponents.Moreover, we show that, according to the period examined, these distributions exhibit a number of interesting features, such as the existence of some “hubs”, i.e. in the graph theory’s jargon, nodes with a very large number of links, and others most probably associated with geographical constraints.Also, we find that the IAN can be classified as a small-world network because the average distance between reachable pairs of airports grows at most as the logarithm of the number of airports. The IAN does not show evidence of “communities” and this result could be the underlying reason behind the smallness of the value of the clustering coefficient, which is related to the probability that two nearest neighbors of a randomly chosen airport are connected.