Suppose a square $[0,1]\times [0,1]$ in which $N$ vehicles $V_i$ and $N$ riders $R_i$ are distributed identically and independently (say, uniform distribution), a bipartite matching (or a permutation, $\pi(i)$) is done between the vehicles and riders with the objective that the total distance
$$Z=\min_{\pi}\sum_1^N \sqrt{\Vert V_{\pi(i)}-R_i\Vert^2}$$
is minimized.
Since the locations of vehicles and riders are distributed randomly, therefore $Z$ is a random variable. The expectation of $Z$ is thus of interest. The question is how to derive the $E(Z)$.
I have found some related papers, such as
- Caracciolo, S., & Sicuro, G. (2015). Quadratic stochastic Euclidean bipartite matching problem. Physical review letters, 115(23), 230601.
- Holroyd, A. E., Pemantle, R., Peres, Y., & Schramm, O. (2009). Poisson matching. In Annales de l'Institut Henri Poincaré, Probabilités et Statistiques (Vol. 45, No. 1, pp. 266-287). Institut Henri Poincaré.
- Boniolo, E., Caracciolo, S., & Sportiello, A. (2014). Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle. Journal of Statistical Mechanics: Theory and Experiment, 2014(11), P11023.
I am trying to read them to figure out how, but their derivation all has some part heavily related to physics and statistical mechanics, which makes me struggle to understand it but I fail.
I was wondering if there is a version with a no-physics-just-operations-research flavor to solve this problem?
