This is a tough problem indeed, but I am not sure about the "extremely NP-hard" part :). All problems which are NP-hard are...very hard.
This looks like a multi-commodity flow problem, one commodity per depot.
It is natural to decompose such a problem as follows. For each customer $v\in V$, for each commodity $k\in K$ we assume that the demand $D_{vk}\in \mathbb{R}^+$ is known. Let $\Omega_k^v$ denote all possible paths from depot/commodity $k\in K$ to customer $v \in V$, and let $\Omega_k =\bigcup_{v \in V}\Omega_k^v$ denote the set of all paths from depot $k$.
Let $y_{p}$ be a binary variable that takes value $1$ if and only if path $p\in \Omega_k^v$ is used to satisfy the demand of customer $v\in V$ for commodity $k\in K$. Let $n_{ij} \in \mathbb{N}$ be a variable for the number of vehicles of capacity $Q$ required on edge $(i,j)\in A$, and let $c_{ij}$ denote the cost of using one vehicle on edge $(i,j)$.
You want to minimize the overall cost :
$$
\sum_{(i,j)\in A}c_{ij} n_{ij}
$$
subject to:
- Each customer $v$ must be serviced by exactly one path for each commodity:
$$
\sum_{p\in \Omega_k^v } y_{p} = 1\quad \forall v \in V, \; \forall k\in K
$$
- Capacity constraints must hold:
$$
\sum_{k \in K}\sum_{v \in V}\sum_{p\in \Omega_k^v|(i,j) \in p} D_{vk}y_{p} \le Q n_{ij}\quad \forall (i,j) \in A
$$
Note that there is an exponential number of paths in a network, so you will not be able to define the entire set $\Omega_k$. You have two options:
- Define a subset of such paths, e.g., the $b$ best ones (shortest ones) for each $(k,v)$. See how the model grows when $b$ varies, and how the quality of the solution evolves.
- Use column generation to define paths dynamically. But since you have $n_{ij}$ variables that are integer, you will need to embed this in a branch-and-bound tree. If you are not familiar with branch-and-price, I would go with option $1$. In my experience option $1$ already gives good results.
Also, note that once you solve this problem, you do not have individual routes per vehicle. You "only" have the routing of each commodity, for each customer, and the number of vehicles that are required on each edge. For individual routes per vehicle, you need to solve another problem after this one : you need to "cover" your network with routes, such that on each edge you have the required number of vehicles. And last but not least, all of this assumes that you may use multiple vehicles to send commodity $k$ to customer $v$, as you may need to transfer the commodity to another vehicle at one point (in order to minimize $n_{ij}$).
ADDENDUM
If it is assumed that commodities cannot be mixed in a same vehicle, and that each depot has its own set of vehicles, then you could simply run a classical CVRP for each depot, independently. Of course in this case you would be missing out on a lot of potential optimization, as mixing different commodities in a same vehicle could turn out to be very cost efficient.
