{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T09:09:35Z","timestamp":1778663375928,"version":"3.51.4"},"reference-count":45,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transportation Science"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>The bipartite matching problem is widely applied in the field of transportation\u2014for 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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>\n                  <jats:p>Supplemental Material: The online appendix is available at https:\/\/doi.org\/10.1287\/trsc.2024.0898 .<\/jats:p>","DOI":"10.1287\/trsc.2024.0898","type":"journal-article","created":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T14:45:19Z","timestamp":1771253119000},"page":"367-386","source":"Crossref","is-referenced-by-count":0,"title":["Average Distance of Random Bipartite Matching in One-Dimensional Spaces and Networks"],"prefix":"10.1287","volume":"60","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-0666-180X","authenticated-orcid":false,"given":"Yuhui","family":"Zhai","sequence":"first","affiliation":[{"name":"Department of Civil and Environmental Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0704-8766","authenticated-orcid":false,"given":"Shiyu","family":"Shen","sequence":"additional","affiliation":[{"name":"Department of Civil and Environmental Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5944-2044","authenticated-orcid":false,"given":"Yanfeng","family":"Ouyang","sequence":"additional","affiliation":[{"name":"Department of Civil and Environmental Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1145\/3542700.3542713"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77200-2_1"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.2027"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1016\/j.scs.2021.103617"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1177\/2399808318784595"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2014\/11\/P11023"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.042112"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.91.062125"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.96.042102"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/ab11d7"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.012118"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1109\/TAES.2016.140952"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1016\/0041-1647(78)90007-2"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1030.0037"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.2015"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2014.05.073"},{"key":"B17","doi-asserted-by":"crossref","unstructured":"Dutta A , \nDasgupta P   (2017) Bipartite graph matching-based coordination mechanism for multi-robot path planning under communication constraints.\n                      2017 IEEE Internat. Conf. Robotics Automation ICRA\n                      (IEEE, Piscataway, NJ), 857\u2013862.","DOI":"10.1109\/ICRA.2017.7989105"},{"key":"B18","unstructured":"Ellis D   (2011) The expansion of random regular graphs. https:\/\/snap.stanford.edu\/class\/cs224w-readings\/ellis11expansion.pdf."},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1016\/j.commtr.2024.100130"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2017.06.012"},{"key":"B21","unstructured":"Georgiev D , \nLi\u00f2 P   (2020) Neural bipartite matching. Preprint, submitted May 22, https:\/\/arxiv.org\/abs\/2005.11304v1."},{"key":"B22","doi-asserted-by":"crossref","unstructured":"Ghassemi P , \nChowdhury S   (2018) Decentralized task allocation in multi-robot systems via bipartite graph matching augmented with fuzzy clustering.\n                      44th Design Automation Conf. Internat. Design Engrg. Tech. Conf. Comput. Inform. Engrg. Conf.\n                      , vol. 2A (American Society of Mechanical Engineers, New York), V02AT03A014.","DOI":"10.1115\/DETC2018-86161"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.0805"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.3.566"},{"key":"B25","doi-asserted-by":"crossref","unstructured":"Hern\u00e1ndez D , \nCec\u00edlia JM , \nCalafate CT , \nCano JC , \nManzoni P   (2021) The Kuhn-Munkres algorithm for efficient vertical takeoff of UAV swarms.\n                      2021 IEEE 93rd Vehicular Tech. Conf. VTC2021-Spring\n                      (IEEE, Piscataway, NJ), 1\u20135.","DOI":"10.1109\/VTC2021-Spring51267.2021.9448873"},{"issue":"1","key":"B26","first-page":"1849877","volume":"2022","author":"Jin C","year":"2022","journal-title":"Mobile Inform. Systems"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02278710"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1137\/0701008"},{"key":"B30","doi-asserted-by":"crossref","unstructured":"M\u00e9zard M , \nParisi G   (1985) Replicas and optimization.\n                      J. Phys. Lett.\n                      46(17):771\u2013778.","DOI":"10.1051\/jphyslet:019850046017077100"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1051\/jphys:0198800490120201900"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2022.10.015"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2020.102110"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.3390\/drones7050300"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2023.104366"},{"key":"B36","unstructured":"Shen S , \nZhai Y , \nOuyang Y   (2024) Expected bipartite matching distance in a d-dimensional      l  p     space: Approximate closed-form formulas and applications to mobility services. Preprint, submitted June 18, https:\/\/arxiv.org\/abs\/2406.12174v1."},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2015.07.025"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2020.02.008"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2019.101430"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2016.05.011"},{"key":"B41","doi-asserted-by":"crossref","unstructured":"Wang Y , \nMakedon F , \nFord J , \nHuang H   (2004) A bipartite graph matching framework for finding correspondences between structural elements in two proteins.\n                      26th Annu. Internat. Conf. IEEE Engrg, Medicine Biology Soc.\n                      , vol. 2 (IEEE, Piscataway, NJ), 2972\u20132975.","DOI":"10.1109\/IEMBS.2004.1403843"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90009-X"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2009.12.010"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-110"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2022.103851"}],"container-title":["Transportation Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/trsc.2024.0898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T08:15:27Z","timestamp":1778660127000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/trsc.2024.0898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/trsc.2024.0898"],"URL":"https:\/\/doi.org\/10.1287\/trsc.2024.0898","relation":{},"ISSN":["0041-1655","1526-5447"],"issn-type":[{"value":"0041-1655","type":"print"},{"value":"1526-5447","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}