12
$\begingroup$

I was wondering if someone has come across this before and/or has a smart idea for the following:

I have a directed graph $G$ with costs $c$ associated with the arcs, and I know the shortest path $P^G_{st} = \{s,\dots,i,j,\dots,t\}$ in $G$ between nodes $s$ and $t$. Is there an efficient way to determine the shortest path between $s$ and $t$ in graph $G'$, which is equal to $G$ with the exception of the cost of a single arc $(i,j)$ in $P^G_{st}$ that is now $c'_{ij} = c_{ij} + \alpha, \alpha > 0$? By "efficient" I mean something better than re-calculating from scratch the complete shortest path in $G'$.

Improve this question
$\endgroup$
2
  • $\begingroup$ This problem looks like NP-complete, it might be possible that there is no polynomial-time solution for this problem. $\endgroup$
    – ooo
    Feb 4, 2020 at 10:49
  • 1
    $\begingroup$ So what you are looking for is sensitivity analysis. There are many papers that tackle this, including without linear programming. See for example researchgate.net/publication/… $\endgroup$
    – Kuifje
    Feb 4, 2020 at 11:00

1 Answer 1

Reset to default
8
$\begingroup$

In DP Bertsekas Network Optimization (that can be downloaded for free) there's an exercise at Page 104 (Finding an initial price vector) where you can find a method for solving shortest paths in dynamic graphs. Basically, it resorts to using the price vectors from the first iteration to warm start the method at the second. Many years ago I implemented that method to solve dynamic shortest paths on road problems under congestion. We used the price vectors given by the nominal speeds (in the absence of congestion) as starting price vectors. We saw that in a scenario of low or very local congestion, this warm start provided substantial speedups over the traditional approach of solving the SPP from scratch every time.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! I think this may be what I am looking for. Also, is your work on the road problems under congestion published somewhere? $\endgroup$
    – Martim Joyce-Moniz
    Feb 4, 2020 at 15:12
  • $\begingroup$ It is in a working paper status ever since :-). My coauthor and I never took the time to wrap this up and eventually followed different paths and left it unfinished. $\endgroup$
    – Claudio Contardo
    Feb 4, 2020 at 22:23
  • $\begingroup$ Lol, ok, no worries! Thank you anyway :) $\endgroup$
    – Martim Joyce-Moniz
    Feb 5, 2020 at 15:31
  • $\begingroup$ I have also used warm start in a column generation setting with success. The problem with the added column is very similar to the problem at the previous step. Warm starting speeds up things significantly. $\endgroup$
    – nimcap
    Feb 10, 2020 at 21:18

Your Answer

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

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