8
$\begingroup$

Given a city map (a graph) $G$,

$b_{i,j}$ is a Boolean variable for whether or not edge $i$,$j$ is allocated, $d_{i,j}$ denotes the distance between $i$,$j$.

The objective is to move from $s$ to $e$ in minimum time. (I am trying an add intermediate stop point with a time limit)

$$\sum_{i,j} b_{i,j} \times d_{i,j}$$

The journey starts from $s$ and ends at $e$.

$$\sum_{i} b_{i,s} - \sum_{k} b_{s,k} = -1$$

The above equation ensures no incoming edges at $s$, i.e., exactly one edge leaves the starting point.

$$\sum_{i} b_{i,j} - \sum_{k} b_{j,k} = 0$$

The above equation ensures the equal number of edges going in and out, i.e., flow conservation.

$$\sum_{i} b_{i,e} - \sum_{k} b_{e,k} = 1$$

The above equation ensures no outgoing edges at $e$, i.e., exactly one edge enters the target node.

To calculate the time at $e$ I can use:

$$\text{time}_{e} = \frac{\sum_{i,j} b_{i,j} \times d_{i,j}}{\text{speed}} + \text{time}_{s}$$

But how can I force the solver to take an intermediate node $j$ forcefully into its path with time limit constraint, i.e., time-bound to reach there?

For example if there is a path from $i$ to $j$ then:

\begin{align}\text{time}_j &= \sum_{i} b_{i,j} \times \left( \frac{d_{i,j}}{\text{speed}} + \text{time}_i\right)\\\text{time}_j &\leq c\end{align} where $c$ is a constant value.

But the solver doesn't accept the above formulation.

$\endgroup$
2
  • $\begingroup$ Are you requiring the path to be acyclic? If not, the problem gets more complicated, in that I think you will need to keep track of whether $b_{i,j}=1$ means you move from $i$ to $j$ the first time you leave $i$, the second time you leave $i$, both the first and second times, ... $\endgroup$
    – prubin
    Jan 23, 2020 at 0:11
  • $\begingroup$ yes i will add that condition, paths are acyclic. $\endgroup$
    – ooo
    Jan 23, 2020 at 3:35

2 Answers 2

6
$\begingroup$

Your update of the $\text{time}_j$ variable results in a non-linear equation.

The propagation of the time value along an edge is like $$b_{i,j} = 1 \implies \text{time}_i + \frac{d_{i,j}}{\text{speed}} \leq \text{time}_j$$ and you can linearize it like $$\text{time}_i + \frac{d_{i,j}}{\text{speed}} \leq \text{time}_j + M(1-b_{i,j})$$ with a "large" constant $M$. Ugly, I know, but it should work. $M$ can be an upper bound on the latest arrival time in the target node.

In order to force the flow/path to visit a certain node, you put a special flow conservation constraint to that node just like you do for the start/target node of the path: enforce that one unit of flow leaves that node you wish to visit (see Simon's answer).

A note on elementarity: You get this "for free" when $d_{i,j}>0$ what I assume to be true in this case.

$\endgroup$
5
  • $\begingroup$ Actually this was the main problem But how can I force the solver to take an intermediate node j forcefully into its path with time limit constraint, i.e., time-bound to reach there? $\endgroup$
    – ooo
    Jan 23, 2020 at 12:35
  • $\begingroup$ I edited my post, you need another flow conversation constraint for that node that enforces to enter or leave it. $\endgroup$ Jan 23, 2020 at 12:40
  • $\begingroup$ Now it can cause sub tour problem $\endgroup$
    – ooo
    Jan 23, 2020 at 13:00
  • $\begingroup$ the "increasing time" along each (sub)path forbids the subtours $\endgroup$ Jan 23, 2020 at 13:02
  • $\begingroup$ Ok, I will try that actually this is what I wanted. $\endgroup$
    – ooo
    Jan 23, 2020 at 13:04
6
$\begingroup$

Adding to Marco's answer on enforcing a visit to a node.

For enforcing a visit to node $j$ you can add either

$$\sum_{i} b_{i,j} = 1$$

or

$$ \sum_{k} b_{j,k} = 1$$

to your model.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.