Finding good candidate cycles for efficient p-cycle network design

摘要

An important problem in p-cycle network design is to find a set of p-cycles to protect a given working capacity distribution so that the total spare capacity used by the p-cycles is minimized. Existing approaches for solving the problem include ILP and heuristic algorithm. Both require a set of candidate p-cycles to be precomputed. In this paper, we propose an algorithm to compute a small set of candidate p-cycles that can lead to good performance when used by ILP or the heuristic algorithm. The key idea of the algorithm is to generate a combination of high efficiency cycles and short cycles so that both densely distributed and sparsely distributed working capacities can be efficiently protected by the candidate cycles. The algorithm is also flexible in that the number of cycles generated is controlled by an input parameter. Simulation study showed that the cycles generated by our algorithm can lead to near optimal solutions when used by either ILP or the heuristic algorithm.