Metaheuristic approaches for solving packing problems: 0/1 multidimensional knapsack problem and two-dimensional bin packing problem as examples

Résumé

The present thesis is about metaheuristic approaches for packing problems. Focusing our investigation on two different problems in terms of kind of assignment: The multidimensional knapsack problem (0/1 MKP) that belongs to the output value maximization type and the two-dimensional bin packing problem (2D-BPP) that falls to the input value minimization type. The 0/1 MKP occupies an important place in packing problems thanks to its theoretical and practical interest, followed by the 2D-BPP that has been also used to model various decision-making processes. These two basic problems arise in numerous real-world applications. They occur, for example, in the allocation of resources problems, scheduling problems, cutting problems as well as in transportation and logistics, to mention just a few. The 0/1 MKP can be informally stated as a problem of packing a set of items that maximizes the profit of a multidimensional knapsack as much as possible, taking into consideration the limited capacity of its dimensions. The knapsack dimensions can be, for instance, the maximum weight that can be carried, the maximum height, or the maximum available volume that can accommodate items. On the other hand, the 2D-BPP is the problem of packing, without overlapping, a given set of small rectangular-shaped items into a minimum number of large identical rectangles (called bins) with the edges of the items parallel to those of bins. The 0/1 MKP as well as the 2D-BPP belong to NP-hard optimization problems, which means there is no exact algorithm that can find an optimal solution for such problems in polynomial time. However, they can be resolved with approximate methods, especially heuristics and metaheuristics. These methods seek to find a trade-off between the solution quality and the consuming-time but without ensuring the optimality. This thesis proposes various metaheuristics for solving the two packing problems. We develop an improved genetic algorithm that solves efficiently the 0/1 MKP in reasonable runtime as well as a hybrid approach that incorporates a k-means clustering method in the genetic algorithm. Moreover, we make use of a recent metaheuristic belonging to the swarm intelligence algorithms, namely the crow search algorithm (CSA). Indeed, we adapt the CSA to the context of 2D-BPP by applying two different techniques, a binarization technique and a hybridization technique. The performance of the proposed metaheuristics is evaluated through extensive computational experiments by using the benchmark data of the two problems. Finally, we should note that the proposed metaheuristics could be applied to various optimization problems to compute approximate solutions.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 2

Téléchargements : 0