CADILAC: CAaminos DIsjuntos de Largo ACotado

Abstract

The problem under study is to find k node-disjoint paths between two terminals of a network. The network has cost in the links, and the goal is to build k node-disjoint paths at the minimum cost, with the additional requirement that the length of each path must not exceed a fixed positive integer d, called the diameter. This combinatorial problem belongs to the N P-Complete class, and as a consequence there is no exact solution available with polynomial time. In the related literature there are particular solutions to the problem when the diameter is not a constraint, such as Suurballe and Bhandari algorithms. Other authors either work with planar, acyclic graphs or study the case where
k = 2. In this work we introduce a GRASP heuristic, named CADILAC, for the general problem. The algo- rithm combines andomization and adaptive diversity to build paths, and it is inspired by Bhandari and DIMCRA algorithms. The latter was considered to build two link-disjoint paths in a graph with multidimensional costs in the links. Randomization is added to Bhandari’ s algorithm during the construction search phase. It also includes some ingredients from DIMCRA. The local search phase has a sub-path replacement strategy to explore the seach space. Finally, we compare the performance of CADILAC versus a Greedy resolution. We remark that Greedy presents lower computational requirements, but CADILAC achieves both feasible and cheaper solutions