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.
Supplemental Material
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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).Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Ziqi Liao. 2003. Real-time taxi dispatching using global positioning systems. Commun. ACM Vol. 46, 5 (2003), 81--83. Google ScholarDigital Library
- Michael L. Littman. 2001. Value-function reinforcement learning in Markov games. Cognitive Systems Research Vol. 2, 1 (2001), 55--66. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Richard S. Sutton and Andrew G. Barto. 1998. Reinforcement learning: An introduction. Vol. 1. MIT press Cambridge. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Michael Wooldridge. 2009. An introduction to multiagent systems. John Wiley &Sons. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach
Recommendations
Value Function is All You Need: A Unified Learning Framework for Ride Hailing Platforms
KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data MiningLarge ride-hailing platforms, such as DiDi, Uber and Lyft, connect tens of thousands of vehicles in a city to millions of ride demands throughout the day, providing great promises for improving transportation efficiency through the tasks of order ...
Real-Time Route Planning and Online Order Dispatch for Bus-Booking Platforms
Database Systems for Advanced ApplicationsAbstractTo cater to the high travel demands in Beijing Capital International Airport during 23:00–2:00, Beijing Traffic Management Bureau (BTMB) intends to develop a new service named bus-booking platforms. Compared to traditional airport shuttle buses, ...
An Order Dispatch Approach in Large-scale Telemarketing System
ICCBDC '19: Proceedings of the 2019 3rd International Conference on Cloud and Big Data ComputingIn traditional order dispatch rule in large scale telemarketing, employee selects one of hundreds orders competing with others during limited time. However, the selected order maybe is not suitable which mean employee finish the order with a poor ...
Comments