Heuristic approaches for freight containerization with business rules

Manufacturing companies who ship goods globally often rely on external Logistics Service Providers (LSPs) to manage the containerization and transportation of their freight. Those LSPs are usually required to follow rules when deciding how to mix the goods in the containers, which complicates the planning task. In this paper, we study such a freight containerization problem with a specific type of cargo mixing requirements recurrently faced by an international LSP. We show that this problem can be formulated as a Multi-Class Constrained Variable Size Bin Packing Problem: given a set of items that all have a size and a fixed number of classes for which they can take certain values, the objective is to pack the items in a minimum-cost set of bins while ensuring that the size capacity and maximum number of distinct values per class are not exceeded in any of the bins. We propose two adapted and one novel greedy heuristics, as well as an Adaptive Large Neighborhood Search (ALNS) metaheuristic, to find feasible solutions to the problem. We also provide a pattern-based formulation that is used to obtain lower bounds using a Column Generation approach. Using three extensive datasets, including a novel one with up to 1000 items and 5 classes reflecting real industrial cases, we show that the novel greedy heuristic outperforms the adaptations of the existing ones and that our ALNS yields significantly better solutions than a commercial solver within a mandatory 5-minute time limit. Practical insights are given about the solutions for the industrial benchmark.