Busca avançada
Ano de início
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Two-dimensional Disjunctively Constrained Knapsack Problem: Heuristic and exact approaches

Texto completo
de Queiroz, Thiago Alves ; Del Bianco Hokama, Pedro Henrique ; Saliba Schouery, Rafael Crivellari ; Miyazawa, Flavio Keidi
Número total de Autores: 4
Tipo de documento: Artigo Científico
Fonte: COMPUTERS & INDUSTRIAL ENGINEERING; v. 105, p. 313-328, MAR 2017.
Citações Web of Science: 4

This work deals with the 0-1 knapsack problem in its two-dimensional version considering a conflict graph, where each edge in this graph represents a pair of items that must not be packed together. This problem arises as a subproblem of the bin packing problem and in supply chain scenarios. We propose some integer programming formulations that are solved with a branch and -cut algorithm. The formulation is based on location-allocation variables mixing the one- and two-dimensional versions of this problem. When a candidate solution is found, a feasibility test is performed with a constraint programming algorithm, which verifies if it satisfies the two-dimensional packing constraints. Moreover, bounds and valid cuts are also investigated. A heuristic that generates iteratively a solution and has components of Tabu search and Simulated Annealing approaches is proposed. The results are extended to consider complete shipment of items, where subsets of items all have to be loaded or left out completely. This constraint is applied in many real-life packing problems, such as packing parts of machinery, or when delivering cargo to different customers. Experiments on several instances derived from the literature indicate the competitiveness of our algorithms, which solved 99% of the instances to optimality requiring short computational time. (C) 2017 Elsevier Ltd. All rights reserved. (AU)

Processo FAPESP: 11/13382-3 - Problema de roteamento de veículos com restrições práticas
Beneficiário:Pedro Henrique Del Bianco Hokama
Linha de fomento: Bolsas no Brasil - Doutorado
Processo FAPESP: 13/21744-8 - Abordagens teóricas e práticas para problemas de empacotamento
Beneficiário:Rafael Crivellari Saliba Schouery
Linha de fomento: Bolsas no Brasil - Pós-Doutorado