Warum eine einzige Flugsuche Millionen kostet

Warum zeigen Flugsuchmaschinen keine vollständigen Suchen und die besten Preise an? Ganz einfach, jede Flugsuche kostet Geld, je vollständiger desto mehr Geld!


Nerd Alarm!, dieser Artikel ist für Nerds!

Eine einfache Suche

Eine Anfrage kostet bei Google/ITA ¢3,5 Dollar Cent. Das klingt nicht teuer, aber eine Anfrage heißt lediglich von A nach Z am Tag 1 und zurück am Tag 30.

Die Kosten steigen exponentiell an, wenn Du von A, B, C, oder D nach W, X, Y oder Z fliegen willst, an den Tagen 1, 2, 3 oder 4 und zurück an den Tagen 27, 28, 29 oder 30. Das wären bei 4 Startflughäfen, 4 Zielflughäfen und jeweils 4 Tagen schon

  • 256 Anfragen und $9 USD für die Suche! (Round Trips, 4 Städte, 4 Tage)

Ein wichtiger Insidertipp ist, dass Du mit Gabelflügen oft Geld sparst, direktere Verbindungen hast oder Überlandstrecken vermeiden kannst. Mit Gabelflügen wird die Komplexität aber richtig heftig.

Wenn Du alle einfachen und doppelten Gabelflüge berücksichtigen willst, sind das bei jeweils 4 Flughäfen und jeweils 4 Tagen Spielraum insgesamt

  • 4² x 4² x 4 x 4 Anfragen (Variationen mit Wiederholung, abzählende Kombinatorik)

Das ergibt

  • 4.096 Anfragen oder $143 USD für eine einzige Suche! (Gabelflüge, 4 Städte, 4 Tage)

Und in 1 Stunde kannst Du wieder suchen, weil sich der Preis vielleicht verändert hat!

Flugsuche für ein ganzes Land

Um ein ganzes Land abzudecken, bräuchtest Du eher 10 Flughäfen und eine Woche hat 7 Tage, also reden wir schon von 10² x 10² x 7 x 7 Anfragen, ergibt

  • 490.000 Anfragen und $17.150 USD (Gabelflüge, 10 Flughäfen, 7 Tage)

Absurd oder? Das ist eine einfache Suche zwischen zwei Ländern, mit einer Woche Flexibilität. 1 Monat Flexibilität würde schon mehr als $300.000 USD kosten.

Millionen Dollar teure Flugsuche

Und dann haben wir noch keine kreativeren Kombinationsmöglichkeiten geprüft, zum Beispiel den Flug als Aneinanderreihung von 2 Round Trips mit jeweils 1 Zwischenlandung auf dem Hin- und einer Zwischenlandung auf dem Rückweg. Und das ist erst der Anfang.

Möglich sind bei maximal 1 Stopover außerdem:
2 One Ways oder 3 One Ways mit 1 Stopover oder 1 Round Trip und 1 One Way mit 1 Stopover oder 1 Gabelflug und 1 One Way mit 1 Stopover oder 4 One Ways mit jeweils 1 Stopover oder 1 Round Trip und 2 One Ways mit jeweils 1 Stopover oder 1 Gabelflug und 2 One Ways mit jeweils 1 Stopover oder 1 Round Trip und 1 Gabelflug mit jeweils 1 Stopover oder 2 Gabelflüge mit jeweils 1 Stopover. Das waren jetzt nur die Kombinationen mit 1 Stopover. Kompliziert wird es, wenn 2 oder mehr Stopover zulässig sind.

Das ist etwas übertrieben, aber grundsätzlich sind manuelle Routings keine sinnlose Gedankenspielerei. Nur so können alle Fare-Bucket Konstruktionen berücksichtigt werden. Nur so können wir mit Nicht-Partner-Airlines und Billigfliegern kombinieren.

Indem Du z.B. das kontinentale Segment mit einem Billigflieger fliegst, kannst Du manchmal viel Geld sparen. Auch Self-Dumps werden so manchmal ausgelöst. Indem Flugsegmente manuell zerlegst, kannst Du manchmal wegen Preisregeln Geld sparen.

Mit dieser Komplexität sind wir dann schnell im Bereich von vielen Millionen Dollar Kosten für eine einzige Suche für einen simplen Hin- und Rückflug.

Und dann haben wir immer noch nicht alle Möglichkeiten berücksichtigt!

Milliarden Dollar teure Flugsuchen

Es macht nämlich manchmal Sinn bei einem einfachen Hin- und Rückflug ein 3. Segment hinzuzufügen, dass Du gar nicht fliegst. Dadurch wird ein sogenannter „Fuel Dump“ ausgelöst und Du kannst teilweise mehrere Hundert Euro sparen.

Der Witz ist, dass das dritte Segment bei einem 3x Fuel Dump nichts mit den anderen beiden Segmenten zu tun haben muss. Es muss bei der gleichen Airline oder Partner-Airline sein, aber es kann z.B. auf einem anderen Kontinent liegen!

Wir müssten also die vielen Tausend Flugverbindungen der jeweiligen Airline oder Partner-Airline mit den Millionen von Kombinationen, die wir eh schon haben kombinieren um gründlich zu sein.

Oder Du willst von Cancun nach Düsseldorf fliegen, buchst aber Deinen Flug nach London mit einem Stopover in der sogenannten „Hidden City“ Düsseldorf und steigst dann einfach in Düsseldorf aus, ohne das letzte Segment nach London zu fliegen. Genau diesen Hidden City Flug habe ich selbst schon gemacht und 200 Euro gespart. ;)

Diese beiden Strategien können sehr lukrativ sein und bereiten Flighthackern feuchte Träume. Leider findet unsere Millionen von Dollar teure Suche diese Strategien nicht, wir bräuchten eine Suche für Milliarden von Dollar!

Nochmal zur Erinnerung: Wir reden bisher nur von einem einfachen Hin- und Rückflug. Mit Multi City und Round the World Routings fangen wir lieber erst gar nicht an. Das wird richtig kompliziert und teuer. Wenn die Reihenfolge egal ist, lässt auch noch der Traveling Salesman grüssen!

Flug Buchen ist nicht gleich Flug Suchen

Eine Suche für ne Billion Dollar muss richtig gut sein, oder? Liefert die denn wenigstens den günstigsten Flug? Nein, so einfach ist das leider nicht!

Nach der Billionen Dollar Suche müsstest Du immer noch schauen, bei welchem Anbieter der gefundene Flug am günstigsten ist, in welcher Währung, von welchem „Wohnort“ aus, usw…

Es kann gut sein, dass Dein günstigster Flug gar nicht der günstigste war, wenn Du die Flugbuchung berücksichtigst.

Und eines ist sicher:Es gibt noch mehr Details, von denen ich gar nicht weiß…

Geht das auch billiger?

Die Flugsuchmaschinen zahlen keine $0,035 USD pro Anfrage, das ist der Preis für Dich und mich. Aber selbst wenn Suchmaschinen nur einen winzig kleinen Bruchteil davon zahlen müssen, wäre eine vollständige Suche immer noch viel zu teuer.

Flugsuchmaschinen haben Gewinnmargen im zweistelligen Dollar-Bereich und wahrscheinlich führen nur wenige Prozent von Flugsuchen zu einer Buchung, wenn überhaupt.

Warum kosten Flugsuchen überhaupt Geld? Weil es möglich ist dafür Geld zu verlangen! Unternehmen wie ITA und die 3 großen GDS machen Geld damit Flugsuche Ergebnisse an Flugsuchmaschinen und OTAs zu verkaufen und zwar auf Transaktions-Basis.

Selbst für diese Unternehmen, die an der Quelle sitzen, sind Flugsuchen nicht umsonst. Auch ITA zahlt für jede Flugsuche aus dem einfachen Grund, weil Flugsuchen ungeheuer aufwendig sind. Es gibt z.B. zwischen San Francisco und Boston 162.006 verschiedene Routings, die Sinn machen!

Es ist sogar so, dass eine Flugsuche mathematisch nicht entscheidbar ist. Das heißt es gibt keine Algorithmen, die terminieren. Es gibt nur Heuristiken, was natürlich gefährlich ist in punkto vollständiger Suche.

Noch dazu sind die Preisstrukturen der Airlines äußerst kompliziert, um möglichst viel Preisdiskriminierung zu betreiben. Zwischen Boston und San Francisco sind 2.389.402.117 verschiedene Preisstrukturen möglich.

Die Preisfindung allein ist NP-vollständig, die Routenfindung ist nochmal NP-vollständig, flexible Suchen sind nochmal NP-vollständig.

Wenn Dich die Komplexität von Flugsuchen interessiert, lies dieses interessante Rechenbeispiel von ITA oder schau gleich in das Paper Computational Complexity of Air Travel Planning von ITA Software. Super gemacht ist außerdem dieser Talk von einem Google (ITA) Ingenieur.

Nerd fact am Rande: Die Matrix ist in Lisp geschrieben. Warum Lisp? Siehe Paul Graham’s Essay Beating the Averages.

Ein weniger naives Verfahren?

Mit Brute Force alle Permutationen zu durchsuchen ist natürlich ein ungeheuer naives Verfahren. Sicher gibt es ein schlaueres Vorgehen, dass die Anzahl der sinnvollen Permutationen senkt. Denkbar wäre es vielleicht Routings auszuschließen, die immer dominiert werden oder vielleicht lässt sich aus den Fare-Buckets-Regeln ein Trend herleiten.

Eine sehr gute Möglichkeit weniger naiv suchen, wäre sicher über die Periodizität. Viele Verbindungen wiederholen sich täglich oder zumindest wöchentlich. Damit kannst Du Dir die Suche eines Routings bei einer zeitflexiblen Suche ab der ersten Wiederholung sparen. Es wäre sogar möglich die Routings für zukünftige Suchen zu speichern und nur dann zu aktualisieren, wenn sich Flugpläne ändern.

Du musst aber trotzdem noch die aktuelle Auslastung abfragen und mit Hilfe von aktuellen Fare-Buckets den Preis berechnen. Das ist wie erwähnt immer noch ein erheblicher Teil des Gesamtaufwands. Die Preisregeln sind angeblich Turing-vollständig!

ITA umschifft dieses Problem teilweise, indem sie Push-Updates nutzen zur Synchronisation und nur einmal am Tag einen kompletten Abgleich machen.

Alle Optimierungen über Fare-Buckets sind so weit ich weiß ITA und den GDS vorbehalten. Wir Normalsterbliche und auch die Suchmaschinen kommen gar nicht automatisiert über eine API an die Auslastungen, ohne eine vollständige Suchanfrage zu stellen, die wieder teuer ist.

Du kannst natürlich immer noch die Matrix scrapen, was wohl auch von vielen Leuten gemacht wird. Webscraper sind angeblich der Grund für die vielen Fehlermeldungen und Performance-Schwächen, die die Matrix in jüngster Vergangenheit zeigt.

Fazit: Lass für Dich suchen

Eine vollständigere Suche als heute wäre schon denkbar, aber nur wenn Du an der Quelle sitzt. ITA kann das machen und die GDS können das machen. Die GDS arbeiten angeblich mit veraltetem Code aus der Mainframe-Zeit und noch viel löchrigeren Heuristiken und können das vielleicht doch nicht machen ;)

Alle Suchmaschinen, die nicht an ein GDS oder an ITA angegliedert sind, können das auf keinen Fall machen, denn sie zahlen pro Transaktion. Die Suchmaschinen können sich eine vollständige Suche nicht leisten, weil die Kosten exponentiell wachsen.

Flugsuchmaschinen zeigen Dir deswegen auch nur einen kleinen Bruchteil der sinnvollen Verbindungen an, außer Du suchst gezielt nach einer einzelnen Verbindung. Bei einer flexiblen Suche siehst Du nur ganz wenige Verbindungen, deren Preise gecached, also womöglich veraltet sind.

Deswegen ist es eine gute Idee Experten suchen zu lassen, die zumindest aus Erfahrung wissen, nach welcher Nadel im Heuhaufen sie suchen müssen.

P.S.
Dieser Text ist eine Vereinfachung von viel komplexeren Tatsachen. Es geht um’s Prinzip, nicht um die Nachkommastelle oder gar Vorkommastelle. Das Prinzip ist: Alle Suchmaschinen cachen alte Suchanfragen und eine flexible Suche läuft nur über diesen Cache, weil Suchanfragen teuer sind.