@article{TOFFOLO2017526,
title = "A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem",
journal = "European Journal of Operational Research",
volume = "257",
number = "2",
pages = "526 - 538",
year = "2017",
issn = "0377-2217",
doi = "https://doi.org/10.1016/j.ejor.2016.07.033",
url = "http://www.sciencedirect.com/science/article/pii/S0377221716305707",
author = "Túlio A.M. Toffolo and Eline Esprit and Tony Wauters and Greet Vanden Berghe",
keywords = "Three dimensional multiple container loading problem, Decomposition strategies, Bin packing, Ruin-and-recreate heuristic, ESICUP challenge",
abstract = "Efficient container loading has the potential to considerably reduce logistics and transportation costs. The container loading problem is computationally complex and, despite extensive academic effort, there remains room for algorithm improvement. Real-world problems are not always addressed satisfactorily primarily due to the large number of complex constraints and objectives. The problem addressed by this work is an unsolved multiple container loading problem introduced by Renault on the occasion of the 2014/2015 ESICUP challenge, organized by the EURO Special Interest Group on Cutting and Packing (ESICUP). Renault’s problem requires a large number of different items to be packed into containers of different types and sizes. Items must be grouped into stacks and respect the ‘this side up’ constraint. The primary objective is to minimize the volume of shipped containers. The smallest volume container may be left behind for the next shipment and is excluded from the main objective. Nevertheless, only a limited percentage of each product may be packed into this container. Additionally, a set of secondary objectives is considered. This work presents a decomposition approach embedded in a multi-phase heuristic for the problem. Feasible solutions are generated quickly, and subsequently improved by local search and post-processing procedures. Experiments revealed that the approach generates optimal solutions for two instances, in addition to good quality solutions for those remaining from the Renault set. The algorithmic contribution is, however, not restricted to the Renault instances. Experiments on less constrained container loading instances from the literature demonstrate the approach’s general applicability and competitiveness."
}

@article{CORRECHER2017139,
title = "Solving a large multicontainer loading problem in the car manufacturing industry",
journal = "Computers & Operations Research",
volume = "82",
pages = "139 - 152",
year = "2017",
issn = "0305-0548",
doi = "https://doi.org/10.1016/j.cor.2017.01.012",
url = "http://www.sciencedirect.com/science/article/pii/S0305054817300126",
author = "J.F. Correcher and M.T. Alonso and F. Parreño and R. Alvarez-Valdes",
keywords = "Container loading, Optimization, Packing, Metaheuristics, GRASP"
}

@article{ASINOWSKI2014165,
title = "Cut equivalence of d-dimensional guillotine partitions",
journal = "Discrete Mathematics",
volume = "331",
pages = "165 - 174",
year = "2014",
issn = "0012-365X",
doi = "https://doi.org/10.1016/j.disc.2014.05.014",
url = "http://www.sciencedirect.com/science/article/pii/S0012365X14002106",
author = "Andrei Asinowski and Gill Barequet and Toufik Mansour and Ron Y. Pinter",
keywords = "Guillotine partitions, Generating functions, Inclusion–exclusion principle"
}

@inbook{doi:10.1137/1.9781611974331.ch106,
author = {Nikhil Bansal and Marek Eliáš and Arindam Khan},
title = {Improved Approximation for Vector Bin Packing},
booktitle = {Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms},
chapter = {},
pages = {1561-1579},
doi = {10.1137/1.9781611974331.ch106},
URL = {https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch106},
eprint = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611974331.ch106}
}

@article{doi:10.1287/ijoc.11.4.406,
author = {Zeger Degraeve and Linus Schrage},
title = {Optimal Integer Solutions to Industrial Cutting Stock Problems},
journal = {INFORMS Journal on Computing},
volume = {11},
number = {4},
pages = {406-419},
year = {1999},
doi = {10.1287/ijoc.11.4.406},
URL = { https://doi.org/10.1287/ijoc.11.4.406 },
eprint = { https://doi.org/10.1287/ijoc.11.4.406 },
abstract = { The “textbook” treatment of the cutting stock problem, using a method termed column generation, solves the problem as if one is allowed to use fractional amounts of patterns. In practice, one can typically run only an integer quantity of a pattern. Dyckhoff was the first to propose an integer linear programming formulation for the problem of getting a guaranteed global optimum to cutting stock problems under the integrality requirement. We describe and test an extension of a method proposed by Degraeve for embedding a column generation procedure within branch and bound. We show that our algorithm is quite general. It can easily cope with various combinations of real world complications, such as 1) upper bounds on the amount by which the demand may be oversatisfied, 2) a limit on maximum waste allowed in each pattern, and 3) a limit on the maximum number of knives in the cutting patterns. We validate our approach using both industrial data sets from the paper industry and generated data sets. The performance of the algorithm is compared with Dyckhoff's formulation. }
}

@article{CASAZZA201661,
title = "Column generation for the variable cost and size bin packing problem with fragmentation",
journal = "Electronic Notes in Discrete Mathematics",
volume = "55",
pages = "61 - 64",
year = "2016",
note = "14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW16)",
issn = "1571-0653",
doi = "https://doi.org/10.1016/j.endm.2016.10.016",
url = "http://www.sciencedirect.com/science/article/pii/S157106531630172X",
author = "Marco Casazza and Alberto Ceselli",
keywords = "Bin Packing, Item Fragmentation, Variable Cost and Size, Column Generation",
abstract = "Bin Packing Problems with Item Fragmentation (BPPIF) are variants of classical Bin Packing in which items can be split at a price. We extend BPPIF models from the literature by allowing a set of heterogeneous bins, each potentially having a different cost and capacity. We introduce extended formulations and column generation algorithms to obtain good bounds with reasonable computing effort. We test our algorithms on instances from the literature. Our experiments prove our approach to be more effective than state-of-the-art general purpose solvers."
}

@Article{Marcotte1985,
author="Marcotte, Odile",
title="The cutting stock problem and integer rounding",
journal="Mathematical Programming",
year="1985",
month="Sep",
day="01",
volume="33",
number="1",
pages="82--92",
abstract="An integer programming problem is said to have the integer round-up property if its optimal value is given by the least integer greater than or equal to the optimal value of its linear programming relaxation. In this paper we prove that certain classes of cutting stock problems have the integer round-up property. The proof of these results relies upon the decomposition properties of certain knapsack polyhedra.",
issn="1436-4646",
doi="10.1007/BF01582013",
url="https://doi.org/10.1007/BF01582013"
}

@article{LINS2002421,
title = "An n-tet graph approach for non-guillotine packings of n-dimensional boxes into an n-container",
journal = "European Journal of Operational Research",
volume = "141",
number = "2",
pages = "421 - 439",
year = "2002",
issn = "0377-2217",
doi = "https://doi.org/10.1016/S0377-2217(02)00135-2",
url = "http://www.sciencedirect.com/science/article/pii/S0377221702001352",
author = "Lauro Lins and Sóstenes Lins and Reinaldo Morabito",
keywords = "3-Dimensional packing, Pallet/container loading, Combinatorial optimization, Graph theory",
abstract = "In this paper we propose a simple recursive uniform algorithm for the problem of packing n-dimensional boxes into an n-container. We are particularly concerned about the special case n=3 where the boxes can be packed in a given subset of their six possible positionings. Our method studies symmetries in the packings by the use of an ordered set of three directed graphs with the same edges (a 3-tet or triad) and induced smaller structures of the same kind named minors. With the method, degeneracy and symmetry issues, which curtail the implicit enumeration to practically acceptable running times, become transparent. In order to illustrate the performance of the algorithm, computational results from solving randomly generated 3-D examples are presented and compared with the ones of a layers and knapsack approach. The present study has real world applications for the problems of pallet and container loading."
}

@article{WU2002341,
title = "An effective quasi-human based heuristic for solving the rectangle packing problem",
journal = "European Journal of Operational Research",
volume = "141",
number = "2",
pages = "341 - 358",
year = "2002",
issn = "0377-2217",
doi = "https://doi.org/10.1016/S0377-2217(02)00129-7",
url = "http://www.sciencedirect.com/science/article/pii/S0377221702001297",
author = "Yu-Liang Wu and Wenqi Huang and Siu-chung Lau and C.K Wong and Gilbert H Young",
keywords = "Two-dimensional packing and cutting, VLSI floor planning",
abstract = "In this paper, we introduce an effective deterministic heuristic, Less Flexibility First, for solving the classical NP-complete rectangle packing problem. Many effective heuristics implemented for this problem are CPU-intensive and non-deterministic in nature. Others, including the polynomial approximation methodology [J. Assoc. Comput. Mach. 32 (1) (1985) 130] are too laborious for practical problem sizes. The technique we propose is inspired and developed by enhancing some rule-of-thumb guidelines resulting from the generation-long work experience of human professionals in ancient days. Although the Less Flexibility First heuristic is a deterministic algorithm, the results are very encouraging. This algorithm can consistently produce packing densities of around 99% on most randomly generated large examples. As compared with the recent results of a well known simulated annealing based Rectangle Packing (RP) algorithm [IEEE Trans. Computer-aided Design Integrated Circuits Systems 17 (1) (1998) 60], the results are much better both in less dead space2Which equals 1−α.2 (4% vs 6.7%) and much less CPU time (9.57 vs 331.78 seconds). Experimenting our heuristics on a public rectangle packing data set covering instances of 16–97 rectangles, the average unpack ratio is quite satisfactory (0.92% for bounding boxes limited to be optimum and 2.68% for the completed packing), while most cases spend only a few minutes in CPU time."
}

@article{PISINGER2002382,
title = "Heuristics for the container loading problem",
journal = "European Journal of Operational Research",
volume = "141",
number = "2",
pages = "382 - 392",
year = "2002",
issn = "0377-2217",
doi = "https://doi.org/10.1016/S0377-2217(02)00132-7",
url = "http://www.sciencedirect.com/science/article/pii/S0377221702001327",
author = "David Pisinger",
keywords = "Cutting/packing, Container loading, Knapsack packing, Heuristics",
abstract = "The knapsack container loading problem is the problem of loading a subset of rectangular boxes into a rectangular container of fixed dimensions such that the volume of the packed boxes is maximized. A new heuristic based on the wall-building approach is proposed, which decomposes the problem into a number of layers which again are split into a number of strips. The packing of a strip may be formulated and solved optimally as a Knapsack Problem with capacity equal to the width or height of the container. The depth of a layer as well as the thickness of each strip is decided through a branch-and-bound approach where at each node only a subset of branches is explored. Several ranking rules for the selection of the most promising layer depths and strip widths are presented and the performance of the corresponding algorithms is experimentally compared for homogeneous and heterogeneous instances. The best ranking rule is then used in a comprehensive computational study involving large-sized instances. These computational results show that instances with a total box volume up to 90% easily may be solved to optimality, and that average fillings of the container volume exceeding 95% may be obtained for large-sized instances."
}

@article{ZAK2002313,
title = "Modeling multistage cutting stock problems",
journal = "European Journal of Operational Research",
volume = "141",
number = "2",
pages = "313 - 327",
year = "2002",
issn = "0377-2217",
doi = "https://doi.org/10.1016/S0377-2217(02)00127-3",
url = "http://www.sciencedirect.com/science/article/pii/S0377221702001273",
author = "Eugene J. Zak",
keywords = "Linear programming, Multistage cutting stock problem, Large-scale optimization, Row-and-column generation",
abstract = "In multistage cutting stock problems (CSP) the cutting process is distributed over several successive stages. Every stage except the last one produces intermediate products. The list of intermediate products may be given or arbitrary. The goal is to minimize the total amount of material taken out of stock to cut finished products sufficient to meet customer demands. If the intermediate sizes are given, the column generation technique can be applied to multistage cutting problems. If the intermediate sizes are not given then another dimension is added to the problem complexity. We propose a special procedure for this case that dynamically generates both rows (intermediate sizes) and columns (patterns). We refer to this method as row-and-column generation. The method uses an auxiliary problem embedded into the frame of the revised simplex algorithm. It is a non-linear knapsack problem that can be solved efficiently. In contrast to the column generation method the developed technique cannot guarantee the optimal solution. However, the results of computational experiments are very promising and prove that the method is a valuable addition to the set of tools for modeling and solving multistage CSPs."
}

@Article{López-Camacho2013,
author="L{\'o}pez-Camacho, Eunice
and Ochoa, Gabriela
and Terashima-Mar{\'i}n, Hugo
and Burke, Edmund K.",
title="An effective heuristic for the two-dimensional irregular bin packing problem",
journal="Annals of Operations Research",
year="2013",
month="Jul",
day="01",
volume="206",
number="1",
pages="241--264",
abstract="This paper proposes an adaptation, to the two-dimensional irregular bin packing problem of the Djang and Finch heuristic (DJD), originally designed for the one-dimensional bin packing problem. In the two-dimensional case, not only is it the case that the piece's size is important but its shape also has a significant influence. Therefore, DJD as a selection heuristic has to be paired with a placement heuristic to completely construct a solution to the underlying packing problem. A successful adaptation of the DJD requires a routine to reduce computational costs, which is also proposed and successfully tested in this paper. Results, on a wide variety of instance types with convex polygons, are found to be significantly better than those produced by more conventional selection heuristics.",
issn="1572-9338",
doi="10.1007/s10479-013-1341-4",
url="https://doi.org/10.1007/s10479-013-1341-4"
}

@article{Hopper2001AnEI,
  title={An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem},
  author={E. Hopper and B. C. H. Turton},
  journal={European Journal of Operational Research},
  year={2001},
  volume={128},
  pages={34-57}
}

@article{LEUNG201157,
title = "A two-stage intelligent search algorithm for the two-dimensional strip packing problem",
journal = "European Journal of Operational Research",
volume = "215",
number = "1",
pages = "57 - 69",
year = "2011",
issn = "0377-2217",
doi = "https://doi.org/10.1016/j.ejor.2011.06.002",
url = "http://www.sciencedirect.com/science/article/pii/S037722171100508X",
author = "Stephen C.H. Leung and Defu Zhang and Kwang Mong Sim",
keywords = "Packing problem, Heuristic search, Simulated annealing"
}

@ARTICLE{4895699, 
author={C. D. Tarantilis and E. E. Zachariadis and C. T. Kiranoudis}, 
journal={IEEE Transactions on Intelligent Transportation Systems}, 
title={A Hybrid Metaheuristic Algorithm for the Integrated Vehicle Routing and Three-Dimensional Container-Loading Problem}, 
year={2009}, 
volume={10}, 
number={2}, 
pages={255-271}, 
keywords={logistics;search problems;transportation;capacitated vehicle routing problem;guided local search;hybrid metaheuristic algorithm;integrated vehicle routing problem;tabu search;three-dimensional container-loading problem;transportation logistics company;Fleet management;guided local search (GLS);tabu search (TS);vehicle routing and packing integration}, 
doi={10.1109/TITS.2009.2020187}, 
ISSN={1524-9050}, 
month={June}
}

@INPROCEEDINGS{8216987, 
author={Q. Zhou and X. Liu}, 
booktitle={IECON 2017 - 43rd Annual Conference of the IEEE Industrial Electronics Society}, 
title={A swarm optimization algorithm for practical container loading problem}, 
year={2017}, 
volume={}, 
number={}, 
pages={5690-5695}, 
abstract={3D container loading problem (3D-CLP) is a classic NP-hard optimization problem. Although computer scientists and discrete mathematicians have studied this problem for decades, there are still some unsolved puzzles, such as multi-constrained 3D container loading optimization. Moreover, with the rapid development of modern logistics, several new 3D container-loading related problems emerged, such as containers with various sizes, considering different orientations of boxes, and two-step 3D container loading with pallets. From the perspective of practical applications, this paper proposes a new heuristic algorithm for emerged 3D container loading problems. Our proposed algorithm regards the loading arrangement as the position of an individual in the swarm, and by the interactions of the individuals with each other and with loading constraints, most of them will gather to the good ones and finally stop at the best position, which is the loading arrangement of boxes. The proposed algorithm can solve both the 3D container loading problem with pallets or without pallets. Experimental results show significant performance improvements over other state-of-the-art approaches.}, 
keywords={computational complexity;containerisation;containers;loading;logistics;particle swarm optimisation;3D container loading optimization;3D-CLP;classic NP-hard optimization problem;heuristic algorithm;loading arrangement;loading constraints;practical container loading problem;swarm optimization algorithm;two-step 3D container loading;Containers;Heuristic algorithms;Loading;Optimization;Particle swarm optimization;Three-dimensional displays;container loading problem;pallet loading;swarm optimization}, 
doi={10.1109/IECON.2017.8216987}, 
ISSN={}, 
month={Oct}
}

@Article{Wang2007,
author="Wang, Zhou-jing
and Li, Kevin W.",
title="Layer-layout-based heuristics for loading homogeneous items into a single container",
journal="Journal of Zhejiang University-SCIENCE A",
year="2007",
month="Nov",
day="01",
volume="8",
number="12",
pages="1944--1952",
abstract="The container loading problem (CLP) is a well-known NP-hard problem. Due to the computation complexity, heuristics is an often-sought approach. This article proposes two heuristics to pack homogeneous rectangular boxes into a single container. Both algorithms adopt the concept of building layers on one face of the container, but the first heuristic determines the layer face once for all, while the second treats the remaining container space as a reduced-sized container after one layer is loaded and, hence, selects the layer face dynamically. To handle the layout design problem at a layer's level, a block-based 2D packing procedure is also developed. Numerical studies demonstrate the efficiency of the heuristics.",
issn="1862-1775",
doi="10.1631/jzus.2007.A1944",
url="https://doi.org/10.1631/jzus.2007.A1944"
}