Uber: Überblick über die wichtigsten Plattformverwaltungsalgorithmen

1. Einleitung

Online-Personenverkehrsplattformen wie Uber, DiDi und Yandex sind erst vor kurzem entstanden, haben jedoch schnell eine beeindruckende Größe erreicht und trotz ihres geringen Alters das städtische Verkehrssystem erheblich verändert und ergänzt. Die Technologien und theoretischen Modelle, die von diesen Plattformen verwendet (oder für sie entwickelt) werden, sind derzeit ein Bereich aktiver Forschung für eine breite Palette von Spezialisten in der wissenschaftlichen Gemeinschaft: Ökonomen, Mathematiker, Programmierer und Ingenieure.

In diesem Artikel werden wir (als Vertreter des Uber Marketplace Optimization-Teams) kurz einen Einblick in die wichtigsten Hebel für die Verwaltung der Effektivität von Online-Plattformen geben: Algorithmen, die für den Versand von Entscheidungen (Matching) verantwortlich sind, dynamische Preisgestaltung und eines der neuen Konzepte - dynamische Zeit der Ernennung des Autos (dynamisches Warten). Basierend auf den tatsächlichen praktischen Erfahrungen werden wir zeigen, dass alle drei Algorithmen eine wichtige Rolle bei der Schaffung eines Systems mit hoher Leistung und geringen Wartezeiten für Bestellungen für Passagiere und Fahrer spielen.

Die vorgestellte Beschreibung der Algorithmen ist explorativer Natur und absichtlich ohne technische Tiefe und Genauigkeit. Ein interessierter Leser ist eingeladen, den Originalartikel ( Dynamische Preisgestaltung und Matching in Ride-Hailing-Plattformen - N. Korolko , D. Woodard , C. Yan , H. Zhu - 2019) zu studieren, der von Forschern des Uber Marketplace veröffentlicht wurde und auf dem diese kurze Einführung basiert und erstellt.

2. Beschreibung der Hauptalgorithmen

In den letzten zehn Jahren ist die Branche der Transportlösungen dank neuer konzeptioneller Ideen und Technologien wie Online-Plattformen für den Personenverkehr, der Entwicklung selbstfahrender Autos und Elektroautos rasant gewachsen. Die Synergie dieser Technologien, an der viele Unternehmen und Labors gleichzeitig arbeiten, verspricht einen großen Durchbruch bei der Reduzierung der Stückkosten des Personenverkehrs, nicht weniger als das Zehnfache über ein paar Jahrzehnte.

Das explosivste Wachstum dieser Technologieliste wird derzeit von Online-Personenbeförderungsplattformen gezeigt. Zum Beispiel hat Uber in seinem 10-jährigen Bestehen über 10 Milliarden Reisen in mehr als 80 Ländern und 700 Städten auf der ganzen Welt durchgeführt [Abbildung 1]. Der weltweite Markt für solche Online-Transporte verspricht, bis 2030 eine unglaubliche Größe von 285 Milliarden US-Dollar zu erreichen. Daher ist es nicht verwunderlich, dass die Wirksamkeit solcher Plattformen, die den bilateralen Markt für Fahrgäste und Fahrer dynamisch steuern, von großer praktischer Bedeutung ist.



Empirische Studien zeigen, dass automatisierte Algorithmen für Datenverarbeitung, Routing, Preisgestaltung und Bestellung Online-Plattformen eine höhere Auslastung der Arbeitszeiten der Fahrer und kürzere Wartezeiten für Fahrgäste ermöglichen als ein klassischer Taxidienst. Darüber hinaus hängen diese beiden Schlüsselmerkmale des Systems (Nutzung der Fahrerzeit und der Wartezeit der Fahrgäste) eng mit der Zuverlässigkeit und Stabilität des Dienstes zusammen: Plötzliche lokale Nachfrageausbrüche (z. B. am Ende eines großen Konzerts oder am Silvesterabend) können beide Messgrößen erheblich verschlechtern und nutzen Service für beide Seiten des Marktes unattraktiv. Dies liegt an der Tatsache, dass Fahrer auf der Linie in der Zone mit hoher Nachfrage schnell einen kleinen Teil der Gesamtzahl der Bestellungen erhalten und Fahrer aus abgelegenen Gebieten dem verbleibenden Teil der Bestellungen zugewiesen werden. Dies erhöht die Lieferzeit des Autos, die meist nicht an den Fahrer gezahlt wird (und damit sein Einkommen pro Zeiteinheit verringert) und wirkt sich gleichzeitig negativ auf den Fahrgast aus. Daher nutzen beide Parteien, die die Plattform nutzen, diese weniger. Aus diesem Grund beginnen sich beide Metriken noch weiter zu verschlechtern, wodurch sich die Abwärtsspirale der Plattformleistung in Richtung Null-Effizienz dreht. In der englischen Literatur wird dieses negative Phänomen als Wild Goose Chase (WGC) bezeichnet, dessen wörtliche Übersetzung „das Streben nach der Wildgans“ lautet.

Zwei Schlüsseltechnologien zur Steigerung der Stabilität und Produktivität der Plattform sind die Algorithmen zur Auftragsverteilung und zur dynamischen Preisgestaltung. Die erste Technologie steuert Versandentscheidungen und dynamische Preisgestaltung in Echtzeit gleicht das äußerst volatile Verhältnis von Angebot und Nachfrage für den Personenverkehr aus. Die dynamische Preisgestaltung ist entscheidend, um die Leistung des Systems aufrechtzuerhalten, die Wartezeit für ein Auto zu verkürzen und die Anzahl der Fahrer in Zeiten hoher Nachfrage zu erhöhen. Darüber hinaus zeigen empirische und theoretische Studien, dass eine dynamische Preisgestaltung das Ausmaß der pathologisch gefährlichen Wirkung von WGC verringern kann.

2.1 Algorithmen zur Auftragsverteilung (Matching)

Der einfachste Versandalgorithmus zum Zuweisen eines Treibers zur Bestellung ist das sogenannte Erstversandprotokoll. Trotz seiner Einfachheit und guten praktischen Leistungsindikatoren ist es leicht zu zeigen, dass dieser Algorithmus in einer großen Anzahl häufig auftretender Situationen unwirksam ist. Erstens wählt er einen Fahrer nur aus dieser Untergruppe von Fahrern aus, die zum Zeitpunkt der Bestellung frei sind, und ignoriert diejenigen Fahrer, die kurz davor stehen, eine Fahrt in unmittelbarer Nähe einer neuen Bestellung abzuschließen [Abbildung 4]. Zweitens berücksichtigt dieser einfache Algorithmus nur Informationen über das System in einem bestimmten Zeitraum, während die Plattform in den meisten Fällen ausreichend genaue Informationen darüber erhalten kann, was in naher Zukunft mit dem Auftragsfluss und der räumlichen Verteilung der Fahrer geschehen wird. In der Literatur wird eine Klasse ähnlicher Aufgaben mit praktischen Rezepten, wie solche Informationen zur Verbesserung der Qualität des Algorithmus verwendet werden können, als "K-Server-Problem" bezeichnet.



Eine weitere beliebte Familie von Versandalgorithmen basiert auf der Idee, eine Gruppe von Reiseaufträgen innerhalb eines kurzen Zeitintervalls zu kombinieren und das aggregierte Optimierungsproblem der paarweisen Zuordnung zu lösen. Mit anderen Worten, anstatt jeder einzelnen Bestellung sofort und nacheinander ein Auto zuzuweisen, sammelt das System Informationen über eingehende Bestellungen und verteilt die akkumulierten Bestellungen mit einer gewissen Häufigkeit unter den Fahrern auf der Linie. Wenn einige Bestellungen ohne einen bestimmten Treiber verbleiben, verbleiben sie im System und nehmen an der Aufgabe teil, den nächsten Zeitschritt zu verteilen. Die Zielfunktion des Optimierungsproblems, das bei jedem Schritt gelöst wird, kann eine breite Palette von Metriken umfassen, die die Qualität der generierten Versandtermine charakterisieren: Wartezeit des Fahrgastes für das Auto, Entfernung zwischen der Bestellung und dem benannten Fahrer, Wahrscheinlichkeit der Stornierung der Bestellung durch den Fahrgast oder Fahrer usw.

In der Praxis sehen Dispatching-Algorithmen viel komplizierter aus, da sie eine Vielzahl von Merkmalen verschiedener Produkte berücksichtigen müssen, die gleichzeitig in der Anwendungsoberfläche dargestellt werden. Beispielsweise können auf der Plattform registrierte Autos unterschiedliche Komfortklassen und Kapazitäten aufweisen. Einige Produkte von Online-Plattformen implizieren die gleichzeitige Nutzung eines Autos durch verschiedene Passagiere (UberPool, Lyft Line), wenn ihre Routen ziemlich eng sind. Darüber hinaus müssen Versandentscheidungen häufig die Präferenzen der Fahrer für Servicebereiche und die Anweisungen der bei ihnen eingegangenen Bestellungen berücksichtigen. Daher wird das Spektrum der Optimierungsprobleme, die zur Steigerung der Effizienz von Versandentscheidungen auftreten und auch in Echtzeit gelöst werden müssen, kontinuierlich mit neuen, immer komplexer werdenden Formulierungen aktualisiert.

2.2 Dynamische Preisalgorithmen

Eine der wichtigsten betrieblichen Schwierigkeiten bei der Verwaltung der Online-Plattform für den Personenverkehr ist das Volumen von Angebot und Nachfrage nach Taxidiensten, die sich räumlich und zeitlich ständig ändern. Die folgende Abbildung [Abbildung 5] zeigt das Verhältnis der Anzahl der Online-Reiseanfragen von Passagieren zur Anzahl der Stunden, die Fahrer in zwei Bereichen von San Francisco auf der Strecke verbracht haben: dem Finanzzentrum und dem Wohnschlafbereich am Stadtrand. Diese Grafik zeigt gut die hohe Volatilität und das mangelnde Gleichgewicht zwischen Angebot und Nachfrage (deren Verhältnis manchmal extrem hohe Werte annehmen kann) sowie die Verschiedenartigkeit des Verhaltens dieses Gleichgewichts in Abhängigkeit vom geografischen Standort.



Um das Gleichgewicht zwischen Angebot und Nachfrage in Raum und Zeit zu kontrollieren, verwenden Online-Plattformen dynamische Preisalgorithmen, die den Grundpreis in Echtzeit erhöhen, wenn die Anzahl der Bestellungen von Passagieren die Anzahl der Freifahrer erheblich übersteigt. Die Vorteile einer dynamischen Preisgestaltung zur Aufrechterhaltung einer stabilen Plattformleistung werden durch eine Vielzahl theoretischer Modelle, Experimente und empirischer Beobachtungen im Zusammenhang mit rekordhohen Systemlasten unterstützt. Solche Belastungen können aus einer Vielzahl vorhersehbarer und nicht sehr wichtiger Gründe auftreten: widrige Wetterbedingungen, öffentliche Ereignisse, fehlerhafte öffentliche Verkehrsmittel usw. Bei fehlerhafter Funktionsweise des Preisalgorithmus, mit einem starken Anstieg der Anzahl der Anfragen von Passagieren (oder mit einem starken Rückgang der Anzahl verfügbarer Autos) können Sie einen sehr geringen Anteil der Passagiere beobachten, denen das Auto als Ergebnis zugewiesen wurde, und die unbefriedigend hohe Zeit seiner Einreichung. Die Schlüsselrolle der dynamischen Preisgestaltung für eine Online-Plattform besteht darin, dass jeder Benutzer überall und jederzeit ein Taxi rufen kann. Selbst wenn der vorgeschlagene Tarif höher als üblich ist, ist dies eine günstigere Option, als den Plattformbenutzer (der möglicherweise dringend ein Auto benötigt) darüber zu informieren, dass derzeit keine Maschinen verfügbar sind.

Beliebte dynamische Preismodellierungsmethoden umfassen Wirtschaftsmodelle, die die stationären Modelle beschreiben, dynamische Programmiermodelle, Regressionsanalysen und Optimierungsmodelle, die Netzwerkeffekte beschreiben. Jüngste Studien von Wirtschaftswissenschaftlern (Castillo, 2017) haben gezeigt, dass eine dynamische Tariferhöhung es der Plattform auch ermöglicht, nicht in die Zone der negativen Auswirkungen von WGC zu fallen, über die wir oben gesprochen haben.

Dynamische Preisgestaltung weist objektive Mängel auf. Erstens kann der Endpreis einer Reise, den Passagiere bei der Bestellung eines Taxis sehen, aufgrund der Volatilität von Angebot und Nachfrage erheblich variieren, wodurch die Unvorhersehbarkeit des Fahrpreises auf derselben Route erhöht wird. Auf der anderen Seite haben Fahrer von Online-Plattformen häufig Zugriff auf Informationen in der Anwendung über die Bereiche der Stadt, in denen der Erhöhungsfaktor aktiv ist. Aufgrund der hohen Volatilität dieses Koeffizienten kann der Tarif jedoch zu den Basiswerten zurückkehren, wenn der Fahrer in die Zone höherer Preise wechselt. Darüber hinaus kann eine automatische Tariferhöhung durch den Algorithmus die Fahrer dazu ermutigen, auf dem lokalen Markt zusammenzuarbeiten und künstlich eine Situation des Mangels an bestellbaren Autos zu schaffen, wodurch zunehmende Koeffizienten für Fahrten aktiviert werden. Natürlich ist ein derart koordiniertes Verhalten der Fahrer für Plattformen, die eine große Menge von Bestelldaten verarbeiten und die erforderlichen Schutzmaßnahmen ergreifen, nicht schwer zu erkennen, aber für Fahrgäste kann eine solche Erfahrung mit künstlich hohen Preisen unbefriedigend sein.

2.3 Dynamische Wartezeit des Autos (Dynamisches Warten)

Um Probleme im Zusammenhang mit der dynamischen Preisgestaltung zu vermeiden, werden in der Praxis andere Algorithmen verwendet, um Angebot und Nachfrage in Einklang zu bringen und um zu vermeiden, dass das System in die Zone des WGC-Effekts gerät. Dazu gehören die Idee, die maximale Entfernung zwischen der Bestellung und dem bestellten Fahrer zu begrenzen (maximaler Versandradius) sowie die Bildung einer Warteschlange für im System empfangene Reiseaufträge (Warteschlange), die die sofortige Ernennung des Fahrers für jede Bestellung ersetzt.

Ein neueres Konzept, das darauf abzielt, einen dynamischen Preisanstieg zu ersetzen oder zu ergänzen, ist der Mechanismus zur dynamischen Steuerung der Wartezeit vor der Zuweisung eines Autos (dynamisches Warten). Eine Variante dieses Mechanismus wird in dem Express Pool-Produkt verwendet, das Uber kürzlich in einigen großen Märkten eingeführt hat. Diese Art der Personenbeförderung zeichnet sich durch niedrigstmögliche Tarife aus und impliziert die gleichzeitige Nutzung eines einzelnen Wagens durch mehrere unabhängige Fahrgäste für die Fahrt auf dem Weg.

Die allgemeine Idee des dynamischen Zielzeitmechanismus ist wie folgt. Für einen Passagier, der eine Reise bestellt, ernennt die Anwendung nicht sofort einen Fahrer, sondern bietet an zu warten, jedoch nicht mehr als eine bestimmte im Voraus angegebene Zeitspanne (typische Obergrenzen sind 2 oder 5 Minuten). Darüber hinaus kann die Ernennung des Fahrers jederzeit für die Plattform günstig erfolgen: vom Augenblick bis zur festgelegten Obergrenze. In diesem Fall besteht die gesamte Wartezeit des Fahrgastes für das Fahrzeug aus zwei (fast unabhängigen) Teilen: der Zeit bis zur Ernennung des Fahrers und der Zeit von seiner Ernennung bis zur Ankunft am Bestellort. Die Unannehmlichkeit, auf einen Passagier zu warten, wird durch einen niedrigeren Tarif ausgeglichen.

Auf der Plattformseite wird ein zusätzlicher Freiheitsgrad über die Zeit, in der Treiber Aufträgen zugewiesen werden, wie folgt verwendet. Da das Produkt die Kombination von Bestellungen und die Ernennung eines Autos für den gleichzeitigen Transport mehrerer Passagiere umfasst, können Sie durch die zusätzliche Zeit zum Sammeln von Informationen die Anzahl der kombinatorischen Optionen erhöhen und dadurch effizientere Fahrten generieren. In diesem Fall kann die Effizienzmetrik beispielsweise die Nähe der Routen von Passagieren sein, die in ein Auto fallen. Sobald die Plattform eine ausreichend hochwirksame Kombination von Reisen findet, trifft sie natürlich sofort den erforderlichen Fahrertermin und benachrichtigt alle ihre Teilnehmer. Wird keine erfolgreiche und bequeme Kombination gefunden, sendet die Plattform einen einzelnen Fahrer an jeden der Passagiere, die die Bestellung aufgegeben haben.

Der beschriebene Mechanismus optimiert in erster Linie Versandentscheidungen und den Zeitpunkt, zu dem diese Entscheidungen getroffen werden, und kann gleichzeitig mit der dynamischen Preisoptimierung verwendet werden. Das im Original des Hauptartikels entwickelte und analysierte theoretische Modell zeigt, dass die gleichzeitige Optimierung von Preisen und Zeit eine Vielzahl von Vorteilen hat: Es kann die Tarifvolatilität verringern, die Risiken des WGC-Effekts verringern und auch die Gesamtzahl der von der Plattform pro Zeiteinheit generierten Fahrten erhöhen. Darüber hinaus sind diese Transportmöglichkeiten sowohl für Fahrer (die gleichzeitig mehrere Passagiere empfangen, die für die Reise bezahlen) als auch für Passagiere (die im Austausch für Flexibilität bei der Wartezeit einen Rabatt erhalten) wirtschaftlicher.

3. Fazit

In diesem Artikel haben wir kurz die wichtigsten Aufgaben des Optimierungsmanagements beschrieben, mit denen Online-Personenbeförderungsplattformen gelöst werden, um einen stabilen Betrieb sicherzustellen und deren Effizienz zu steigern. Solche Aufgaben umfassen die Konstruktion von Versandalgorithmen, dynamischen Preisalgorithmen und die dynamische Bestimmung von Fahrerterminzeiten. Die gleichzeitige Steuerung dieser Hebel ermöglicht eine hohe Auslastung der Fahrerzeit, eine geringe Wartezeit für das Auto und die Anzahl der von der Plattform pro Zeiteinheit erzeugten Fahrten. Die Klasse dieser Aufgaben wird ständig mit neuen, zunehmend realistischen Beispielen aktualisiert, die einen weiten Horizont für theoretische und praktische Forschung eröffnen.

Alle Verweise auf zitierte Quellen finden sich im Originalartikel ( Dynamische Preisgestaltung und Matching in Ride-Hailing-Plattformen - N. Korolko , D. Woodard, C. Yan, H. Zhu - 2019).