Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach

ABSTRACT

We present a novel order dispatch algorithm in large-scale on-demand ride-hailing platforms. While traditional order dispatch approaches usually focus on immediate customer satisfaction, the proposed algorithm is designed to provide a more efficient way to optimize resource utilization and user experience in a global and more farsighted view. In particular, we model order dispatch as a large-scale sequential decision-making problem, where the decision of assigning an order to a driver is determined by a centralized algorithm in a coordinated way. The problem is solved in a learning and planning manner: 1) based on historical data, we first summarize demand and supply patterns into a spatiotemporal quantization, each of which indicates the expected value of a driver being in a particular state; 2) a planning step is conducted in real-time, where each driver-order-pair is valued in consideration of both immediate rewards and future gains, and then dispatch is solved using a combinatorial optimizing algorithm. Through extensive offline experiments and online AB tests, the proposed approach delivers remarkable improvement on the platform's efficiency and has been successfully deployed in the production system of Didi Chuxing.

References

1. Bram Bakker, Shimon Whiteson, Leon Kester, and Frans C. A. Groen. 2010. Traffic light control by multiagent reinforcement learning systems. In Interactive Collaborative Information Systems. Springer, 475--510.
2. Jie Bao, Tianfu He, Sijie Ruan, Yanhua Li, and Yu Zheng. 2017. Planning Bike Lanes based on Sharing-Bikes' Trajectories Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1377--1386.
3. Lucian Busoniu, Robert Babuska, and Bart De Schutter. 2008. A comprehensive survey of multiagent reinforcement learning. IEEE Trans. Systems, Man, and Cybernetics, Part C Vol. 38, 2 (2008), 156--172.
4. Bo Chen and Harry H. Cheng. 2010. A review of the applications of agent technology in traffic and transportation systems. IEEE Transactions on Intelligent Transportation Systems Vol. 11, 2 (2010), 485--497.
5. Robert H. Crites and Andrew G. Barto. 1998. Elevator group control using multiple reinforcement learning agents. Machine learning Vol. 33, 2-3 (1998), 235--262.
6. Der Horng Lee, Hao Wang, Ruey Long Cheu, Hoon Siew, and Teo. 2004. A Taxi Dispatch System Based on Current Demands and Real-Time Traffic Conditions. Transportation Research Record Journal of the Transportation Research Board Vol. 1882, 1 (2004).
7. Bin Li, Daqing Zhang, Lin Sun, Chao Chen, Shijian Li, Guande Qi, and Qiang Yang. 2011. Hunting or waiting? Discovering passenger-finding strategies from a large-scale real-world taxi dataset. In Pervasive Computing and Communications Workshops (PERCOM Workshops), 2011 IEEE International Conference on. IEEE, 63--68.
8. Ziqi Liao. 2003. Real-time taxi dispatching using global positioning systems. Commun. ACM Vol. 46, 5 (2003), 81--83.
9. Michael L. Littman. 2001. Value-function reinforcement learning in Markov games. Cognitive Systems Research Vol. 2, 1 (2001), 55--66.
10. Junming Liu, Leilei Sun, Qiao Li, Jingci Ming, Yanchi Liu, and Hui Xiong. 2017. Functional Zone Based Hierarchical Demand Prediction For Bike System Expansion. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 957--966.
11. Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. 2017. Multi-agent actor-critic for mixed cooperative-competitive environments Advances in Neural Information Processing Systems. 6382--6393.
12. Michal Maciejewski, Joschka Bischoff, and Kai Nagel. 2016. An assignment-based approach to efficient real-time city-scale taxi dispatching. IEEE Intelligent Systems Vol. 31, 1 (2016), 68--77.
13. Fei Miao, Shuo Han, Shan Lin, John A Stankovic, Desheng Zhang, Sirajum Munir, Hua Huang, Tian He, and George J. Pappas. 2016. Taxi dispatch with real-time sensing data in metropolitan areas: A receding horizon control approach. IEEE Transactions on Automation Science and Engineering Vol. 13, 2 (2016), 463--478.
14. Luis Moreira-Matias, Joao Gama, Michel Ferreira, Joao Mendes-Moreira, and Luis Damas. 2013. Predicting taxi-passenger demand using streaming data. IEEE Transactions on Intelligent Transportation Systems Vol. 14, 3 (2013), 1393--1402.
15. James Munkres. 1957. Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics Vol. 5, 1 (1957), 32--38.
16. Meng Qu, Hengshu Zhu, Junming Liu, Guannan Liu, and Hui Xiong. 2014. A cost-effective recommender system for taxi drivers ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 45--54.
17. Kiam Tian Seow, Nam Hai Dang, and Der-Horng Lee. 2010. A collaborative multiagent taxi-dispatch system. IEEE Transactions on Automation Science and Engineering Vol. 7, 3 (2010), 607--616.
18. Hugo P. Simao, Jeff Day, Abraham P. George, Ted Gifford, John Nienow, and Warren B. Powell. 2009. An approximate dynamic programming algorithm for large-scale fleet management: A case application. Transportation Science Vol. 43, 2 (2009), 178--197.
19. Richard S. Sutton and Andrew G. Barto. 1998. Reinforcement learning: An introduction. Vol. 1. MIT press Cambridge.
20. Yongxin Tong, Yuqiang Chen, Zimu Zhou, Lei Chen, Jie Wang, Qiang Yang, Jieping Ye, and Weifeng Lv. 2017. The simpler the better: a unified approach to predicting original taxi demands based on large-scale online platforms. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1653--1662.
21. Michael Wooldridge. 2009. An introduction to multiagent systems. John Wiley &Sons.
22. Carl Yang, Lanxiao Bai, Chao Zhang, Quan Yuan, and Jiawei Han. 2017. Bridging Collaborative Filtering and Semi-Supervised Learning: A Neural Approach for POI Recommendation. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1245--1254.
23. Daqing Zhang, Lin Sun, Bin Li, Chao Chen, Gang Pan, Shijian Li, and Zhaohui Wu. 2015. Understanding taxi service strategies from taxi GPS traces. IEEE Transactions on Intelligent Transportation Systems Vol. 16, 1 (2015), 123--135.
24. Lingyu Zhang, Tao Hu, Yue Min, Guobin Wu, Junying Zhang, Pengcheng Feng, Pinghua Gong, and Jieping Ye. 2017. A taxi order dispatch model based on combinatorial optimization Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2151--2159.
25. Rick Zhang and Marco Pavone. 2016. Control of robotic mobility-on-demand systems: a queueing-theoretical perspective. The International Journal of Robotics Research Vol. 35, 1-3 (2016), 186--203.
26. Qingnan Zou, Guangtao Xue, Yuan Luo, Jiadi Yu, and Hongzi Zhu. 2013. A novel taxi dispatch system for smart city. In International Conference on Distributed, Ambient, and Pervasive Interactions. Springer, 326--335.

Index Terms

• Applied computing

  • Operations research

    • Transportation

• Computing methodologies

  • Artificial intelligence

    • Planning and scheduling

      • Multi-agent planning

  • Machine learning

    • Learning paradigms

      • Reinforcement learning