Linear Programming for suppliers grouping

Question

I have a set of suppliers each one with a set of products to be picked up with a certain quantity. The objective is to know what suppliers to group with each other in order to minimize the distance traveled by the truck between suppliers. I am trying to model this as a mixed linear program where $x_{ij}=1$ if the supplier $i$ is assigned to the truck $j$. but the issue is that I don't know in advance the number of trucks to be used. My question: is there a classical model for this problem or a closer one to adapt? The VRP suppose that the number of trucks is known and optimizes the distance.

Answer 1

One way is to use graph type transport model like $ G = (V,E)$ where $V$ is the set of suppliers
indexed by $i$ and $E$ is set of routes/edges between the suppliers $ (i,j)$
Two sets of variables
Binary $ x_{i,j} = 1$ if edge $ (i,j)$ is selected by trucks $t_{i,j} $.
and $ t$ being a nonnegative integer, similar to a flow between suppliers using an edge.
Then some of familiar constraints that you'd use for graph type model
$ x_{i,j} \le t_{i,j} \le Tx_{i,j}$
where $T$ could be some big enough number like an estimate of max number of trucks used.

Another approach or you can say phase 2 of the model is once $T$ total/minimum number of trucks driving along edges is known then you can remodel with each truck from $1$ to $T$ as binary $t_{ij}$

Answer 2

If you do not have a specified number of trucks, you can build the MIP model under the assumption that the number of trucks equals the number of customers. You definitely will not need more trucks than customers (unless trucks have capacity limits and individual customers can provide loads larger than the capacity of a single truck). If the optimal solution does not require that many trucks, some trucks will receive no assignments and will travel zero distance.