An Efficient Algorithm for the Knapsack Sharing Problem |
| |
Authors: | Mhand Hifi Slim Sadfi Abdelkader Sbihi |
| |
Institution: | (1) LaRIA, Université de Picardie Jules Verne, 5 rue du Movlin Neuf, 80000 Amiens, France;(2) CERMSEM-CNRS URA 8095, Maison des Sciences Economiques, Université de Paris 1 Panthéon-Sorbonne, 106-112 Boulevard de l'Hôpital, 75647 Paris Cedex 13, France |
| |
Abstract: | The Knapsack Sharing Problem (KSP) is an NP-Hard combinatorial optimization problem, admitted in numerous real world applications. In the KSP, we have a knapsack of capacity c and a set of n objects, namely N, where each object j, j = 1,...,n, is associated with a profit p
j and a weight w
j. The set of objects N is composed of m different classes of objects J
i, i = 1,...,m, and N =
m
i=1
J
i. The aim is to determine a subset of objects to be included in the knapsack that realizes a max-min value over all classes.In this article, we solve the KSP using an approximate solution method based upon tabu search. First, we describe a simple local search in which a depthparameter and a tabu list are used. Next, we enhance the algorithm by introducing some intensifying and diversifying strategies. The two versions of the algorithm yield satisfactory results within reasonable computational time. Extensive computational testing on problem instances taken from the literature shows the effectiveness of the proposed approach. |
| |
Keywords: | combinatorial optimization heuristic knapsack local search |
本文献已被 SpringerLink 等数据库收录! |
|