A parallel hybrid optimization algorithm for some network design problems

Diarrassouba, Ibrahima; Labidi, Mohamed Khalil; Mahjoub, Ali Ridha

Diarrassouba, Ibrahima; Labidi, Mohamed Khalil; Mahjoub, Ali Ridha (2019), A parallel hybrid optimization algorithm for some network design problems, Soft Computing, 23, 6, p. 1947-1964. 10.1007/s00500-017-2907-x

Type

Article accepté pour publication ou publié

Date

2019

Journal name

Soft Computing

Volume

Number

Pages

1947-1964

Abstract (EN)

Network design problems have been widely studied in the last decades due to the importance of ICT in our daily life and are still the subject of extensive researches. Network design covers a large family of problems, and several algorithms, both exact and heuristic methods, have been proposed to address each of them. In this paper, we consider two variants of the so-called survivable network design problem and propose a generic parallel hybrid algorithm to solve them. The algorithm is based on the hybridization of a Lagrangian relaxation algorithm, a greedy algorithm and a genetic algorithm. We present, for each variant, a computational study showing the efficiency of our approach in producing both lower and upper bounds for the optimal solution.

Subjects / Keywords

Genetic algorithm; Hybridization; kHNDP; kESNDP; Lagrangian relaxation; Metaheuristic; Parallel computing