Comparing Algorithms for Minimizing Congestion and Cost in the Multi-Commodity k-Splittable Flow

摘要

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, A_1, A_2 and A_3. 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.