Problema de carregamento em um único contêiner: abordagem exata e restrições práticas - (:unkn) unknown (Universidade Federal de Goiás, 2018)
This work presents an approach to solve the single container loading problem. The goal is to decide which items should be loaded inside the container in order to maximize the packed value. The approach is divided into two steps. The approach integrates integer programming and constraint programming models within an iterative scope. In addition, thirteen practical constraints are considered. These constraints are used to ensure complete shipment of items from the same customer, separation of conflicting items, priority conditions, vertical and horizontal cargo stability, items’ fragility, multi-drop situations, load balancing, that the resulting packing can be separated by cuts that go from one side to the other of the container without items being fragmented during the cutting, manual loading, separation of different customer’s items within the container, grouping of items and that items can be packed in different orientations. Mathematical formulations are developed for each one of them. The formulations are the main contribution of this research since there is a gap in the literature with respect to works that present mathematical formulations to practical constraints in the studied problem. Other contributions are the integration of integer programming and constraint programming models, the presentation of a new relaxation of integer programming to the problem, a new cut, and constraints for the reduction of symmetries. Instances from the literature are solved. The results showed that the largest losses of container’s volume are for the complete shipment constraint, while the smallest losses of container’s volume are for the grouping of items. The largest runtimes happen for the cargo vertical stability. The results also showed that the proposed relaxation, the constraints for symmetries breaking and the cut bring contributions with respect to the computational time and the number of instances solved to optimality.
Single container loading problem: exact approach and practical constraints
Keywords: Problema de carregamento em contêineres; Restrições práticas; Programação linear inteira; Programação por restrições; Método exato; Container loading problem; Practical constraints; Integer linear programming; Constraint Programming; Exact method; CIENCIAS EXATAS E DA TERRA::MATEMATICA