Comparison of Different Grasp Algorithms for the Heterogeneous Vector Bin Packing Problem

摘要

In this paper, we address the practical problem of packing multiple items into containers for further transport. Dense packing of containers can significantly decrease supply chain costs, since transport fees are related to the the number of used containers and not the content. This practical problem is generally modeled using the vector bin packing problem (VBPP) and its variations. In the recent years, the heterogeneous VBPP with two sets of constraints has proven to be a good representation of container packing related problems. In this work we extend this model to a more realistic setting, by allowing multiple containers of the same type. To solve this problem, an integer program is designed. To be able to find feasible solutions for large scale problem instances, a greedy constructive algorithm is developed. With the intention of improving the solutions generated in this way, a local search is developed and used to extend the greedy algorithm to the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic. To evaluate the potential of using GRASP on this problem, several variations are designed and implemented. In our computational experiments, we have generated test instances based on real-world data. Experimental results show that the designed metaheuristic approaches provide high quality solutions compared to solutions obtained by the CPLEX solver. Further, one of the proposed GRASP variants has been adapted for the homogeneous VBPP and tested on standard benchmark instances in order to evaluate its performance against existing metaheuristic. The final conclusion is that the GRASP presents a promising approach for more challenging instances for which CPLEX cannot find feasible solution within a reasonable time limit.