Spatiotemporal Random Bipartite Matching Problems and Applications in Mobility Systems
Advisor: Professor Yanfeng Ouyang
Abstract
This dissertation presents new findings on a variant of bipartite matching problem, referred to as the Spatiotemporal Random Bipartite Matching Problem (ST-RBMP), which accommodates randomness and heterogeneity in the spatial distribution and temporal arrival of bipartite vertices. This fundamental problem has direct application to a variety of theoretical or practical contexts. In this study, we use on-demand mobility services as an example, where randomly arriving demand and supply points (i.e., customers and vehicles) must be dynamically matched over space and time.
The first part of this dissertation addresses an open question: how to derive closed-form formulas that accurately estimate the expected optimal matching distance between arbitrary numbers of randomly distributed bipartite vertices in a š·-dimensional Lš space. Three interrelated and increasingly complex versions of RBMPs are studied: (i) RBMP-I, where edge costs are independently and identically distributed (i.i.d.) random variables; (ii) RBMP-S, where edge costs represent distances between vertices uniformly distributed on the surface of a hyper-sphere in a š·-dimensional Euclidean space; and (iii) RBMP-B, where the vertices are uniformly distributed in a hyper-ball within a š·-dimensional Lš space. All derived formulas are verified by a series of Monte-Carlo simulation experiments, where the formula predictions are between 1% and 5% of errors under a wide range of parameter combinations.
The second part of this dissertation proposes a new modeling framework to address spatiotemporal heterogeneity in RBMP (i.e., ST-RBMP), as well as ways to support matching decisions in a dynamic and heterogeneous environment. With proper formulas to estimate RBMP's expected matching distance, one can dynamically determine the matching restrictions in the time dimension (e.g., optimal pooling time intervals) and spatial dimension (e.g., maximum permitted matching radii) to minimize the system-wide expected matching costs. To this end, new closed-form formulas for estimating the expected matching distances under a maximum matching radius are developed for static and homogeneous RBMPs, and then they are extended to accommodate spatial heterogeneity via continuum approximation. The ST-RBMP is then formulated as an optimal control problem to allow dynamic decision making over time. A series of numerical experiments are conducted to demonstrate the effectiveness of the proposed ST-RBMP modeling framework under various demand and supply patterns.
The third part of this dissertation proposes a new Pareto-improving dynamic swap strategy to further reduce the expected matching cost among matched vertices in ST-RBMP. Using the on-demand mobility system as an example, this strategy ensures that the swap of matched vertices (e.g., idle
vehicles and customers) allow all involved parties to achieve a Pareto improvement (e.g., reduction in the deadheading or waiting time) and at the same time reduce the needed resources (e.g., fleet size). Approximate analytic formulas that estimate the expected system performance in the steady state are derived from a series of differential equations and spatial probability models. Agent-based simulations are used to verify the accuracy of the derived formulas, and to demonstrate the effectiveness of the proposed strategy (achieving cost reductions of 10–60% across tested scenarios).
The proposed modeling frameworks and findings offer valuable managerial insights for operators of various location-based resource allocation systems, such as shared mobility, freight logistics, and healthcare. Moreover, the ST-RBMPs are general and fundamental; they can be applied to a wide range of other applications in other contexts, including physics (e.g., analyzing energy configurations of atomic magnets), artificial intelligence (e.g., matching data points or neurons in high-dimensional feature spaces), and information or social science (e.g., modeling interactions among socioeconomic groups via social networks).