Two-commodity flow formulation for an asymmetric cost VRP

Question

The two-commodity flow formulation is introduced by Baldacci et al. (2004). It is known for its good performance and providing a tight lower bound. I searched the literature, but couldn't find any study that expands this formulation on asymmetric digraphs. Do you think it is possible to expand this formulation on asymmetric digraphs? If not, why? If yes, do you know a study that did this already?

Answer 1

One way to do this is as follows: for each edge $(i,j)$ introduce binary variables $z_{ij}$ and $z_{ji}$ that indicate whether a vehicle travels from $i$ to $j$ or from $j$ to $i$, and add the constraint $z_{ij} + z_{ji} \le 1$.

Now $z_{ij} + z_{ji}$ is equal to 1 if edge $(i,j)$ is used in the solution and equal to 0 if edge $(i,j)$ is not used. You can now simply replace $\xi_{ij}$ by $z_{ij} + z_{ji}$. This follows from the fact that capacity is symmetric: it does not matter in which direction you travel, the load remains the same.

The above approach is explained in more detail in a paper of mine. I am not claiming that this is the only way or the best way to use this formulation in an asymmetric setting.