elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Flight Gate Assignment with a Quantum Annealer

Lobe, Elisabeth and Stollenwerk, Tobias and Jung, Martin (2019) Flight Gate Assignment with a Quantum Annealer. First International Workshop on Quantum Technology and Optimization Problems (QTOP’19), 18. - 19.03.2019, München, Deutschland.

[img] PDF - Registered users only
2MB

Abstract

Optimal flight gate assignment is a highly relevant optimization problem from airport management. Among others, an important goal is the minimization of the total transit time of the passengers. The corresponding objective function is quadratic in the binary decision variables encoding the flight-to-gate assignment. Hence, it is a quadratic assignment problem being hard to solve in general. In this work we investigate the solvability of this problem with a D-Wave quantum annealer. These machines are optimizers for quadratic unconstrained optimization problems (QUBO). Therefore the flight gate assignment problem seems to be well suited for these machines. We use real world data from a mid-sized German airport as well as simulation based data to extract typical instances small enough to be amenable to the D-Wave machine. In order to mitigate precision problems, we employ bin packing on the passenger numbers to reduce the precision requirements of the extracted instances. We find that, for the instances we investigated, the bin packing has little effect on the solution quality. Hence, we were able to solve small problem instances extracted from real data with the D-Wave 2000Q quantum annealer.

Item URL in elib:https://elib.dlr.de/128864/
Document Type:Conference or Workshop Item (Speech)
Title:Flight Gate Assignment with a Quantum Annealer
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Lobe, ElisabethElisabeth.Lobe (at) dlr.dehttps://orcid.org/0000-0002-3473-8906
Stollenwerk, Tobiastobias.stollenwerk (at) dlr.dehttps://orcid.org/0000-0001-5445-8082
Jung, MartinM.Jung (at) dlr.dehttps://orcid.org/0000-0002-1860-297X
Date:18 March 2019
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
Status:Published
Keywords:Quadratic Assignment Problem, QUBO, Airport Planning, Quantum Annealing Application, Combinatorial Optimization
Event Title:First International Workshop on Quantum Technology and Optimization Problems (QTOP’19)
Event Location:München, Deutschland
Event Type:international Conference
Event Dates:18. - 19.03.2019
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Technik für Raumfahrtsysteme
DLR - Research theme (Project):R - Quantencomputing
Location: Braunschweig
Institutes and Institutions:Institut of Simulation and Software Technology > High Performance Computing
Institute of Air Transport and Airport Research > Airport Research
Deposited By: Lobe, Elisabeth
Deposited On:06 Nov 2019 10:42
Last Modified:06 Nov 2019 10:42

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.