Artículos de revistas
A Multi-start Random Constructive Heuristic For The Container Loading Problem
Registro en:
Pesquisa Operacional. , v. 27, n. 2, p. 311 - 331, 2007.
1017438
10.1590/S0101-74382007000200007
2-s2.0-37349016250
Autor
De Araujo O.C.B.
Armentano V.A.
Institución
Resumen
This paper deals with the container loading problem which involves the selection of a subset of boxes, each box with a given volume, such that they fit in a single container and maximize its volume utilization subject to orientation and stability constraints. We propose a multi-start random constructive heuristic with a load arrangement that is based on maximal cuboids that fit in given empty spaces. Each instance is adaptively evaluated by a set of criteria, and at each step of the construction process one maximal cuboid is chosen probabilistically from a restricted list of candidates. In order to enhance the flexibility in the construction of a solution, a probabilistic reduction on such cuboids is allowed. Computational tests on several instances from the literature show that the proposed method performs better than other approaches. 27 2 311 331 Bischoff, E.E., Marriott, M.D., A Comparative Evaluation of Heuristics for Container Loading (1990) European Journal of Operational Research, 44, pp. 267-276 Bischoff, E.E., Ratcliff, M.S.W., Issues in the development of approaches to container loading (1995) Omega, 4, pp. 377-390 Bischoff, E.E., Three-dimensional packing of items with limited load bearing strength (2006) European Journal of Operational Research, 168 (3), pp. 952-966 Bischoff, E.E., Janetz, F., Ratcliff, M.S.W., Loading Pallets with Non-Identical Items (1995) European Journal of Operational Research, 84, pp. 681-692 Bortfeldt, A., Gehring, H., Ein Tabu Search-Verfahren für Containerbeladeprobleme mit schwach heterogenem Kistenvorrat (1998) OR Spektrum, 20 (4), pp. 237-250 Bortfeldt, A., Gehring, H., A Hybrid Genetic Algorithm for the Container Loading Problem (2001) European Journal of Operational Research, 131, pp. 143-161 Bortfeldt, A., Gehring, H., Mack, D., A parallel tabu search algorithm for solving the container loading problem (2003) Parallel Computing, 29 (5), pp. 641-662 Bresina, J. (1996). Heuristic-Biased Stochastic Sampling. In: Proceedings of the 13 th National Conference on Artificial Intelligence, 271-278Cecilio, F.O., Morabito, R., Refinamentos na heurística de George e Robinson para o problema de carregamento de caixas dentro de contêineres (2004) Transportes, 12 (1), pp. 32-45 Chen, C.S., Lee, S.M., Shen, Q.S., An Analytical Model for the Container Loading Problem (1995) European Journal of Operational Research, 80, pp. 68-76 Chien, C.F., Deng, J.F., A container packing support system for determining and visualizing container packing patterns (2004) Decision Support Systems, 37 (1), pp. 23-34 Davies, A.P., Bischoff, E.E., Weight Distribution Considerations in Container Loading (1999) European Journal of Operational Research, 114, pp. 509-527 Dyckhoff, H., A typology of cutting and packing problems (1990) European Journal of Operational Research, 44, pp. 145-159 Eley, M., Solving container loading problems by block arrangement (2002) European Journal of Operational Research, 141 (2), pp. 393-409 Faroe, O., Pisinger, D., Zachariasen, M., Guided Local Search for the Three-Dimensional Bin-Packing Problem (2003) INFORMS Journal on Computing, 15 (3), pp. 267-283 Feo, T.A., Resende, M.G.C., Greedy randomized adaptive search procedures (1995) Journal of Global Optimization, 6, pp. 109-133 Festa, P., Resende, M.G.C., An annotated bibliography of GRASP (2004) European Journal of Operational Research, , submitted Gehring, H., Bortfeldt, A., A Genetic Algorithm for Solving the Container Loading Problem (1997) International Transactions in Operations Research, 4 (5-6), pp. 401-418 Gehring, H., Menschner, K., Meyer, M., A Computer-Based Heuristic for Packing Pooled Shipment Containers (1990) European Journal of Operational Research, 44, pp. 277-288 George, J.A., Robinson, D.F., A Heuristic for Packing Boxes into a Container (1980) Computers and Operations Research, 7, pp. 147-156 Haessler, R.W., Talbot, F.B., Load Planning for Shipments of Low Density Products (1990) European Journal of Operational Research, 44, pp. 289-299 Hassamontr, J., On decomposing 3D Packing Problem in Wooden Furniture Industry (2003) Proceedings 2003 IEEE International Symposium on Computational Intelligence in Robotics and Automation, pp. 497-502 He, D.Y., Cha, J.Z., Research on Solution to Complex Container Loading Problem Based on Genetic Algorithm (2002) Proceeding of First International Conference on Machine Learning and Cybernetics, 1, pp. 78-82. , Beijing, November Hifi, M., Exact algorithms for unconstrained three-dimensional cutting problems: A comparative study (2004) Computers & Operations Research, 31 (5), pp. 657-674 Lai, K.K., Xue, J., Xu, B., Container packing in a multi-customer delivering operation (1998) Computers & Industrial Engineering, 35 (1-2), pp. 323-326 Lim, A., Zhang, X., The container loading problem (2005) ACM Symposium on Applied Computing, pp. 913-917 Lim, A., Rodrigues, B., Wang, Y., A multi-faced buildup algorithm for threedimensional packing problems (2003) Omega, 31 (6), pp. 471-481 Lin, S., Kernighan, B.W., An Effective Heuristic Algorithm for the Travelling-Salesman Problem (1973) Operations Research, 21, pp. 0498-0516 Mack, D., Bortfeldt, A., Gehring, H., A parallel hybrid local search algorithm for the container loading problem (2004) International Transaction in Operational Research, 11, pp. 511-534 Martello, S., Pisinger, D., Vigo, D., The Three Dimensional Bin Packing Problem (2000) Operations Research, 48, pp. 256-267 Martí, R., Multi-Start Methods (2003) Handbook of MetaHeuristics, pp. 355-368. , edited by F. Glover and G. Kochenberger, Kluwer Morabito, R., Arenales, M., An And/Or-graph Approach to the Container Loading Problem (1994) International Transactions in Operations Research, 1 (1), pp. 59-73 Moura, A., Oliveira, J.F., A GRASP Approach to the Container-Loading Problem (2005) IEEE Intelligent Systems, 4 (20), pp. 50-57 Ngoi, B.K.A., Tay, M.L., Chua, E.S., Applying spatial representation techniques to the container packing problem (1994) International Journal of Production Research, 32, pp. 111-123 Pisinger, D., Heuristics for the container loading problem (2002) European Journal of Operational Research, 141, pp. 143-153 Prais, M., Ribeiro, C.C., Reactive GRASP: An application to a matrix decomposition problem in TDMA traffic assignment (2000) INFORMS Journal on Computing, 12, pp. 164-176 Resende, M.G.C., Ribeiro, C.C., Greedy randomized adaptive search procedures (2003) Handbook of MetaHeuristics, pp. 219-249. , edited by F. Glover and G. Kochenberger, Kluwer Verweij, A.M. (1996). Multiple destination bin packing. UU-CS (Ext. r. no. 1996-39). Utrecht, the Netherlands: Utrecht University: Information and Computing Sciences