How to avoid discontinuous path?

Question

I have a mid-size two sided network, and am just trying to run a simple routing. $x_{i,j}^d$ takes a value of one if $d$ travel from $i$ to $j$. Each driver starts from origins $s_d$ and finishes at $e_d$. This is my simple routing:

$\sum_{j} x_{s_d,j}^d = 1 \qquad \forall d$

$\sum_{i} x_{i,e_d}^d = 1 \qquad \forall d$

$\sum_{i} x_{i,j}^d = \sum_{k} x_{j,k}^d \qquad \forall d , \forall j \ne {s_d,e_d}$

The issue I'm facing is that my network is two sided (i.e. if we have $(i,j)$ then we do have $(j,i)$. And this cause an issue of seeing all routes ended up just exiting and entering origins and exiting and entering destination. This way the model actually satisfies all the above constraints without even actually traveling from $s_d$ to $e_d$. What's the issue? And how can I fix it?

Answer 1

To eliminate such 2-cycles, you can impose additional constraints $$x_{ij}^d+x_{ji}^d\le 1.$$ To eliminate longer subtours, look up generalized subtour elimination constraints.

Answer 2

If the driver start node $s_d$ and end node $e_d$ are always different, then you can disallow entry into the start node ($x^d_{j,s_d}=0\ \forall j$) and exit from the end node ($x^d_{e_d, j}=0\ \forall j$).

If arcs have positive transit costs, and if you are minimizing cost, subtours should not be a problem (they would just add unnecessarily to costs).

Answer 3

In general to avoid 2-sided network you can try something like
$x_{i,j}^d+ x_{j,i}^d = 0$
followed by your last flow balance/even degree constraint.