  Coordination of dynamical routes can alleviate traffic congestion and is
essential for the coming era of autonomous self-driving cars. However,
dynamical route coordination is difficult and many existing routing protocols
are either static or without inter-vehicle coordination. In this paper, we
first apply the cavity approach in statistical physics to derive the
theoretical behavior and an optimization algorithm for dynamical route
coordination, but they become computational intractable as the number of time
segments increases. We therefore map static spatial networks to space-time
networks to derive a computational feasible message-passing algorithm
compatible with arbitrary system parameters; it agrees well with the analytical
and algorithmic results of conventional cavity approach and outperforms
multi-start greedy search in saving total travel time by as much as 15% in
simulations. The study sheds light on the design of dynamical route
coordination protocols, and the solution to other dynamical problems via static
analytical approaches on space-time networks.
