Global benefit of randomness in individual routing on transportation networks

By introducing a simple model based on two-dimensional cellular automata, we reveal the relationship between the routing strategies of individual vehicles and the global behavior of transportation networks. Specifically, we characterize the routing strategies by a single parameter called path-greediness, which corresponds to the tendency for individuals to travel via a shortest path to the destination. Remarkably, we found that the effective dimension of the system is reduced when the congested states emerge. We also found that a high individual tendency to travel via the shortest path does not necessarily shorten the average journey time, as the system may benefit from less greedy routing strategies in congested situations. Finally, we show that adaptive routing strategies outperform controlled strategies in the free-flow state but not in the congested state, implying that controlled strategies may increase coordination among vehicles and are beneficial for suppressing traffic congestion.

Figure 1

The simulation results of the average vehicle speed $\overline{v}$ as a function of $\rho$ with path-greediness $g=0.6$ on square lattices with various length $L$. The results are obtained with $T=3\times {10}^6$ and an equilibration time $T_e=2.5\times {10}^6$, averaged over 1000 instances. The cases with different $L$ become congested as vehicle density $\rho$ increases beyond a critical value.

Figure 2

(a) The simulation results of the average movement count ${\overline{n}}_{\mathrm{movement}}$ as a function of $\rho$ with $L=20$ and various values of $g$. (b) The simulation results of ${\overline{n}}_{\mathrm{arrival}}$, i.e., the average arrival count per time step, as a function of $\rho$ with $L=20$ and various values of $g$. The results are obtained with $T=3\times {10}^6$ and an equilibration time $T_e=2.5\times {10}^6$, averaged over 1000 instances. The average movement count ${\overline{n}}_{\mathrm{movement}}$ and the average arrivals count per time step ${\overline{n}}_{\mathrm{arrival}}$ show that the cases with smaller $g$ become congested as vehicle density increases beyond $\rho >{\rho }_c$.

Figure 3

An example of the snapshots of vehicle location on a $20\times 20$ square lattice, with $g=0.6$ and (a) $\rho =0.1$, (b) $\rho =0.4$, and (c) $\rho =0.66$. Filled sites are occupied by vehicles while unfilled sites are empty. (a) The system is in the free-flow state and vehicles are roughly evenly distributed on the lattice. (b) The system is in the congested-flow state and most vehicles are stuck in the congested cluster, except vehicles at the cluster periphery. (c) The system is in the congested state, and the congested cluster increases to a size which spans the system.

Figure 4

(a) The simulation results of the average movement count ${\overline{n}}_{\mathrm{movement}}$ as a function of $\rho$ with $L=20$ and $g=0.6$. Three states are shown: the free-flow state with $\rho <{\rho }_c$, the congested-flow state with ${\rho }_1<\rho <{\rho }_2$ and the congested state with $\rho <{\rho }_2$. (b) The phase diagram showing the three states as a function of $\rho$ and $g$.

Figure 5

The simulation results of the system traffic flow $F=f{L}^2$, rescaled as (a) ${\overline{n}}_{\mathrm{movement}}/L^2$ and (b) ${\overline{n}}_{\mathrm{movement}}/L$ as a function of $\rho$ with $g=0.6$ and various values of $L$. Data collapse is observed in the regime of the free-flow state (i.e., $\rho <{\rho }_c$) in (a), and the congested-flow and the congested state (i.e., $\rho >{\rho }_c$) in (b).

Figure 6

(a) The average vehicle speed $\overline{v}$, (b) the average journey time and (c) the average journey distance between the origin and destination of vehicles, as well as (d) the average arrival count per time step as a function of vehicle density $\rho$, for $L=20$ and various values of path-greediness $g$. The corresponding results for the cases with adaptive path-greediness are also shown. The results are obtained with $T=3\times {10}^6$ and an equilibration time $T_e=2.5\times {10}^6$, averaged over 1000 instances. Insets: the enlarged plots of the average journey time and distance in the regime with small density $\rho$ are shown in the insets of (d) and (c). As we can see, the cases with higher path-greediness $g$ have higher tendency to be congested than the cases with lower $g$ at the same vehicle density, or in other words, a lower critical density ${\rho }_c$ beyond which congestion occur.

Figure 7

The simulation results of the optimal value of $g$ identified in the controlled case for each density $\rho$, compared with the average value of $g$ in the adaptive case, on $20\times 20$ square lattices with $T=3\times {10}^6$ and an equilibration time $T_e=2.5\times {10}^6$, averaged over 1000 instances. Compared to vehicles in the controlled case, vehicles in the adaptive case self-adapt to a higher $g$ value in the free-flow state and are globally beneficial as shown by Fig. 6; this is not true in the congested state.

Figure 8

The simulation results of the threshold densities ${\rho }_c$ and ${\rho }_2$ as a function of system size $L^2$. Inset: the enlarged plots of the average movement count in the regime with $\rho \approx {\rho }_2$. These results show that the values of ${\rho }_c$ and ${\rho }_2$ converge as system size $L^2$ increases.