Neuer Algorithmus für «Problem des Handlungsreisenden»

Jakub Tarnawski hat den mit 5000 Euro dotierten Dissertationspreis erhalten, eine gemeinsame Auszeichnung der Schweizer Informatik Gesellschaft (SI), der Österreichischen Computergesellschaft (OCG) und der Gesellschaft für Informatik, die herausragende Promotionsarbeiten würdigt.

Die an der ETH Lausanne eingereichte Forschungsarbeit widmet sich unter anderem dem mathematischen Problem des Handlungsreisenden (Traveling Salesman Problem). Die Herausforderung besteht darin, eine optimale Reise-Route für den Besuch mehrerer Orte zu finden. Dabei muss jede Station mindestens einmal besucht werden, jedoch soll die Reisestrecke des Handlungsreisenden möglichst kurz sein und die erste Station der letzten Station entsprechen.

In der einfachen, der symmetrischen Variante, sind die Kosten, die Zeit oder das Unfallrisiko einer Strecke unabhängig davon in welcher Richtung sie zurückgelegt wird. In der erschwerten, asymmetrischen Variante des Problems, hängen die Widrigkeiten einer Strecke davon ab, in welcher Richtung sie zurückgelegt wird.

Die Strecke von A nach B könnte zum Beispiel länger dauern oder mehr kosten als die Strecke von B nach A. Mit dem von Jakub Tarnawski im Rahmen seiner Promotion entwickelten Algorithmus lässt sich nun deutlich besser als bisher eine Annäherung an eine optimale Route berechnen.

Die gewonnen Erkenntnisse sind insbesondere für Logistikunternehmen von hohem praktischem Nutzen. Durch die nun möglichen Verbesserungen in der Routenplanung lassen sich Zeit, Geld und CO2-Emmissionen einsparen.

«Jakub Tarnawski hat im Bereich der Informatik-Grundlagenforschung ein herausragendes Forschungsergebnis erzielt: den ersten Algorithmus, der eine zufrieden stellende Annäherung an das asymmetrische Problem des Handlungsreisenden bietet», kommentiert GI-Präsident Hannes Federrath die Arbeit. «Sowohl die Laufzeit des Algorithmus als auch der Grad der Annäherung an eine optimale Lösung sind einmalig. Darüber hinaus hat sich Herr Tarnawski einen deterministischen parallelen Algorithmus für das perfekte Matching entwickelt, der ein zweites herausragendes Forschungsergebnis darstellt», erklärt er weiter.

Mit ihrem gemeinsam vergebenen Dissertationspreis möchten die Gesellschaft für Informatik, die Österreichischen Computer Gesellschaft und die Schweizer Informatik Gesellschaft besonders wichtige Arbeiten junger Wissenschaftlerinnen und Wissenschaftler in der Öffentlichkeit herausstellen. Die beteiligen Fachgesellschaften möchten darüber hinaus einen Beitrag zum Wissenstransfer von den Hochschulen in die Bereiche Technik, Wirtschaft und Gesellschaft leisten. Vorschlagsberechtigt für den GI-Dissertationspreis der sind alle wissenschaftlichen Hochschulen in der Bundesrepublik Deutschland, in Österreich und in der Schweiz, die das Promotionsrecht in den oben genannten Bereichen besitzen. Jede dieser Hochschulen darf eine Dissertation für den Preis vorschlagen.