Distributionally Robust Chance-Constrained Multicommodity Network Flow Problem in Time-Varying Networks: By Column-Generation Approach

Abstract

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 arc capacities, node demands, and travel costs may be uncertain, and this uncertainty can significantly affect the optimal solution. To address this, several studies have developed methods to incorporate uncertainty into multicommodity network flow models. This study focuses on the discrete dynamic multicommodity flow (DDMF) problem with intermediate node storage, which aims to minimize the cost of network flow over time. To achieve this, the path-flow formulation of DDMF is considered for the minimum cost network flow problem under parameter uncertainty. The study explores different perspectives, including robust optimization, chance-constrained (CC) optimization, and distributionally robust chance-constrained (DRCC) optimization. Certain models are formulated for each perspective. Furthermore, the performance of the DRCC, CC, proposed robust counterpart (RC), and stochastic optimization (SO) methods is compared. Computational results demonstrate that the DRCC and RC models offer efficient approaches that require significantly fewer CPU times compared to the CC and SO models for solving uncertain DDMF problems in large-scale networks.