Packing with Item Availability and Bin Due Dates

Felix Brandt and Jan-Nikola Popratnjak and Enrico Schulz
EURO Special Interest Group on Cutting and Packing
In this work, we present a new generalisation of the multiple heterogeneous knapsack problem (MHKP), by considering earliest availability dates of items and latest usage dates of bins. In the standard MHKP it is assumed that all the items to pack into bins are available and there are no restrictions about the time of bin assembly. In logistics however, especially in an air cargo environment this is not necessarily the case. Instead, the items for a flight arrive at the hub at different times, due to their inbound connection or delivery by the shipper. Furthermore, we assume there already exists a general production schedule for the bins of all flights. For a given flight to pack, we interpret this schedule as a sequence of possible due dates of its bins. In a solution each of these due dates can be assigned to at most one bin, i.e., the order of assembly of the bins is determined by the procedure. Accordingly, each bin can only be filled with items that are available before its due date. We propose an integrated problem formulation, from which we derive and solve a MIP model. Furthermore, we present our preliminary experiments to motivate the benefits of an integrated approach and compare its performance to simple decompositions into a sequence of standard MHKP.
Logistik und Supply-Chain-Optimierung
Innovationspartnerschaft mit der Lufthansa Cargo
Download .bib
Download .bib
Eingetragen von
Felix Brandt