A hybrid-bundle decomposition method and its application to the traffic assignment problem

LOTITO, PABLO; SAGASTIZABAL, CLAUDIA

Rio de Janeiro, Brasil

Congreso; 19th International Symposium on Mathematical Programming; 2006

Mathematical Programming Society

The traffic assignment problem consists in finding an equilibrium state, over a network, defined in terms of arc travel costs that depend on the arc flows. Mathematically, it is a convex multi-flow problem of large scale. To obtain a good reduction of the objective function the Frank- Wolfe method based on arc flows can be applied. When more precision is needed other methodology must be considered like decomposition or column generation techniques based on route flows. We propose a new decomposition technique derived from coupling a hybrid projectionproximal point algorithm with a bundle method. We prove convergence of the resulting algorithm and report some preliminary numerical experience comparing our method with Frank-Wolfe, a column generation algorithm called DSD and other algorithms based on other decomposition techniques.