Data: I have the following items I need to ship, with the input data as below. Each item needs to be shipped by shipDate at the latest, but can be shipped as early as availDate. Each truck has a min/max load, so if there is not enough load for 1 truck, the shipment is postpone to next day.
shipDate item weight availDate
10/20/23 1 10kg 10/20/23
10/20/23 2 20kg 10/19/23
10/21/23 3 30kg 10/19/23
10/22/23 4 40kg 10/21/23
Currently, I am running a bin packing problem for each ship date, and for any leftover space for each day, I will take
for date in shipDate
filter items for date, and run bin packing problem with those items
take all items in current date and update to next date
get total empty remaining weight for all trucks (i.e if truck 1 is 90/100kg, and trucks 2 is 95/100kg, then total remaining weight is 15kg)
make list of all items that are available today but have ship date in future
with that list, make combination of all items that total up to remaining weight (15kg in example). then sort the list by weight desc
for item in list:
rerun bin packing problem with added items til feasible is found
if no feasible found, then original solution with no items from future dates is optimal
This heuristic seems to work, but then I realize a problem. If I take items from a future date, then there is a chance that all shipments for that future date may be infeasible if there is not enough items to meet the minimum load.
One approach I am thinking of is to treat this as one whole bin packing problem. If i create assignment variables with dates A(item)(truck)(date) and have each item have multiple dates between availDate and shipDate (i.e - for item 3 above, there would be assignment variables for 10/19, 10/20, and 10/21), then update the each item assigned to one truck/date constraint. Then I can add a weight to the objective function to prioritize an item to ship earlier if possible. sum( A(item,truck,date) * n) ), where n = 1 for first date etc.
It is very hacky but I think it should work. Is there any holes in this logic that will cause issues or prevent scalability? I want to make sure I am not missing anything. Thanks