Airport Gate Assignment Problem:

Deep Reinforcement Learning Methods

Airport Gate Assignment Problem

What is AGAP?

  • Problem of assigning airplanes to gates
  • Has to minimize multiple objectives like waiting for free gate, forced movement of people etc.

Current approaches to AGAP

  • Integer linear programming - Schiphol
  • Stochastic model - Taiwan International, Ataturk
  • Heuristic approach - Toronto International
  • Genetic algorithm - KSA airport
  • Over 43 publications

Limits of current approaches

  • Static deterministic environments - mathematical definitions
  • Many oversimplifications

Motivation

53.5% Punctual
46.5% Delayed
  • In 2018 535mln flights departed with some delay
  • 150mln with more than 30min delay
  • 87mln due to airport organization issues

Sources: EuroStat - "Air transport statistics 2018"; EuroControl - "Annual report for 2018/2019"

How solving AGAP can benefit us?

  • Airports want to fit more flights
  • Preventing delays
  • Reducing waiting time

Ideate

  • Genetic Algorithm
  • Swarm Optimization
  • Tabu Search
  • Reinforcement Learning

  • Linear Programming
  • Gradient Search
  • Exhaustive Search

Proposed solution architecture

  • Actor model based environment
  • Use of state of the art RL algorithms

Evaluation

  • Reward function composed of:
    waiting time, forced people movement,
    costs of changing gates, etc.
  • Bellman Optimality equation
  • Performance comparison to greedy algorithm

Team/Partners

Team
  • Reinforcement Learning
  • Fast Time Simulation (e.g. AirTOp)
  • Deep Learning
Partners
  • Airport employees and managers as domain experts for prior knowledge definition

Simulator

  • Model airport behaviour
  • Environment for RL algorithm
  • Visualize decisions

Deployment

  • Generation of analysis reports focused on optimization of passenger traffic
  • Human decision-making support tools as web application
  • Simulation API - for different layout/parameters analysis
  • Scientific publications

Costs & Benefits

Costs
  • Gathering data for simulation purposes
  • Simulation engine
  • Time and resources spent on interviews with domain experts
  • Model training costs
Benefits
  • Improved knowledge in domain of reinforcement learning for multiobjective optimization
  • Practical (research-based) insight into the difficulty of solving similar tasks with reinforcement learning techniques
  • Better optimization and planning of flights and airport spatial layout

Agile methodology

Thanks

"There's no such thing as a stupid question!"

Presented by:
Marek Pokropiński, Filip Strzałka, Kemal Erdem

Credits: Icons designed by Freepik