STOCHASTIC USER EQUILIBRIUM ASSIGNMENT IN NETWORKS WITH QUEUES

A stochastic user equilibrium assignment algorithm is presented for st eady state store-and-forward networks. The links of the network have c onstant travel times and the links or nodes have finite capacities. Wh en capacity is reached, delay sufficient to match demand to the availa ble capacity is generated. It has been shown by others that the equili brium assignment in networks of this kind is the solution to a particu lar linear programming problem. By adding an entropy term to the objec tive 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 li near and the non-linear programming problems give the equilibrium dela ys in the network. The requirements for uniqueness are investigated. I terative algorithms are formulated for solving the nonlinear programmi ng problem with either link or node constraints and convergence is pro ven. For networks where path enumeration is likely to be a problem, a column generation technique is proposed. An illustrative example is pr esented.