elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

Flight Gate Assignment with a Quantum Annealer

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

[img] PDF - Nur DLR-intern zugänglich
2MB

Kurzfassung

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.

elib-URL des Eintrags:https://elib.dlr.de/128864/
Dokumentart:Konferenzbeitrag (Vortrag)
Titel:Flight Gate Assignment with a Quantum Annealer
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Lobe, ElisabethElisabeth.Lobe (at) dlr.dehttps://orcid.org/0000-0002-3473-8906NICHT SPEZIFIZIERT
Stollenwerk, Tobiastobias.stollenwerk (at) dlr.dehttps://orcid.org/0000-0001-5445-8082NICHT SPEZIFIZIERT
Jung, MartinM.Jung (at) dlr.dehttps://orcid.org/0000-0002-1860-297X137359900
Datum:18 März 2019
Referierte Publikation:Ja
Open Access:Nein
Gold Open Access:Nein
In SCOPUS:Nein
In ISI Web of Science:Nein
Status:veröffentlicht
Stichwörter:Quadratic Assignment Problem, QUBO, Airport Planning, Quantum Annealing Application, Combinatorial Optimization
Veranstaltungstitel:First International Workshop on Quantum Technology and Optimization Problems (QTOP’19)
Veranstaltungsort:München, Deutschland
Veranstaltungsart:internationale Konferenz
Veranstaltungsbeginn:18 März 2019
Veranstaltungsende:19 März 2019
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Raumfahrt
HGF - Programmthema:Technik für Raumfahrtsysteme
DLR - Schwerpunkt:Raumfahrt
DLR - Forschungsgebiet:R SY - Technik für Raumfahrtsysteme
DLR - Teilgebiet (Projekt, Vorhaben):R - Quantencomputing (alt)
Standort: Braunschweig
Institute & Einrichtungen:Institut für Simulations- und Softwaretechnik > High Performance Computing
Institut für Flughafenwesen und Luftverkehr > Flughafenforschung
Hinterlegt von: Lobe, Elisabeth
Hinterlegt am:06 Nov 2019 10:42
Letzte Änderung:24 Apr 2024 20:32

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.