文章基本信息

标题：Comparing Algorithms for Minimizing Congestion and Cost in the Multi-Commodity k-Splittable Flow
本地全文：下载
作者：Chengwen Jiao ; Suixiang Gao ; Wenguo Yang 等
期刊名称：Computer and Information Science
印刷版ISSN：1913-8989
电子版ISSN：1913-8997
出版年度：2015
卷号：8
期号：2
页码：1
DOI：10.5539/cis.v8n2p1
出版社：Canadian Center of Science and Education
摘要：In the k-splittable flow problem, each commodity can only use at most k paths and the key point is to find the suitable transmitting paths for each commodity. To guarantee the efficiency of the network, minimizing congestion is important, but it is not enough, the cost consumed by the network is also needed to minimize. Most researches restrict to congestion or cost, but not the both. In this paper, we consider the bi-objective (minimize congestion, minimize cost) k-splittable problem. We propose three different heuristic algorithms for this problem, A1, A2 and A3. Each algorithm finds paths for each commodity in a feasible splittable flow, and the only difference between these algorithms is the initial feasible flow. We compare the three algorithms by testing instances, showing that choosing suitable initial feasible flow is important for obtaining good results.