Lot-sizing problem variant

Question

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.

Answer 1

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.