@article{9023e3d88edd4f349ec74e4db261e475,
title = "Average minimum distance to visit a subset of random points in a compact region",
abstract = "This paper seeks an analytical estimate of the expected distance for visiting an arbitrary subset of independently and uniformly distributed random points within a compact region. This problem has many real-world application contexts such as the emerging on-demand transportation and logistics services (e.g., ridesharing, customized buses). The lower bounds of the expected optimal tour length are analytically derived by considering a so-called “trapping effect”, which explicitly addresses probabilistically the situation that some of the tour legs must connect points that are not neighbors. A parametric approach is developed to estimate the expected optimal tour length for both Euclidean and rectilinear metrics. Numerical experiments demonstrate the validity of these bounds, as well as the closeness of the proposed estimator to simulated results.",
keywords = "Continuous approximation, Dynamic routing, On-demand service, TSP",
author = "Chao Lei and Yanfeng Ouyang",
note = "This research was supported in part by the U.S. National Science Foundation via Grant CMMI-1662825. The first author was a postdoctoral research associate at Illinois while the majority of this research was conducted. His efforts after joining Shanghai Maritime University were supported by the National Natural Science Foundation of China via Grant no. 72001136. This research topic was originally stimulated by an informal discussion with Prof. Yafeng Yin (University of Michigan). Professors Carlos Daganzo (University of California, Berkeley) and Yafeng Yin provided helpful comments on an earlier version of the paper. The very insightful suggestions from the associate editor and two anonymous reviewers (e.g. on comparison with benchmark models, elongated shapes, and on best position this paper's contribution) also stimulated us to significantly improve the paper during the revision process. This research was supported in part by the U.S. National Science Foundation via Grant CMMI-1662825 . The first author was a postdoctoral research associate at Illinois while the majority of this research was conducted. His efforts after joining Shanghai Maritime University were supported by the National Natural Science Foundation of China via Grant no. 72001136 . This research topic was originally stimulated by an informal discussion with Prof. Yafeng Yin (University of Michigan). Professors Carlos Daganzo (University of California, Berkeley) and Yafeng Yin provided helpful comments on an earlier version of the paper. The very insightful suggestions from the associate editor and two anonymous reviewers (e.g., on comparison with benchmark models, elongated shapes, and on best position this paper{\textquoteright}s contribution) also stimulated us to significantly improve the paper during the revision process.",
year = "2024",
month = mar,
doi = "10.1016/j.trb.2024.102904",
language = "English (US)",
volume = "181",
journal = "Transportation Research Part B: Methodological",
issn = "0191-2615",
publisher = "Elsevier Ltd",
}