An Approximate Solution Using K-Shortest Paths for a Communication Link Load Balancing Problem
Himeno Takahashi, Norihiko Shinomiya · 2023
In recent years, the amount of data traffic in information and communication networks has been increasing and the risk of congestion has been rising. Our previous study formulated a problem to determine the flow distribution that minimizes the maximum load factor of links with a goal of leveling the traffic load on the communication links. This problem is called UELB problem and proven to be NP-hard. Therefore, this paper proposes an approximate solution method for the UELB problem using K-shortest paths as one of the heuristic methods. As a result, the proposed method could obtain a feasible solution with less computational complexity than obtaining an exact solution.