标题： 时空异质性下的动态随机二部匹配：通用模型及其在移动服务中的应用 显示英文标题

标题： Dynamic Random Bipartite Matching under Spatiotemporal Heterogeneity: General Models and Application to Mobility Services

摘要： 本文探讨了一种二分匹配问题的变体，称为时空随机二分匹配问题（ST-RBMP），该问题能够适应二分顶点在空间分布和时间到达中的随机性和异质性。 此类问题可以应用于许多基于位置的服务，例如共享出行系统，其中随机到达的客户和车辆必须进行动态匹配。 本文提出了一种新的建模框架，以解决与时空异质性、动态性和随机决策相关的ST-RBMP挑战。 目标是动态确定最优的车辆/客户聚合间隔和最大匹配半径，以最小化系统范围内的匹配成本，包括客户和车辆的等待时间和匹配距离。 针对静态和同质的RBMP，开发了用于估计最大匹配半径下期望匹配距离的显式公式，并通过连续逼近扩展以适应空间异质性。 随后，将ST-RBMP表述为一个最优控制问题，其中在时间和空间上求解聚合间隔和匹配半径的最优值。 进行了一系列使用模拟数据的实验，以证明在匹配半径和空间异质性下，针对静态RBMP的所提公式在估计匹配概率和距离方面具有非常准确的结果。 还提供了额外的数值结果，以展示所提出的ST-RBMP建模框架在设计各种需求和供应模式下的动态匹配策略的有效性，为出行服务运营商提供了关键的管理洞察。 显示英文摘要

摘要： 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.