A Stochastic User Equilibrium Approach for Solution of the Continuous Network Design Problem

The continuous network design problem (NDP) is an idealized mathematical version of a problem frequently faced by highway agencies, namely how to best increase the capacities of various links in the highway network. In particular, the objective in the NDP is to find a set of capacity increases which minimizes a combination of construction cost and the resulting travelling costs to highway users. In order to account for users' reactions to capacity increases, the NDP is contrained so that the minimim total cost is achieved when user route choices are in equilibrium. Characterization of this equilibrium condition is difficult, and the resulting optimization problems tend to be numerically intractable. In the most common formulation of the NDP, it is assumed that users know exactly which routes in the network result in lowest travel costs, and the characteristics of the resulting deteministic user equilibrium (DUE) are the source of the numerical difficulties. If instead we make the more realistic assumption that user perceptions of travel costs are subject to error but that low cost routes are chosen with greater probability than are high cost routes, the resulting stochastic user equilibrium (SUE) is often actually easier to characterize than the DUE, and the resulting NDP is, at least in principle, easier to solve. This project developed software implementing the NDP with SUE assignment using two optimization algorithms, sequential quadratic programming (SQP) and the generalized reduced gradient method (GRG2), and then evaluated their ability to solve NDPs on several hypthotical networks. Generally they performed as well or better than DUE based methods on small networks with low to moderate levels of congestion, but had difficulties as congestion became artificially high. Both SQP and GRG2 tended to find the same solutions in about the same amount of computer time, with GRG2 showing a slight advantage for the larger networks. On the Sioux Falls network of 24 nodes and 76 links, excessive computer costs prohibited running GRG2 on the available mainframe computers. A version of SQP was however implemented on a Sun Sparcstation computer, and this program was able to generate solutions for the Sioux Falls network that were comparable to those produced by DUE methods, but with fewer assignment iterations. It is concluded that the use of SUE provides both a theoretically and computationally feasible approach to solving the continuous NDP.