Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

A Tabu Search Algorithm with Direct Representation for Strip Packing

Abstract :

This paper introduces a new tabu search algorithm for a two-dimensional (2D) Strip Packing Problem (2D-SPP). It integrates several key features: A direct representation of the problem, a satisfaction-based solving scheme, two different complementary neighborhoods, a diversification mechanism and a particular tabu structure. The representation allows inexpensive basic operations. The solving scheme considers the 2D-SPP as a succession of satisfaction problems. The goal of the combination of two neighborhoods is (to try) to reduce the height of the packing while avoiding solutions with (hard to fill) tall and thin wasted spaces. Diversification relies on a set of historically “interesting” packings. The tabu structure avoids visiting similar packings. To assess the proposed approach, experimental results are shown on a set of well-known benchmark instances and compared with previously reported tabu search algorithms as well as the best performing algorithms.

Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03255431
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : mercredi 9 juin 2021 - 15:13:59
Dernière modification le : mercredi 20 octobre 2021 - 03:19:09

Lien texte intégral

Identifiants

Collections

Citation

Jean-Philippe Hamiez, Julien Robet, Jin-Kao Hao. A Tabu Search Algorithm with Direct Representation for Strip Packing. 9th European Conference, EvoCOP 2009, 2009, Tübingen, Germany. pp.61 - 72, ⟨10.1007/978-3-642-01009-5_6⟩. ⟨hal-03255431⟩

Partager

Métriques

Consultations de la notice

10