Optimizing Matching for On-Demand Ride-Pooling with Stochastic Day-to-Day Dynamics

Ride-pooling significantly reduces traffic congestion by enhancing fleet utilization through effective ride-matching. Real-world ride-pooling systems are dynamic, with fluctuations in driver availability and demand throughout the day. This necessitates adaptive ride-matching strategies that can quickly adjust to changing proximities and identify new carpooling opportunities by recalculating driver-rider correlations. However, most current methods primarily focus on static demand-supply scenarios and short-term accessibility, falling short in dynamic environment. In this study, we introduce a dynamic heterogeneous network model that captures the evolving nature of ride-pooling systems, where new requests and carpooling arrangements continuously emerge. We propose an embedding model-based matching decision process that operates online, adjusting to changes in the network’s structure. This process involves constructing a dynamic heterogeneous ride-pooling network that encompasses diverse node attributes and driver-rider connections, updating these representations to reflect the network’s evolution, and quickly identifying and ranking candidate riders for efficient online matching. Our approach demonstrates improved performance in offline evaluations using datasets from Austin, TX (RideAustin) and Chengdu, China (DiDi Chuxing). We observe a reduction in the necessary fleet size as new orders are placed, and an improvement in drivers’ matching probability compared to existing methods (e.g., an increase of 5.4–31.1% in the assignment rate on DiDi dataset), showcasing the advantage of employing dynamic network embedding to cut down on matching time (e.g., a decrease of 3.7–228.8 seconds in running time on DiDi dataset). Furthermore, we develop a simulated ride-pooling system (SRPool) that mimics dynamic demand-supply fluctuations and supports vehicle routing, providing a robust platform for evaluating ride-matching strategies. Our strategy not only excels in the SRPool environment but also effectively minimizes the total trip distance and rider waiting times.