Distributionally Robust Chance-Constrained Multicommodity Network Flow Problem in Dynamic Networks: A Column-Generation Approach
摘要
The multicommodity network flow problem is a classical issue in network optimization, where the objective is to route multiple commodities through interconnected nodes and arcs to minimize the overall flow cost. However, in practical scenarios, parameters such as capacity and demand vectors may be uncertain, and this uncertainty can significantly affect the optimal solution. To address this, several studies have incorporated uncertainty into multicommodity network flow models. We consider the situation where the probability distributions of arc capacities and node demands belong to a class of distributions. In this case, we consider the worst-case approach named distributionally robust chance-constrained (DRCC) optimization. For the given class of distributions, we present the deterministic counterpart of the path-flow formulation of the discrete dynamic multicommodity flow (DDMF) problem with intermediate storage is presented. Owing to the special structure of the proposed models, an algorithm based on the column-generation approach is provided for solving the proposed models. Furthermore, the performance of the DRCC is compared with the stochastic optimization (SO) method. Computational results demonstrate that the DRCC offers efficient approaches that require significantly fewer CPU times compared to the SO models for solving uncertain DDMF problems in large-scale networks.