Haben Sie schon einmal einen Zauberwürfel gelöst? Wenn nicht, haben Sie aber vielleicht schon ein Sudoku-Rätsel geknackt, oder auch einfach nur ein Labyrinth auf der Rückseite einer Cornflakes-Packung. Falls Sie eines dieser Dinge schon geschafft haben: herzlichen Glückwunsch! Sie haben ein nichtdeterministisches Polynomialproblem gelöst! Dieser Begriff scheint vielleicht zuerst einschüchternd, aber man braucht nicht Mathematik studiert zu haben, um die Grundlagen dieses Phänomens zu verstehen, denn Sie haben tagtäglich mit Polynomen (P) und nichtdeterministischen Polynomialproblemen (NP) zu tun.
Polynome sind Funktionen von n in verschiedenen Potenzen, zum Beispiel n2 oder n3. Polynomialzeit bedeutet, dass bei einem Problem mit n Elementen (z. B. die Anzahl an Haltestellen einer Linie oder die Anzahl an Blöcken eines Zauberwürfels), die Zeit, die ein Computer benötigt, um die optimale Lösung des Problems zu ermitteln, eine Polynomfunktion von n sein wird.
Zum Lösen eines „P-Problems” braucht ein Computer „Polynomialzeit“. Zum Lösen eines „NP-schweren Problems“ benötigt er jedoch exponentiell viel Zeit, da kein bekannter Algorithmus vorliegt, der das Problem in Polynomialzeit lösen könnte. Wie der Name schon verrät, sind NP-schwere Probleme weitaus schwerer zu lösen als P-Probleme. Falls Sie sich fragen, was Einsatzplanungen so kompliziert macht, folgt hier ein Beispiel:
Stellen Sie sich vor, Ihnen stehen in Ihrem Kalender drei Stunden zur Verfügung, um drei einstündige Besprechungen mit Alex, Bob und Carol zu terminieren. In diesem einfachen Fall gibt es sechs Optionen.
In diesem Szenario würden natürlich alle sechs Optionen gleich gut funktionieren. Aber wie Sie wissen, ist heutzutage jeder vielbeschäftigt und hat seine eigenen Wünsche. Nehmen wir also an, Sie erhalten folgende Anfragen von Alex, Bob und Carol:
- Alex kann nur bis 11.30 Uhr, würde sich mit Ihnen aber gern eine volle Stunde lang treffen.
- Bob würde sich gern nach 10 Uhr treffen, denn vorher könnte er unvorbereitet zum Termin erscheinen und dann würde das Treffen 90 Minuten in Anspruch nehmen.
- Carol würde sich vor dem Termin mit Ihnen gern für eine Stunde mit Alex treffen. In diesem Fall würde ein Treffen zwischen Ihnen und Carol nur 30 Minuten in Anspruch nehmen.
Zusätzlich zu den Bedürfnissen der anderen haben Sie vielleicht auch noch eigene Wünsche. Vielleicht haben Sie gerade viel Arbeit und möchten so wenig Zeit wie möglich für diese Treffen aufwenden. Vielleicht ist Ihnen aber auch das Treffen mit Alex am wichtigsten, während Carol und Bob keine Priorität sind. Wenn jetzt auch noch eine zusätzliche Person ein Treffen mit Ihnen vereinbaren wollte, hätten sie viermal so viel zu koordinieren, denn auf einmal gäbe es 24 Alternativen. Angenommen, 10 Personen wollten Sie treffen, stünden Sie vor 3,6 Milliarden Optionen (fast die halbe Weltbevölkerung), bei 20 Personen wären wir schon bei 2,4 Trillionen (2,4*1018) Möglichkeiten (das entspricht ungefähr einem Drittel aller Sandkörner der Erde). Mit wechselnden Vorlieben und Bedürfnissen und insbesondere mit zunehmender Anzahl an Personen in Ihrem Kalender, wächst die Zahl der Möglichkeiten – und damit die Schwierigkeit, das optimale Szenario zu finden – sehr schnell an.
Optibus hilft seinen Kunden, ähnliche, fast unlösbare Probleme in ihrer Planungsarbeit zu lösen. Was keine einfache Aufgabe ist. Unser Algorithmus verarbeitet Hunderte bis Tausende von Fahrzeugen und Fahrern/-innen, berücksichtigt dabei nicht verhandelbare Vorgaben als auch nicht bindende Präferenzen, um daraus das optimale Ergebnis zu kalkulieren. Einige der von uns berücksichtigten Elemente sind: Netz- und Streckenpläne, Standorte von Haltestellen und Depots, Angleichung von Zeitplänen, Fahrzeugtyp und -kapazität, Schichtwünsche der Fahrer/-innen, Ladevorgänge von Elektrofahrzeugen, rechtliche Vorschriften und Leistungskennzahlen.
Egal ob ein Verkehrsbetreiber staatlich gefördert wird oder nicht, sollte er seinen Fahrgästen immer den besten Service zu den niedrigsten Kosten anbieten. Zwischen einer optimalen und einer suboptimalen Lösung können pro Jahr Millionen von Dollar liegen – schlechte Nachrichten sowohl für die Unternehmen als auch für die Steuerzahler. Ein herkömmlicher Optimierungsalgorithmus benötigt zur Lösung eines Problems zwischen wenigen Stunden und ein paar Tagen, selbst mit viel Rechenleistung. Soll es dann noch einen Tag länger dauern, um die optimale Lösung zu finden, ist es für ein Unternehmen einfach nicht realistisch, verschiedene Szenarien berechnen zu lassen, um herauszufinden, welches am besten funktionieren würde – vor allem unter unbeständigen Bedingungen (z. B. Straßensperren).
Bei Optibus lösen wir komplexe Probleme innerhalb weniger Minuten oder sogar Sekunden. Unser Algorithmus teilt das Problem in verschiedene Unterprobleme auf, die mit spezialisierten Algorithmen gelöst werden können. Zum Beispiel verfügen wir über einen Algorithmus, der die Rechenzeit erheblich reduziert, indem er unrealistische Szenarien umgehend eliminiert.
Bei Optibus lösen wir komplexe Probleme innerhalb weniger Minuten oder sogar Sekunden. Unser Algorithmus teilt das Problem in verschiedene Unterprobleme auf, die mit spezialisierten Algorithmen gelöst werden können. Zum Beispiel verfügen wir über einen Algorithmus, der die Rechenzeit erheblich reduziert, indem er unrealistische Szenarien umgehend eliminiert.
Mit unserer Innovation machen wir die Optimierung von Planungsaufgaben für Nahverkehrsbetreiber zu einem einfachen und effizienten Vorgang. Unsere Technologie kümmert sich um die lästigen und dennoch äußerst wichtigen Elemente eines Verkehrsnetzes, damit die Betreiber ihren Fokus (und ihr Budget) auf die Bereitstellung eines überzeugenden Angebots für ihre Kunden richten können.
