An approach for the pallet-building problem and subsequent loading in a heterogeneous fleet of vehicles with practical constraints

Cuellar-Usaquen, D.; Camacho-Muñoz, G.; Quiroga-Gomez, C.; Álvarez-Martínez, D.

Growing Science » International Journal of Industrial Engineering Computations » An approach for the pallet-building problem and subsequent loading in a heterogeneous fleet of vehicles with practical constraints

Journals

IJIEC Volumes

Volume 1 (17)
- Issue 1 (9)
- Issue 2 (8)

Volume 2 (68)
- Issue 1 (12)
- Issue 2 (20)
- Issue 3 (20)
- Issue 4 (16)

Volume 3 (76)
- Issue 1 (9)
- Issue 2 (15)
- Issue 3 (20)
- Issue 4 (12)
- Issue 5 (20)

Volume 4 (50)
- Issue 1 (14)
- Issue 2 (10)
- Issue 3 (12)
- Issue 4 (14)

Volume 5 (47)
- Issue 1 (13)
- Issue 2 (12)
- Issue 3 (12)
- Issue 4 (10)

Volume 6 (39)
- Issue 1 (7)
- Issue 2 (12)
- Issue 3 (10)
- Issue 4 (10)

Volume 7 (47)
- Issue 1 (10)
- Issue 2 (14)
- Issue 3 (10)
- Issue 4 (13)

Volume 8 (30)
- Issue 1 (9)
- Issue 2 (7)
- Issue 3 (8)
- Issue 4 (6)

Volume 9 (32)
- Issue 1 (9)
- Issue 2 (6)
- Issue 3 (7)
- Issue 4 (10)

Volume 10 (34)
- Issue 1 (8)
- Issue 2 (10)
- Issue 3 (8)
- Issue 4 (8)

Volume 11 (36)
- Issue 1 (9)
- Issue 2 (8)
- Issue 3 (9)
- Issue 4 (10)

Volume 12 (29)
- Issue 1 (9)
- Issue 2 (6)
- Issue 3 (8)
- Issue 4 (6)

Volume 13 (41)
- Issue 1 (10)
- Issue 2 (8)
- Issue 3 (10)
- Issue 4 (13)

Volume 14 (50)
- Issue 1 (11)
- Issue 2 (15)
- Issue 3 (9)
- Issue 4 (15)

Volume 15 (55)
- Issue 1 (19)
- Issue 2 (15)
- Issue 3 (12)
- Issue 4 (9)

Volume 16 (75)
- Issue 1 (12)
- Issue 2 (15)
- Issue 3 (19)
- Issue 4 (29)

Volume 17 (51)
- Issue 1 (21)
- Issue 2 (30)

Countries

International Journal of Industrial Engineering Computations

ISSN 1923-2934 (Online) - ISSN 1923-2926 (Print) Quarterly Publication Volume 12 Issue 3 pp. 329-344 , 2021

An approach for the pallet-building problem and subsequent loading in a heterogeneous fleet of vehicles with practical constraints Pages 329-344 Download PDF

Authors: Daniel Cuellar-Usaquen, Guillermo A. Camacho-Muñoz, Camilo Quiroga-Gomez, David Álvarez-Martínez

DOI: 10.5267/j.ijiec.2021.1.003

Keywords: Pallet Packing, Container Loading Problem, GRASP

Abstract: This article presents a metaheuristic algorithm to solve the pallet-building problem and the loading of these in trucks. This approach is used to solve a real application of a Colombian logistics company. Several practical requirements of goods loading and unloading operations were modeled, such as the boxes’ orientation, weight support limits associated with boxes, pallets and vehicles, and static stability constraints. The optimization algorithm consists of a two-phase approach, the first is responsible for the construction of pallets, and the second considers the optimal location of the pallets into the selected vehicles. Both phases present a search strategy type of GRASP. The proposed methodology was validated through the comparison of the performance of the solutions obtained for deliveries of the logistics company with the solutions obtained using a highly accepted commercial packing tool that uses two different algorithms. The proposed methodology was compared in similar conditions with the previous works that considered the same constraints of the entire problem or at least one of the phases separately. We used the sets of instances published in the literature for each of the previous works. The results allow concluding that the proposed algorithm has a better performance than the most known commercial tool for real cases. The proposed algorithm managed to match most of the test instances and outperformed some previous works that only involve decisions of one of the two problems. As future work, it is proposed to adapt this work to the legal restrictions of the European community.

How to cite this paper

 Cuellar-Usaquen, D., Camacho-Muñoz, G., Quiroga-Gomez, C & Álvarez-Martínez, D. (2021). An approach for the pallet-building problem and subsequent loading in a heterogeneous fleet of vehicles with practical constraints.International Journal of Industrial Engineering Computations , 12(3), 329-344.

Refrences

Alonso, M. T., Alvarez-Valdes, R., Iori, M., & Parreño, F. (2019). Mathematical models for Multi Container Loading Problems with practical constraints. Computers & Industrial Engineering, 127, 722-733.
Alonso, M. T., Alvarez-Valdes, R., Iori, M., Parreño, F., & Tamarit, J. M. (2017). Mathematical models for multicontainer loading problems. Omega, 66, 106-117.
Alonso, M. T., Alvarez-Valdes, R., & Parreño, F. (2020). A GRASP algorithm for multi container loading problems with practical constraints. 4OR, 18(1), 49-72.
Alonso, M. T., Alvarez-Valdes, R., Parreño, F., & Tamarit, J. M. (2016). Algorithms for pallet building and truck loading in an interdepot transportation problem. Mathematical Problems in Engineering, 2016.
Alvarez-Valdés, R., Parreño, F., & Tamarit, J. M. (2013). A GRASP/Path relinking algorithm for two-and three-dimensional multiple bin-size bin packing problems. Computers & Operations Research, 40(12), 3081-3090.
Alvarez-Valdés, R., Parreño, F., & Tamarit, J. M. (2015). Lower bounds for three-dimensional multiple-bin-size bin packing problems. OR spectrum, 37(1), 49-74.
Amossen, R. R., & Pisinger, D. (2010). Multi-dimensional bin packing problems with guillotine constraints. Computers & operations research, 37(11), 1999-2006.
Ballew, B. P. (2000). The distributor's three-dimensional pallet-packing problem: a mathematical formulation and heuristic solution approach (No. AFIT/GOR/ENS/00M-02). AIR FORCE INST OF TECH WRIGHT-PATTERSONAFB OH SCHOOL OF ENGINEERING.
Bortfeldt, A., & Wäscher, G. (2013). Constraints in container loading–A state-of-the-art review. European Journal of Operational Research, 229(1), 1-20.
Brunetta, L., & Grégoire, P. (2005). A general-purpose algorithm for three-dimensional packing. INFORMS Journal on Computing, 17(3), 328-338.
Burke, E. K., Hyde, M. R., Kendall, G., & Woodward, J. (2012). Automating the packing heuristic design process with genetic programming. Evolutionary computation, 20(1), 63-89.
Camacho-Munoz, G., Rodriguez, C., Alvarez-Martinez, D., (2018, June). Modelling the kinematic properties of an industrial manipulator in packing applications. In 2018 IEEE 14th International Conference on Control and Automation (ICCA), IEEE, pp. 1028–1033.
Ceschia, S., & Schaerf, A. (2013). Local search for a multi-drop multi-container loading problem. Journal of Heuristics, 19(2), 275-294.
Ceschia, S., Stutzle, T., (2017). http://www.diegm.uniud.it/ceschia/index.php?page=vrclp.
Clautiaux, F., Dell’Amico, M., Iori, M., & Khanafer, A. (2014). Lower and upper bounds for the Bin Packing Problem with Fragile Objects. Discrete applied mathematics, 163, 73-86.
Crainic, T. G., Perboli, G., & Tadei, R. (2008). Extreme point-based heuristics for three-dimensional bin packing. Informs Journal on computing, 20(3), 368-384.
de Almeida, A., & Figueiredo, M. B. (2010). A particular approach for the Three-dimensional Packing Problem with additional constraints. Computers & Operations Research, 37(11), 1968-1976.
de Castro Silva, J. L., Soma, N. Y., & Maculan, N. (2003). A greedy search for the three‐dimensional bin packing problem: the packing static stability case. International Transactions in Operational Research, 10(2), 141-153.
Delorme, M., Iori, M., & Martello, S. (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255(1), 1-20.
Epstein, L., & Levy, M. (2010). Dynamic multi-dimensional bin packing. Journal of Discrete Algorithms, 8(4), 356-372.
Esko, (2016). https://www.esko.com/es/products/cape-pack.
Gehan, E.A., (1965). A generalized wilcoxon test for comparing arbitrarily singly-censored samples. Biometrika 52, 203– 224.
Hifi, M., Negre, S., & Wu, L. (2014). Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem. International Transactions in Operational Research, 21(1), 59-79.
Jin, Z., Ito, T., & Ohno, K. (2003). The three-dimensional bin packing problem and its practical algorithm. JSME International Journal Series C Mechanical Systems, Machine Elements and Manufacturing, 46(1), 60-66.
Lim, A., & Zhang, X. (2005, March). The container loading problem. In Proceedings of the 2005 ACM symposium on Applied computing (pp. 913-917).
Martello, S., Pisinger, D., & Vigo, D. (2000). The three-dimensional bin packing problem. Operations research, 48, 256-267.
Martínez, D. A., Alvarez-Valdes, R., & Parreño, F. (2015). A grasp algorithm for the container loading problem with multi-drop constraints. Pesquisa Operacional, 35(1), 1-24.
Martínez, J. C., Cuellar, D., & Martínez, D. (2018a). Review of Dynamic Stability Metrics and a Mechanical Model Integrated with Open Source Tools for the Container Loading Problem. Electronic Notes in Discrete Mathematics, 69, 325-332.
Martínez, J.C., Cuellar, D., Cespedes, E., Martínez, D., (2018b). Packagecargo - open source tool based on optimization and simulation for the container loading problem with dynamic stability. In 2018 International Conference on Industrial Engineering and Operations Management, IEOM, pp. 2363–2370.
Miyazawa, F. K., & Wakabayashi, Y. (2009). Three-dimensional packings with rotations. Computers & Operations Research, 36(10), 2801-2815.
Morabito, R., & Morales, S. (1998). A simple and effective recursive procedure for the manufacturer's pallet loading problem. Journal of the Operational Research Society, 49(8), 819-828.
Morabito, R., Morales, S. R., & Widmer, J. A. (2000). Loading optimization of palletized products on trucks. Transportation Research Part E: Logistics and Transportation Review, 36(4), 285-296.
Moura, A., & Bortfeldt, A. (2017). A two‐stage packing problem procedure. International Transactions in Operational Research, 24(1-2), 43-58.
Moura, A., & Oliveira, J. (2005). A GRASP approach to the container-loading problem. IEEE Intelligent Systems, 20, 50-57.
Olsson, J., Larsson, T., & Quttineh, N. H. (2020). Automating the planning of container loading for Atlas Copco: Coping with real-life stacking and stability constraints. European Journal of Operational Research, 280(3), 1018-1034.
Paquay, C., Limbourg, S., & Schyns, M. (2018). A tailored two-phase constructive heuristic for the three-dimensional Multiple Bin Size Bin Packing Problem with transportation constraints. European Journal of Operational Research, 267(1), 52-64.
Pisinger, D., (2016). http://hjemmesider.diku.dk/∼pisinger/codes.html.
Silva, E., Oliveira, J. F., & Wäscher, G. (2016). The pallet loading problem: a review of solution methods and computational experiments. International Transactions in Operational Research, 23(1-2), 147-172.
Takahara, S. (2005, July). Loading problem in multiple containers and pallets using strategic search method. In International Conference on Modeling Decisions for Artificial Intelligence (pp. 448-456). Springer, Berlin, Heidelberg.
Viklund, A., (2010). http:http://metrology.burtini.ca/dimwt.php.
Wäscher, G., Haußner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European journal of operational research, 183(3), 1109-1130.
Zachariadis, E.E., (2017). http://users.ntua.gr/ezach/. Online; accessed 13/12/2018.
Zachariadis, E. E., Tarantilis, C. D., & Kiranoudis, C. T. (2012). The pallet-packing vehicle routing problem. Transportation Science, 46(3), 341-358.
Zudio, A., da Silva Costa, D. H., Masquio, B. P., Coelho, I. M., & Pinto, P. E. D. (2018). BRKGA/VND hybrid algorithm for the classic three-dimensional bin packing problem. Electronic Notes in Discrete Mathematics, 66, 175-182.