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


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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).

About the authors

A. V. Gasnikov

Chair of Mathematical Foundations of Control, Moscow Institute of Physics and Technology; Kharkevich Institute for Information Transmission Problems; Department of Big Data and Data Search, Faculty of Computer Science, State University—Higher School of Economics

Author for correspondence.
Email: gasnikov@yandex.ru
Russian Federation, Dolgoprudnyi, Moscow oblast, 141700; Moscow, 127051; Moscow, 125319

E. V. Gasnikova

Laboratory of Structural Analysis Methods in Predictive Simulation, Moscow Institute of Physics and Technology

Author for correspondence.
Email: egasnikova@yandex.ru
Russian Federation, Dolgoprudnyi, Moscow oblast, 141700

Yu. E. Nesterov

Center for Operation Research and Econometrics, Université Catholique de Louvain; Department of Big Data and Data Search, Faculty of Computer Science, State University—Higher School of Economics

Author for correspondence.
Email: yurii.nesterov@uclouvain.be
Belgium, Louvain-la-Neuve, B-1348; Moscow, 125319

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2018 Pleiades Publishing, Ltd.