December 2016 - February 2017
Working in Didi over the winter as a research and development intern had introduced me to a whole new realm of technology. As China's and possibly the world's largest ride-sharing company, Didi has always been striving to use the most cutting-edge technologies and I felt lucky to have worked with so many young talents.
In such a vibrant working environment that was always open for fresh knowledge, I too pushed myself to learn and research. During the course of the internship, I read multiple academic papers related to artificial intelligence as well as real-time assignment algorithms. Our team held weekly discussions for us to share our thoughts on these papers and how the ideas presented in these paper can influence and improve our service.
The DeepStack paper drew inspiration from Texas Hold'em and encouraged us to think ahead of the game. Unlike AlphaGo, DeepStack took in consideration of human factors such as bluffing in its model and was therefore much more related to real life situations. In Didi Carpool assignment problem, we sometimes rely too much on Greedy Algorithm, that is, we try to assign a new customer to a car already with a passenger. This approach is lucrative given a short time frame. However, one might raise a question: what if we assign this new customer to an empty car, and another customer might join later, resulting in much more profit? That was exactly we were trying to research on.
Another interesting paper addressed dynamic trip-vehicle assignment through solving bipartite graphs and cliques. It showed impressive results that 98% of all the taxi requests can be fulfilled with only 15% of the NYC taxi fleet. The objective function of this optimization function introduced a very large constant to penalize sub-optimal assignments and thus generated better and better results after each batch. However, this algorithm relies too heavily on the assumption that all passenger would be willing to pool with other people. To increase the willingness to pool has always been Didi's main objective. Currently, our data show that only 25% of the people are willing to share their rides.
Other than researching, I trained with my colleagues and mentors on Spark programming. I compared driver's summoning rates and profit-to-fare ratio by collecting data of multiple cities' as well as using Spark to aggregate, join and filter them. I also worked with another intern to convert Java Spark programs to Python for easier code integrations.