- A Markov Decision Process Approach
Abstract
For e-hailing drivers, "cruising"—driving empty while seeking the next fare—accounts for 35–60% of total operation time, leading to reduced income and increased urban congestion. This paper proposes a Markov Decision Process (MDP) framework to optimize driver repositioning strategies. By applying Inverse Reinforcement Learning (IRL) to a massive dataset of 44,160 drivers in Beijing, we uncover the underlying reward functions that drive successful behavior. Our model incorporates dynamic competition adjustments and stacked-order logic, achieving a 17.5% improvement in the rate of return compared to standard local hotspot strategies and nearly doubling the efficiency of average real-world drivers.
Introduction: The Cruising Challenge
In the taxi and e-hailing industry, idle time is a primary source of inefficiency. Traditional taxi drivers rely on street hails, requiring active searching in high-traffic areas. In contrast, e-hailing platforms (e.g., Uber, Didi) match drivers to passengers via algorithms, shifting the driver's strategic burden from "searching" to "repositioning." Drivers must constantly decide whether to wait at a drop-off point, cruise locally, or move to a distant neighborhood to maximize their chances of a high-value match.
Methodology
We model the passenger-seeking process as a sequential decision-making problem under uncertainty using a Markov Decision Process (MDP).
The MDP Framework
The state space $s$ is defined by the driver's current hexagonal grid location, the time interval, and an indicator $I$ representing whether the driver is already matched to a future "stacked" order. Available actions include moving to an adjacent grid, staying within the current grid to search, or waiting statically.
Learning from the Best: IRL and Competition
Rather than assuming a simple reward function based solely on fare value, we utilize Inverse Reinforcement Learning (IRL). This allows the model to "imitate" the behavior of top-performing drivers by uncovering what they actually optimize for, such as balancing fuel costs against potential earnings. To ensure the model remains realistic, we incorporate an exponential decay function that adjusts matching probabilities based on driver supply, preventing the "herd effect" where all drivers are sent to the same hotspot.
Data and Experimental Setup
The study utilized a comprehensive dataset from Didi Chuxing covering Beijing, China. The area within the 6th Ring Road was discretized into 6,421 hexagonal grids. The dataset included GPS trajectories and trip records for over 44,000 drivers over three weekdays in November 2017. We validated the policy using Monte Carlo simulations, comparing the MDP-based strategy against real-world driver performance and "local hotspot" heuristics.
Key Results and Insights
The MDP model significantly outperformed existing strategies across several key metrics:
- Rate of Return: The model achieved 0.67 Yuan/Minute, a 17.5% improvement over the hotspot heuristic and nearly double the 0.36 Yuan/Minute average of real drivers.
- Utilization: Drivers following the optimal policy spent 72% of their time with passengers, compared to 51% for the average driver in the dataset.
- Efficiency: The policy reduced average daily idle time from 47.9 minutes to 22.6 minutes while increasing the number of completed orders from 6.08 to 8.92.
Interestingly, the model revealed that drivers are not a monolith. Some exhibit a "homebody" preference, where their intrinsic reward increases when moving toward a familiar central location, even if it slightly reduces immediate fare probability.
Conclusion and Future Work
This research demonstrates that an MDP-based approach, powered by IRL, can drastically improve the efficiency of e-hailing operations. While the current model uses historical demand probabilities, future iterations could integrate real-time data to account for weather or traffic incidents. Additionally, scaling the model via Hierarchical MDPs could allow for more granular decision-making in even larger metropolitan areas.
Summary updated