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 Université d'Angers <>
Soumis le : mercredi 9 juin 2021 - 15:13:59
Dernière modification le : jeudi 10 juin 2021 - 03:39:57

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

14