Stochastic user equilibrium assignment in networks with queues

A stochastic user equilibrium assignment algorithm is presented for steady state store-and-forward networks. The links of the network have constant travel times and the links or nodes have finite capacities. When capacity is reached, delay sufficient to match demand to the available capacity is generated. It has been shown by others that the equilibrium assignment in networks of this kind is the solution to a particular linear programming problem. By adding an entropy term to the objective function, a convex nonlinear programming problem is formed which yields a stochastic user equilibrium assignment. For the case of link constraints, it is proven that the Lagrange multipliers of both the linear and the non-linear programming problems give the equilibrium delays in the network. The requirements for uniqueness are investigated. Iterative algorithms are formulated for solving the nonlinear programming problem with either link or node constraints and convergence is proven. For networks where path enumeration is likely to be a problem, a column generation technique is proposed. An illustrative example is presented.