Dynamic random bipartite matching under spatiotemporal heterogeneity

This paper explores a variant of bipartite matching problem, referred to as the Spatiotemporal Random Bipartite Matching Problem (ST-RBMP), that accommodates randomness and heterogeneity in the spatial distributions and temporal arrivals of bipartite vertices. This type of problem can be applied to many location-based services, such as shared mobility systems, where randomly arriving customers and vehicles must be matched dynamically. This paper proposes a new modeling framework to address ST-RBMP’s challenges associated with the spatiotemporal heterogeneity, dynamics, and stochastic decision-making. The objective is to dynamically determine the optimal vehicle/customer pooling intervals and maximum matching radii that minimize the system-wide matching costs, including customer and vehicle waiting times and matching distances. Closed-form formulas for estimating the expected matching distances under a maximum matching radius are developed for static and homogeneous RBMPs, and then extended to accommodate spatial heterogeneity via continuum approximation. The ST-RBMP is then formulated as an optimal control problem where optimal values of pooling intervals and matching radii are solved over time and space. A series of experiments with simulated data are conducted to demonstrate that the proposed formulas for static RBMPs under matching radius and spatial heterogeneity yield very accurate results on estimating matching probabilities and distances. Additional numerical results are presented to demonstrate the effectiveness of the proposed ST-RBMP modeling framework in designing dynamic matching strategies for mobility services under various demand and supply patterns, which offers key managerial insights for mobility service operators.