Stochastic Modelling Of Aircraft Queues: A Review

1y ago
7 Views
0 Downloads
673.93 KB
23 Pages
Last View : 27d ago
Last Download : n/a
Upload by : Dani Mulvey
Transcription

Stochastic Processes and their ApplicationOR60 Annual Conference - Keynote Papers and Extended AbstractsLancaster University. Lancaster. 11 - 13 September 2018Stochastic Modelling of Aircraft Queues: A ReviewRob Shone, Kevin Glazebrook, Konstantinos ZografosLancaster University, Department of Management Science, Lancaster, United Kingdomr.shone@lancaster.ac.uk, k.glazebrook@lancaster.ac.uk, k.zografos@lancaster.ac.ukAbstractIn this paper we consider the modelling and optimal control of queues of aircraft waiting to usethe runway(s) at airports, and present a review of the related literature. We discuss theformulation of aircraft queues as nonstationary queueing systems and examine the commonassumptions made in the literature regarding the random distributions for inter-arrival andservice times. These depend on various operational factors, including the expected level ofprecision in meeting pre-scheduled operation times and the inherent uncertainty in airportcapacity due to weather and wind variations. We also discuss strategic and tactical methods formanaging congestion at airports, including the use of slot controls, ground holding programs,runway configuration changes and aircraft sequencing policies.Keywords: Aviation; Queueing systems; Stochastic modelling1. IntroductionMany of the busiest airports around the world experience very high levels of traffic congestionfor lengthy periods of time during their daily operations. This is due to a rapid growth indemand for air transport services, combined with physical and political constraints whichusually prevent the expansion of airport infrastructure in the short-term. Congestion increasesthe likelihood of flights being delayed, and these delays may propagate throughout an airportnetwork, with serious financial consequences for airlines, passengers and other stakeholders(Pyrgiotis et al, 2013). As airport slot coordinators and traffic controllers strive to improve theefficiency of their operations, there is considerable scope for new and innovative mathematicalmodelling techniques to offer valuable insight.The capacity of the runway system represents the main bottleneck of operations at a busy airport(de Neufville and Odoni, 2013). When demand exceeds capacity, queues of aircraft form eitherin the sky (in the case of arriving aircraft) or on the ground (in the case of departures). Thepurpose of this paper is to present a concise review of the methods used by researchers to modelaircraft queues since research in this area began in earnest about 60 years ago. Aviation ingeneral is currently a very active research area, and our review will touch upon some of thewider topics that are closely related to aircraft queue modelling, including demand managementstrategies and the potential of strategic and tactical interventions to improve the utilisation ofscarce resources at airports. Thus, we intend to discuss aircraft queues not only from amathematical modelling perspective, but also in the context of the optimisation problemsfrequently posed in the literature.61

Stochastic Processes and their ApplicationShone, Glazebrook and ZografosOf course, queueing theory itself is also a vast topic and there is no common agreement onwhich of the classical models (if any) are most appropriate in the context of air traffic. Classicalqueueing theory texts such as Kleinrock (1975) tend to focus on models which aremathematically tractable, such as those with Markovian distributions for customer inter-arrivaltimes and/or service times. Generally, closed-form “steady-state” expressions for expectedqueue lengths, waiting times and other performance measures are available only in cases wherethe parameters of these distributions are stationary and customer arrival rates do not exceedservice rates. However, demand for runway use at a typical airport varies considerably duringthe day according to the schedule of operations, and runway throughput rates may be affectedby weather conditions, sequencing rules and other factors. Moreover, demand rates may exceedcapacity limits for extended periods of time at busy hub airports (Barnhart et al, 2003). Wetherefore need to consider time-dependent queues, for which steady-state results are of limitedpractical use (Schwarz et al, 2016).In general, two of the most important characteristics of a queueing system are the customerarrival and customer service processes. We therefore organise this paper in such a way thatthese processes are discussed in Sections 2 and 3 respectively. Other, more application-specificaspects of modelling air traffic queues, including the effects of weather conditions andapproaches for modelling airport networks, are discussed in Section 4. In Section 5 we providea summary and discuss possible directions for future research.2. Modelling demand for runway usage at airportsThis section is divided into two parts. The first part focuses on the modelling assumptions oftenmade regarding demand processes at airports, and the second part discusses related optimisationproblems which frequently attract attention in the literature.2.1. Modelling assumptionsThroughout this section we are concerned with the processes by which aircraft join queueswaiting to use the runway(s) at airports. In the case of departing aircraft, these queues arelocated on the ground, usually at the threshold of the departure runway(s). Arriving aircraft, onthe other hand, must wait in airborne “holding stacks” which are usually located near theterminal airspace, although in some cases they may also be “held” at other stages of theirjourneys by air traffic controllers (to control the flow of traffic into a congested air sector, forexample). In many cases, a plane which lands at an airport will take off again (not necessarilyfrom the same runway) within a couple of hours. This implies that the demand processes forarrivals and departures are not independent of each other, but in fact it is quite common inexisting mathematical models for arrivals and departures to be treated as independent queueswith time-varying demand rates which are configured according to the schedule of operations.The assumption of independence is undoubtedly an oversimplification, but it may not beparticularly harmful if one considers a large airport with separate runways being used forarrivals and departures (this system is referred to as “segregated operations” and is used atLondon Heathrow, for example).62

Stochastic Processes and their ApplicationShone, Glazebrook and ZografosNonhomogenous Poisson processes (i.e. those with time-varying demand rates) were first usedby Galliher and Wheeler (1958) to model the arrivals of landing aircraft at an airport. Theyused a discrete-time approach to compute probability distributions for queue lengths andwaiting times. Subsequently, the Poisson assumption became very popular. Koopman (1972)considered the case of arrivals and departures sharing a single runway and modelled the Poissonarrival rates for both operation types as not only time-dependent but also state-dependent, withthe two-dimensional state consisting of the queue lengths for arrivals and departures. Thismodel allows for the possibility of “controlled” demand rates, whereby the demand placed onthe system is reduced during peak congestion hours.Hengsbach and Odoni (1975) extended Koopman’s approach to the case of multiple-runwayairports, and claimed that the nonhomogeneous Poisson model was consistent with observeddata from several major airports. Subsequently, Dunlay and Horonjeff (1976) and Willemainet al (2004) used case studies to provide further evidence in support of the Poisson assumption.In the last few decades, nonhomogeneous Poisson processes have been widely adopted forqueues of arrivals and departures at single airports (Kivestu, 1976; Bookbinder, 1986; Jung andLee, 1989; Daniel, 1995; Hebert and Dietz, 1997; Fan, 2003; Mukherjee et al, 2005; Lovell etal, 2007; Stolletz, 2008; Jacquillat and Odoni, 2015a; Jacquillat et al, 2017) and also atnetworks of airports (Malone, 1995; Long et al, 1999; Long and Hasan, 2009; Pyrgiotis et al,2013; Pyrgiotis and Odoni, 2016).In case studies which rely on the nonhomogeneous Poisson model, the question arises as to howthe demand rate functions for arrivals and departures – which we will denote here by 𝜆𝑎 (𝑡) and𝜆𝑑 (𝑡) respectively – should be estimated. The schedule of operations for a single day at anairport can be used to aggregate the numbers of arrivals and departures expected to take placein contiguous time intervals of fixed length – for example, 15 minutes or one hour. Theapproach of Hengsbach and Odoni (1976) was to model 𝜆𝑎 (𝑡) and 𝜆𝑑 (𝑡) as piecewise linearfunctions, obtained by aggregating scheduled operations over each hour and then connectingthe half-hour points using line segments, as shown in Figure 1. Various alternative data-drivenmethods can be devised. Jacquillat et al (2017) modelled 𝜆𝑎 (𝑡) and 𝜆𝑑 (𝑡) as piecewise constantover 15-minute intervals, while Bookbinder (1986) used hourly data but relied on a three-pointmoving average method to remove “jump discontinuities” in the demand rates which wouldotherwise occur at the end of each hour.Of course, airlines operate flights according to pre-defined schedules, so it is reasonable toquestion whether the Poisson assumption (which implies memoryless inter-arrival times)actually makes sense in this context. Various arguments can be put forward to make the casethat, in practice, inter-arrival (and inter-departure) times are ‘sufficiently random’ for thePoisson model to be valid. For example, Pyrgiotis (2011) argues that large deviations fromscheduled operations can occur as a result of flight cancellations, delays at “upstream” airports,gate delays for departures, variability of flight times due to weather and winds, etc. Thesedeviations have the effect of “randomising” actual queue entry times.63

Stochastic Processes and their ApplicationShone, Glazebrook and ZografosFigure 1: A piecewise linear, continuous function 𝜆(𝑡), obtained by interpolating between half-hourpoints on a bar chart showing hourly demand. The function 𝜆(𝑡) can be used as the demandfunction for a nonhomogeneous Poisson process.Nevertheless, it is no surprise that various authors have challenged the Poisson assumption. Inrecent years, several authors have cited the development of the Next Generation AirTransportation System (NextGen) in the US as a possible reason for abandoning the Poissonmodel in the future. The NextGen system, which is expected to be fully in place by 2025, willallow four-dimensional trajectory-based operations (TBO). This should allow arrivals anddepartures to meet their scheduled operating times with greater precision (Joint Planning andDevelopment Office, 2010). There is a similar ongoing project in Europe, known as SingleEuropean Sky ATM Research or SESAR (European Commission, 2014). In the light of thesedevelopments, there is considerable interest in modelling demand processes which have lessvariability than Poisson processes. Nikoleris and Hansen (2012) argued that the Poisson modelcannot capture the effects of different levels of trajectory-based precision, because the variancein inter-arrival times is simply determined by the rate parameter. In a related piece of work,Hansen et al (2009) considered deterministic and exponentially-distributed inter-arrival times(both with time-varying rates) as two opposite extremes for the level of precision in meetingpre-scheduled operation times, and used case studies to show that the deterministic case couldyield delay savings of up to 35%.One type of demand process which has gained significant attention in recent years is the “prescheduled random arrivals” (PSRA) process. In PSRA queueing systems, customers have prescheduled arrival times but their actual arrival times vary according to randomearliness/lateness distributions; for example, deviations from scheduled times may be normallyor exponentially distributed. PSRA queues have been studied since the late 1950s (Winsten,1959; Mercer, 1960), but their application to aircraft queues is a relatively recent development.An advantage of using the PSRA model is that variances of arrival and departure times can becontrolled by choosing appropriate parameters for the earliness/lateness distributions, and thismay be useful for modelling the more precise operation times expected under the NextGen and64

Stochastic Processes and their ApplicationShone, Glazebrook and ZografosSESAR systems. One disadvantage, however, is that PSRA queues are more difficult to studyanalytically, and indeed they are quite different from many of the classical models usuallystudied in queueing theory since inter-arrival times are neither independent nor identicallydistributed.Guadagni et al (2011) made explicit comparisons between Poisson and PSRA demandprocesses and pointed out that PSRA queues exhibit negative autocorrelation, in the sense thattime intervals which experience fewer arrivals than expected are likely to be followed by timeperiods with more arrivals than expected. Jouini and Benjaafar (2011) also made some progressin proving analytical properties of PSRA systems with heterogeneous customers and possiblecancellations, although their model assumes that earliness/lateness distributions are bounded insuch a way that customers are guaranteed to arrive in order of their scheduled times, which maynot be suitable in an airport context. Caccavale et al (2014) used a PSRA model to studyinbound traffic at Heathrow Airport, and argued that Poisson processes are a poor model forarrivals at a busy airport since, in practice, the arrivals stream is successively rearrangedaccording to air traffic control (ATC) rules. Gwiggner and Nagaoka (2014) compared a PSRAmodel with a Poisson model using a case study based on Japanese air traffic, and found that thetwo models exhibited similar behaviour in systems with moderate congestion, but deviated fromeach other during high congestion. Lancia and Lulli (2017) studied the arrivals process at eightmajor European airports and found that a PSRA model with nonparametric, data-driven delaydistributions provided a better fit for the observed data than a Poisson model.Although time-dependent Poisson, deterministic and PSRA processes are by far the mostpopular choices for modelling aircraft queues found in the literature, a handful of otherapproaches have also been proposed. Krishnamoorthy et al (2009) considered “Markovianarrival processes” (MAPs), which generalise Poisson processes and can be studied using matrixanalytic methods. Some authors have used observed data to fit nonparametric distributions forarrival and/or departure delays (Tu et al, 2008; Kim and Hansen, 2013). Finally, although ourdiscussion throughout this section has focused on the use of time-dependent distributions, anumber of authors have considered stationary demand processes (e.g. homogeneous Poissonprocesses) and attempted to gain insight by modelling aircraft as customers of different jobclasses (Rue and Rosenshine, 1985; Horonjeff and McKelvey, 1994; Bolender and Slater, 2000;Bauerle et al, 2007; Grunewald, 2016).2.2. Optimisation ProblemsDemand-related optimisation problems at airports are based on managing patterns of demandin such a way that the worst effects of congestion are mitigated, while at the same time the levelof service provided (in terms of flight availability, punctuality, etc.) remains acceptable topassengers and other airspace users. Demand management strategies can be implemented atthe strategic level, as part of an airport’s schedule design (which usually takes place severalmonths in advance of operations) or at the tactical level, by making adjustments to aircraft flightplans in real time in order to prevent particular airports or airspace sectors from becomingheavily congested at certain times of day.65

Stochastic Processes and their ApplicationShone, Glazebrook and ZografosThe busiest airports outside the US fall into the category of slot-controlled (level 3) airports,which means that airlines intending to use these airports for take-offs or landings must submitrequests for time slots (typically 15 minutes long) during which they have permission to usethe runways and other airport infrastructure. Although the US does not implement slot controlsin the same manner, a small number of its airports are subject to the ‘high density rule’, whichimposes hourly capacity limits (Madas and Zografos, 2006). Since slot allocation is usuallycarried out with a broad set of objectives in mind (including the need to design schedules whichsatisfy airlines’ requirements as equitably as possible), the resulting schedules do not alwaysinsure effectively against the danger of severe operational (queueing) delays occurring inpractice. For example, if too many flights are allocated to a small set of consecutive time slots,the consequences for airport congestion levels may be catastrophic. Thus, there is a need fordemand management strategies to ensure that congestion mitigation is included as part of theslot allocation procedure.Various authors (Barnhart et al, 2012; Swaroop et al, 2012; Zografos et al, 2012) havecommented on the inherent trade-off that exists between schedule displacement and operationaldelays, as illustrated by Figure 2. At slot-controlled airports, certain time slots tend to be moresought-after by airlines than others. As a result, flight schedules which conform closely toairline requests are likely to result in large ‘peaks’ in demand at certain times of day. Theseschedules incur only a small amount of schedule displacement, since the requests from airlinesare largely satisfied; however, severe operational delays are likely to be caused by the peaks indemand. Conversely, operational delays can be reduced by smoothing (or ‘flattening out’) theschedule to avoid such peaks, but this generally involves displacing flights to a greater extentfrom the times requested by airlines.A useful survey of demand management strategies that have been implemented around theworld is provided by Fan and Odoni (2002). These strategies can generally be divided into twocategories: administrative and market-based. Administrative strategies involve setting ‘caps’on the numbers of runway operations that can take place at an airport in a single time period,or a number of consecutive time periods. These ‘caps’ may apply to arrivals, departures orboth, and are usually referred to in the aviation community as declared capacities (Zografos etal, 2017). The relevant optimisation problems involve deciding how these caps should be setoptimally in order to ensure a satisfactory trade-off is achieved between congestion levels(which are usually modelled stochastically) and airlines’ operational needs (Swaroop et al,2012; Churchill et al, 2012; Corolli, 2013). On the other hand, market-based strategies arebased on using economic measures such as congestion pricing and slot auctions to relievecongestion during peak periods (Andreatta and Odoni, 2003; Fan, 2003; Pels and Verhoef,2004; Mukherjee et al, 2005; Ball et al, 2006; Andreatta and Lulli, 2009; Pellegrini et al, 2012).A number of authors have directly compared administrative and market-based strategies usinganalyses and/or case studies (Brueckner, 2009; Basso and Zhang, 2010; Czerny, 2010; Gillenet al, 2016).66

Stochastic Processes and their ApplicationShone, Glazebrook and ZografosFigure 2: The trade-off between schedule displacement and operational delays.As mentioned earlier, demand management can also be done at a tactical level. Ground-holdingprograms can be used to delay departing aircraft in order to ensure that they do not arrive attheir destination airports during periods of high congestion. This not only relieves congestionat busy airports, but also has the benefit of preventing aircraft from wasting too much fuel bybeing forced to wait in airborne holdi

Aviat ion in general is currently a very active research area, and our review will touch upon some of the . approach es for modelling airport networks, are discussed in Section 4. In Section 5 we provide a summary and discuss possible directions for future research. 2. Modelling demand for runway usage at airports

Related Documents:

Jul 09, 2010 · Stochastic Calculus of Heston’s Stochastic–Volatility Model Floyd B. Hanson Abstract—The Heston (1993) stochastic–volatility model is a square–root diffusion model for the stochastic–variance. It gives rise to a singular diffusion for the distribution according to Fell

- B734 aircraft model added - B735 aircraft model added - E145 aircraft model added - B737 aircraft model added - AT45 aircraft model added - B762 aircraft model added - B743 aircraft model added - Removal of several existing OPF and APF files due to the change of ICAO aircraft designators according to RD3: A330, A340, BA46, DC9, MD80

stochastic modelling in dealing with them, are also again appreciated, after a period of growing hopes for radical reduction of uncertainty. Yet in stochastic modelling of natural processes several families of models are used which are often non-parsimonious, unnatural or artificial, theoretically unjustified and, eventually, unnecessary.

sion analysis on discrete-time stochastic processes. We now turn our focus to the study of continuous-time stochastic pro-cesses. In most cases, it is di cult to exactly describe the probability dis-tribution for continuous-time stochastic processes. This was also di cult for discrete time stochastic processes, but for them, we described the .

(e.g. bu er stocks, schedule slack). This approach has been criticized for its use of a deterministic approximation of a stochastic problem, which is the major motivation for stochastic programming. This dissertation recasts this debate by identifying both deterministic and stochastic approaches as policies for solving a stochastic base model,

Stochastic Programming Stochastic Dynamic Programming Conclusion : which approach should I use ? Objective and constraints Evaluating a solution Presentation Outline 1 Dealing with Uncertainty Objective and constraints Evaluating a solution 2 Stochastic Programming Stochastic Programming Approach Information Framework Toward multistage program

STOCHASTIC CALCULUS AND STOCHASTIC DIFFERENTIAL EQUATIONS 5 In discrete stochastic processes, there are many random times similar to (2.3). They are non-anticipating, i.e., at any time n, we can determine whether the cri-terion for such a random time is met or not solely by the “history” up to time n.

processes 1.Basics of stochastic processes 2.Markov processes and generators 3.Martingale problems 4.Exisence of solutions and forward equations 5.Stochastic integrals for Poisson random measures 6.Weak and strong solutions of stochastic equations 7.Stochastic equations for Markov processes in Rd 8.Convergenc

Chapter 11: Priority queues and Heaps 1 Chapter 11: Priority Queues and Heaps In this chapter we examine yet another variation on the simple Bag data structure. A priority queue maintains values in order of importance. A metaphor for a priority queue is a to-do list of tasks waiting to be performed, or a list of patients waiting for an

Oracle Grid Engine software provides powerful abstractions for resource and cluster modeling. Three of those abstractions, queues, host groups, and resources, are discussed below. Queues In an Oracle Grid Engine cluster, queues define where and how jobs are executed. An Oracle Grid

A summary of all Call Queues and Auto Attendants is initially displayed with monitors showing Call volumes, Missed call volumes, Unused Call Queues and Auto Attendants and Overflow details. A Queue or Auto Attendant can be selected from here to show full details on the Call Queues or Auto Attendant including individual agents performance.

F/A-18E/F Super Hornet Fighter 1,253.1 million (14 aircraft) 1,996.4 million (24 aircraft) V-22 Osprey Tiltrotor Aircraft 961.8 million (6 aircraft) 1,280.1 million (7 aircraft) C-130J Hercules Military Transport Aircraft 886.1 million (9 aircraft) 1,571.9 millio

A holding pattern is a shift by T This is the set in which we want to schedule aircraft. We seek one arrival time for each aircraft in each of the colored sets. aircraft 1 aircraft 2 aircraft 3 feasible arrival times aircraft aircraft 4 a1 b1 a2 b2 a3 b3 a4 b4 A holding pattern can be expressed as a MILP

and simplified method to describe masonry vaults in global seismic analyses of buildings. Fig. 1 summarizes three different modelling techniques for ma sonry modelling, respectively, mi cro- , macro- and simplified micro modelling. In the case a micro modelling approach is take n, the challenge is to describe the complex behavior of the

Step decision rules for multistage stochastic programming: a heuristic approach J. Th eni e J.-Ph.Vial September 27, 2006 Abstract Stochastic programming with step decision rules, SPSDR, is an attempt to over-come the curse of computational complexity of multistage stochastic programming problems. SPSDR combines several techniques.

Keywords: Multistage stochastic programming; Monte-Carlo sampling; Benders decomposition 1. Introduction Multistage stochastic linear programs with recourse are well known in the stochastic programming community, and are becoming more common in applications. The typical approach to solving these problems is to approximate the random

Analysis of Stochastic Numerical Schemes 1227 5. A STOCHASTIC ADAMS-BASHFORTH SCHEME The following is a stochastic version of a scheme which is very effective and commonly used in computational fluid dynamics. The deterministic Adams-Bashforth scheme for the ordinary

STOCHASTIC DIFFERENTIAL EQUATIONS fully observed and so must be replaced by a stochastic process which describes the behaviour of the system over a larger time scale. In effect, although the true mechanism is deterministic, when this mechanism cannot be fully observed it manifests itself as a stochastic process.

Lecture 21: Stochastic Differential Equations In this lecture, we study stochastic di erential equations. See Chapter 9 of [3] for a thorough treatment of the materials in this section. 1. Stochastic differential equations We would like to solve di erential equations of the form dX (t;X(t))dtX (t; (t))dB(t)

thermal management system is necessary to dissipate the heat generated inside the batteries. Moreover, in low-temperature scenarios, heating is required to ensure the best performance. This project aims to analyze and compare the performance of different cooling methods used for thermal management of lithium battery modules consisting of 21700 cylindrical cells. The comparison is done by .