Didi - dispatching

1 2017 - 《A Taxi Order Dispatch Model based On Combinatorial Optimization》

Information ：
Detailed explanation of the paper : Didi big data predicts user destinations , The accuracy is superior 90% | KDD 2017 | Leifeng net

A summary of the paper ：
Dispathing system Distribution system ： That is, many to many drivers and passengers match , Make drivers make more money , Higher passenger satisfaction .

1. The traditional way is ： For each order , Maximize the driver's order taking rate . shortcoming ： The overall success rate may not be high .
2. The new method ： The order splitting model based on combinatorial optimization , Maximize the overall success rate of receiving orders , Maximize overall efficiency , To enhance the user experience .

The details of the algorithm are as follows ：

1. Optimize the overall transaction rate when splitting orders
   The mathematical form of the model is ：
   

among ,max(E) For the optimization goal of the whole model , That is, the transaction rate ;g(a)≤0 For the constraints that the model must meet , Here may be some business rules , For example, a driver can only assign one order at a time ;a Is the solution of the model , That is, how to allocate the overall order and the overall driver .

2. Logistics Regression The model calculates the driver acceptance probability
   According to the value of the order 、 Pick up distance 、 The angle between directions 、 Characteristics such as driving direction , Use logistics regression Model to calculate the probability of the driver accepting the order .
   
   Because an order will be sent to m A driver , So the first i The probability of closing an order is ：
   

In this way, the whole combinatorial optimization model is ：
among N Is the current total number of orders ,M It is the number of drivers notified in one order . What is optimized is the sum of the success rates of all orders at the current moment .

2 2018 - 《Large‑Scale Order Dispatch in On‑Demand Ride‑Hailing Platforms: A Learning and Planning Approach》

Information ：
sound of dripping water KDD 2018 Detailed explanation of the paper : Intelligent dispatch model based on Reinforcement Learning Technology | Leifeng net

1. traditional method ： Focus on immediate passenger satisfaction .
2. The new method ： Pay more attention to resource utilization and user experience in the overall and long-term perspective .

The overall architecture ：

1. Offline training value function , Reinforcement learning is used here ,MAP Method of state space transition
2. Online reasoning is based on current benefits , And the comprehensive judgment of income in the future
   

3 2019 - 《A Deep Value-networkBased Approach for Multi-Driver Order Dispatching》

sound of dripping water KDD 2019 Detailed explanation of the paper ： Multi driver intelligent dispatch model based on deep value network

1. This article is based on the previous article , Deep reinforcement learning is used + Semi Markov decision process （ With time ductility ）.
2. Add situational features to the state space , In the last paper , State space is only related to time and place . The current revision is ： state ( Time 、 place 、 Situational features - Hot spot , Cold zone, etc ).
3. Add delay decreasing information in the update of value function
   
4. And different cities use transfer learning , Cities with less data are more friendly , Don't go from 0 Start .

4 2019 - 《Efficient Collaborative Multi-Agent Deep Reinforcement Learning for Large-Scale Fleet Management》

Multi agent , Reinforcement learning
It's Didi's new play , Added the concept of team , This team is a team , Between teams , It's competition . On the one hand, drivers won't be bored , Between team members , There will be a sense of belonging . On the other hand , The competitive relationship between teams , It will stimulate the driver's enthusiasm for work . It also uses the method of reinforcement learning . Didn't take a close look at , Little correlation .