A Clustering-Based Multi-Agent Reinforcement Learning Framework for Finer-Grained Taxi Dispatching

The rapid growth of Internet services dramatically drives the development of various intelligent technologies. As an important composition, modern ride-hailing platforms allow citizens to order taxis in a fast, simple, and secure manner. The key to developing a successful ride-hailing system largely depends on efficient fleet management that narrows the demand-supply gap. For this reason, many Deep Reinforcement Learning (DRL) frameworks are becoming increasingly popular for proactive taxi dispatching. However, existing approaches have very coarse formulations and solutions to the dispatching problem, which overly simplify the real situations. To this end, we propose a fine-grained DRL framework for effective taxi dispatching with tractable solutions. Our framework features three components. 1) The basic model is a multi-agent DRL that optimizes the standard objectives (i.e., fulfilling the taxi orders). To reduce the status space and environment dynamics, we cluster regions based on their daily moving patterns and allow agents in the same cluster to learn cooperatively by sharing their policies, i.e., learning from like-pattern peers. 2) We further employ a recurrent neural network to forecast the demand and supply, which helps the agents make globally optimal decisions. 3) Finally, we design a two-phase central dispatching strategy based on Maximum Network Flow to relocate taxis in fine granularity. We conduct extensive experiments in a realistic environment simulator using a real-world dataset, and the results demonstrate the superior performance of our new framework over existing approaches, promoting the average total order response rate by 2.67%, taxi effort gain by 25.77%, and decreasing the average number of repositions by 2.96%.