Efficient algorithms for the knapsack sharing problem
Résumé. Dans cet article, nous proposons deux méthodes efficaces pour la résolution du problème de la distribution, équitable (Knapsack Sharing Problem, noté KSP). Une instance du KSP est définie par une capacité c et un ensemble de n objets, où à chaque objet j, j=1,...,n, associe un profit pj et un poids wj. L'ensemble des objets est divisé en m différentes classes et le but est de déterminer un sous-ensemble d'objets qui rentre dans le knapsack réalisant la valeur max-min sur l'ensemble des classes. La première méthode approchée est considérée comme une recherche locale simple, notée SDTS. Dans cette méthode nous utilisons un paramètre représentant la profondeur des éléments critiques des classes considérées tout en utilisant une liste tabou. La liste tabou nous permet d'éviter de retomber sur des solutions déjà visitées auparavant. La deuxième méthode approchée est une version plus sophistiquée. Cette fois, la trajectoire de la profondeur est utilisée sur deux différentes directions tout en maintenant la liste tabou déjà utilisée dans la première méthode. Les méthodes proposées ont été testées sur un ensemble d'instances de la littérature. Les résultats obtenus ont été très satisfaisants.
Abstract.
In this paper, we propose two efficient algorithms in order to approximately solve the Knapsack Sharing
Problem (KSP). In KSP, we have a knapsack of capicity c and a set of n objects, where each
object j, j=1,...,n, is associated with a profit pj and a weight
wj. The set of objects is divided into m different classes of objects and, the
aim is to determine a subset of objects to be included in the knapsack which realizes a max-min value over
all classes. The first algorithm is considered as a simple local search, namely Simple Depth Tabu Search
(SDTS), in which a depth-parameter and a tabu list are used. The second algorithm, namely Multiple Depth
Tabu Search (MDTS), is considered as an extended approach in which the depth-parameter is applied in two
different ways. The proposed algorithms are implemented and computational experiments are carried out to
analyze their behavior. Encouraging results have been obtained.
*PRiSM-CNRS URA 1525, Université de Versailles-Saint-Quentin en Yvelines, 45 avenue des Etats-Unis, 78035 Versailles Cedex, France |