[CMZ02] Variable neighborhood search for the optimization of cable layout problem

Revue Internationale avec comité de lecture : Journal Journal of Intelligent Manufacturing (Kluwer), vol. 13(5), 2002
Résumé: This paper deals with the optimization of cable layout, which is a problem encountered by Electricité de France (EDF) in power plant design. The problem consists in finding optimized cable routes connecting a set of pairs of facilities, respecting shelves’ capacities and a number of other constraints. We show that the problem is equivalent to optimizing the cost of multiple paths subject to capacity constraints. This is a special case of the integer min-cost multicommodity flow problem. In this paper, we first give a description of the cable layout problem (CLP) and a modelization of the most important constraints. We then propose to solve this problem using the extension variable neighborhood decomposition search (VNDS) of the recent variable neighborhood search (VNS) metaheuristic. This metaheuristic combines local search with systematic changes of neighborhood in the descent phases to escape from local optima. In the cable layout problem, we define the kth neighborhood of a solution S as the set of solution S¢ which differs from S in k cable paths. The obtained results are validated by bounds provided by Lagrangian relaxation and compared to results obtained by a tabu search.


@article {
title="{Variable neighborhood search for the optimization of cable layout problem}",
author="M.-C. Costa and F. Monclar and M. Zrikem",
journal="Journal of Intelligent Manufacturing (Kluwer)",