×

Solving a large multicontainer loading problem in the car manufacturing industry. (English) Zbl 1391.90511

Summary: Renault, a large car manufacturer with factories all over the world, has a production system in which not every factory produces all the parts required to assemble a vehicle. Every day, large quantities of car parts are sent from one factory to another, defining very large truck/container transportation problems. The main challenge faced by the Renault logistics platforms is to load the items into trucks and containers as efficiently as possible so as to minimize the number of vehicles sent. Therefore, the problem to be solved is a multicontainer loading problem in which, besides the usual geometric constraints preventing items from overlapping and exceeding the dimensions of the container, there are many other constraints, concerning the way in which items are put into layers, layers into stacks, and stacks into containers, limiting the total weight and the weight supported by the items. In this paper, we propose a GRASP algorithm, including constructive procedures to build solutions satisfying all the constraints, randomization strategies to produce diversity of solutions, and improvement moves to obtain high-quality solutions in short computing times. The algorithm has been tested on a set of real instances provided by the company and the results are competitive with the best results known, including some new improved solutions.

MSC:

90C27 Combinatorial optimization
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI

References:

[1] Alonso, M.; Alvarez-Valdes, R.; Iori, M.; Parreño, F.; Tamarit, J., Mathematical models for multicontainer loading problems, OMEGA, 66, 106-117, (2017)
[2] Alonso, M.; Alvarez-Valdes, R.; Parreño, F.; Tamarit, J., A reactive grasp algorithm for the container loading problem with load-bearing constraints, Eur. J. Indus. Eng., 8, 1, 669-694, (2014)
[3] Araujo, O.; Armentano, V., A multi-start random constructive heuristic for the container loading problem, Pesquisa Operacional, 27, 2, 311-331, (2007) · Zbl 1156.90313
[4] Bischoff, E.; Janetz, F.; Ratcliff, M., Loading pallets with non-identical items, Eur. J. Oper. Res., 84, 3, 681-692, (1995) · Zbl 0928.90075
[5] Bischoff, E.; Marriott, M., A comparative evaluation of heuristics for container loading, Eur. J. Oper. Res., 44, 2, 267-276, (1990) · Zbl 0684.90083
[6] Bischoff, E.; Ratcliff, M., Issues in the development of approaches to container loading, Omega, 23, 4, 377-390, (1995)
[7] Bortfeldt, A.; Gehring, H., A hybrid genetic algorithm for the container loading problem, Eur. J. Oper. Res., 131, 1, 143-161, (2001) · Zbl 0979.90101
[8] Bortfeldt, A.; Gehring, H.; Mack, D., A parallel tabu search algorithm for solving the container loading problem, Parallel Comput., 29, 5, 641-662, (2003)
[9] Bortfeldt, A.; Wäscher, G., Constraints in container loading. A state of the art review, Eur. J. Oper. Res., 229, 1, 1-20, (2013) · Zbl 1317.90172
[10] Ceschia, S.; Schaerf, A., Local search for a multi-drop multi-container loading problem, J. Heuristics, 19, 2, 275-294, (2013)
[11] Che, C.; Huang, W.; Lim, A.; Zhu, W., The multiple container loading cost minimization problem, Eur. J. Oper. Res., 214, 3, 501-511, (2011) · Zbl 1226.90085
[12] Duhamel, C.; Lacomme, P.; Quilliot, A.; Toussaint, H., A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem, Comput. Oper. Res., 38, 3, 617-640, (2011) · Zbl 1201.90026
[13] Eley, M., Solving container loading problems by block arrangement, Eur. J. Oper. Res., 141, 2, 393-409, (2002) · Zbl 1081.90610
[14] Fanslau, T.; Bortfeldt, A., A tree search algorithm for solving the container loading problem, INFORMS J. Comput., 22, 2, 222-235, (2010) · Zbl 1243.90090
[15] Clautiaux, J. B. F., Nguyen, A., 2015. chalenge. http://challenge-esicup-2015.org/. [Online; accessed 3-october-2016].
[16] Gehring, H.; Bortfeldt, A., A genetic algorithm for solving the container loading problem, Int. Trans. Oper. Res., 4, 5-6, 401-418, (1997) · Zbl 0906.90145
[17] Haessler, R.; Talbot, F., Load planning for shipments of low density products, Eur. J. Oper. Res., 44, 2, 289-299, (1990) · Zbl 0684.90085
[18] Iori, M.; Martello, S., Routing problems with loading constraints, TOP, 18, 1, 4-27, (2010) · Zbl 1279.90146
[19] Ivancic, N.; Mathur, K.; Mohanty, B. B., An integer programming based heuristic approach to the three-dimensional packing problem, J. Manuf. Oper. Manage., 2, 268-298, (1989)
[20] Jin, Z.; Ohno, K.; Du, J., An efficient approach for the three-dimensional container packing problem with practical constraints, Asia-Pacific J. Oper. Res., 21, 3, 279-295, (2004) · Zbl 1056.90118
[21] Junqueira, L.; Morabito, R.; Yamashita, D., Three-dimensional container loading models with cargo stability and load bearing constraints, Comput. Oper. Res., 39, 1, 74-85, (2012) · Zbl 1251.90240
[22] Iori, M.; Martello, S., An annotated bibliography of combined routing and loading problems, Yugoslav J. Oper. Res., 23, 3, 311-326, (2013) · Zbl 1313.90026
[23] Martí, R.; Resende, M. G.; Ribeiro, C. C., Multi-start methods for combinatorial optimization, Eur. J. Oper. Res., 226, 1, 1-8, (2013) · Zbl 1292.90257
[24] Morabito, R.; Arenales, M., An and/or-graph approach to the container loading problem, Int. Trans. Oper. Res., 1, 1, 59-73, (1994) · Zbl 0854.90121
[25] Moura, A.; Bortfeldt, A., A two-stage packing problem procedure, Int. Trans. Oper. Res., 24, 1-2, 43-58, (2017) · Zbl 1358.90120
[26] Ngoi, B.; Tay, M.; Chua, E., Applying spatial representation techniques to the container packing problem, Int. J. Prod. Res., 32, 1, 111-123, (1994) · Zbl 0905.90145
[27] Parreño, F.; Alvarez-Valdes, R.; Tamarit, J.; Oliveira, J., A maximal-space algorithm for the container loading problem, INFORMS J. Comput., 20, 3, 412-422, (2008) · Zbl 1243.90094
[28] Pollaris, H.; Braekers, K.; Caris, A.; Janssens, G.; Limbourg, S., Capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints, EURO J. Transp. Logist., 1-25, (2015)
[29] Ramos, A. G.; Oliveira, J. F.; Gonçalves, J. F.; Lopes, M. P., Dynamic stability metrics for the container loading problem, Transp. Res. Part C, 60, 480-497, (2015)
[30] Ramos, A. G.; Oliveira, J. F.; Lopes, M. P., A physical packing sequence algorithm for the container loading problem with static mechanical equilibrium conditions, Int. Trans. Oper. Res., 23, 1-2, 215-238, (2016) · Zbl 1335.90080
[31] Ratcliff, M.; Bischoff, E., Allowing for weight considerations in container loading, Oper. Res. Spektrum, 20, 1, 65-71, (1998) · Zbl 0897.90094
[32] Scheithauer, G.; Terno, J., A heuristic approach for solving the multi-pallet packing problem, Technical Report, (1996), Dresden university
[33] Takahara, S., Loading problem in multiple containers and pallets using strategic search method, (Torra, V.; Narukawa, Y.; Miyamoto, S., Modeling Decisions for Artificial Intelligence, Lecture Notes in Computer Science, 3558, (2005), Springer Berlin Heidelberg), 448-456 · Zbl 1121.90305
[34] Terno, J.; Scheithauer, G.; Sommerweiss, U.; Riehme, J., An efficient approach for the multi-pallet loading problem, Eur. J. Oper. Res., 123, 2, 372-381, (2000) · Zbl 0967.90040
[35] Toffolo, T. A.; Esprit, E.; Wauters, T.; Berghe, G. V., A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem, Eur. J. Oper. Res., 257, 2, 526-538, (2017) · Zbl 1394.90500
[36] Wäscher, G.; Haußner, H.; Schumann, H., An improved typology of cutting and packing problems, Eur. J. Oper. Res., 183, 3, 1109-1130, (2007) · Zbl 1278.90347
[37] Zhao, X.; Bennell, J.; Betkas, T.; Dowsland, K., A comparative review of 3d container loading algorithms, Int. Trans. Oper. Res., 23, 287-320, (2016) · Zbl 1338.90360
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.