Optimal paths on the road network as directed polymers

We analyze the statistics of the shortest and fastest paths on the road network between randomly sampled end points. We find that, to a good approximation, the optimal paths can be described as directed polymers in a disordered medium, which belong to the Kardar-Parisi-Zhang universality class of interface roughening. Comparing the scaling behavior of our data with simulations of directed polymers and previous theoretical results, we are able to point out the few characteristics of the road network that are relevant to the large-scale statistics of optimal paths. Indeed, we show that the local structure is akin to a disordered environment with a power-law distribution which become less important at large scales where long-ranged correlations in the network control the scaling behavior of the optimal paths.

Figure 1

The location of the three regions considered. For simplicity and efficiency of our algorithm, they are chosen to be large rectangular areas (in latitude-longitude coordinates) without sea or ocean.

Figure 2

Shortest (left) and fastest (right) paths from a center point (near Munich, Germany) to ${10}^4$ randomly chosen points at a distance of 300 km. The arrow points to the most prominent overhang in the paths.

Figure 3

Average length of the optimal paths $\langle L\rangle$ and length of overhangs $\langle L_h\rangle$ as a function of the distance $d$ between the end points. All lengths are measured in km. Left: Shortest paths. Right: Fastest paths. ${10}^6$ points for each curve. Lines are guides to the eye.

Figure 4

Optimal paths between points at a distance $d=1$ km. Top: Probability distribution of the length $L$ of the shortest paths. Bottom: Probability distribution of the travel time $T$ of the fastest paths. $N=5\times {10}^5$ paths for each curve. Insets: Scaled plots with the best-fit exponent $\alpha$ indicated in the legend.

Figure 5

Top: Probability distribution of the length $L$ of the shortest paths in Europe rescaled with $\beta =0.66$. $5\times {10}^5$ paths for each curve. Bottom: Probability distribution of the energy for the DPRM model with power-law noise rescaled with $\beta =1/3$. ${10}^7$ paths for each curve. Lattice of size ${10}^7$ in the transverse direction with periodic boundary conditions. The insets show the same data with a logarithmic $y$ axis. $P_m$ denotes the maximum of the distribution, found at a value $L=L_m$ or $E=E_m$.

Figure 6

Autocorrelation function of the road density as defined in the text. The oscillations in the curve for the U.S. are not an artifact. The peaks are located every mile (with subpeaks at half miles) and correspond to large regions (up to 60 miles) of gridlike road network.

Figure 7

Transverse wandering for the shortest paths as a function of the coordinate $x$ on the axis between the end points. Average over $5\times {10}^5$ paths between points at distance $d=1000\mathrm{km}$.