Multicommodity network flow problem with substitution

Abstract

Birden fazla ürünün ayrıt kapasiteleri gibi ortak kaynakları paylaştığı çok ürünlü ağ akış problemleri, tek ürünlü ağ akış problemlerinin genelleşmiş bir halidir. Tek ürünlü problemlerde ayrıtlar üzerindeki akış miktarları tam sayı olmaya zorlansa bile problem polinom zamanda çözülmesine karşın, problemin çok ürünlü ve ayrıt kapasiteli versiyonu NP-zor bir problemdir. Bu çalışmada çok ürünlü ağ akış probleminin ürünler arasında ikamenin mümkün olduğu daha da genelleşmiş bir halini tanımlıyoruz. İki veya üç ürünün yer aldığı, hem genel hem de ürüne özgü ayrıt kapasitelerin var olduğu problemlerin doğrusal tam sayılı programlama gösterimlerini matematiksel modeller olarak geliştiriyoruz. Kapasitesiz versiyonların matematiksel programlama gösterimlerindeki kısıt matrisinin tamamen ünimodüler olduğunu kanıtlıyoruz. Hipotez testi yöntemiyle rastgele yaratılan problemler üzerinden problem gösterimlerinin kapasiteli versiyonlarının deneysel hesaplama zorluğunu istatistiksel analiz yoluyla inceliyoruz. Kapasitelerin ve problem büyüklüğünün çözüm zamanına etkisini araştırıyoruz. Sonuçlarımız hem iki hem de üç ürünlü problemlerde hem genel hem de ürüne özgü kapasiteler probleme dahil edildiğinde çözüm zamanının önemli derecede arttığını gösteriyor. Problem boyutu büyüdükçe de çözüm zamanının arttığı ortaya çıkıyor. Son olarak iki ve üç ürünlü matematiksel modelleri çok ürünlü problem için genelleştiriyoruz.

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 NP-hard. 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 generalize two and three-commodity models for the multicommodity problem.