Average Distance of Random Bipartite Matching in One-Dimensional Spaces and Networks

The bipartite matching problem is widely applied in the field of transportation—for example, to find optimal matches between supply and demand over time and space. Recent efforts have been made on developing analytical formulas to estimate the expected matching distance in bipartite matching with randomly distributed vertices in two- or higher-dimensional spaces, but no accurate formulas currently exist for one-dimensional problems. This paper presents a set of closed-form formulas, without curve-fitting, that can provide accurate average distance estimates for one-dimensional random bipartite matching problems (RBMPs). We first focus on a lattice case and propose a new method that relates the corresponding matching distance to the area size between a random walk path and the x-axis. This result directly leads to a straightforward closed-form formula for balanced RBMPs. For unbalanced RBMPs on a lattice, we first analyze the properties of an unbalanced random walk that can be related to balanced RBMPs after optimally removing a subset of unmatched points and then derive a set of approximate formulas. Additionally, we build upon an optimal point-removal strategy to derive a set of recursive formulas that can provide more accurate estimates. Then, we extend the results to three problem variants, including RBMPs with periodic boundaries, uniformly distributed points, and arbitrary-length line. Last, we shift our focus to regular networks and use the one-dimensional results as building blocks to derive RBMP formulas. To verify the accuracy of the proposed formulas, a set of Monte Carlo simulations are generated for a variety of matching problems settings. Results indicate that our proposed formulas provide quite accurate distance estimations for one-dimensional line segments and networks under a variety of conditions. Funding: Financial support from the U.S. Department of Transportation (Region V University Transportation Center) and the Zhejiang University-University of Illinois Urbana-Champaign Institute Joint Research Center Project DREMES-202001 is gratefully acknowledged. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2024.0898 .