Multicommodity network flow problem with substitution

Official URL: http://risc01.sabanciuniv.edu/record=b1534417 (Table of Contents)

Multicommodity network flow problems are generalizations of single commodity network flow problems, where a number of commodities flow through the network often sharing common resources such as arc capacities. While the single commodity problem can be solved in polynomial time even when the flow quantities are imposed as integer values only, the integer multicommodity version of the problem with arc capacities is NPhard. We introduce a generalization of the multicommodity network flow problem where substitution is possible amongst commodities. We develop mathematical models as the linear integer programming formulations of two-commodity and three-commodity problems with both commodity-specific and overall arc capacities. We prove that constraint matrices are totally unimodular in the mathematical programming formulations for the uncapacitated versions. We investigate the empirical computational difficulty of capacitated versions of the problem formulations through a computational study with randomly generated problems and statistical analysis with hypothesis testing. In particular, we explore the effect of capacities and the problem size on solution time. Our results show that solution time significantly increases for both two-commodity and three-commodity problems when both overall and commodity-specific capacities exist. Solution time significantly increases when problem size is increased. Finally, we generalized the two and three-commodity models for the multicommodity problem.