We study the optimal provision of information for two natural performance measures of queuing systems: throughput and makespan. A set of parallel links is equipped with deterministic capacities and stochastic travel times where the latter depend on a realized scenario. A continuum of flow particles arrives at the system at a constant rate. A system operator knows the realization of the scenario and may (partially) reveal this information via a public signaling scheme to the flow particles. Upon arrival, the flow particles observe the signal issued by the system operator, form an updated belief about the realized scenario, and decide on a link to use. Inflow into a link exceeding the link's capacity builds up in a queue that increases the travel time on the link. Dynamic inflow rates are in a Bayesian dynamic equilibrium when the expected travel time along all links with positive inflow is equal at every point in time. We provide an additive polynomial time approximation scheme (PTAS) that approximates the optimal throughput by an arbitrary additive constant $ε>0$. The algorithm solves a Langrangian dual of the signaling problem with the Ellipsoid method whose separation oracle is implemented by a cell decomposition technique. We also provide a multiplicative fully polynomial time approximation scheme (FPTAS) that does not rely on strong duality and, thus, allows to compute also the optimal signals. It uses a different cell decomposition technique together with a piece-wise convex under-estimator of the optimal value function. Finally, we consider the makespan of a Bayesian dynamic equilibrium which is defined as the last point in time when a total given value of flow leaves the system. Using a variational inequality argument, we show that full information revelation is a public signaling scheme that minimizes the makespan.

Reinforcement learning is an efficient, widely used machine learning technique that performs well in problems with a reasonable number of states and actions. This is rarely the case regarding control-related problems, as for instance controlling traffic signals, where the state space can be very large. One way to deal with the curse of dimensionality is to use generalization techniques such as function approximation. In this paper, a linear function approximation is used by traffic signal agents in a network of signalized intersections. Specifically, a true online SARSA$(\lambda)$algorithm with Fourier basis functions (TOS($\lambda $)-FB) is employed. This method has the advantage of having convergence guarantees and error bounds, a drawback of non-linear function approximation. In order to evaluate TOS($\lambda $)-FB, we perform experiments in variations of an isolated intersection scenario and a scenario of the city of Cottbus, Germany, with 22 signalized intersections, implemented in MATSim. We compare our results not only to fixed-time controllers, but also to a state-of-the-art rule-based adaptive method, showing that TOS($\lambda $)-FB shows a performance that is highly superior to the fixed-time, while also being at least as efficient as the rule-based approach. For more than half of the intersections, our approach leads to less congestion and delay, without the need for the knowledge that underlies the rule-based approach.

The mathematical approaches for modeling dynamic traffic can roughly be divided into two categories: discrete packet routing models and continuous flow over time models. Despite very vital research activities on models in both categories, the connection between these approaches was poorly understood so far. In this work we build this connection by specifying a (competitive) packet routing model, which is discrete in terms of flow and time, and by proving its convergence to the intensively studied model of flows over time with deterministic queuing. More precisely, we prove that the limit of the convergence process, when decreasing the packet size and time step length in the packet routing model, constitutes a flow over time with multiple commodities. In addition, we show that the convergence result implies the existence of approximate equilibria in the competitive version of the packet routing model. This is of significant interest as exact pure Nash equilibria, similar to almost all other competitive models, cannot be guaranteed in the multi-commodity setting. Moreover, the introduced packet routing model with deterministic queuing is very application-oriented as it is based on the network loading module of the agent-based transport simulation MATSim. As the present work is the first mathematical formalization of this simulation, it provides a theoretical foundation and an environment for provable mathematical statements for MATSim.