A Parallel Hybrid Genetic Algorithm for the k-Edge-Connected Hop-Constrained Network Design Problem

Network design problems have been largely studied in the last decades due to the ubiquity of IT communication in our daily life. We address in this paper the k-edge-connected hop-constrained network design problem (kHNDP) which is known to be NP-hard. In this paper, we present a hybrid parallel approach for solving the kHNDP based on a Lagrangian relaxation algorithm, a greedy algorithm, and a genetic algorithm. Computational results obtained with our algorithms are compared with those from CPLEX.