# Bin packing problem with multiple dates

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

if infeasible
take all items in current date and update to next date
else
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

• Is it possible to split orders to fill the loading of each truck? If no, how can you fill (e.g. $15$kg) deviation from the list? Also, do you check how what you proposed works in the presence of real situations? Oct 21, 2023 at 7:29
• No splitting. Sorry I didn’t do the 85 total from my example data. And yes it works when I run with shipment data, but I just realize the case where it can output a bad solution and delay an entire shipment by a day Oct 21, 2023 at 20:24
• Thanks for the clarification. In your case, do you try adding an appropriate penalty in the objective function to force the model or algorithm to minimize delay? Oct 22, 2023 at 5:14
• yes, i am thinking of adding a weight value to each day (first day is 0, 2nd is 1, etc) and then multiplying each assignment variable by the date weight. that way itll always prioritize each item to ship as early as possible Oct 22, 2023 at 6:39

You can use the follow model:

#### Assumptions

• No split delivery
• Each shipment can be done in at most one day

#### Parameters

• $$q_k$$ minimum capacity for vehicle $$k \in K$$
• $$Q_k$$ maximum capacity for vehicle $$k \in K$$
• $$c_k$$ cost of using vehicle $$k \in K$$
• $$v_i$$ volume of item $$i \in I$$
• $$T_i \subseteq T$$ set of feasible shipment dates for item $$i \in I$$
• $$I_t \subseteq I$$ set of feasible shipments (items) on day $$t \in T$$

#### Variables

• $$x_{ik}^t \in\{0,1\}$$ takes value $$1$$ $$\Leftrightarrow$$ item $$i\in I$$ is shipped in vehicle $$k\in K$$ on day $$t\in T$$ (note: this is the assignment variable proposed by OP)
• $$y_{k}^t \in\{0,1\}$$ takes value $$1$$ $$\Leftrightarrow$$ vehicle $$k\in K$$ is used on day $$t\in T$$ for a shipment

#### Objective function

You want to minimize total shipment costs: $$\min \sum_{t\in T}\sum_{k\in K}c_ky_k^t$$

#### Constraints

• Each item must be shipped in one vehicle, on a feasible date: $$\sum_{k \in K}\sum_{t \in T_i} x_{ik}^t = 1 \quad \forall i\in I$$
• Capacity constraints: $$q_k y_{k}^t \le \sum_{i \in I_t} v_i x_{ik}^t \le Q_k y_{k}^t \quad \forall k\in K, \; \forall t \in T$$
• If a vehicle cannot be used more than once: $$\sum_{t\in T}y_{k}^t \le 1 \quad \forall k\in K$$

To prioritize early shipments, the following term can be included (minimized) in the objective function: $$\sum_{i,k,t}C_{i}^tx_{ik}^t$$ where $$C_i^t$$ is a "penalty" for shipping item $$i$$ on day $$t$$. This penalty can be zero for the first shipment date possible, and then increase with time.
Note that adding this term to the objective function creates a trade-off between minimizing vehicle costs and prioritizing shipments. It may not be easy to fix the right value for penalty $$C_i^t$$.
• @J.Doe, in the first constraint and in the inner summation on $t$, you can set a filter on the time window for each order. ($t \in T_{i}$) Oct 22, 2023 at 5:16