4
$\begingroup$

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 !

$\endgroup$
23
  • $\begingroup$ Your images suggest the equations were typeset using LaTeX. You can enter LaTeX code directly on this site (using single or double dollar signs as delimiters). $\endgroup$
    – prubin
    Aug 6 at 16:15
  • $\begingroup$ thank's for the tips ! It must be way easier to read now :) $\endgroup$
    – Pierre Ftn
    Aug 6 at 16:44
  • $\begingroup$ I edited your objective function -- you did not have the vehicle index in it. $\endgroup$
    – prubin
    Aug 6 at 19:38
  • $\begingroup$ You mention "stores" and "factories" (which I assume are the same), and you mention transferring product between factories. If a product is transferred from factory 1 to factory 2, must it immediately go on another vehicle, or can it sit at factory 2 until the optimization gods decide it is time to move it ahead? $\endgroup$
    – prubin
    Aug 6 at 19:41
  • $\begingroup$ Thanks for the edit ! $\endgroup$
    – Pierre Ftn
    Aug 7 at 0:32
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ "I assume from the question that a vehicle can visit at most one node in a given time period." It's not necessary! In fact a vehicle will be allowed to have maximum two products on board. It will be used in France and... it's a small country. So delivering in one day is not a problem! So let's say there is no restriction about the distance made in one day. I haven't thought about any inventory variable because each product is unique. It is custom made product. That's why I assimilated a product with its client. Do you think it still is the best solution to introduce inventory? I will test that $\endgroup$
    – Pierre Ftn
    Aug 7 at 22:13
  • $\begingroup$ (1) Can a vehicle make more than one trip in a day, meaning starting point -> factory -> customer -> other customer -> factory (same or different) -> third customer - > fourth customer (or more)? (2) Do the same vehicles also handle moving product from one factory to another factory? (2a) If so, what is the advantage of taking a product to a factory v. taking it straight to the customer (given that distance is unrestricted)? $\endgroup$
    – prubin
    Aug 8 at 20:13
  • $\begingroup$ Yes a vehicle can do deliver several clients on one day (we can fix a limit for example 1000km/d). He can also move a product from a factory to another. He can also do both at the same time. For example deliver a product to a client, and another one in a factory. $\endgroup$
    – Pierre Ftn
    Aug 8 at 22:32
  • $\begingroup$ Let's imagine the following problem : Factory A can produce product 1 and factory B can produce product 2. But both client for product 1 and 2 are located next to factory B. It can be cheaper to transfer product 1 from Factory A to Factory B, then make a grouped delivery of both products (second vehicle doing Factory B --> Client 1 --> Client2, which is efficient if Client 1 and Client 2 are close) $\endgroup$
    – Pierre Ftn
    Aug 8 at 22:36
  • $\begingroup$ I just edited my initial message with an image for a better understanding. I've used real cities and distances on the graph to explain why it can be cheaper to transfer products from factories. $\endgroup$
    – Pierre Ftn
    Aug 8 at 22:47
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank's for the answer ! For (1) indeed restricting j1 < j2 is good idea, I was already doing that in the code actually ! I deleted when m[j1][j2] = 1 since you are right on the fact that it is redundant. Unfortunately m matrix is very sparse so it doesn't speed up a lot. For (2) I deleted the precedent constraint that you mention (that was false, because several products can be in a single vehicle). Sorry for forgetting to edit the original post, I do it now ! $\endgroup$
    – Pierre Ftn
    Aug 24 at 20:31

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.