Uma nota sobre modelagem matemática de carregamento de caixas dentro de contêineres com considerações de estabilidade da carga
A note on mathematical modeling for loading boxes into containers while considering cargo stability
Yamashita, Denise Sato; Morabito, Reinaldo
http://dx.doi.org/10.1590/S0103-65132013005000041
Production, vol.25, n1, p.113-124, 2015
Resumo
Este estudo trata do problema de carregamento de caixas dentro de contêineres levando em consideração a estabilidade do carregamento. Uma formulação matemática generalizando o conceito de estabilidade descrito em Junqueira, Morabito e Yamashita (2010) é apresentada e testes computacionais são realizados utilizando-se um aplicativo de otimização. Esta formulação explora a estabilidade da carga por meio do suporte de alguns pontos da base e das laterais das caixas (por exemplo, pontos dos cantos e bordas das caixas). Convém notar que (na sua versão atual) a abordagem proposta está limitada a resolver problemas de tamanho moderado, motivando pesquisas futuras que explorem métodos heurísticos, métodos de relaxação e decomposição, entre outros, para tratar problemas maiores.
Palavras-chave
Problemas de corte e empacotamento. Carregamento de contêineres. Estabilidade da carga. Otimização combinatória. Modelagem matemática
Abstract
This study addresses the problem of packing boxes into containers while considering the cargo stability of the loading. The mathematical formulation generalizing the stability concept in Junqueira, Morabito and Yamashita (2010) is presented, and computational tests are performed using optimization software. This formulation explores cargo stability by accounting for the support of various points in the base and the lateral faces of the boxes (for example, points in the corners and borders of the boxes). The proposed method (in its current version) is limited to problems of moderate size, thus motivating future research to explore heuristic approaches and relaxation and decomposition methods, among others, to approach large problems.
Keywords
Cutting and packing problems. Container loading. Cargo stability. Combinatorial optimization. Mathematical modeling
References
ARAÚJO, O. Problemas de corte e empacotamento tridimensional e integração com roteamento de veículos. 2006. Tese (Doutorado em Engenharia Elétrica)-Universidade Estadual de Campinas, Campinas, 2006.
BEASLEY, J. Algorithms for unconstrained two-dimensional guillotine cutting. Journal of the Operacional Research Society, v. 36, p. 297-306, 1985.
BISCHOFF, E.; MARRIOTT, M. D. A Comparative Evaluation of Heuristics for Container Loading. European Journal of Operational Research, v. 44, p. 267-276, 1990. http://dx.doi.org/10.1016/0377-2217(90)90362-F
BISCHOFF, E. E.; RATCLIFF, M. S. W. Issues in the development of approaches to container loading. Omega, v. 23, n. 4, p. 377-390, 1995. http://dx.doi.org/10.1016/0305-0483(95)00015-G
BORTFELDT, A.; GEHRING, H. A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research, v. 131, p. 143-161, 2001. http://dx.doi.org/10.1016/S0377-2217(00)00055-2
BORTFELDT, A.; GEHRING, H.; MACK, D. A parallel tabu search algorithm for solving the container loading problem. Parallel Computing, v. 29, n. 5, p. 641-662, 2003. http://dx.doi.org/10.1016/S0167-8191(03)00047-4
CAMPOS, D. S. Integração dos problemas de carregamento e roteamento de veículos com janela de tempo e frota heterogênea. 2008. Tese (Doutorado em Engenharia de Produção)-Universidade de São Paulo, São Paulo, 2008.
CECÍLIO, F.; MORABITO, R. Refinamentos na heurística de George e Robinson para o problema de carregamento de caixas dentro de contêineres. Transportes, v. 1, n. 1, p. 32-45, 2004.
CHRISTOFIDES, N.; WHITLOCK, C. An algorithm for two-dimensional cutting problems. Operations Research, v. 25, n. 1, p. 30-44, 1977. http://dx.doi.org/10.1287/opre.25.1.30
ELEY, M. Solving container loading problems by block arrangement. European Journal of Operational Research, v. 141, p. 393-409, 2002. http://dx.doi.org/10.1016/S0377-2217(02)00133-9
GEHRING, H.; MENSCHNER, K.; MEYER, M. A. Computer-based heuristic for packing pooled shipment containers. European Journal of Operational Research, v. 44, p. 277-288, 1990. http://dx.doi.org/10.1016/0377-2217(90)90363-G
GENDREAU, M. et al. A tabu search algorithm for a routing and container loading problem. Transportation Science, v. 40, n. 3, p. 342-350, 2006. http://dx.doi.org/10.1287/trsc.1050.0145
JIN, Z.; OHNO, K.; DU, J. An efficient approach for the three-dimensional container packing problem with practical constraints. Asia-Pacific Journal of Operational Research, v. 21, n. 3, p. 279-295, 2004. http://dx.doi.org/10.1142/S0217595904000254
JUNQUEIRA, L. Modelos de programação matemática para problemas de carregamento de caixas dentro de contêineres. 2009. Dissertação (Mestrado em Engenharia de Produção)-Universidade Federal de São Carlos, São Carlos, 2009.
JUNQUEIRA, L.; MORABITO, R.; YAMASHITA, D. S. Modelos de otimização para problemas de carregamento de contêineres com considerações de estabilidade e de empilhamento. Pesquisa Operacional, v. 30, n. 1, p. 73-98, 2010.
JUNQUEIRA, L.; MORABITO, R.; YAMASHITA, D. S. Three-dimensional container loading models with cargo stability and load bearing constraints. Computers & Operations Research, v. 39, p. 74-85, 2012a. http://dx.doi.org/10.1016/j.cor.2010.07.017
JUNQUEIRA, L.; MORABITO, R.; YAMASHITA, D. S. MIP-based approaches for the container loading problem with multi-drop constraints. Annals of Operations Research, v. 199, n. 1, p. 51-75, 2012b. http://dx.doi.org/10.1007/s10479-011-0942-z
LINS, L.; LINS, S.; MORABITO, R. An n-tet graph approach for non-guillotine packings of n-dimensional boxes into an n-container. European Journal of Operational Research, v. 141, p. 421-439, 2002. http://dx.doi.org/10.1016/S0377-2217(02)00135-2
MOURA, A.; OLIVEIRA, J. F. A GRASP approach to the container-loading problem. IEEE Intelligent Systems, v. 20, n. 4, p. 50-57, 2005. http://dx.doi.org/10.1109/MIS.2005.57
MIYAZAWA, F. K.; WAKABAYASHI, Y. Three-dimensional packings with rotations. Computers & Operations Research, v. 36, p. 2801-2815, 2009. http://dx.doi.org/10.1016/j.cor.2008.12.015
QUEIROZ, T. A. Algoritmos para problemas de corte e empacotamento. 2010. Tese (Doutorado em Ciência da Computação)-Universidade Estadual de Campinas, Campinas, 2010.
SILVA, J. L. C.; SOMA, N. Y.; MACULAN, N. A greedy search for the three-dimensional bin packing problem: the packing static stability case. International Transactions in Operational Research, v. 10, p. 1-13, 2003.
YEUNG, L. H.; TANG, W. K. S. A hybrid genetic approach for container loading in logistics industry. IEEE Transactions on Industrial Electronics, v. 52, n. 2, p. 617-627, 2005. http://dx.doi.org/10.1109/TIE.2005.844224
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email