Modified Harmony Search for a Truck Loading Problem Application

Authors

Keywords:

Packing, Truck Loading Problem, Harmony Search

Abstract

We must decide how to load boxes in a truck, to avoid damaging during the transportation and simplifying the delivery to multiple clients. We propose a constructive heuristic and a modified Harmony Search metaheuristic, using the open dimension approach, the length in this case. The constructive heuristic, based on the Wall Building approach, provides a very fast initial solution for the metaheuristic. The selection algorithm, guiding the metaheuristic, considers the optimization of the multi-client features originally. The results show the effectiveness of the metaheuristic in searching solutions that improve the considered features, in reasonable times according to the truck's load planning.

Downloads

Download data is not yet available.

Author Biographies

Nicolás Anabalón Romero, Universidad de Concepción, Chile

Nacido en Bulnes el 16 de mayo de 1997, con estudios básicos y medios en la misma ciudad, para luego estudiar en la Universidad de Concepción, obteniendo el título de Ingeniero Civil Industrial, al mismo tiempo que realiza algunos trabajos y participa en algunas actividades de la carrera. Recientemente titulado y con residencia en Concepción.

Matías Barros Vásquez, Universidad de Concepción, Chile

Ingeniero Civil Industrial de la Universidad de Concepción. Durante sus estudios trabajo en dos artículos sobre optimización de redes de contacto, basando sus estudios e intereses en Investigación de operaciones. Realiza su Memoria de Título en optimización de reparto de productos, mediante un método exacto, estudio que continua, con métodos heurísticos para la Tesis de Magíster en Ingeniería Industrial, grado que obtiene dos años después.

Rosa Medina, Departamento de Ingeniería Industrial, Universidad de Concepción, Chile

Ingeniera Civil Industrial de la Universidad de Concepción, Magíster en Ingeniería Industrial de la misma casa de estudios. Doctora en Investigación de Operaciones de la Universidad de Bologna. Sus áreas de investigación corresponden a Optimización Combinatoria con aplicaciones en problemas de corte, empaquetamiento, forestal, minería y turismo.

References

A. Bortfeldt and D. Mack, “A heuristic for the three-dimensional strip packing problem,” European Journal of Operational Research, vol. 183, pp. 1267 – 1279, 2007.

S. Allen, E. K. Burke, and G. Kendall, “A hybrid placement strategy for the three-dimensional strip packing problem,” European Journal of Operational Research, vol. 209, pp. 219 – 227, 2011.

L. Wei, W.-C. Oon, W. Zhu, and A. Lim, “A reference length approach for the 3d strip packing problem,” European Journal of Operational Research, vol. 220, pp. 37 – 47, 2012.

O. X. do Nascimento, T. Alves de Queiroz, and L. Junqueira, “Practical constraints in the container loading problem: Comprehensive formula- tions and exact algorithm,” Computers & Operations Research, vol. 128, pp. 105–186, 2021.

C. A. Vega-Mejía, R. G. García-Cáceres, and J. P. Caballero-Villalobos, “Hacia la optimización integral del problema de carga de contenedores,” in Congreso Latino-Iberoamericano de Investigación Operativa, Simpo- sio Brasileiro de Pesquisa Operacional, pp. 482–493, september 2012.

M. da Graça Costa and M. E. Captivo, “Weight distribution in contai- ner loading: a case study,” International Transactions in Operational Research, vol. 23, pp. 239 – 263, 2016.

M. T. Alonso, R. Alvarez-Valdes, F. Parreño, and J. M. Tamarit, “Algorithms for pallet building and truck loading in an interdepot trans- portation problem.,” Mathematical Problems in Engineering., vol. 2016, pp. 1 – 11, 2016.

L.Junqueira,R.Morabito,andD.S.Yamashita,“Mip-basedapproaches for the container loading problem with multi-drop constraints,” Annals of Operations Research, vol. 199, pp. 51–75, 2012.

A.BortfeldtandG.Wäscher,“Constraintsincontainerloading–astate- of-the-art review,” European Journal of Operational Research, vol. 229, no. 1, pp. 1 – 20, 2013.

J. Respen and N. Zufferey, “Metaheuristics for truck loading in the car production industry,” International Transactions in Operational Research, vol. 24, pp. 277 – 301, 2017.

M. Iori, S. Martello, and M. Monaci, “Metaheuristic algorithms for the strip packing problem,” in Optimization and Industry: New Frontiers. Applied Optimization (P. Pardalos and V. Korotkikh, eds.), vol. 78, Springer, Boston, MA, 2013.

N. Bansal, X. Han, K. Iwama, M. Sviridenko, and G. Zhang, “A harmonic algorithm for the 3d strip packing problem.,” SIAM Journal on Computing, vol. 42, pp. 579 – 592, 2013.

D. V. Kurpel, C. T. Scarpin, J. E. P. Junior, C. M. Schenekemberg, and L. C.Coelho, “The exact solutions of several types of container loading problems.,” European Journal of Operational Research, vol. 284, pp. 87 – 107, 2020.

M.A.AlbaMartínez,F.Clautiaux,M.Dell’Amico,andM.Iori.,“Exact algorithms for the bin packing problem with fragile objects.,” Discrete Optimization, vol. 10, pp. 210 – 223, 2013.

M.T.Alonso, R.Alvarez-Valdes, M.Iori, F.Parreño, and M.Tamarit, “Mathematical models for multicontainer loading problems.,” Omega., vol. 66, pp. 106 – 117, 2017.

Z. W. Geem, J. H. Kim, and G. V. Loganathan, “A new heuristic optimization algorithm: Harmony search,” Simulation, vol. 76, no. 2, pp. 60 – 68, 2001.

X.-S. Yang, “Harmony search as a metaheuristic algorithm,” in Music- Inspired Harmony Search Algorithm: Theory and Applications (Z. W. Geem, ed.), ch. 1, pp. 1–14, Studies in Computational Intelligence, Springer Berlin, vol 191, 2009.

X. Gao, V. Govindasamy, H. Xu, X. Wang, and K. Zenger, “Harmony search method: Theory and applications,” Computational Intelligence and Neuroscience, vol. 2015, p. 10 pages, 2015.

Z. W. Geem, Music-Inspired Harmony Search Algorithm: Theory and Applications. Studies in Computational Intelligence, Springer Berlin, vol 191, 2009.

I. Ayachi, R. Kammarti, M. Ksouri, and P. Borne, “Harmony search algorithm for the container storage problem.,” 8th International Confe- rence of Modeling and Simulation, 2010.

Published

2021-10-14

How to Cite

Anabalón Romero, N., Barros Vásquez, M., & Medina, R. (2021). Modified Harmony Search for a Truck Loading Problem Application. IEEE Latin America Transactions, 100(XXX). Retrieved from https://latamt.ieeer9.org/index.php/transactions/article/view/5691