Modeling soft unloading constraints in the multi-drop container loading problem
METADATA ONLY
Loading...
Author / Producer
Date
2021-09-28
Publication Type
Working Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
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, considerably limits the flexibility to optimize the packing and utilize the vehicle capacity. We thus 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 total value of the loaded cargo including penalty functions 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 to solve large instances, which is 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 penalties 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
Pages / Article No.
3929994
Publisher
Social Science Research Network
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
09611 - Corman, Francesco / Corman, Francesco
02655 - Netzwerk Stadt u. Landschaft ARCH u BAUG / Network City and Landscape ARCH and BAUG
Notes
Funding
181210 - DADA - Dynamic data driven Approaches for stochastic Delay propagation Avoidance in railways (SNF)
Related publications and datasets
Is previous version of: