6
$\begingroup$

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

                                               enter image description here

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

                                               enter image description here

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:

                                               enter image description here

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:

                                               enter image description here

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

enter image description here

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.

enter image description here

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

enter image description here

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.

enter image description here

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Thanks RobPratt for your precious input! This essentially separates each request on the edges where necessary, if I understand correctly, which is great. But what if somewhere upstream there is a node where transshipment is allowed ? Wouldn't the constraint be too restrictive ? I will add an example in the question. $\endgroup$ – Kuifje May 21 at 13:22
  • $\begingroup$ I don't see why my suggestion would be too restrictive, but I modified my answer to disaggregate only where needed. $\endgroup$ – RobPratt May 21 at 13:48
  • $\begingroup$ I added an example in the question where appears a difficulty: how do you know if merging is allowed on a given edge $(i,j)$ ? In the last example, although $a$ is a transshipment node, merging is not possible on $(a,b)$, as it would imply splitting the requests downstream, which is not possible. $\endgroup$ – Kuifje May 21 at 14:29
  • $\begingroup$ But if we had a third request $r_{ab}$, it could be merged with either of the other two. $\endgroup$ – Kuifje May 21 at 14:38
  • $\begingroup$ Do you maybe want to enforce $\sum_j N_{ji}^{uv}=\sum_j N_{ij}^{uv}$ if $i$ is not a transshipment node and $i \not\in\{u,v\}$? $\endgroup$ – RobPratt May 21 at 16:27

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.