A NONSMOOTH OPTIMIZATION APPROACH TO NONLINEAR MULTICOMMODITY NETWORK FLOW PROBLEMS

From MaRDI portal





Determine the traffic equilibrium on a congested road network. This task typically raises a multicommodity flow problem with nonlinear, nondecreasing, convex arc cost functions. In the present article, the author considers the general network problem and in particular discusses the traffic equilibrium example. He first shows that one can concentrate on the dual of the multicommodity problem, since its solution directly determines an optimal solution of the original one. Moreover, the dual problem is rather well structured, it can be viewed as an essentially unrestricted maximization of a sum of concave functions: There will be one such function for every arc and one for every commodity, and for any specification of the dual variables, the values of these functions are implicately defined by rather simple minimization problems. Therefore, this structure naturally leads to a doubly iterative algorithm, reminiscent of column generation techniques. The author gives extensive guidelines concerning the implementation of the algorithm, proves its adequacy and discusses methods to speed up its convergence. The analysis, together with the reported computational results, convinces, so that one may expect this new approach to be able to deal with fairly large problems.











This page was built for publication: A NONSMOOTH OPTIMIZATION APPROACH TO NONLINEAR MULTICOMMODITY NETWORK FLOW PROBLEMS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3329185)