Multi-product distribution modeling : too many constraints

Question

I have received many helps to model the problem, thank's for that ! I just edited the post to make clear what my actuel problem is.

The following model is giving me amazing results with few products (5 to 10 products), but it is not working at all with largest numbers of products.

In fact there are so many constraints n1 that I can't even start a solving. With 10 vehicles, 3 factories and 100 products, we have around 50B rows for this constraint... this is never going to work.

So I think I have to model this differently... but I lack inspiration to be honest.

Problem

A company is delivering bespoke products to client from several factories. Bespoke products means that we can assimilate products and clients (a client = its product).

The products are very large product, so you can only deliver once at a time with a vehicle, but sometimes it is possible to deliver two products on the same vehicle (we'll have a matrix giving compatibilities). When we deliver two products with the same vehicle, we only pay once for the delivery, so it is cheaper.

It is possible to transfer products from a factory to another before the final delivery.

So the typical case we want our algorithm to find is : transfer a product from a factory to another if it allows to make a grouped delivery.

For example : product 1 is only possible to product in factory A, and product 2 in factory B. But both client 1 and 2 are located next to factory B. It is probably better to transfer product 1 from A to B, before making a grouped delivery.

Actual model

Indices

$ t \in T = \{ 0, 1, ..., T_f \} $ : time steps

$i \in I = \{1,2,..,n\}$ : factories

$j \in J = \{ n+1, n+2, ..., m \}$ : products ( = clients)

$k \in K = \{1,2,...p\} $ : vehicles

$s \in S = \{1,2,...s_t\}$ : product types (it is not 100% bespoke so sometimes two products are the same, but it's rare)

$V = I \bigcup J$ : nodes of the graph of the clients and factories

Decision variables

$\text{producted}_{i,j,t} \in \{0,1\} \forall i \in I, j \in J, t\in T$ : 1 if product $j$ is producted in factory $i$ at day $t$.

$\text{inventory}_{i,j,t} \in \{0,1\} \forall i \in V, j \in J, t\in T$ : 1 if product $j$ is located at $i$ at end of day $t$.

$\text{board}_{i_1,i_2,j,t,k} \in \{0,1\} \forall i_1 \in V, i_2 \in V, t\in T, j\in J, k\in, K$ : 1 if product $j$ goes from $i_1$ to $i_2$ with the vehicle $k$ during day $t$.

$\text{road}_{i_1,i_2,t,k} \in \{0,1\} \forall i_1 \in V, i_2 \in V, t\in T, k\in, K$ : 1 if vehicle goes from $i_1$ to $i_2$ during day $t$.

Objective function

$$ \sum_{k\in K} \sum_{t\in T} \sum_{i_1 \in V} \sum_{i_2 \in V} c_{i_1,i_2} \text{road}_{i_1,i_2,t,k} $$

$c_{i_1,i_2}$ is the cost of the traject $i_1$->$i_2$ for a vehicle.

** Constraints **

n1 : Compatibility between products

$$ board(i_1,i_2,j_1,t,k) + board(i_1,i_2,j_2,t,k) \leq 1 + m[j_1][j_2] $$ $$\forall i_1,i_2 \in V^2, \forall j_1,j_2 \in J^2, \forall t \in T, \forall k \in K $$ (only applied when $m[j_1][j_2] = 0$

n2 : each product is only produced one

$$ \sum_{i} \sum_{t} \text{producted}_{i,j,t} = 1, \forall j \in J $$

n3 : just to avoid strange behaviour

$$ \text{road}_{i,i,t,k} = 0, \forall i \in V, t \in T, k \in K $$

n4 : a product can only be transported by a vehicle

$$ \text{board}_{i_1,i_2,j,t,k} \leq \text{road}_{i_1,i_2,t,k}, \forall (i_1,i_2) \in V^2, j \in J, t \in T, k \in K $$

n5 : a product can only be producted in some factories

$$ \text{producted}_{i,j,t} \leq p[i][j], \forall i \in I, j \in J, t \in T $$ where $p[i][j] = 1$ if factory $i$ can produce product $j$.

n6 : inventory formula (simplified)

$$ \text{inventory}_{i,j,t} = \text{inventory}_{i,j,t-1} \sum_{k \in K} \sum_{i2 \in V} \text{board}_{i2,i,j,t,k} - \sum_{k \in K} \sum_{i2 \in V} \text{board}_{i,i2,j,t,k} + producted{i,j,t-1}, \forall t \in T, i \in I $$

7n: only factories can have stocks at the end of day

$$ \text{inventory}_{i,j,t} = 0, \forall i \in J, \forall j in J-\{I\} \forall t \in T$$

Thank's for the help !

Answer 1

I assume from the question that a vehicle can visit at most one node in a given time period. Without writing out the full model (which is pretty gory), I would start with the following variables: how much of each product is produced at each factory in each period (with upper bound zero if the factory cannot produce that product); inventory of each product at each factory at the end of each period; inventory of each product on each vehicle at the end of each period; indicators for whether a vehicle travels each arc in each period; unsatisfied demand for each product at each client at the end of each period; and delivery quantity for each product at each client in each period. (If each client demands only a single product, some of those variables can be zeroed out.)

For constraints, the inventory of any product at any factory at the end of any period is the sum of the starting inventory, the production in that period and the inventory of that product on all arriving vehicles minus the sum of the inventory of that product on all departing vehicles. At clients, the unsatisfied demand for any product at the end of any period is the unsatisfied demand at the start of the period minus the amount delivered (and must be zero by the end of the required delivery date), and the amount delivered is the difference between the inventory of the product on all arriving vehicles in the previous period and the inventory on all departing vehicles in the current period. You may also have capacity constraints on the vehicles.

The objective function unchanged from what you have.

The key idea is to introduce inventory levels, which will allow for accumulation and depletion of stocks at factories. It also opens the door to the possibility of adding inventory holding costs to the objective function (if storage is not free).

Answer 2

I have suggestions for your two recently added constraints.

Your first one is: $$\text{board}(i_1,i_2,j_1,t,k) + \text{board}(i_1,i_2,j_2,t,k) \leq 1 + m[j_1][j_2]\\\forall i_1,i_2 \in V^2, \forall j_1,j_2 \in J^2, \forall t \in T, \forall k \in K \tag1$$

You do not need to impose $(1)$ when $m[j_1][j_2] = 1$ because it is redundant. You can also restrict to $j_1 < j_2$. When $m[j_1][j_2] = 0$, you might also consider generating these constraints dynamically only when they are violated.

Your second one is: $$ \text{board}(i_1,i_2,j,t,k) \leq \text{road}(i_1,i_2,t,k) \\ \forall i_1,i_2 \in V^2, \forall j \in J, \forall t \in T, \forall k \in K \tag2$$

But $(2)$ is already implied by your existing constraints: $$ \sum_{j\in J} \text{board}(i_1,i_2,j,t,k) \leq \text{road}(i_1,i_2,t,k) \\ \forall i_1,i_2 \in V^2, \forall t \in T, \forall k \in K$$ So you can omit $(2)$.