Modified Harmony Search for a Truck Loading Problem Application
Keywords:
Packing, Truck Loading Problem, Harmony SearchAbstract
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
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.
