Modeling soft unloading constraints in the multi-drop container loading problem
| Autor: | Guillem Bonet Filella, Alessio Trivella, Francesco Corman |
|---|---|
| Přispěvatelé: | Industrial Engineering & Business Information Systems |
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
Multi-drop shipments
History Information Systems and Management General Computer Science Polymers and Plastics Computer science Drop (liquid) UT-Hybrid-D Mechanical engineering Mixed-integer programming Management Science and Operations Research Industrial and Manufacturing Engineering Container loading Packing Improvement heuristic Modeling and Simulation Container (abstract data type) Business and International Management Integer programming |
| Zdroj: | European Journal of Operational Research, 308 (1) European journal of operational research. Elsevier |
| ISSN: | 0377-2217 1872-6860 |
| Popis: | 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. European Journal of Operational Research, 308 (1) ISSN:0377-2217 ISSN:1872-6860 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect