An optimization approach for a complex real-life container loading problem

Mikele Gajda, Alessio Trivella*, Renata Mansini, David Pisinger

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

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 CO2 savings.
Original languageEnglish
Article number102559
JournalOmega: The International Journal of Management Science
Volume107
Number of pages16
ISSN0305-0483
DOIs
Publication statusPublished - 2022

Keywords

  • Container loading problem
  • Real-life constraints
  • Randomized constructive heuristic
  • Industry collaboration

Fingerprint

Dive into the research topics of 'An optimization approach for a complex real-life container loading problem'. Together they form a unique fingerprint.

Cite this