An optimization approach for a complex real-life container loading problem. (February 2022)

• Record Type: Journal Article
• Authors: Gajda, Mikele; Trivella, Alessio; Mansini, Renata; Pisinger, David
• Is Part Of: Omega. Volume 107(2022)
• Publication Date: 2022-02
• Subjects: Container loading problem -- Real-life constraints -- Randomized constructive heuristic -- Industry collaboration; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2021.102559
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: We study a real container loading problem in collaboration with a logistics company. The problem involves challenging practical constraints, some new to the literature. We propose a randomized constructive heuristic to solve large industry instances. The heuristic improves the cargo value by 22% compared to the company's solutions. The heuristic is benchmarked against dual bounds and commercial software. Abstract: We consider a real-world packing problem faced by a logistics company that loads and ships hundreds of trucks every day. For each shipment, the cargo has to be selected from a set of heterogeneous boxes. The goal of the resulting container loading problem (CLP) is to maximize the value of the cargo while satisfying a number of practical constraints to ensure safety and facilitate cargo handling, including customer priorities, load balancing, cargo stability, stacking constraints, positioning constraints, and limiting the number of unnecessary cargo move operations during multi-shipment deliveries. Although some of these constraints have been considered in the literature, this is the first time a problem tackles all of them jointly on real instances. Moreover, differently from the literature, we treat the unnecessary move operations as soft constraints and analyze their trade-off with the value maximization. As a result, the problem is inherently multi-objective and extremely challenging. We tackle it by proposing a randomized constructive heuristic that iteratively combines items in a preprocessing procedure, sorts them based on multiple criteria, uses randomization to partially perturb the sorting, and finally constructs the packing while complying with all the side constraints. We also propose dual bounds based on CLP relaxations. On large-scale industry instances, our algorithm runs in a few seconds and outperforms (in terms of value and constraints handling) both the solutions constructed manually by the company and those provided by a commercial software. The algorithm is currently used by the company generating significant economic and CO 2 savings.