# Bounding arrival time at a node in a resource-constrained shortest path problem

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.

• 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, ...
– prubin
Jan 23, 2020 at 0:11
• yes i will add that condition, paths are acyclic.
– ooo
Jan 23, 2020 at 3:35

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.

• 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?
– ooo
Jan 23, 2020 at 12:35
• I edited my post, you need another flow conversation constraint for that node that enforces to enter or leave it. Jan 23, 2020 at 12:40
• Now it can cause sub tour problem
– ooo
Jan 23, 2020 at 13:00
• the "increasing time" along each (sub)path forbids the subtours Jan 23, 2020 at 13:02
• Ok, I will try that actually this is what I wanted.
– ooo
Jan 23, 2020 at 13:04

For enforcing a visit to node $$j$$ you can add either
$$\sum_{i} b_{i,j} = 1$$
$$\sum_{k} b_{j,k} = 1$$