Please use this identifier to cite or link to this item:
http://doi.org/10.25358/openscience-7216
Authors: | Heßler, Katrin Irnich, Stefan Kreiter, Tobias Pferschy, Ulrich |
Title: | Bin packing with lexicographic objectives for loading weight- and volume-constrained trucks in a direct-shipping system |
Online publication date: | 27-Jun-2022 |
Year of first publication: | 2022 |
Language: | english |
Abstract: | We consider a packing problem that arises in a direct-shipping system in the food and beverage industry: Trucks are the containers, and products to be distributed are the items. The packing is constrained by two independent quantities, weight (e.g., measured in kg) and volume (number of pallets). Additionally, the products are grouped into the three categories: standard, cooled, and frozen (the latter two require refrigerated trucks). Products of different categories can be transported in one truck using separated zones, but the cost of a truck depends on the transported product categories. Moreover, splitting orders of a product should be avoided so that (un-)loading is simplified. As a result, we seek for a feasible packing optimizing the following objective functions in a strictly lexicographic sense: minimize the (1) total number of trucks; (2) number of refrigerated trucks; (3) number of refrigerated trucks which contain frozen products; (4) number of refrigerated trucks which also transport standard products; (5) and minimize splitting. This is a real-world application of a bin-packing problem with cardinality constraints a.k.a. the two-dimensional vector packing problem with additional constraints. We provide a heuristic and an exact solution approach. The heuristic meta-scheme considers the multi-compartment and item fragmentation features of the problem and applies various problem-specific heuristics. The exact solution algorithm covering all five stages is based on branch-and-price using stabilization techniques exploiting dual-optimal inequalities. Computational results on real-world and difficult self-generated instances prove the applicability of our approach. |
DDC: | 330 Wirtschaft 330 Economics 650 Management 650 Management and auxiliary services |
Institution: | Johannes Gutenberg-Universität Mainz |
Department: | FB 03 Rechts- und Wirtschaftswissenschaften |
Place: | Mainz |
ROR: | https://ror.org/023b0x485 |
DOI: | http://doi.org/10.25358/openscience-7216 |
Version: | Published version |
Publication type: | Zeitschriftenaufsatz |
License: | CC BY |
Information on rights of use: | https://creativecommons.org/licenses/by/4.0/ |
Journal: | OR spectrum 44 2 |
Pages or article number: | 375 417 |
Publisher: | Springer |
Publisher place: | Berlin u.a. |
Issue date: | 2022 |
ISSN: | 1436-6304 |
Publisher DOI: | 10.1007/s00291-021-00628-x |
Appears in collections: | JGU-Publikationen |
Files in This Item:
File | Description | Size | Format | ||
---|---|---|---|---|---|
bin_packing_with_lexicographi-20220624141747293.pdf | 1.15 MB | Adobe PDF | View/Open |