The ring loading problem

摘要

The following problem arose in the planning of optical communications networks in which various ring structures are used to carry given traffic demands at least cost. When the pool of demand that is potentially carried on a ring is large relative to the ring's line capacity, the problem is to find the subset of demands and their respective routing choices that maximizes the total demand carried by the ring. This is a NP-hard problem. In the complex network programming, this problem needed to be solved numerous times. Two heuristic algorithms are proposed and the relative performance of these algorithms is assessed in this paper.