text: ABSTRACTIn many ‘smart city’ applications, congestion arises in part due to the nature of signals received by individuals from a central authority. In the model of , each agent uses one out of multiple resources at each time instant. The per-use cost of a resource depends on the number of concurrent users. A central authority has up-to-date knowledge of the congestion across all resources and uses randomisation to provide a scalar or an interval for each resource at each time. In this paper, the interval to broadcast per resource is obtained by taking the minima and maxima of costs observed within a time window of length r, rather than by randomisation. We show that the resulting distribution of agents across resources also converges in distribution, under plausible assumptions about the evolution of the population over time.
  @cite_14: Most research and applications of network equilibrium models are based on the assumption that traffic volumes on roadways are virtually certain to be at or near their equilibrium values if the equilibrium volumes exist and are unique. However, it has long been known that this assumption can be violated in deterministic models. This paper presents an investigation of the stability of stochastic equilibrium in a two-link network. The stability of deterministic equilibrium also is discussed briefly. Equilibrium is defined to be stable if it is unique and the link volumes converge over time to their equilibrium values regardless of the initial conditions. Three models of route choice decision-making over time are formulated, and the stability of equilibrium is investigated for each. It is shown that even when equilibrium is unique, link volumes may converge to their equilibrium values, oscillate about equilibrium perpetually, or converge to values that may be considerably different from the equilibrium ones, depending on the details of the route choice decision-making process. Moreover, even when convergence of link volumes to equilibrium is assured, the convergence may be too slow to justify the standard assumption that these volumes are usually at or near their equilibrium values. When link volumes converge to non-equilibrium values, the levels at which the volumes stabilize typically depend on the initial link volumes or perceptions of travel costs. Conditions sufficient to assure convergence to equilibrium in two of the three models of route choice decision-making are presented, and these conditions are interpreted in terms of the route choice decision-making process.
  @cite_54: The Stochastic User Equilibrium (SUE) model predicts traffic equilibrium flow assuming that users choose their perceived maximum utility paths (or perceived shortest paths) while accounting for the effects of congestion that arise due to users sharing links. Inspired by recent work on distributionally robust optimization, specifically a Cross Moment (CMM) choice model, we develop a new SUE model that uses the mean and covariance information on path utilities but does not assume the particular form of the distribution. Robustness to distributional assumptions is obtained in this model by minimizing the worst-case expected cost over all distributions with fixed two moments. We show that under mild conditions, the CMM-SUE (Cross Moment-Stochastic User Equilibrium) exists and is unique. By combining a simple projected gradient ascent method to evaluate path choice probabilities with a gradient descent method to find flows, we show that the CMM-SUE is efficiently computable. CMM-SUE provides both modeling flexibility and computational advantages over approaches such as the well-known MNP-SUE (Multinomial Probit-Stochastic User Equilibrium) model that require distributional (normality) assumptions to model correlation effects from overlapping paths. In particular, it avoids the use of simulation methods employed in computations for the distribution-based MNP-SUE model. Preliminary computational results indicate that CMM-SUE provides a practical distributionally robust alternative to MNP-SUE.
  @cite_21: Incidents whose frequencies are unknown cause a large part of the unreliability of road networks. Especially risk-averse road users avoid the possibility of large travel times under a disruption. This paper proposes a traffic assignment which accounts for risk-averseness. Scenarios for all possible disruptions are simulated. The risk-averseness of a user is generalized in a two-parameter route choice formulation. Depending on the parameters, users assign a weight on the travel times for each scenario. This is the basis for their route choice. The simulator can handle a traffic flow composed from different user classes simultaneously in the same network. In the presented case study, the link loads depend on the parameter settings of the users. The route choice for a user class also depends on the risk-averseness of the other users in the network.
  @cite_50: The paper formulates link-flow definitions of equilibrium and stability, and gives conditions which guarantee the existence, uniqueness and stability of traffic equilibria. Junction delays in towns usually depend on the traffic flow along intersecting links; the theory presented here is designed to be applicable when there are such junction interactions.
  @cite_49: This paper contains a quantitative evaluation of probabilistic traffic assignment models and proposes an alternate formulation. First, the concept of stochastic-user-equilibration (S-U-E) is formalized as an extension of Wardrop's user-equilibration criterion. Then, the stochastic-network-loading (S-N-L) problem (a special case of S-U-E for networks with constant link costs) is analyzed in detail and an expression for the probability of route choice which is based on two general postulates of user behavior is derived. The paper also discusses the weaknesses of existing S-N-L techniques with special attention paid to Dial's multipath method and compares them to the suggested approach. The proposed model seems reasonable and does not exhibit the inherent weaknesses of the logit model when applied to sets of routes which overlap heavily. The discussion is supported by several numerical examples on small contrived networks. The paper concludes with the discussion of two techniques that can be used to approximate the link flows resulting from the proposed model in large networks.
  @cite_31: We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0−1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0−1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard α-approximable 0−1 discrete optimization problem, remains α-approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network.
summary: In the transportation literature, Daganzo and Sheffi @cite_49 have introduced the concept of stochastic user equilibrium, where users have considerable amounts of information, and perhaps surprising analytical powers. Subsequently, a number of variants have been proposed, e.g., @cite_31 consider robust variants and @cite_54 consider the stochastic user equilibrium with distributional uncertainty over the travel times. @cite_21 consider a stratified and risk-averse population, but only as much as a link failure is concerned. There are a number of other notions of stability, perhaps closer to our notion, inasmuch they capture the repeated nature of the problem. For example, @cite_50 introduces the notion of equilibrium as the limit of the congestion distribution if it exists. @cite_14 considers a number of notions of noisy signals and studies greedy policies and equilibria. Our approach is different from those that assign actions to agents, instead of presenting them with information and letting them make the decisions.