Orange Girl Guide: When it comes to Didi's algorithm, you may feel both mysterious and curious. From the taxi call to the driver, the Drip platform grabs the order and finally goes to the platform to send the order. Everyone’s travel experience has already taken place. The change, facing tens of millions of calls every day, Didi's dispatch algorithm has been continuously trying to get more people to hit the car, this article will focus on how we analyze and model this problem, and this one What kind of algorithm challenges are faced, and introduce some of our commonly used dispatch algorithm, which allows us to continuously improve the user's taxi certainty.

1. Why do we need a better dispatch algorithm?

Speaking of Didi's dispatch algorithm, you may feel both mysterious and curious. From the call to the grab to the order, how did we evolve to today's taxi experience? Let's first take a look, good. Why is the dispatch algorithm an indispensable ability in the travel industry?

Recall that a few years ago, when we did not have Didi, we could only wait in the cold wind or the sweltering heat for a taxi that might or might not be available. Later, we could call a taxi from Didi, and passengers could go there. It is relatively comfortable to wait for the arrival of vehicles indoors. From online to offline, the certainty of passengers has been improved for the first time. However, this is not enough. , Didi launched its express train service. We have evolved from rushing orders to dispatching orders. The response rate of passengers has increased by more than 15 points. In many cases, it can be as high as 20+ throughout the day (peak & local tight supply and demand response rates will be relatively tight ), the certainty of passengers has once again been greatly improved. It can be seen that the dispatch mode has created huge user value for Didi.

Looking at the O2O business that has been booming in recent years, from the domestic and international network car companies, including our friends Uber, Lyft, based on the form of the product to carry out the transaction between the driver and the passenger, when Uber is listed The single engine is also placed in the prospectus as a core technical capability; looking at our domestic take-out platform, the strengths and weaknesses of the core dispatch system also determine the transaction efficiency (single-average distribution cost) and user experience (delivery duration) of the entire platform. In the end, the entire large logistics industry has been continuously undergoing online transformation in recent years. How to match goods and drivers, as well as better ability to spell together is also the key to the entire transaction link and whether the business model is established. From transporters to transporters, single engines are increasingly being used in real business and life.

2. A preliminary study on the issue of dispatching orders

Closer to home, here we also look at how the Drip Network car platform is how to send a single. First of all, let us look at what kind of problems we are facing?

"Order allocation is the process of allocating orders issued by passengers to online drivers in the order dispatch system"

This is a seemingly simple but actually very complicated issue. Speaking of this, many people may ask, can you just assign my order to the driver closest to me?

Indeed, in fact, the biggest principle of Didi's dispatch algorithm is “distribution nearby” (70%~80% orders are assigned to the nearest driver). As far as I know, other competing companies in the world. (including Uber), are also based on this principle. 

Let's take a closer look at this question. If we only distribute according to the nearest, first-come-first-served greedy strategy, can we best meet the demands of all passengers and drivers on the platform?The answer is no. The reason is that if we only make decisions based on the current moment and the current partial orders, we ignore the new orders and driver changes in the future, and we also ignore the needs of other areas adjacent to you or even the entire city. (Note: In terms of time sequence, the emergence of new drivers & orders will cause the greedy strategy to violate the target of the nearest distribution).This is why this problem is still very complicated.

It's a little bit abstract here, but it doesn't matter, let's take a step-by-step process to dispose of the order allocation problem so that everyone can have a better understanding:

To put it simply, on our platform, at each moment, there are N orders created by passengers, and there are M drivers that can be used for distribution. Our powerful platform can give the driver real-time performance for the dispatch algorithm. The geographic location coordinates, as well as the starting and ending positions of all orders, and tell us the real-time navigation distance of each driver received the order.

▍ If it is 1 orders, 1 drivers

It seems to be very simple, we just assign this order to this driver just fine.

"So why is there sometimes an empty car nearby that can't be assigned to you?"

The actual online system will be a little more complicated than this. The reason may be that the driver is just in the network, or is communicating with the customer service, etc., causing the driver to be unable to listen. On the other hand, the reason is that not all cars can you meet the service requirements of the order, the basic strategy is actually a set of filtering rules manually. Here are a few basic examples:

  • Rule A: Express driver can't pick up the car order
  • Rule B: to ensure that the driver does not take orders, limit line area by restricting the number of
  • Rule C: Filtering the non-shun area for the driver setting the real-time destination
  • Rule D: Filter real-time orders for listeners only
  • Rule E: The same order will only be issued to one driver once
  • ……

It must be clarified that the rules here do not create an unfair effect when ordering, but are completely set up for the normal operation of the business. These strategies bear the important responsibility of ensuring the correctness of the business.

▍ If it is 1 orders and 2 drivers

Assuming that both drivers are able to assign this order, let's see how the system should be allocated.

First of all, in the first case, at the same time, how should the system be allocated when the distance between the two drivers and the order is exactly the same?

Just said, we are the largest platform for order distribution principle is the nearest distribution, when exactly the same distance, the current system we will consider the merits of the main drivers of service points, service points higher driver will get to this order (Note: the impact of service points on the split order, a simple understanding can be converted into how many points can be replaced by the advantage of how many meters distance, this piece is not the focus of today will not be introduced), then explain, the system uses the map The navigation distance, not the straight-line distance that people can see intuitively, sometimes the distance between the intersections will be greatly different because of the need to turn around; and if the driver's positioning is problematic, there will be too far.

Then we look at the second situation, if the A driver is close, the B driver is far away, how is the system sent?

This simple, according to the principle of the nearest distribution, we will A driver assigned to this order. 嘿嘿~~, suppose we set the problem more practically. When the order is issued, the B driver is online and idle, but the A driver has not appeared (not on the line, or is still sending passengers), but after 1s, leaving The closer A driver suddenly appears to be able to be split. Assuming we use the greedy strategy on a first-come-first-served basis, then the B driver will be given the order, which is contrary to the goal we want to close the order: (. So it looks simple, but in reality, the algorithm needs to be better. This problem is called the timing problem in the dispatch list. Let's see how to solve it later.

▍If there are N passengers, M drivers

Finally, let's consider the most complicated many-to-many situation. This is also the challenge that the online system needs to face every day at the peak. We generally formalize this situation as a bipartite graph matching problem. The problem called matching is as shown:

We then issue concrete, let's say this time we have a passenger 20, 20 have a driver, the passengers can be a driver in this 20 a Jiejia, our system requires these 20 passengers are allocated out, And let everyone's overall pick-up time be the shortest. Does it sound a bit complicated? We apply the knowledge of combinatorial mathematics. The possible solution is as many as the factorial of 20. What is the concept of 20's factorial? 20*19*18*...*1= 2432902008176640000, this number is huge, and it is absolutely impossible to want a complete violent search. There needs to be a smarter approach here.

▍If there are N passengers and M drivers, how many passengers and drivers will be there in a while?

This is the biggest challenge in sending a single question. We don't just need the best of the moment. We have to consider the overall optimality for a while in the future. New drivers and passengers will insert new nodes in real time throughout the allocated network. How to make better allocations has also undergone new changes, so how to consider timing is very important to us. This problem is also called Dynamic VRP in the industry. This Dynamic is the meaning of time series change, which is why The issue of Didi's dispatch is far more complicated than the relatively static planning of goods and routes in the logistics industry. Suppose we know the complete real changes in supply and demand in the future. The simulation tells us that our system may be able to use the same capacity to complete the 1.2~1.5 times of demand. This is also the direction that the students who send the single algorithm continue to work hard.

Recalling the Tucao conference some time ago, everyone mentioned that Wen Song once said that our order dispatching problem is more difficult than alpha go. In fact, these two problems are indeed a bit similar. Both find an approximate optimal in the super large search space. However, alpha go will be solved in a more clear game rules and environment. Its difficulty lies in the game, and the difficulty of our dispatch problem lies in the uncertainty of future supply and demand & the uncertainty of user behavior.In recent years, there have been many attempts in the academia to use technologies similar to alpha go to explore VRP&TSP and other directions. Reinforcement learning combined with operations research theory is one of the most cutting-edge directions in the future operations research field (non-technical students can skip here:) )

3. Introduction to the single algorithm

Above we have described what is the order allocation problem, and the various challenges it faces, then let's talk about how our online distribution strategy solves some of these problems.

Before introducing the specific strategy, let us first talk about the principle of sending a single algorithm. The main principle of the current single strategy is to stand at a global perspective and try to meet as many travel needs as possible to ensure that every passenger needs. They can be satisfied more quickly and surely, and at the same time try to improve the efficiency of each driver's order, so that the total distance and time of the driver is the shortest.

How to understand this principle?We say that the strategy will be based on the overall perspective to achieve the global optimal. In this way, for each independent demand, the dispatch may not be a "local optimal", but what can be told is that even under this strategy, it is still 70% to 80% of the demand is also in line with the current greedy order result.

Next, here are two important strategy for sending a single strategy. (The content here is mainly to explain the strategy's motivation mainly, the details are no longer expanded)

▍ batch matching (global optimal)

The most basic part of the dispatch strategy is to solve the timing problem mentioned in the previous section. This algorithm is almost the most basic model for all similar dispatch systems in order to solve this problem. In Uber, it is called Batching Matching. We also call it "global optimal" or "delay centralized split".

This Idea is also very intuitive. Because the user orders and the driver's appearance are often not at the same time, the greedy ordering method in the time dimension (that is, the nearest driver's dispatch list when each order appears) cannot be used. Get the global optimal effect. A natural idea is to let the passengers and drivers wait for a while, and then collect the orders and drivers for a period of time before distributing them. In this way, with relatively more and more intensive orders and drivers, a single strategy can find a more reasonable and more reasonable way of dispatching.

Finding the global optimum of driver and order allocation is a bipartite graph matching problem. One side is the passenger and the other side is the driver. It can be solved by various methods of solving the Matching problem in operation research optimization.

And let's clarify, the batch matching model we used and the "single-single mode" that everyone wants to "send me the driver closest to me" is not contradictory. We are also seeking "the passengers to pick up the driving time." The shortest "optimal solution, in most cases, also assigns the driver closest to you, but fully meets the individual needs of each passenger's "delivering the driver closest to me", sometimes it will lead to the needs of some passengers. Unable to be satisfied, for example the following:

When two passengers numbered 1 and 2 call the car at the same time, if the model is “in the nearest order”, although the 1 passenger can be accepted first, the passenger of 2 will have a longer waiting time. Long, even because the nearest driver exceeded the platform dispatch distance, the 2 passenger could not call the car. 1 and 2 passengers always wait for 15 minutes, and the average waiting time is 7.5 minutes.

The approach we took was to send the 2 car farther away to the 1 passenger.

The 1 car is dispatched to the 2 passengers. As a result, the average waiting time for 1 passengers and 2 passengers is shortened to 5 minutes, which is shorter than 2.5 minutes, and the total waiting time is shortened to 10 minutes. Sending a single, shortening the full 5 minutes.

By improving the overall efficiency, it can be transformed into meeting the needs of more passengers.

分Based on supply and demand forecasting

"If a prophet tells us when and where each order is generated in the future, and when and where each driver goes online, dispatching orders will become a very easy thing."

The batch matching method just mentioned can theoretically guarantee that the matching of that batch is optimal. But is this enough?

Unfortunately, the above-mentioned delayed centralized order splitting strategy can only solve part of the problem, and it is still not a complete solution.The biggest problem is that users have limited tolerance for the response time of system dispatch. In many cases, just a few seconds will make users lose confidence in the platform and cancel orders.Therefore, we only accumulated a few seconds of order and driver information on the actual line for centralized order splitting. In the overall situation, this can still be approximated as a greedy strategy in the time dimension.

The only way to get the best-paying results in real time is to use the forecast for the future, that is, the order based on supply and demand forecasting. This kind of thinking is mysterious. In fact, the core content is very simple: if we predict that there will be more orders/drivers in a future area, then the matching driver/order will be more waiting for the match. Order/driver in the same area.

▍连环派单

Split orders based on supply and demand forecasts are of great significance, but due to the uncertainty of forecasts, its actual effects are difficult to guarantee.To this end, we use a more deterministic forecasting method to dispatch orders, that is, serial dispatch.

"Serial dispatching means assigning the order to the driver who is about to end the service, and the condition is if the driver's destination is very close to the position of the order"

Contrary to the distribution of predicted orders, the serial order predicts the location of the idle driver at the next moment. Since the idle driver during the peak period is mostly converted after the driver completes the order, predicting the driver's position becomes a relatively certain problem, that is, monitoring the distance and time of the driver to the destination. When the driver in the service is close to the end point and the end point is close to the new order generated by the passenger, the serial logic will be hit. After the driver finishes the last service, the driver will immediately enter the order process of the new order, effectively compressing the response time of the order and the driver's order receiving distance.

How do you do better?

The core of the entire dispatching algorithm overcomes the uncertainty of future supply and demand, the modeling of dynamic spatio-temporal structure, and the uncertainty of user behavior. For these uncertainties, we are now more adopting deep learning methods for our spatio-temporal data. Modeling and predicting user behavior.

In addition, our problem is a layer of matching decision compared to the traditional recommendation search field. How long do we accumulate orders, we are faced with or not for each allocation, and now it is distributed in the future, and The question of who is assigned to it, this problem can be modeled as a reinforcement learning problem by nature, and intensive learning methods are also introduced in our system to optimize longer-term benefits.

In addition to constantly optimizing the dispatch problem mentioned before, the entire dispatch system also faces a large number of other challenges, including how to use the capacity of multiple categories such as express car enjoyment for cross-layer optimal distribution, and how to provide users and drivers at the same time & Platform to optimize multiple goals such as short-term and long-term, how to optimize reservations & real-time orders at the same time, how to evaluate algorithms in scenarios with network effects, if you build a more accurate simulation system, etc., here are both challenges and AI For There are plenty of new opportunities to redefine problems and innovate algorithms in Transportation.

 4. Summary

Every day, our order dispatch system has to face the demand of more than 3000 million users for car-hailing. During peak periods, it receives more than 6 demand for rides per minute. On average, it needs to match hundreds to thousands of passengers and drivers every two seconds.Our current dispatch strategy is able to meet the travel needs of more than one million passengers every day compared to the original dispatch strategy version.In order to allow more people to get a taxi faster and with more certainty, our trading strategy team will continuously optimize and polish our dispatch algorithm under the premise of a better perception of fairness, and create more for passengers & drivers value.

Of course, there are still a lot of incomplete and complete strategies for the current dispatch strategy. It is also a rather complicated problem and system. On the one hand, it is an opportunity for everyone to have a better understanding and understanding of the dispatch. On the other hand, it is also more Everyone is welcome to give us more valuable advice to help us grow further.

This article is transferred from the public number drop technology,Original address