Evolutionary, constructive and hybrid procedures for the biobjective set packing problem

Abstract : The bi-objective set packing problem is a multi-objective combinatorial optimization problem similar to the well-known set covering/partitioning problems. To our knowledge, this problem has surprisingly not yet been studied. In order to resolve a practical problems encountered in railway infrastructure capacity planning, procedures for computing a solution to this bi-objective combinatorial problem were investigated. Unfortunately, solving the problem exactly in a reasonable time using a generic solver (Cplex) is only possible for small instances. We designed three alternative procedures approximating solutions to this problem. The first is based on version 1 of the 'Strength Pareto Evolutionary Algorithm', which is a population based-metaheuristic. The second is an adaptation of the 'Greedy Randomized Adaptative Search Procedure', which is a constructive metaheuristic. As underlined in the overview of the literature summarized here, almost all the recent, effective procedures designed for approximating optimal solutions to multi-objective combinatorial optimization problems are based on a blend of techniques, called hybrid metaheuristics. Thus, the third alternative, which is the primary subject of this paper, is an original hybridization of the previous two metaheuristics. The algorithmic aspects, which differ from the original definition of these metaheuristics, are described, so that our results can be reproduced. The performance of our procedures is reported and the computational results for 120 numerical instances are discussed.
Type de document :
Rapport
2005
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00679897
Contributeur : Florent Breuil <>
Soumis le : vendredi 16 mars 2012 - 15:28:42
Dernière modification le : jeudi 5 avril 2018 - 10:36:49

Identifiants

  • HAL Id : emse-00679897, version 1

Citation

Xavier Delorme, Xavier Gandibleux, Fabien Degoutin. Evolutionary, constructive and hybrid procedures for the biobjective set packing problem. 2005. 〈emse-00679897〉

Partager

Métriques

Consultations de la notice

225