Optimal geometry of transportation networks

Motivated by the shape of transportation networks such as subways, we consider a distribution of points in the plane and ask for the network $G$ of given length $L$ that is optimal in a certain sense. In the general model, the optimality criterion is to minimize the average (over pairs of points chosen independently from the distribution) time to travel between the points, where a travel path consists of any line segments in the plane traversed at slow speed and any route within the subway network traversed at a faster speed. Of major interest is how the shape of the optimal network changes as $L$ increases. We first study the simplest variant of this problem where the optimization criterion is to minimize the average distance from a point to the network, and we provide some general arguments about the optimal networks. As a second variant we consider the optimal network that minimizes the average travel time to a central destination, and we discuss both analytically and numerically some simple shapes such as the star network, the ring, or combinations of both these elements. Finally, we discuss numerically the general model where the network minimizes the average time between all pairs of points. For this case, we propose a scaling form for the average time that we verify numerically. We also show that in the medium-length regime, as $L$ increases, resources go preferentially to radial branches and that there is a sharp transition at a value $L_c$ where a loop appears.

Figure 1

(a) Histogram of the total length $L$ of subway networks. (b) Total length of the network versus first construction date $t_0$. We grouped the networks according to broad regions.

Figure 2

Typical observed shapes when the length $L$ increases. For small $L$ we observe a line or a simple tree. For larger $L$ we observe the appearance of a loop and for much larger $L$ more complex shapes including a lattice like network or a superimposition of a ring and radial lines.

Figure 3

Definition of the model. Residences or workplaces are represented by points. The graph $G$ represents the subway and we look for the quickest path that connects any pair of nodes. We have to compare the direct path (dotted line) with the “multimodal” path (dashed and solid red lines) that combines both walking and using the subway.

Figure 4

Rescaled average distance $L\overline{d}{\left(L\right)}_{\text{opt}}$ versus $L$ for the spiral and the star network (for the Gaussian disorder with $\sigma =1$). For the spiral, we observe a slow convergence toward the theoretical limit $2\pi$ for gaussian disorder (horizontal dotted line). The convergence is even slower for the star network which converges to $2^{1/2}{\pi }^{3/2}$ (horizontal dashed line). For $L\approx 110$ (dashed vertical line) the spiral outperforms the star network.

Figure 5

Main shapes studied here (in addition to the line and the spiral). (a) The “hashtag” of $2\times 2$ grid with parameter $s$. (b) The “C-shape” with paramerers $s$ and $\theta$. (c) The “S-shape” with parameter $\theta$. (d) The star network with $n_b$ branches of size $r^{*}$.

Figure 6

Average distance to the network versus L for various shapes.

Figure 7

Study of the C-shape with parameter $s$ and $\theta$.

Figure 8

Study of the S-shape: evolution of the optimal angle $\theta$ versus $L$.

Figure 9

Best configurations obtained with simulated annealing for different values of $L=5,10,20,50$. The simulations are obtained with a lattice polymer and using the pivot algorithm [28].

Figure 10

We show here the result of the minimization of the average time for the star network with parameters $n_b$ and $r^{*}$ with the constraint $L=n_b{r}^{*}$. On the left (a, c) we show the length of branches $r^{*}$ versus $u_0=L/R$ and on the right (b, d) the number of branches $n_b$ versus $u_0$ (here $\eta =1/8$). The top row corresponds to the uniform density case and the bottom one to the exponential density.

Figure 11

Schematic of the star network combined with a ring. We have now three parameters: the number of branches $n_b$, the length $r^{*}$ of the branches, and the radius $\ell$ of the ring.

Figure 12

Uniform density: results for the star+loop network for different values of $n_b$. (a) Normalized radius of the ring. (b) Normalized length of branches. We normalized $u_0$ by $n_b$ to get the same “transition” point at $u_0/n_b=1$. These results are obtained for $\eta =1/8$.

Figure 13

Gaussian density ($\sigma =1$): results for the star+loop network for $n_b=8$. (a) Size $r^{*}$ of the branches. (b) Radius of the ring. These results are averaged over 100 configurations and are obtained for $\eta =1/8$. The gray curves represent the results for each configuration.

Figure 14

Average journey time in the Gaussian case for different values of $S$ and for (a) a line $[-L/2.L/2]$ and (b) a ring of radius $R=L/2\pi$.

Figure 15

Average journey time (in the Gaussian case) for star networks with different number of branches ($n_b=2,4,6$).

Figure 16

Average time (Gaussian density) for $n_b$ branches plus a loop for values of $S$ from 14 to 100.

Figure 17

Rescaled average time $S{\overline{\tau }}_{\text{min}}$ versus the rescaled variable $S/\sqrt{L}$.

Figure 18

Optimal length of branches and optimal size of the loop versus the total length $L$ (for gaussian disorder): typical shape for $r^{*}$ and $\ell$. As in the case of the quickest path to the origin, we observe a sharp transition for $L\approx 20\sigma$ where a loop of radius $\ell \approx \sigma$ appears (here $\eta =1/2$).