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


  •  Chengwen Jiao    
  •  Suixiang Gao    
  •  Wenguo Yang    

Abstract

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.


This work is licensed under a Creative Commons Attribution 4.0 License.
  • ISSN(Print): 1913-8989
  • ISSN(Online): 1913-8997
  • Started: 2008
  • Frequency: quarterly

Journal Metrics

WJCI (2020): 0.439

Impact Factor 2020 (by WJCI): 0.247

Google Scholar Citations (March 2022): 6907

Google-based Impact Factor (2021): 0.68

h-index (December 2021): 37

i10-index (December 2021): 172

(Click Here to Learn More)

Contact