On the ring loading problem with demand splitting. (Q1417597)

The ring loading problem with demand splitting (RLPW) is defined on an undirected ring network. For each \(k\in K\) there are given \(r_k\) units of flow requirements, which can be routed in either of two directions (\(K\) is the index set of the selected origin-destination pairs of nodes). The objective of this problem is to find an optimal routing that minimizes the maximum edge load. The RLPW arises when designing synchronous optical network bidirectional self-healing rings. In this paper the authors develop an algorithm for RLPW that runs faster than any other existing algorithm. It requires \(O(\min\{n| K|, n^2\})\) time. The authors also conduct a computational study to evaluate the practical performance of proposed algorithm.