A Bender's Decomposition Based Solution Method for Solving User Equilibrium Problem: Deterministic and Stochastic Cases

The traffic assignment problem is one of the most important problems for analyzing and optimizing the transportation network to find optimal flows. This study presented a new formulation based on a generalized Bender's decomposition approach to solve its important part, i.e. user equilibrium problems, in deterministic and stochastic cases. The new approach decomposed the problem into a master problem and a sub problem. The first one was a nonlinear and the latter a linear programming problem. Iteratively, the master problem was solved and its outputs were used to solve the sub-problem in which to form appropriate cuts and add them to the master problem for solving it in the next iteration. Based on the convergence of Bender's decomposition, the iterative process was terminated in a finite number of steps. In this manner, some numerical examples were explained and compared with other methods.