{"id":5470,"date":"2024-05-17T14:38:17","date_gmt":"2024-05-17T12:38:17","guid":{"rendered":"https:\/\/www.sequoia-iao.de\/?page_id=5470"},"modified":"2025-09-01T14:32:59","modified_gmt":"2025-09-01T12:32:59","slug":"szenariobasierte-routenplanung","status":"publish","type":"page","link":"https:\/\/www.kqcbw.de\/en\/szenariobasierte-routenplanung\/","title":{"rendered":"Scenario-based Route Planning"},"content":{"rendered":"
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Scenario-based Route Planning<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t

\n\t\t\t\t\t\tAccelerating TSP approximation through problem encoding optimization\t\t\t\t\t<\/h3>\n\t\t\t\t\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\tUniversity of T\u00fcbingen\t\t\t\t\t<\/h5>\n\t\t\t\t\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

In der ersten Projektphase von SEQUOIA haben wir einen Algorithmus entwickelt, der Instanzen von kombinatorischen Optimierungsproblemen in mehrere kleine Unterinstanzen gleicher Gr\u00f6\u00dfe zerlegt. Die selektive L\u00f6sung einiger dieser Teilprobleme und die Kombination ihrer L\u00f6sungen ergibt eine L\u00f6sung f\u00fcr die urspr\u00fcngliche Problemstellung. Dieser Ansatz wurde durch die begrenzte Anzahl von Qubits der derzeit verf\u00fcgbaren Quantenhardware motiviert.<\/span>
In SEQUOIA End-to-End besch\u00e4ftigten wir uns mit der Methode zur L\u00f6sung der generierten Teilprobleme. In der ersten Projektphase haben wir zur L\u00f6sung der Teilprobleme QAOA so implementiert, wie es in Forschungsarbeiten beschrieben ist. Wir stellten jedoch M\u00e4ngel bei der Laufzeit und der L\u00f6sungsqualit\u00e4t fest, die das Gesamtergebnis stark beeintr\u00e4chtigten. Daher beschlossen wir, eine andere Problemkodierung f\u00fcr das TSP zu konstruieren, die es uns erm\u00f6glichen w\u00fcrde, die Problemparameter und -beschr\u00e4nkungen direkter in einem Quantenschaltkreis zu implementieren. Die Kernidee besteht darin, die Abst\u00e4nde 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.\u00a0<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\tTo the demonstrator in the Fraunhofer GitLab<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\tTo the interactive Jupyter Notebook<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t
<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t

\n\t\t\t\t\t\tScenario-based route planning to safeguard automotive driving functions (TSP\/ORP)\t\t\t\t\t<\/h3>\n\t\t\t\t\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\tFZI Research Center for Information Technology\t\t\t\t\t<\/h5>\n\t\t\t\t\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\tneu\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

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\u00a0\"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\u00a0\u00bbcore\u00ab\u00a0of 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.\u00a0The 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.\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\tTo the demonstrator in the Fraunhofer GitLab<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\tTo the interactive Jupyter Notebook<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Disclaimer<\/h4>

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<\/a> 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.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"

Szenariobasierte Routenplanung Beschleunigte TSP-Approximation durch Optimierung der Problemcodierung Eberhard Karls Universit\u00e4t T\u00fcbingen In der ersten Projektphase von SEQUOIA haben wir einen Algorithmus entwickelt, der Instanzen von kombinatorischen Optimierungsproblemen in mehrere kleine Unterinstanzen gleicher Gr\u00f6\u00dfe zerlegt. Die selektive L\u00f6sung einiger dieser Teilprobleme und die Kombination ihrer L\u00f6sungen ergibt eine L\u00f6sung f\u00fcr die urspr\u00fcngliche Problemstellung. Dieser Ansatz … <\/p>\n

Read more „Szenariobasierte Routenplanung“<\/span><\/a><\/p>","protected":false},"author":2,"featured_media":9842,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-5470","page","type-page","status-publish","has-post-thumbnail","hentry"],"featured_media_urls":{"thumbnail":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-150x150.jpg",150,150,true],"medium":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-300x117.jpg",300,117,true],"medium_large":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled.jpg",768,301,false],"large":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-1024x401.jpg",950,372,true],"1536x1536":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled-1536x602.jpg",1536,602,true],"2048x2048":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled-2048x802.jpg",2048,802,true],"trp-custom-language-flag":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled-18x7.jpg",18,7,true],"inspiro-featured-image":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-2000x783.jpg",2000,783,true],"inspiro-loop":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-950x320.jpg",950,320,true],"inspiro-loop@2x":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-1900x640.jpg",1900,640,true],"portfolio_item-thumbnail":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled-600x400.jpg",600,400,true],"portfolio_item-thumbnail@2x":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled-1200x800.jpg",1200,800,true],"portfolio_item-masonry":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled-600x235.jpg",600,235,true],"portfolio_item-masonry@2x":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled-1200x470.jpg",1200,470,true],"portfolio_item-thumbnail_cinema":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled-800x335.jpg",800,335,true],"portfolio_item-thumbnail_portrait":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled-600x900.jpg",600,900,true],"portfolio_item-thumbnail_portrait@2x":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled-1200x1003.jpg",1200,1003,true],"portfolio_item-thumbnail_square":["https:\/\/www.kqcbw.de\/wp-content\/uploads\/2025\/08\/Banner-Wide_ohne_Schrift-scaled-800x800.jpg",800,800,true]},"_links":{"self":[{"href":"https:\/\/www.kqcbw.de\/en\/wp-json\/wp\/v2\/pages\/5470","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.kqcbw.de\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.kqcbw.de\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.kqcbw.de\/en\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kqcbw.de\/en\/wp-json\/wp\/v2\/comments?post=5470"}],"version-history":[{"count":37,"href":"https:\/\/www.kqcbw.de\/en\/wp-json\/wp\/v2\/pages\/5470\/revisions"}],"predecessor-version":[{"id":10204,"href":"https:\/\/www.kqcbw.de\/en\/wp-json\/wp\/v2\/pages\/5470\/revisions\/10204"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.kqcbw.de\/en\/wp-json\/wp\/v2\/media\/9842"}],"wp:attachment":[{"href":"https:\/\/www.kqcbw.de\/en\/wp-json\/wp\/v2\/media?parent=5470"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}