2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – A.Omidi
    Oct 21, 2023 at 7:29
  • $\begingroup$ 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 $\endgroup$
    – J. Doe
    Oct 21, 2023 at 20:24
  • $\begingroup$ 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? $\endgroup$
    – A.Omidi
    Oct 22, 2023 at 5:14
  • $\begingroup$ 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 $\endgroup$
    – J. Doe
    Oct 22, 2023 at 6:39

1 Answer 1

1
$\begingroup$

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 $$

Addendum

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$.

$\endgroup$
3
  • $\begingroup$ In this solution, how does it prioritize a shipment to be shipped on earliest possible day? If we add to the objective function, sum( c(t) * x(i,k,t) ) where c(t) is 1 for 1st day, 2 for 2nd etc. Would that solve that problem? Sorry for the formula, I’m typing on my phone $\endgroup$
    – J. Doe
    Oct 21, 2023 at 20:30
  • $\begingroup$ @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}$) $\endgroup$
    – A.Omidi
    Oct 22, 2023 at 5:16
  • $\begingroup$ @J.Doe yes you can add the proposed term in the objective function to prioritize early shipments. $\endgroup$
    – Kuifje
    Oct 22, 2023 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.