Title: A procedure-based heuristic for 0-1 Multiple Knapsack Problems
Authors: Mohamed Esseghir Lalami; Moussa Elkihel; Didier El Baz; Vincent Boyer
Addresses: CNRS, LAAS, 7, avenue du Colonel Roche, Université de Toulouse; UPS, INSA, INP, ISAE, LAAS, F-31077 Toulouse, France. ' CNRS, LAAS, 7, avenue du Colonel Roche, Université de Toulouse; UPS, INSA, INP, ISAE, LAAS, F-31077 Toulouse, France. ' CNRS, LAAS, 7, avenue du Colonel Roche, Université de Toulouse; UPS, INSA, INP, ISAE, LAAS, F-31077 Toulouse, France. ' CNRS, LAAS, 7, avenue du Colonel Roche, Université de Toulouse; UPS, INSA, INP, ISAE, LAAS, F-31077 Toulouse, France
Abstract: In this paper, we present a heuristic which derives a feasible solution for the Multiple Knapsack Problem (MKP). The proposed heuristic called RCH, is a recursive method that performs computation on the core of knapsacks. The RCH heuristic is compared with the MTHM heuristic of Martello and Toth. Computational results on randomly generated instances show that the proposed approach gives better gap and smaller restitution times.
Keywords: MKP; multiple knapsack problems; heuristics; dynamic programming; subset sum problem; operational research.
DOI: 10.1504/IJMOR.2012.046684
International Journal of Mathematics in Operational Research, 2012 Vol.4 No.3, pp.214 - 224
Published online: 23 Dec 2014 *
Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article