4
$\begingroup$

I have a the following optimization problem: I have mandates,(e,g. to deliver 100 tonnes of products) that I need to schedule its delivery during the month (day 2: deliver 40 Tonnes, day 15: deliver 40 tonnes, day 28:deliver 20 tonnes, their sum is equal 100). I have limited inventory that is daily fed by the factory (forecast of production for the month is given as an input).

Delivery is done using multiple vehicles with different capacities (e.g, 2T, 4T, 6T) on multiple stations along the month. For each product, a subset of stations can do the delivery, and stations can't handle more than 1 vehicle at a time.

The problem can be modeled as a variant of the lot-sizing problem. However, hard to solve even for small instances because of the decision variable $Y_{p,t,s,c}$ that indicate if a product $p$ is delivered on day $t$ on station $s$ using vehicle $c$. First it has high dimensions, and second it introduces symmetry (I optimize only the stock level)

However, since I don't really care on which station a product is loaded, I just need to ensure that at day $t$ stations are not overloaded (since two different products can use same station). Do you think removing subscript $s$, and doing a row-generation in which each time I compute a solution I check if its feasible with respect to stations and I add constraint seems like a good approach? It worked on my instance but I don't know what kind of problems it may add if more complex instances are being solved.

Edit: The model is:

Let $\mathbb{J}$ be the set of all stations. Let $\mathbb{P}$ be the set of all products. Moreover, let $\mathbb{T}$ be the set of time periods. Finally, let $\mathbb{C}$ be the set of all vehicles

The optimization variables and parameters are the following:

$x_{p,t,j,c}$ continuous variable that denotes the quantity of product $p$ that is served at time $t \in \mathbb{T}$ on station $j \in \mathbb{J}$ using vehicle $c$.

$Y_{p,t,j,c}$ binary variable product $p$ that is served at time $t \in \mathbb{T}$ on station $j \in \mathbb{J}$ using vehicle $c$.

$S_{p,t}$ level of stock of product $p \in \mathbb{P}$ at time $t \in \mathbb{T}$

$d_{p,t}$ is the daily production of product $p$. input to the model

The objective function is to stay as close as possible to a given inventory target $$ \sum_p \sum_t \lvert S_{p,t} - Target_p \rvert \tag{1} $$

Mandate fulfillment constraint: $$ \sum_t \sum_j \sum_c x_{p,t,j,c} = Mandate_p \; \forall p \tag{2} $$

Flow balance constraint: $$ S_{p,t} = S_{p,t-1} + d_{p,t} - \sum_{j}\sum_{c} x_{p,t,j,c} \; \forall p \in P, \; \forall t \in T \tag{3} $$

Stock limits: $$ Min_p \leq S_{p,t} \leq Max_p, \forall p \forall t \tag{4} $$

Stations constraints: $$ \sum_p \sum_c Cap_c Y_{p,t,j,c} \leq MaxCap_j \forall j, \forall t \tag{5} $$

Fixed charge constraint: $$ x_{p,t,j,c} \le Cap_c*Y_{p,t,j,c}, \forall p, \forall t, \forall j, \forall c \tag{6} $$

Choose the vehicle: $$ x_{p,t,j,c} + 1000 \geq Cap_c*Y_{p,t,j,c}, \forall p, \forall t, \forall j, \forall c \tag{7} $$

Limited vehicle per product (not have a solution with small quantities delivered every day): $$ \sum_t \sum_j \sum_c Y_{p,t,j,c} \leq MaxVehicle_p , \forall p \tag{8} $$

I fix the value of variable $Y_{p,t,j,c}$ to zero when the station is incompatible.

$\endgroup$
9
  • $\begingroup$ It would be helpful if you detailed your lot sizing model. $\endgroup$
    – Kuifje
    Sep 2 at 9:19
  • $\begingroup$ @Kuifje I added the model $\endgroup$
    – MarcM
    Sep 2 at 10:11
  • $\begingroup$ This helps! You may have a typo, as you have two identical sets of constraints (stations constraints and one product per station at a time). $\endgroup$
    – Kuifje
    Sep 2 at 10:24
  • $\begingroup$ What are you trying to do with the "Choose the vehicle" constraint ? You want to maximize the filling rate ? $\endgroup$
    – Kuifje
    Sep 2 at 10:30
  • $\begingroup$ @Kuifje yes so I can choose vehicles without making the problem harder $\endgroup$
    – MarcM
    Sep 2 at 11:58
4
$\begingroup$

You could try and get rid of variables $Y_{p,t,j,c}$:

  • remove constraints $(6)-(7)$; constraints $(6)$ simply link $x$ and $Y$ variables, so removing them should not have any impact on the feasibility of the solution (assuming you remove $Y$ variables) ; constraints $(7)$ are not mandatory if my understanding is correct
  • replace constraints $(5)$ by $$ \sum_{p,c} x_{p,t,j,c} \le MaxCap_j \\ x_{p,t,j,c} \le Cap_c $$ This way, you are replacing $Cap_c Y_{p,t,j,c}$ by $x_{p,t,j,c}$
  • replace constraints $(8)$ by $$ \sum_{t,j,c} \frac{x_{p,t,j,c}}{Cap_c} \le MaxVehicle_p $$ $ \sum_{t,j,c} \frac{x_{p,t,j,c}}{Cap_c}$ is an approximation of the number of vehicles used for product $p$. This may need some tweaking, as ideally you would need $\sum_{t,j,c} \left\lceil \frac{x_{p,t,j,c}}{Cap_c} \right \rceil \le MaxVehicle_p$. If your vehicles are nearly full, then the approximation should not be too bad.
$\endgroup$
3
  • 2
    $\begingroup$ For a more precise replacement of (8), you could add to Kuifje's solution binary variables $y_{p,t}$ (1 if a delivery of any amount of product $p$ occurs at time $t$, a constraint $\sum_t y_{p,t} \le MaxVehicle_p \, \forall p$ to limit the number of times at which product $p$ is delivered, and constraints $\sum_{j,c} x_{p,t,j,c} \le Mandate_p y_{p,t} \, \forall p, t$ to define $y_{p,t}$. That would reduce the number of binary variables from what you had. $\endgroup$
    – prubin
    Sep 2 at 16:02
  • 1
    $\begingroup$ Great suggestion $\endgroup$
    – Kuifje
    Sep 2 at 16:06
  • $\begingroup$ I used also the suggestion of @prubin, works like a charm. Thanks! $\endgroup$
    – MarcM
    Sep 3 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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