Scatter Search and Bionomic Algorithms for the aircraft landing problem

The problem of deciding how to land aircraft approaching an airport involves assigning each aircraft to an appropriate runway, computing a landing sequence for each runway and scheduling the landing time for each aircraft. Runway allocation, sequencing and scheduling for each aircraft must ensure the scheduled landing time lies within a predefined time window and meet separation time requirements with other aircraft. The objective is to achieve effective runway use.In this paper, the multiple runway case of the static Aircraft Landing Problem is considered. Two heuristic techniques are presented: Scatter Search and the Bionomic Algorithm, population heuristic approaches that have not been applied to this problem before.Computational results are presented for publicly available test problems involving up to 500 aircraft and five runways showing that feasible solutions of good quality can be produced relatively quickly.     

Estimating returns to scale of Chinese airport airside activities using the CCR-0-objective RTS method

The returns to scale (RTS) nature of 41 Chinese airport airsides is investigated in this paper. We introduce take-off distance available and landing distance available into RTS estimation. To deal with the existence of multiple optimal solutions when estimating RTS using the CCR (Charnes, Cooper and Rhodes) RTS method in Data Envelopment Analysis, we introduce the CCR-0-objective RTS method. The empirical study shows that all those airsides with two runway operate under decreasing RTS. Those airsides with only one runway either show constant RTS or show increasing RTS.     

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.     

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.     

Delays to Aircraft Serviced by the Glide-Path

This paper considers some of the statistical service, flow and delay problems which arriving aircraft encounter in the glide-path of an airport runway. Mathematical expressions for service time distributions and delays are formulated in terms of the probability distributions of spacings between discharges of the glide-path. In this paper the author also considers some numerical solutions of the average glide-path separation as a function of \(\overline{w}\), the average delay to arriving aircraft, x₀, a minimum glide-path separation and λ the average Poisson flow rate of landing aircraft.     

Aircraft wake vortices – prediction and mitigation

The current abstract presents selected topics investigated within the wake-vortex research program of DLR. Two approaches are addressed that both aim at increasing airport capacity without compromising safety. One approach is to directly alleviate wake vortex strength and stability by constructive measures at the aircraft wings. The other approach utilizes the dominant influence of meteorological parameters like turbulence, wind shear, and temperature stratification on wake vortex fate. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Airport runway scheduling

Airport runway optimization is an ongoing challenge for air traffic controllers. Since demand for air-transportation is predicted to increase, there is a need to realize additional take-off and landing slots through better runway scheduling. In this paper, we review the techniques and tools of operational research and management science that are used for scheduling aircraft landings and take-offs. The main solution techniques include dynamic programming, branch and bound, heuristics and meta-heuristics.     

Airport runway scheduling

Airport runway optimization is an ongoing challenge for air traffic controllers. Since demand for air-transportation is predicted to increase, there is a need to realize additional take-off and landing slots through better runway scheduling. In this paper, we review the techniques and tools of operational research and management science that are used for scheduling aircraft landings and take-offs. The main solution techniques include dynamic programming, branch and bound, heuristics and meta-heuristics.     

The FCFS service discipline: Stable network topologies, bounds on traffic burstiness and delay, and control by regulators

We consider the well-known First Come First Serve (FCFS) scheduling policy under bursty arrivals. This policy is commonly used in scheduling communication networks and manufacturing systems. Recently it has been shown that the FCFS policy can be unstable for some nonacyclic network topologies.We identify some network topologies under which FCFS is stable for all arrival and service rate vectors within the system's capacity. This is done by determining a sharp bound on the burstiness of traffic exiting from a tandem section of the system, in terms of the burstiness of the incoming traffic. This burstiness bound further allows us to provide a bound on the maximum number of parts in the system, and the maximum delay. It also enables us to analyze the performance of some systems controlled by the use of traffic smoothing regulators. The maximum delay can remain bounded even in the heavy traffic limit, when all stations are 100% utilized.     

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.     

Developments in operational research: R.W. Eglese and G.K. Rand (eds.) Pergamon, Oxford, 1984, vii + 110 pages, $20.00

A practical method of calculating the distribution of the number of customers in the single server queueing system with inhomogeneous arrival rate and discrete service time distribution is proposed. The system is formulated as an inhomogeneous Markov chain in discrete time, leading to recurrence relations for the state probabilities. The recurrence relations are then solved numerically. Various measures of performance, such as mean and variance of the number of customers in the system and virtual waiting time can be obtained from these results. Examples are presented to demonstrate the scope of the method, including time-dependent behaviour of homogeneous queues; cyclic behaviour of queues with cyclic arrival rates; and a previously published study of an airport runway in which the author had to resort to crude interpolation to obtain results. The method can be further extended to provide a reasonably accurate approximation for some systems with continuous distributions of service times.     

基于优先级的进离港航班排序优化问题研究

研究机场终端区进离港航班排序优化问题,对于提高跑道利用率以及降低航班延误损失具有重要意义。本文首先考虑航班运行方式(降落和起飞)、飞机类型以及航班的重要程度(航程是否连续)的不同所造成延误损失的不同,设计三维优先级表反映调度优先等级,并将其转化为延误成本系数。其次,为实现调度的公平性和减轻管制人员的工作负荷,设置允许延误的航班架次约束、邻边约束以及最大限制位置约束。再次,以最小化航班总延误成本为目标建立模型,提出相应的改进蚁群算法(GJAC)进行求解。最后通过数值实验验证所提算法在考虑调度优先等级及上述约束条件的同时能有效减少进离港航班队列的总延误成本。     

Airport ground workforce planning with hierarchical skills: a new formulation and branch-and-price approach

Annals of Operations Research - We address the problem of strategic workforce planning for airport ground staff. The goal is to find a minimum workforce mix that satisfies a target coverage rate...     

Asymptotic analysis for closed multichain queueing networks with bottlenecks

We consider a two-chain exponential queueing network with a large number of customers that consists of one infinite-server (IS) station and two processor-sharing (PS) or FCFS single-server stations. The asymptotic behavior of the partition function is studied for such a network when one or both PS (FCFS) nodes are heavily loaded. The results are derived using methods of multidimensional complex analysis (the theory of homologies and residues) and the saddle-point method.     

有等待席位限制的基于终端区系统运行效能的枢纽机场最优跑道设计算法

根据枢纽机场实际终端区系统瓶颈和航空公司及旅客的关键需求,利用随机服务系统理论,分析了有等待席位限制的枢纽机场终端区的空域结构、飞行、管制状况,建立其运行模型,能根据相关参数计算航班滞留时间、队长和空闲跑道数等有用指标;再进一步应用系统运行效能理论,成功地建立了枢纽机场的最佳跑道设计算法,算法对枢纽机场跑道建设规划有较大的理论意义和参考应用价值,实践中已经得到应用.     

Scheduling of Jobs in a Hypercube Processing System

When a job is processed in a hypercube multi-processor, it is allocated a cube of processing elements of the requisite size. There are three distinct costs involved in the hypercube scheduling problem: the cost of detecting a free cube (allocation), the cost of migrating jobs and merging the free spaces to accommodate a larger cube request (relocation) and the cost of not meeting the due date (tardiness). Traditionally, research in this area has focused on finding efficient algorithms for allocating a free cube (if any) in the hypercube system. The relocation cost has been treated as an independent cost metric. The role of scheduling has not received much attention and present subcube allocation methods assume a first-come-first-serve (FCFS) approach over the input job set.This paper considers the underlying scheduling issues in a hypercube processing system and shows how techniques other than FCFS scheduling of the incoming jobs can help in reducing the relocation cost and hence the overall subcube resource assignment cost. We discuss five simple and easily implementable dispatching heuristics, and compare their relative performance with the FCFS scheduling rule to demonstrate the advantages of scheduling in subcube allocation.     

Displacement problem and dynamically scheduling aircraft landings

In this paper we define a generic decision problem — the displacement problem. The displacement problem arises when we have to make a sequence of decisions and each new decision that must be made has an explicit link back to the previous decision that was made. This link is quantified by means of the displacement function. One situation where the displacement problem arises is that of dynamically scheduling aircraft landings at an airport. Here decisions about the landing times for aircraft (and the runways they land on) must be taken in a dynamic fashion as time passes and the operational environment changes. We illustrate the application of the displacement problem to the dynamic aircraft landing problem. Computational results are presented for a number of publicly available test problems involving up to 500 aircraft and five runways.     

Highway toll pricing

For a tolled highway where consecutive segments allow vehicles to enter and exit unrestrictedly, we propose a simple toll pricing method. It is shown that the method is the unique method satisfying the classical axioms of Additivity and Dummy in the cost sharing literature, and the axioms of Toll Upper Bound for Local Traffic and Routing-proofness. We also show that the toll pricing method is the only method satisfying Routing-proofness Axiom and Cost Recovery Axiom. The main axiom in the characterizations is Routing-proofness which says that no vehicle can reduce its toll charges by exiting and re-entering intermediately. In the special case when there is only one unit of traffic (vehicle) for each (feasible) pair of entrance and exit, we show that our toll pricing method is the Shapley value of an associated game to the problem. In the case when there is one unit of traffic entering at each entrance but they all exit at the last exit, our toll pricing method coincides with the well-known airport landing fee solution-the Sequential Equal Contribution rule of Littlechild and Owen (1973).     

On the waiting time of arriving aircrafts and the capacity of airports with one or two runways

In this paper we examine a model for the landing procedure of aircrafts at an airport. The characteristic feature here is that due to air turbulence the safety distance between two landing aircrafts depends on the types of these two machines. Hence, an efficient routing of the aircraft to two runways may reduce their waiting time.     

Algorithms for Toyota's goal of sequencing mixed models on an assembly line with multiple workstations

Toyota's goal of sequencing mixed models on an assembly line is to keep the constant usage rate of every part used in the assembly line. This paper deals with Toyota's goal of sequencing mixed models on an assembly line with multiple workstations. A sequencing problem with Toyota's goal is formulated. Two algorithms based on different mechanisms, respectively modified goal chasing and simulated annealing, are developed for solving the sequencing problem. A number of numerical experiments are carried out for evaluating the efficiency of the algorithms. Computational results show that one of the algorithms generates good sub-optimal solutions with very short CPU times, while the other can reach optimal solutions with longer, but acceptable, CPU times.