Very large-scale neighborhood search for the K-Constraint Multiple Knapsack Problem

Very large-scale neighborhood search for the K-Constraint Multiple Knapsack Problem

Autor Ahuja, R. Google Scholar
Cunha, C. Google Scholar
Instituição Univ Florida
Universidade Federal de São Paulo (UNIFESP)
Resumo The K-Constraint Multiple Knapsack Problem (K-MKP) is a generalization of the multiple knapsack problem, which is one of the representative combinatorial optimization problems known to be NP-hard. in K-MKP, each item has K types of weights and each knapsack has K types of capacity. in this paper, we propose several very large-scale neighborhood search (VLSN) algorithms to solve K-MKP. One of the VLSN algorithms incorporates a novel approach that consists of randomly perturbing the current solution in order to efficiently produce a set of simultaneous non-profitable moves. These moves would allow several items to be transferred from their current knapsacks and assigned to new knapsacks, which makes room for new items to be inserted through multi-exchange movements and allows for improved solutions. Computational results presented show that the method is effective, and provides better solutions compared to exact algorithms run for the same amount of time.
Palavra-chave heuristics
neighborhood search algorithms
knapsack problem
Idioma Inglês
Data de publicação 2005-12-01
Publicado em Journal of Heuristics. Dordrecht: Springer, v. 11, n. 5-6, p. 465-481, 2005.
ISSN 1381-1231 (Sherpa/Romeo, fator de impacto)
Publicador Springer
Extensão 465-481
Direito de acesso Acesso restrito
Tipo Artigo
Web of Science WOS:000232530800005
Endereço permanente

Exibir registro completo


Arquivo Tamanho Formato Visualização

Não existem arquivos associados a este item.

Este item está nas seguintes coleções



Minha conta