Uber: Overview of Key Platform Management Algorithms

1. Introduction

Online passenger transportation platforms, such as Uber, DiDi and Yandex, arose quite recently, while they quickly reached impressive sizes and, despite their small age, significantly modified and supplemented the city transport system. The technologies and theoretical models used by these platforms (or developed for them) are currently an area of ​​active research for a wide range of specialists in the scientific community: economists, mathematicians, programmers and engineers.

In this article, we (as representatives of the Uber Marketplace Optimization team) briefly present an inside look at the main levers of managing the effectiveness of online platforms: algorithms responsible for dispatching decisions (matching), dynamic pricing, and also introduce one of the new concepts - dynamic time of appointment of the car (dynamic waiting). Based on actual practical experience, we will show that all three algorithms play an important role in creating a system with high performance and low waiting times for orders for both passengers and drivers.

The presented description of the algorithms will be exploratory in nature and intentionally devoid of technical depth and rigor. An interested reader is invited to study the original article (Dynamic Pricing and Matching in Ride-Hailing Platforms - N. Korolko , D.Woodard, C.Yan, H.Zhu - 2019), published by researchers from the Uber Marketplace department, based on which this short introductory review was created.

2. Description of the main algorithms

Over the past decade, the transportation industry has been growing rapidly thanks to new conceptual ideas and technologies, such as online passenger transportation platforms, the development of self-driving cars and electric cars. The synergy of these technologies, which many companies and laboratories are working at the same time, promises a huge breakthrough in reducing the unit cost of passenger transportation, not less than 10 times over a couple of decades.

The most explosive growth from this list of technologies is currently demonstrated by online passenger transportation platforms. For example, over 10 years of its existence, Uber has generated more than 10 billion trips to more than 80 countries and 700 cities around the world [Figure 1]. The global market for such online transport promises to reach an incredible size of $ 285 billion by 2030. Therefore, it is not surprising that the effectiveness of such platforms that dynamically control the bilateral market of passengers and drivers is of great practical importance.



Empirical studies show that automated algorithms for data processing, routing, pricing and ordering allow online platforms to achieve a higher utilization of drivers' working hours and shorter passenger waiting times compared to the classic taxi service. Moreover, these two key characteristics of the system (utilization of driver’s time and passenger waiting time) are closely related to the reliability and stability of the service: sudden local outbreaks of demand (for example, at the end of a major concert or on New Year’s Eve) can significantly worsen both metrics, thereby making use of service unattractive for both sides of the market. This is due to the fact that drivers on the line in the high demand zone quickly receive a small part of the total number of orders, and for the rest of the orders, drivers from remote areas are assigned. This increases the car delivery time, which is most often not paid to the driver (and therefore reduces his earnings per unit time), and at the same time forms a negative impression on the passenger. Thus, both parties using the platform begin to use it less. Because of this, both metrics begin to deteriorate even more, thereby spinning the downward spiral of platform performance in the direction of zero efficiency. In English literature, this negative phenomenon is called the Wild Goose Chase (WGC), the literal translation of which is “the pursuit of the wild goose”. and at the same time forms a negative impression on the passenger. Thus, both parties using the platform begin to use it less. Because of this, both metrics begin to deteriorate even more, thereby spinning the downward spiral of platform performance in the direction of zero efficiency. In English literature, this negative phenomenon is called the Wild Goose Chase (WGC), the literal translation of which is “the pursuit of the wild goose”. and at the same time forms a negative impression on the passenger. Thus, both parties using the platform begin to use it less. Because of this, both metrics begin to deteriorate even more, thereby spinning the downward spiral of platform performance in the direction of zero efficiency. In English literature, this negative phenomenon is called the Wild Goose Chase (WGC), the literal translation of which is “the pursuit of the wild goose”.

Two key technologies aimed at increasing the stability and productivity of the platform are the algorithms of distribution of orders and dynamic pricing. The first technology controls dispatch decisions, and dynamic real-time pricing balances the extremely volatile supply-demand ratio for passenger transportation. Dynamic pricing is critical to maintaining the system’s performance, reducing the waiting time for a car, and increasing the number of drivers during periods of high demand. Moreover, empirical and theoretical studies show that dynamic pricing can reduce the scale of the pathologically dangerous effect of WGC.

2.1 Algorithms for the distribution of orders (matching)

The simplest dispatching algorithm for assigning a driver to order is the so-called first-dispatch protocol. Despite its simplicity and good practical performance indicators, it is easy to show that this algorithm is ineffective in a large number of frequently occurring situations. First, he selects a driver only from that subset of drivers who are free at the time of order, ignoring those drivers who may be close to completing a trip in the immediate vicinity of a new order [Figure 4]. Secondly, this simple algorithm takes into account only information about the system in a given period of time, while most often the platform can be provided with sufficiently accurate information about what will happen with the flow of orders and the spatial distribution of drivers in the near future.



Another popular family of dispatch algorithms is based on the idea of ​​combining a group of travel orders within a short time interval and solving the aggregated optimization problem of pairwise assignment. In other words, instead of instantly and sequentially assigning a car to each individual order, the system collects information about incoming orders and distributes the accumulated orders among the drivers on the line with some frequency. If some orders are left without a designated driver, then they remain in the system and participate in the task of distributing the next time step. The objective function of the optimization problem solved at each step may include a wide range of metrics characterizing the quality of the generated dispatch appointments: passenger waiting time for the car,

In practice, dispatching algorithms look much more complicated, since they must take into account a large number of features of different products that are simultaneously presented in the application interface. For example, cars registered on the platform can be of different classes of comfort and of different capacities. Some products of online platforms involve the simultaneous use of one car by different passengers (UberPool, Lyft Line), in the event that their routes are close enough. Moreover, dispatching decisions often must take into account the preferences of drivers in service areas and the directions of orders received by them. Thus, the range of emerging optimization problems aimed at improving the efficiency of dispatching solutions, which also need to be solved in real time,

2.2 Dynamic pricing algorithms

One of the main operational difficulties of managing an online passenger transportation platform is the volume of supply and demand for taxi services that are constantly changing in space and time. The figure below [Figure 5] shows the ratio of the number of online travel requests from passengers and the number of hours that drivers spent on the line for two areas of San Francisco: the financial center and the residential sleeping area on the outskirts of the city. This graph illustrates well the high volatility and lack of balance between supply and demand (the ratio of which can sometimes take extremely high values), as well as the diversity of the behavior of this balance depending on the geographical location.



In order to control the balance of supply and demand in space and time, online platforms use dynamic pricing algorithms that increase the basic rate in real time if the number of orders received from passengers significantly exceeds the number of free drivers. The benefits of dynamic pricing to maintain stable platform performance are supported by a large number of theoretical models, experiments, and empirical observations associated with record-high system loads. Such loads can happen due to a large number of predictable and not very reasons: adverse weather conditions, public events, malfunctioning public transport system, etc. In case of incorrect operation of the pricing algorithm, with a sharp increase in the number of requests from passengers (or with a sharp decrease in the number of cars available), one can observe a very low proportion of passengers to whom the car is assigned and an unsatisfactory high time for its submission. The key role of dynamic pricing for an online platform is to enable any user anywhere and at any time to call a taxi. Even if the proposed tariff is higher than usual, it will be a more favorable option than informing the platform user (who may urgently need a car) that there are currently no available machines. to which the car is finally assigned and the unsatisfactory high time of its submission. The key role of dynamic pricing for an online platform is to enable any user anywhere and at any time to call a taxi. Even if the proposed tariff is higher than usual, it will be a more favorable option than informing the platform user (who may urgently need a car) that there are currently no available machines. to which the car is finally assigned and the unsatisfactory high time of its submission. The key role of dynamic pricing for an online platform is to enable any user anywhere and at any time to call a taxi. Even if the proposed tariff is higher than usual, it will be a more favorable option than informing the platform user (who may urgently need a car) that there are currently no available machines.

Popular methods for modeling dynamic pricing include economic models that describe the steady-state models, dynamic programming models, regression analysis, and optimization models that describe network optimization. Recent studies by economists (Castillo, 2017) showed that a dynamic tariff increase also allows the platform to avoid getting into the zone of the negative effect of WGC, which we talked about above.

Dynamic pricing has objective flaws. Firstly, the final price of the trip, which passengers see when ordering a taxi, can vary significantly due to the volatility of supply and demand, thereby increasing the unpredictability of the fare on the same route. On the other hand, drivers of online platforms often have access to information in the application about those areas of the city where the increase factor is active. However, due to the high volatility of this coefficient, by the time the driver moves to the zone of higher prices, the tariff may return to baseline values. Moreover, an automatic tariff increase by the algorithm can encourage drivers to cooperate and artificially create in the local market a situation of shortage of cars available for ordering, thereby activating increasing coefficients for trips.

2.3 Dynamic waiting time of the car (Dynamic waiting)

To avoid problems associated with dynamic pricing, in practice, other algorithms are used to balance supply and demand, as well as to avoid getting the system into the zone of the WGC effect. These include the idea of ​​limiting the maximum distance between the order and the assigned driver (Maximum Dispatch Radius), as well as the formation of a queue of travel orders (queueing) received in the system, replacing the instant appointment of the driver for each order.

A newer concept aimed at replacing or supplementing a dynamic increase in prices is the mechanism for dynamically controlling the time to wait before assigning a car (dynamic waiting). One of the options for this mechanism is used in the Express Pool product, recently launched by Uber in some large markets. This type of passenger transportation is characterized by the lowest possible tariffs and implies the simultaneous use of a single car by several independent passengers for traveling along the way.

The general idea of ​​the dynamic appointment time mechanism is as follows. For a passenger ordering a trip, the application does not immediately appoint a driver, but offers to wait, but no more than a certain amount of time indicated ahead (typical upper bounds are 2 or 5 minutes). Moreover, the driver’s appointment can occur at any time convenient for the platform: from instant to the specified upper limit. In this case, the total passenger waiting time for the car consists of two (almost independent) parts: the time until the driver is appointed and the time from his appointment to arrival at the place of order. The inconvenience of waiting for a passenger is compensated by a lower fare.

On the platform side, an additional degree of freedom over the time drivers are assigned to orders is used as follows. Since the product involves the combination of orders and the appointment of one car for the simultaneous transportation of several passengers, the additional time to collect information allows you to increase the number of combinatorial options and as a result generate more efficient trips. In this case, the efficiency metric may be, for example, the proximity of the routes of passengers falling into one car. It is obvious that as soon as the platform finds a sufficiently highly effective combination of travel, it immediately makes the necessary driver's appointment and notifies all its participants. If a successful and convenient combination is not found, then the platform sends an individual driver to each of the passengers who made the order.

The described mechanism primarily optimizes dispatch decisions and the time when these decisions are made, and it can be used simultaneously with dynamic price optimization. The theoretical model developed and analyzed in the original of the main article demonstrates that the simultaneous optimization of prices and time has a large number of advantages: it can reduce tariff volatility, reduce the risks of the WGC effect, and also increase the total number of trips generated by the platform per unit time. Moreover, these transportation options are economically more beneficial both for drivers (who simultaneously receive several passengers paying for the trip), and for passengers (who receive a discount in exchange for flexibility with waiting time).

3. Conclusion

In this article, we briefly described the main optimization management tasks that solve online passenger transportation platforms to ensure stable operation and increase their efficiency. Such tasks include the construction of dispatch algorithms, dynamic pricing algorithms and the dynamic determination of driver appointment times. Simultaneous control of these levers allows achieving high rates of utilization of drivers' time, low waiting time for the car and the number of trips generated by the platform per unit time. The class of these tasks is constantly updated with new, increasingly realistic examples, opening wide horizons for theoretical and practical research.

All references to cited sources can be found in the original article (Dynamic Pricing and Matching in Ride-Hailing Platforms - N. Korolko , D.Woodard, C.Yan, H.Zhu - 2019).