KDD Papers

A Taxi Order Dispatch Model based On Combinatorial Optimization

Lingyu Zhang (Didi Chuxing);Tao Hu (Didi Chuxing);Yue Min (Didi Chuxing);Guobin Wu (Didi Chuxing);Junying Zhang (Didi Chuxing);Pengcheng Feng (Didi Chuxing);Pinghua Gong (Didi Chuxing);Jieping Ye (Didi Chuxing)


Taxi-booking apps have been very popular all over the world as they provide fast response time and convenience to the users. The key component of a taxi-booking app is the dispatch system which aims to provide optimal matches between drivers and riders. Traditional dispatch systems sequentially dispatch taxis to riders and aim to maximize the driver acceptance rate for each individual order. However, the traditional systems cannot guarantee the global success rate, which degrades the rider experience when using the app. In this paper, we propose a novel system that attempts to optimally dispatch taxis to serve multiple bookings. The proposed system aims to maximize the global success rate, and thus it optimizes the overall traffic efficiency, leading to enhanced user experience. To further enhance users’ experience, we also propose a method to predict destinations of a user once the taxi-booking APP is started. The proposed method employs the Bayesian framework to model the distribution of a user’s destination based on his/her travel histories. We use A/B tests to compare our new taxi dispatch method with state-of-the-art models using data collected in Beijing. Experimental results show that the proposed method is significantly better than other state-of-the art models in terms of global success rate (increased from 80% to 84%). Moreover, we have also achieved significant improvement on other metrics such as user’s waiting-time and pick-up distance. For our destination prediction algorithm, we show that our proposed model is superior to the baseline model which is based on the KNN method by improving the top-3 accuracy from 89% to 93%. The new taxi dispatch and destination prediction algorithms are both deployed in our online systems and serve tens of millions of users everyday.