Dual Methods for Finding Equilibriums in Mixed Models of Flow Distribution in Large Transportation Networks

Аннотация

The problem of equilibrium distribution of flows in a transportation network in which a part of edges are characterized by cost functions and the other edges are characterized by their capacity and constant cost for passing through them if there is no congestion is studied. Such models (called mixed models) arise, e.g., in the description of railway cargo transportation. A special case of the mixed model is the family of equilibrium distribution of flows over routes—BMW (Beckmann) model and stable dynamics model. The search for equilibrium in the mixed model is reduced to solving a convex optimization problem. In this paper, the dual problem is constructed that is solved using the mirror descent (dual averaging) algorithm. Two different methods for recovering the solution of the original (primal) problem are described. It is shown that the proposed approaches admit efficient parallelization. The results on the convergence rate of the proposed numerical methods are in agreement with the known lower oracle bounds for this class of problems (up to multiplicative constants).