Solving the 3D-pallet loading problem by a mixed integer linear programming and a hybrid genetic algorithm

In this thesis, the three-dimensional pallet loading problem (3D-PLP), which is a kind of container loading problems (CLP), was studied under the constraints as rotation, fragility, load-bearing strength, relative positioning as well as the constraints that should be considered due to the nature of the problem. A mixed integer linear programming (MILP) model was developed for the optimal solution of the studied 3D-PLP. The developed model can be used to optimize small-scale 3D-PLP. However, due to increase in some problem parameters as the number of customers, the number of objects and the pallet loading rate, it cannot be solved in an acceptable time for large-scale real-life problems. For this reason, a new hybrid genetic algorithm (HGA) was developed for solving large-scale problems. It was hybridized with two different heuristic approaches, one of them is based on a stack-building approach and the other one is based on a layer building approach. The stack-building approach determines the objects which have at least two equal dimensions by searching structure of genetic algorithm (GA). This operation reduces the number of objects to be placed. The chromosome lengths in the GA may change because of the combining operation. For this reason, existing crossover operators in the literature cannot be employed. And a crossover operator called the intelligent dynamic crossover operator (I-DCO) was developed. Another heuristic approach in the proposed HGA is deepest bottom left fill (DBLF) approach which is available in the literature. Under favor of the steps of DBLF, all objects can be loaded to the pallets and the coordinates of all objects on the pallets are determined. The proposed HGA was compared with classical DBLF on test problems and it was shown that the proposed HGA produced better solutions statistically. In addition, the proposed HGA was compared with two existing meta-heuristic algorithms on test problems. It was shown that the proposed HGA achieved better results than these algorithms. As a result, the proposed HGA for the 3D-PLP yielded much better results.