Demand-responsive zone generation for real-time vehicle rebalancing in ride-sharing fleets

Enabling Ride-sharing (RS) in existing Mobility-on-demand (MoD) systems allows to reduce the operating vehicle fleet size while achieving a similar level of service. This however requires an efficient vehicle to multiple requests assignment, which is the focus of most RS-related research, and an adaptive fleet rebalancing strategy, which counter-acts the uneven geographical spread of demand and relocates unoccupied vehicles to the areas of higher demand. Existing research into rebalancing generally divides the system coverage area into predefined geographical zones, however, this is done statically at design-time and can limit their adaptivity to evolving demand patterns. To enable dynamic, and therefore more accurate rebalancing, this paper proposes a Dynamic Demand-Responsive Rebalancer (D2R2) for RS systems. D2R2 uses Expectation-Maximization (EM) clustering to determine relocation zones at runtime. D2R2 re-calculates zones at each decision step and assigns them relative probabilities based on current demand. We demonstrate the use of D2R2 by integrating it with a Deep Reinforcement Learning multi-agent RS-enabled MoD system in a fleet of 200 vehicle agents serving 10,000 trips extracted from New York taxi trip data. Results show a more fair workload division across the fleet without loss of performance with respect to waiting time and distribution of passengers per vehicle, when compared to baselines with no rebalancing and static pre-defined equiprobable zones.