Uber: Overview of the main platform control algorithms

1. Introduction

Online passenger transport platforms such as Uber, DiDi and Yandex have emerged quite recently, while they quickly reached impressive sizes and, despite their small age, significantly altered and supplemented the urban transport system. The technologies and theoretical models used by these platforms (or being 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 insider look at the main levers of performance management of online platforms: algorithms responsible for dispatching solutions (matching), dynamic pricing (dynamic pricing), and also present one of the new concepts - dynamic vehicle assignment time (dynamic waiting). Based on real 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 introductory in nature and deliberately 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 brief introductory review and created.

2. Description of the main algorithms

Over the past decade, the transport solutions industry has been developing at a rapid pace thanks to new conceptual ideas and technologies, such as the online platform for passenger transportation, the development of self-driving cars and electric cars. The synergy of these technologies, which many companies and laboratories simultaneously work on, promises a huge breakthrough in reducing the unit cost of passenger transportation by a factor of 10 times over a couple of decades.
')
The most explosive growth from this list of technologies is currently demonstrated by the online platform for passenger traffic. For example, the Uber company for 10 years of its existence 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 shipments promises to reach an incredible size of $ 285 billion by 2030. It is therefore not surprising that the effectiveness of such platforms, which dynamically control the two-way passenger and driver market, is of great practical importance.



Empirical studies show that automated algorithms for data processing, routing, pricing and order assignment allow online platforms to achieve a higher utilization of drivers' working time and less long waiting times for a car by passengers compared to the classic taxi service. Moreover, these two key characteristics of the system (driver time utilization and passenger waiting time) are closely related to service reliability and sustainability: sudden local outbreaks of demand (for example, at the end of a large concert or on the eve of the New Year) can significantly worsen both metrics, thus making use of The service is 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 drivers from remote areas are assigned to the rest of the orders. This increases the time of the car, which is often not paid to the driver (and therefore reduces his earnings per unit time), and at the same time creates a negative impression on the passenger. Thus, both parties using the platform begin to use less of it. Because of this, both metrics begin to deteriorate even more, thereby twisting the downward spiral of platform performance in the direction of zero efficiency. In the English-language literature, this negative phenomenon is called Wild Goose Chase (WGC), the literal translation of which is “the pursuit of a wild goose”.

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

2.1 Algorithms for the distribution of orders (matching)

The simplest dispatch 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 chooses a driver only from the subgroup of drivers who are free at the time of the order, ignoring those drivers who may be close to completing the trip in the immediate vicinity of the new order [Figure 4]. Secondly, this simple algorithm takes into account only information about the system in a given period of time, while more often the platform may have access to fairly accurate information about what will happen with the flow of orders and the spatial distribution of drivers in the near future. In the literature, a class of similar tasks that give practical recipes as such information can be used to improve the quality of the algorithm is called the “K-server problem”.



Another popular family of dispatch algorithms is based on the idea of ​​combining a group of travel orders within a small time interval and solving an aggregated optimization problem of pairwise assignment. In other words, instead of instantly and consistently assigning a car to each individual order, the system collects information about incoming orders and with some frequency distributes the accumulated orders between the drivers on the line. If some orders are left without a designated driver, 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 dispatcher-generated assignments: passenger waiting time, distance between the order and the designated driver, probability of canceling the order by the passenger or driver, and so on.

In practice, dispatching algorithms look much more complicated, since they must take into account the 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 comfort classes and different capacities. Some products of online platforms imply the simultaneous use of one car by different passengers (UberPool, Lyft Line), in the event that their routes are close enough. Moreover, dispatching solutions often have to take into account the preferences of drivers in service areas and the directions of incoming orders. Thus, the range of emerging optimization tasks aimed at improving the efficiency of dispatching solutions, which, moreover, must be solved in real time, is continuously updated with new and more complex formulations.

2.2 Algorithms dynamic pricing (Dynamic pricing)

One of the main operational difficulties of managing the online platform for passenger transportation is the continuously changing in space and time volumes of supply and demand for taxi services. 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 sleeping area of ​​Sunset on the outskirts of the city. This graph well illustrates the high volatility and the lack of a balance between supply and demand (the ratio of which can sometimes take extremely high values), as well as the diversity of 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 base fare in real time if the number of incoming orders from passengers significantly exceeds the number of free drivers. The benefits of dynamic pricing to maintain stable platform operation are confirmed by a large number of theoretical models, experiments, and empirical observations associated with record high loads on the system. Such loads can occur due to a large number of predictable and not very causes: adverse weather conditions, mass events, malfunctioning of the public transport system, and so on. 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 available cars), a very low proportion of passengers can be observed, to whom a car is ultimately assigned and the delivery time is not satisfactory. The key role of dynamic pricing for the online platform is to enable any user anywhere and at any time to call a taxi. Even if the proposed tariff will be higher than usual, it will be a more favorable option than to put the platform user (who may need a car urgently) aware that there are no available machines at the moment.

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

Dynamic pricing also has objective drawbacks. First, 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 annex about those areas of the city where the boost factor is active. However, due to the high volatility of this coefficient, by the time the driver moves to a higher price zone, the tariff may return to baseline values. Moreover, the automatic tariff increase by the algorithm can encourage drivers to cooperate and artificially create situations of shortage of cars available for ordering on the local market, thereby activating the increase rates for trips. Of course, such coordinated behavior of drivers is not difficult to detect for platforms that process a large amount of data on orders, and to take the necessary protective actions, but for passengers this experience of artificially high prices may be unsatisfactory.

2.3 Dynamic car appointment time (Dynamic waiting)

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

A new concept aimed at replacing or complementing dynamic price increases is the dynamic waiting time control mechanism. One variation of this mechanism is used in the Express Pool product, recently launched by Uber in some major markets. This type of passenger transportation is characterized by the lowest possible prices and implies the simultaneous use of one car by several independent passengers to make passing journeys.

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

On the platform side, an additional degree of freedom with the time that drivers are assigned to orders is used as follows. Since the product involves a combination of orders and the appointment of one vehicle 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 metric of efficiency may be, for example, the proximity of the routes of passengers entering into one car. Obviously, as soon as the platform finds a sufficiently high-performance combination of the trip, it immediately makes the necessary driver assignment and notifies all its participants. If the 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 main article demonstrates that the simultaneous optimization of prices and time has a large number of advantages: it reduces the volatility of tariffs, reduces the risks of the WGC effect, and also increases the total number of trips generated by the platform per time. Moreover, these transportation options are more cost-effective for both drivers (who simultaneously receive several passengers paying for the trip) and passengers (who receive a discount in exchange for flexibility with waiting times).

3. Conclusion

In this article, we briefly described the main optimization management problems that solve online passenger transport platforms to ensure stable operation and increase their efficiency. These tasks include the construction of dispatching algorithms, dynamic pricing algorithms and dynamic determination of the time of appointment of the driver. The simultaneous control of these levers allows us to achieve high rates of utilization of driver time, low car waiting time and the number of trips generated by the platform per unit of time. The class of these tasks is constantly updated with new, increasingly realistic examples, opening up broad 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).