Three-Dimensional Container Loading: A Simulated Annealing .

International Journal of Applied Engineering Research ISSN 0973-4562 Volume 12, Number 7 (2017) pp. 1290-1304 Research India Publications. http://www.ripublication.comThree-Dimensional Container Loading: A Simulated AnnealingApproach1Hanan Mostaghimi,2Bryan St. Amour and1#Walid Abdul-KaderFaculty of Engineering, University of Windsor, Windsor (Ontario), Canada12Department of Computer Science, University of Windsor, Windsor (Ontario), Canada#ORCID: 0000-0002-2926-5059to a compact, which results in a potential loss of the marketwhen compared to other competitor's vehicles (Hifi, 2002;Bortfeldt et al., 2003; and Wang et al., 2008).AbstractHigh utilization of cargo volume is an essential factor in thesuccess of modern enterprises in the market. Althoughmathematical models have been presented for container loadingproblems in the literature, there is still a lack of studies thatconsider practical constraints. In this paper, a Mixed IntegerLinear Programming is developed for the problem of packing asubset of rectangular boxes inside a container such that the totalvalue of the packed boxes is maximized while some realisticconstraints, such as vertical stability, are considered. Thepacking is orthogonal, and the boxes can be freely rotated intoany of the six orientations. Moreover, a sequence triple-basedsolution methodology is proposed, simulated annealing is usedas modeling technique, and the situation where some boxes arepreplaced in the container is investigated. These preplacedboxes represent potential obstacles. Numerical experiments areconducted for containers with and without obstacles. Theresults show that the simulated annealing approach issuccessful and can handle large number of packing instances.The basic form of the container loading problem is packing thebest subset of rectangular boxes (called cargo) into a largeobject (called container) to maximize the total value of theloaded boxes. The boxes should not be overlapped and shouldlie entirely in the container. According to the topologyintroduced by Wascher et al. (2007), the containers can beeither homogeneous or heterogeneous. If the boxes placed inthe given container are identical, it is called homogeneous;however, if various types of boxes are loaded, the container isconsidered as heterogeneous. Besides the non-overlappingconstraints, some other practical constraints should beconsidered in the real-world container loading problem, such ascargo vertical stability, preplaced boxes, and box rotation(Junqueira et al., 2012; Bortfeldt et al., 2012). However, notmany papers have considered these practical constraints in theirproposed models.The problem addressed in this research and as per the topologypresented by Dyckhoff (1990), belongs to 3/B/O/F (3: threedimensional, B/O: one object/bin and items selection, F: fewitems of different types), while Wascher et al. (2007) classify itas the three-dimensional single orthogonal knapsack problem.The given problem considers the packing of rectangular itemsinto a container to maximize the total value of the packed itemsby minimizing the amount of lost space. The value of boxes isassumed to be equal to their volume. The rotation of the boxesis considered as well. The multidimensional knapsack Problem(MKP) is a NP-hard optimization problem that can be shownby reduction from the one-dimensional packing problem(Egeblad and Pisinger, 2009). Although technologicalknowledge has been enhanced, solving real knapsack problemsis still a challenge. Due to NP-hardness of the packing problem,only heuristic methods, and a few exact algorithms have beenpresented.Keywords: knapsack, packing sequence, rotation, obstacles,simulated annealingINTRODUCTIONLogistics has recently played an important role in the successof modern enterprises. Packing boxes inside a container is anessential material handling activity in manufacturing andtransportation industries. It is also a key function for operatingsupply chain efficiently. The efficient use of transportationdevices, like containers and palettes, leads to significant costsaving. Moreover, high utilization of transportation devicesreduces the traffic of goods and protects natural resources.Therefore, optimal loading of a container decreases theshipping cost and increases the stability of the load. Containerloading problem has practical values, and it can be applied tovarious fields. Loading cars, trucks, trains, or ships can be alsoconsidered as a container loading or a three-dimensionalpacking problem. Furthermore, cargo volume is an importantfactor used by motor vehicle companies to market theirproducts as sub-compact, compact, midsize, or full size. Ifinaccurate, the cargo volume found may downgrade the vehiclefrom its real size. For example, a mid-size may be downgradedIn this paper, a mixed integer linear model and a simulatedannealing algorithm are developed to address a iderations, such as vertical stability and preplaced(obstacles) constraints, are tackled. These practical constraintsand box rotation contribute significantly to a study of a more1290

International Journal of Applied Engineering Research ISSN 0973-4562 Volume 12, Number 7 (2017) pp. 1290-1304 Research India Publications. http://www.ripublication.comproposed for packing a batch of objects. Goncalves et al. (2012)propose a multi-population biased random-key geneticalgorithm for the single container loading problem. Maximalspace representation is used to manage the container free space.The authors consider stability and orientation constraints;however, they do not develop a mathematical model for thegiven problem. Peng et al. (2009) present a hybrid simulatedannealing algorithm for three-dimensional container loadingproblem. Firstly, a heuristic algorithm is used for encodingfeasible packing solutions, and then the simulated annealingalgorithm is applied to search in the encoding neighborhood.Hongtao et al. (2012) address a three-dimensional singlecontainer loading problem by using a multi-stage search basedsimulated annealing algorithm.Wei et al. (2012) use areference length approach to address the three-dimensionalstrip packing problem. In another paper, Wei et al. (2015)address the problem of multiple container loading costminimization problem by using a new approach that combinescolumn generation technique with a goal driven search.realistic 3D knapsack problem as proposed in this researchwork. The aim of this proposed research is to provide managersand decision-makers with an adequate modeling tool that helpsmake shipping goods more efficient and eco-friendly as fewertrips can be made if higher container utilization is achieved.Also, auto-makers can market the class size of their vehiclesmore accurately.LITERATURE REVIEWThe focus of most of the container loading or three-dimensionalcutting and packing problems is on the rectangular bins. Feketeand Schepers (2004) propose a new method for obtaining lowerbound classes for higher-dimensional packing problem. Themajor objective of this paper is to define good criteria forremoving a candidate set of boxes. Dual feasible function is away to build conservative scales. The computational results aremainly limited to the two-dimensional packing problem. Hifi(2004) proposes a dynamic algorithm and an exact depth-firstsearch to solve the three-dimensional cutting problem.Orientation and guillotine constraints are considered. Optimalsolutions are obtained for a significant number of instances, butnot all of them. Althaus et al. (2007) consider the trunk packingproblem where the box dimensions are as per the SAE J1100standard. They propose two discretized methods. First, thespace to be packed is discretized. Then, an approximationapproach is considered using linear inequalities. The spacediscretization causes insufficient representation of the boxes.Additionally, the runtime of the enumerative algorithms isexponential.Other research works related to design automation focus onthree-dimensional placement of circuit elements by exploringthe layout of the integrated circuits (Obenaus and Szymansky,2003), and Cheng et al. (2005) address floor planning for 3-DVLSI Design. While this technique is less known to containerloading practices, it carries some similarities and it is moreefficient in terms of search time than other methods such aspartitioning placement.Models that provide information on optimal objective functionvalue and bounds help to assess the solution quality of heuristicalgorithms. Although modeling three-dimensional knapsackproblems considers practical constraints, it is still at itsbeginnings. Junqueira et al. (2012) present mixed integer linearprogramming models for the container loading problem.Vertical and horizontal stability of the cargo, as well as cargoload bearing strength, are considered in the proposed model.However, the models are only able to handle moderate sizedproblems. Table 1 compares some relevant papers and models,and shows their similarities and differences.Although considerable advancement has been made in thedevelopment of exact algorithms, heuristic algorithms still playan important role in solving three-dimensional knapsackproblems. Only heuristic methods can provide reasonablesolutions within an acceptable running time for instances ofreal-world sized problems. Pisinger (2002) develops a wallbuilding based heuristic. Both homogenous and heterogeneousinstances are considered. Moreover, several ranking rules arestudied to select the best layers’ depths. Bortfeldt et al. (2003)propose a parallel tabu search approach for a single containerloading problem and give little consideration to heterogeneousinstances. Wang et al. (2008) also present a heuristic methodfor a heterogeneous container loading problem and developeda dynamic space decomposition approach based on the tertiarytree structure. Egeblad and Pisinger (2009) propose a simulatedannealing based methodology for the two and threedimensional knapsack problems, and a three-dimensionalknapsack model is presented. The authors present an iterativeheuristic approach for the knapsack problem that is based onthe sequence triple representation. Also, Yamazaki et al. (2000)apply a variety of packing sequences including sequence-triplein their 3-D packing solution approach. To control the heuristicmethod, simulated annealing is used. However, rotation ofboxes and preplaced boxes (obstacles) are not considered in thethree-dimensional model and experiments. Wu et al. (2010)consider the three-dimensional bin packing problem withvariable bin heights. A mixed integer programming model isproposed, and they also present the case when more than onetype of bin is used. A genetic algorithm-based heuristic isPer the literature, not all papers consider box rotation since itincreases the search space significantly. Bin stabilityconstraints have likewise been just considered in a few papers.To the best of our knowledge, preplaced boxes (obstacles) havenot been studied in three-dimensional knapsack problems,although it is so essential for such problems since it is oftenrequired to place certain boxes in certain positions. Theseconstraints can also be used in the case of having a nonrectangular container. Therefore, it is important to study morepractical constraints in the knapsack problem. This proposedresearch work aims to contribute to the literature so that a 3Dknapsack problem can be tackled where box rotation isconsidered to help finding more practical packingconfigurations. Furthermore, preplaced boxes (bin with someobstacles) and vertical stability constraints are considered andaddressed. This is useful, especially when considering trunkloading for auto size classification as indicated earlier in theIntroduction section.1291