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'$.

$\endgroup$
  • $\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 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 at 11:00
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$
  • $\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 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 at 22:23
  • $\begingroup$ Lol, ok, no worries! Thank you anyway :) $\endgroup$ – Martim Joyce-Moniz Feb 5 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 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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