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

Question

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 '20 at 00:11

score 6 · Accepted Answer · edited Jan 23 '20 at 13:50

6

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.

edited Jan 23 '20 at 13:50

ə̷̶̸͇̘̜́̍͗̂̄︣͟

5,412
5
22
55

answered Jan 23 '20 at 09:47

Marco Lübbecke

5,919
22
64

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

score 6 · Answer 2 · answered Jan 23 '20 at 12:47

6

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.

answered Jan 23 '20 at 12:47

Simon Spoorendonk

136
5

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

2 Answers2

Linked