  We consider a largely untapped potential for the improvement of traffic
networks that is rooted in the inherent uncertainty of travel times. Travel
times are subject to stochastic uncertainty resulting from various parameters
such as weather condition, occurrences of road works, or traffic accidents.
Large mobility services have an informational advantage over single network
users as they are able to learn traffic conditions from data. A benevolent
mobility service may use this informational advantage in order to steer the
traffic equilibrium into a favorable direction. The resulting optimization
problem is a task commonly referred to as signaling or Bayesian persuasion.
Previous work has shown that the underlying signaling problem can be NP-hard to
approximate within any non-trivial bounds, even for affine cost functions with
stochastic offsets. In contrast, we show that in this case, the signaling
problem is easy for many networks. We tightly characterize the class of
single-commodity networks, in which full information revelation is always an
optimal signaling strategy. Moreover, we construct a reduction from optimal
signaling to computing an optimal collection of support vectors for the Wardrop
equilibrium. For two states, this insight can be used to compute an optimal
signaling scheme. The algorithm runs in polynomial time whenever the number of
different supports resulting from any signal distribution is bounded to a
polynomial in the input size. Using a cell decomposition technique, we extend
the approach to a polynomial-time algorithm for multi-commodity parallel link
networks with a constant number of commodities, even when we have a constant
number of different states of nature.
