Stollenwerk, Tobias and Lobe, Elisabeth and Jung, Martin (2019) Flight Gate Assignment with a Quantum Annealer. Lecture Notes in Computer Science, 11413, pp. 99-110. Springer. doi: 10.1007/978-3-030-14082-3. ISSN 0302-9743.
![]() |
PDF
- Preprint version (submitted draft)
457kB |
Official URL: https://link.springer.com/chapter/10.1007/978-3-030-14082-3_9
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/123777/ | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Document Type: | Article | ||||||||||||
Title: | Flight Gate Assignment with a Quantum Annealer | ||||||||||||
Authors: |
| ||||||||||||
Date: | 19 February 2019 | ||||||||||||
Journal or Publication Title: | Lecture Notes in Computer Science | ||||||||||||
Refereed publication: | Yes | ||||||||||||
Open Access: | Yes | ||||||||||||
Gold Open Access: | No | ||||||||||||
In SCOPUS: | Yes | ||||||||||||
In ISI Web of Science: | No | ||||||||||||
Volume: | 11413 | ||||||||||||
DOI: | 10.1007/978-3-030-14082-3 | ||||||||||||
Page Range: | pp. 99-110 | ||||||||||||
Publisher: | Springer | ||||||||||||
ISSN: | 0302-9743 | ||||||||||||
Status: | Published | ||||||||||||
Keywords: | Quantum Compting, Air Traffic Management | ||||||||||||
HGF - Research field: | Aeronautics, Space and Transport | ||||||||||||
HGF - Program: | Space | ||||||||||||
HGF - Program Themes: | Space System Technology | ||||||||||||
DLR - Research area: | Raumfahrt | ||||||||||||
DLR - Program: | R SY - Space System Technology | ||||||||||||
DLR - Research theme (Project): | R - Quantencomputing (old) | ||||||||||||
Location: | Braunschweig , Köln-Porz | ||||||||||||
Institutes and Institutions: | Institut of Simulation and Software Technology > High Performance Computing Institut of Simulation and Software Technology | ||||||||||||
Deposited By: | Stollenwerk, Tobias | ||||||||||||
Deposited On: | 23 Jul 2019 10:39 | ||||||||||||
Last Modified: | 23 Jul 2022 13:45 |
Repository Staff Only: item control page