Back to search

Georgia Institute of Technology

Stochastic programming methods for scheduling of airport runway operations under uncertainty

Abstract

dc:description.abstract

Runway systems at airports have been identified as a major source of delay in the aviation system and efficient runway operations are, therefore, important to maintain and/or increase the capacity of the entire aviation system. The goal of the airport runway scheduling problem is to schedule a set of aircraft and minimize a given objective while maintaining separation requirements and enforcing other operational constraints. Uncertain factors such as weather, surrounding traffic and pilot behavior affect when aircraft can be scheduled, and these factors need to be considered in planning models. In this thesis we propose two stochastic programs to address the stochastic airport runway scheduling problem and similarly structured machine scheduling problems. In the first part, we develop a two-stage stochastic integer programming model and analyze it by developing alternative formulations and solution methods. As part of our analysis, we first show that a restricted version of the stochastic runway scheduling problem is equivalent to a machine scheduling problem on a single machine with sequence dependent setup times and stochastic due dates. We then extend this restricted model by considering characteristics specific to the runway scheduling problem and present two different stochastic integer programming models. We derive some tight valid inequalities for these formulations, and we propose a solution methodology based on sample average approximation and Lagrangian based scenario decomposition. Realistic data sets are then used to perform a detailed computational study involving implementations and analyses of several different configurations of the models. The results from the computational tests indicate that practically implementable truncated versions of the proposed solution algorithm almost always produce very high quality solutions. In the second part, we propose a sampling based stochastic program for a general machine scheduling problem with similar characteristics as the airport runway scheduling problem. The sampling based approach allows us to capture more detailed aspects of the problem, such as taxiway operations crossing active runways. The model is based on the stochastic branch and bound algorithm with several enhancements to improve the computational performance. More specifically, we incorporate a method to dynamically update the sample sizes in various parts of the branching tree, effectively decreasing the runtime without worsening the solution quality. When applied to runway scheduling, the algorithm is able to produce schedules with makespans that are 5% to 7% shorter than those obtained by optimal deterministic methods. Additional contributions in this thesis include the development of a global cost function, capturing all relevant costs in airport runway scheduling and trading off different, sometimes conflicting, objectives. We also analyze the impact of including environmental factors in the scheduling process.

Degree

thesis:*
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sölveling, Gustaf
Advisors dc:contributor.advisor
  • Clarke, John-Paul B.
  • Johnson, Ellis L.
Committee members dc:contributor.committeemember
  • Ahmed, Shabbir
  • Sokol, Joel
  • Solak, Senay

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/44842

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Sölveling, Gustaf. Stochastic programming methods for scheduling of airport runway operations under uncertainty. Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/44842