Skip to content

Reference

Jump to bottom
Heron Yang edited this page Feb 4, 2018 · 10 revisions

Shared folder (Click on request access for the first time)

REIF 1979: Complexity of the Generalized Mover's Problem

  • NP-hard problem

Atkin 2010: The airport ground movement problem: past and current research and future directions

  • the airport ground movement problem = routing and scheduling problem
  • constraints
    • consideration of the route taken
    • separation constraints between aircraft
    • aircraft movement speeds
    • timing constraints for arrivals
    • timing constraints for departures
  • integration of other airport operations
    • integration of departure sequences
    • integration of arrival sequences
    • integration of gate assignment
  • objective functions
    • minimizing the total taxi time
    • minimizing the makespan
    • multi-objective problem (ex. penalizing deviations from a scheduled time of departure/arrival)
  • existing models
    • mixed integer linear programming (MILP) formulations: "in the first step, a relaxed MULP formulation was solved, and no guarantees were given for a conflict-free solution. An iterative procedure was then applied, where additional constraints were added where they were necessary to avoid any conflicts detected in the previous iteration. This was repeated until a conflict-free schedule was found" -> [clare2009]
      • problem: too hard/complex to solve
    • genetic algorithm (GA) models
      • "maintain a population of candidate solutions, have a method (called a fitness function) for evaluating solutions and apply a selection mechanism to guide the algorithm towards good solutions"
      • "a correct encoding of the problem can be key for the successful application of a GA" (a good simulation like ours?)
  • future direction: "robustness and uncertainty"

Clare 2009: Optimization of Taxiway Routing and Runway Scheduling

  • Receding Horizon (RH) formulation and use of iteration in the avoidance constraints allows the scalability of the baseline algorithm presented to e illustrated. RH means that a single large planning problem is approximated as a sequence of smaller problems.
  • Use Heathrow airport containing up to 240 aircrafts (122 arrivals), 126 node, 9am to 12 noon
  • Background and Motivation

An Iterative A* Algorithm for Planning of Airport Ground Movements

  • "Managing uncertainty": time uncertainty, speed uncertainty
  • Allen's algebra (13 relations to compare two intervals)
  • Drawback: "controlling the aircraft speed to ensure separation may lead to unexpected situations where the aircraft speed is very small; as separation constraint is only verified on nodes (and not on edges), a situation where several aircrafts are slowly moving on a busy taxiway is possible"

Solveling2012: Stochastic programming methods for scheduling of airport runway operations under uncertainty (thesis)

  • Nice summary: "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
  • The first part, two-stage stochastic integer programming model. The practically implementable truncated versions of the proposed solution algorithm almost always produce very high-quality solution
  • The second part, sampling based stochastic program
  • 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
  • We can found separation requirements in the table.
  • Good point: "Researchers often focus on the decision problem without consideration of the control problem, which can lead to models giving solutions that cannot be implemented in practice."
  • Due to unpredictable factors such as weather, pilot behavior, surface traffic, and other circumstances, deviations from the estimated input parameters are inevitable -> uncertainty
  • Stochastic program
    • the input data to a stochastic model is not known with certainty at the time the model is evaluated
    • an optimization model where the uncertain input parameters have known probability distributions
    • first stage decision: uncertainty is realized; second stage decision: a resource decision

Balakrishna2009: Application of Reinforcement Learning Algorithms for Predicting Taxi-out Times

Lee-MIT 2008 : Airport Surface Traffic Optimization and Simulation in the Presence of Uncertainties

  • most research optimize scheduling for taxiway and runway separately, this paper is doing them together
  • simulation tool: SIMMOD (not maintained after 2010)
  • it's expected that in the near future, taxi operations will experience a shift from voice to data link
  • literature review
    • runway scheduling: FCFS -> CPS (add separation, maximum position shift), job shop, MILP
    • taxiway scheduling: Aircraft Taxi-scheduling Problem (ATP), dynamic programming, node-link network model, dijkstra, Multiple Route Aircraft Taxi Scheduling Problem (MRATSP), Integer Programming (IP), heuristic method, rolling horizon method
  • Sport And Runway Departure Advisor (SARDA), NASA
  • Surface Operations Data Analysis and Adaptation (SODAA) tool
Clone this wiki locally