Scenario-based Route Planning
Accelerating TSP approximation through problem encoding optimization
University of Tübingen
In der ersten Projektphase von SEQUOIA haben wir einen Algorithmus entwickelt, der Instanzen von kombinatorischen Optimierungsproblemen in mehrere kleine Unterinstanzen gleicher Größe zerlegt. Die selektive Lösung einiger dieser Teilprobleme und die Kombination ihrer Lösungen ergibt eine Lösung für die ursprüngliche Problemstellung. Dieser Ansatz wurde durch die begrenzte Anzahl von Qubits der derzeit verfügbaren Quantenhardware motiviert.
In SEQUOIA End-to-End beschäftigten wir uns mit der Methode zur Lösung der generierten Teilprobleme. In der ersten Projektphase haben wir zur Lösung der Teilprobleme QAOA so implementiert, wie es in Forschungsarbeiten beschrieben ist. Wir stellten jedoch Mängel bei der Laufzeit und der Lösungsqualität fest, die das Gesamtergebnis stark beeinträchtigten. Daher beschlossen wir, eine andere Problemkodierung für das TSP zu konstruieren, die es uns ermöglichen würde, die Problemparameter und -beschränkungen direkter in einem Quantenschaltkreis zu implementieren. Die Kernidee besteht darin, die Abstände zwischen den Punkten direkt zu kodieren, anstatt eine 1-hot-kodierte Reihe von Punkten zu verwenden. Wir stellen unsere Implementierung und die Ergebnisse im Demonstrator vor und vergleichen sie mit dem bisherigen Ansatz.
Scenario-based route planning to safeguard automotive driving functions (TSP/ORP)
FZI Research Center for Information Technology
The demonstrator shows two different modeling approaches and corresponding implementation for scenario-based route planning. The first approach is based on a QAOA implementation created as part of the project for the "Traveling Salesperson Problem". In addition, an algorithm for partitioning the TSP developed in the course of the project will be demonstrated. The algorithm, which is based on A*, splits large TSP instances into several smaller ones so that they can be solved on the quantum computer. This approach is hybrid, whereby the partitioning takes place on a classical computer and only the difficult combinatorial »core« of the problem is solved on a quantum computer. Our QAOA implementation is embedded into this algorithm and can alternatively be exchanged with classical solver for comparison. In order to guide the choices of our method on which subinstanced to generate, several heuristics have been developed. This includes notably a small neural network that can estimate the expected length of a TSP instance. The second approach models the problem as an orienteering problem rather than the usual TSP. The orienteering problem is a combination of TSP and knapsack problem. In this approach, we show how this different kind of modeling affects the implementation and the complexity of the underlying optimization problem.
Disclaimer
The interactive demonstrator notebooks have been licensed under the Apache licence (version 2.0). The files may only be used in accordance with the licence. A copy of the licence can be downloaded from http://www.apache.org/licenses/LICENSE-2.0 Except as required by applicable law or agreed to in writing, software distributed under this licence is distributed on an "AS IS" basis, without warranties or conditions of any kind, either express or implied. See the licence for the specific rights and restrictions associated with it.
This is a research prototype. Liability for loss of profit, loss of production, business interruption, loss of use, loss of data and information, financing costs and other financial and consequential damage is excluded, except in cases of gross negligence, intent and personal injury.