How to model this multi-commodity flow problem with a twist?

Question

Problem description

I am working on a variation of the multicommodity flow problem on a graph $G=(V,E)$. I have requests $r_{uv}$ for pairs of nodes $(u,v), u\in V, v\in V$, which means that $r_{uv}$ units of flow must be shipped from node $u$ to node $v$.

The variation of the problem is twofold:

1. There are capacity constraints on the edges of the graph: when the total flow on an edge $(i,j)\in E$ exceeds a given threshold $Q$, an integer variable $N_{ij}$ is incremented, so that $$ N_{ij} = \Bigg\lceil\frac{{\rm flow}_{ij}}{Q} \Bigg\rceil $$ A weighted sum of the $N_{ij}$ is minimized in the objective function. You can interpret $N_{ij}$ as vehicles with capacity $Q$, transporting units of flow.
2. Transshipment cannot be performed in some vertices of the graph. This means that in these specific vertices, a unit of flow cannot be transferred from a given vehicle to another. As an example, consider the graph below, with two requests: $1$ unit from $a$ to $c$, and $1$ unit from $a$ to $d$. Also, let $Q=2$.

                                              

If transshipment is allowed in node $b$, then the following flow is feasible, yealding $N_{ab}=1$ ($N_{ij}$ is represented by the purple squares, flows are represents by the filled triangles):

                                              

Since transshipment is allowed, all the units of flow can be packed in one vehicle on edge $(a,b)$; and then one of the two demands, $r_{ac}$ or $r_{ad}$ can be transferred to another vehicle when arriving in node $b$.

Now, if transshipment is not allowed, this is not a valid configuration, and both requests must be in individual vehicles on edge $(a,b)$, as follows:

                                              

Problem formulation

Assuming transshipment can take place at all vertices, I am currently using a columnwise formulation with a predefined set of paths $P_{uv}$ for each request $r_{uv} \in R$. So I use binary variables $y_p$ that take value $1$ if path $p \in \bigcup_{(u,v)\in R} P_{uv}$ is used, and variables $N_{ij}$ for the vehicles with capacity $Q$. As mentioned above, a weighted sum the $N_{ij}$ variables is minimized, subject to:

\begin{align*} \sum_{p\in P_{uv}}y_p &= 1 \;\;\;\;\;\; &\forall (u,v) \in R \\ \sum_{(u,v)\in R}\sum_{p\in P_{uv}|(i,j)\in p}r_{uv}y_p &\le Q N_{ij} \;\;\;\;\;\; &\forall (i,j)\in E \end{align*}

The first constraint enforces the selection of one path per request, while the second one handles capacity constraints. The way transshipment constraints are handled is explained hereafter.

A possible way of dealing with transshipment constraints

The way I currently cope with transshipment constraints is by duplicating vertices when I need to. For example, for the above example, I use the following graph:

                                              

This way, it is guaranteed that both requests are not in the same vehicle on edge $(a,b)$, and so the transshipment constraint is satisfied structurally.

My question

Is there another way to handle the transshipment constraints? I would be interested in a formulation which can handle them, so that I do not have to transform the graph. Transforming the graph does work, but sometimes it becomes very big. Also, there are many pitfalls with this approach that I can detail if necessary.

One of its weaknesses is that if there is for example a request $r_{ab}$ with path $a-b$, then this path must also be duplicated. This makes the whole process quite heavy.

I am interested in any other approach, which could simplify things.

---

More examples to illustrate the problem, and help validate answers

First example: we have two requests $r_{ad}$ and $r_{cd}$. The nodes in green are transshipment nodes, and the node in red is not. Since $b$ is a transshipment node, all requests can be packed together on edge $(b,d)$.

Another one: we have two requests $r_{ad}$ and $r_{ae}$. Although $a$ is a transshipment node, the requests cannot be merged on $(a,b)$, as it would imply splitting them downstream, where it is not possible.

And to make things harder, if we had a third request $r_{ab}$, it could be merged with either of the other two.

Another example with requests $r_{gd}, r_{ge},r_{ab}$. Although $f$ is not a transshipment node, merging the requests is possible. Requests $r_{gd}$ and $r_{ge}$ must be split in node $a$, which is a transshipment node.

The above examples illustrate that it is not trivial to determine if requests can be merged on a given edge. In particular, this does not only depend on the nature of the endpoints of the edge. And the condition may vary from one pair of requests to another. So the formulation should probably take into account some binary parameter $\delta_{p(r_1),p(r_2)}^{i,j}$ which takes value $1$ if and only if requests $r_1,r_2$ can be merged on edge $(i,j)$ if paths $p(r_1),p(r_2)$ are used ($p(r_i)$ denotes the considered path for request $r_i$).

I believe this parameter could be computed as follows: for each pair of paths $p(r_1),p(r_2)$, let $q$ be the intersection of $p(r_1)$ and $p(r_2)$. The parameter $\delta_{p(r_1),p(r_2)}^{i,j}$ is only defined over the edges of $q$, and takes value $1$ if one of the following conditions holds:

• $q = p(r_1) \subseteq p(r_2)$
• $q = p(r_2) \subseteq p(r_1)$
• $p(r_1)$ and $p(r_2)$ have the same destination node, and there is a transshipment node somewhere before $j$
• $p(r_1)$ and $p(r_2)$ have the same origin, and there is a transshipment node somewhere downstream after $i$

This list may not be complete.

Answer 1

One approach is to introduce disaggregated variables $N_{ij}^{uv}$ where needed, in addition to the original $N_{ij}$ variables. For edges $(i,j)$ where merging requests is allowed, use your original capacity constraint. For edges $(i,j)$ where merging requests is not allowed, replace your original capacity constraint with $$\sum_{p\in P_{uv}\mid (i,j)\in p} r_{uv} y_p \le Q N_{ij}^{uv}.$$