Modeling soft unloading constraints in the multi-drop container loading problem
OPEN ACCESS
Loading...
Author / Producer
Date
2023-07-01
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
The multi-drop container loading problem (MDCLP) requires loading a truck so that boxes can be unloaded at each drop-off point without rearranging other boxes to deliver later. However, modeling such unloading constraints as hard constraints, as done in the literature, limits the flexibility to optimize the packing and utilize the vehicle capacity. We instead propose a more general approach that considers soft unloading constraints. Specifically, we penalize unnecessary relocations of boxes using penalty functions that depend on the volume and weight of the boxes to move as well as the type of move. Our goal is to maximize the value of the loaded cargo including penalties due to violations of the unloading constraints. We provide a mixed-integer linear programming formulation for the MDCLP with soft unloading constraints, which can solve to optimality small-scale instances but is intractable for larger ones. We thus propose a heuristic framework based on a randomized extreme-point constructive phase and a subsequent improvement phase. The latter phase iteratively destroys regions in the packing space where high penalties originate, and reconstructs them. Extensive numerical experiments involving different instances and penalties highlight the advantages of our method compared to a commercial optimization solver and a heuristic from the literature developed for a related problem. They also show that our approach significantly outperforms: (i) the hard unloading constraints approach, and (ii) a sequential heuristic that neglects unloading constraints first and evaluates the penalties afterwards. Our findings underscore the relevance of accounting for soft unloading constraints in the MDCLP.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
308 (1)
Pages / Article No.
336 - 352
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Packing; Container loading; Multi-drop shipments; Mixed-integer programming; Improvement heuristic
Organisational unit
Notes
Funding
181210 - DADA - Dynamic data driven Approaches for stochastic Delay propagation Avoidance in railways (SNF)
Related publications and datasets
Is new version of: http://hdl.handle.net/20.500.11850/514161