Solving semi-asymmetric traffic assignment problems with the dantzig-wolfe decomposition method

In this paper, we show that how to use the Dantzig-Wolfe decomposition to solve the semi-asymmetric TAP (traffic assignment problem). By adding dummy variables for creating linking constraints, the problem can be decomposed into a master problem (an asymmetric TAP) and a subproblem (a symmetric TAP). That is, the subproblem can be solved by performing shortest path computations, which is further modified by information passed from the last solution of the master problem in a manner analogous to Dantzig-Wolfe decomposition for optimization. The master problem forms convex combinations of proposals from the subproblem, and enforces the linking constraints. The motivation of this work is to ease model development and maintenance, such as how to build a semi-asymmetric TAP from a well-developed symmetric TAP by means of the solution method. A valid stopping condition is derived, and an illustration is provided.