Haasler, IsabelRingh, AxelChen, YongxinKarlsson, Johan2023-07-172023-07-172023-07-172023-06-1510.1287/moor.2021.148https://infoscience.epfl.ch/handle/20.500.14299/199206WOS:001014609000001In this work, we develop a new framework for dynamic network flow pro-blems based on optimal transport theory. We show that the dynamic multicommodity minimum-cost network flow problem can be formulated as a multimarginal optimal transport problem, where the cost function and the constraints on the marginals are asso-ciated with a graph structure. By exploiting these structures and building on recent advances in optimal transport theory, we develop an efficient method for such entropy -regularized optimal transport problems. In particular, the graph structure is utilized to efficiently compute the projections needed in the corresponding Sinkhorn iterations, and we arrive at a scheme that is both highly computationally efficient and easy to implement. To illustrate the performance of our algorithm, we compare it with a state-of-the-art linear programming (LP) solver. We achieve good approximations to the solution at least one order of magnitude faster than the LP solver. Finally, we showcase the methodology on a traffic routing problem with a large number of commodities.Operations Research & Management ScienceMathematics, AppliedOperations Research & Management ScienceMathematicsmultimarginal optimal transportdynamic network flowmulticommodity network flowsinkhorn's methodcomputational methodstraffic routingmarginal optimal transporttraffic-controlmulticommodityformulationtext::journal::journal article::research article