<p>The problem is known as the <strong>Canadian Traveler Problem</strong>. </p>

CC BY-SA 3.0
2014-01-30T05:43:29.107Z
2014-01-30T05:43:29.107Z
Bangye
<p>The problem is also knwon and heavily studied as <strong>Dynamic Vehicle Routing Problem</strong> (or <em>On-line vehicle routing problem</em>):</p>

<p>It differs from the static counterpart because:</p>

<ol>
<li><p>Not all information relevant to the planning of the routes is known by the planner when the routing process begins;</p></li>
<li><p>Information can change after the initial routes have been constructed.</p></li>
</ol>

<p>You can take a look to: </p>

<ul>
<li><p>Victor Pillaca, Michel Gendreauc, Christelle Guéreta, Andrés L. Medaglia, <a href="http://www.sciencedirect.com/science/article/pii/S0377221712006388" rel="nofollow">A review of dynamic vehicle routing problems</a>, (2011);</p></li>
<li><p>Victor Pillaca, Christelle Guéreta, Andrés L. Medaglia, <a href="http://hal.archives-ouvertes.fr/docs/00/62/34/74/PDF/Pillac2010_-_Dynamic_vehicle_routing_problems_-_state_of_the_art_and_prospects.pdf" rel="nofollow">Dynamic Vehicle Routing Problems: State of the art and Prospects</a>, (2010);</p></li>
<li><p>Allan Larsen's thesis: <a href="http://orbit.dtu.dk/fedora/objects/orbit:83345/datastreams/file_5261816/content" rel="nofollow">The Dynamic Vehicle Routing Problem</a>, with some real-world applications;</p></li>
</ul>

CC BY-SA 3.0
2014-01-30T08:06:32.963Z
2014-01-30T08:19:09.573Z
2014-01-30T08:19:09.573Z
Marzio De Biasi
<p>I'm working on a path finding algorithm for my thesis and I've gotten to a problem I need to solve where agents can replan their path if they need/have to. For example, if an agent is traversing across a corridor and then a barrier is inserted in, the agent has to replan because his old path is invalid. Another case is if the barrier already exists and the agent has to take a longer route, but while traveling, the barrier is removed and a significantly shorter route becomes available so the agent may replan but can still continue on his old path.</p>

<p>I have some ideas on how to work on the first case, but I'm at a loss for where to start for the second case. Does anyone know how other path planning algorithms deal with replanning, or can point me to any resources that can help me find some direction in tackling this problem?</p>

<ds.algorithms><graph-theory><graph-algorithms>
Path replanning in path finding algorithms
zaloo
# Path replanning in path finding algorithms

(Asked by: username_0 on 2014-01-30)

I'm working on a path finding algorithm for my thesis and I've gotten to a problem I need to solve where agents can replan their path if they need/have to. For example, if an agent is traversing across a corridor and then a barrier is inserted in, the agent has to replan because his old path is invalid. Another case is if the barrier already exists and the agent has to take a longer route, but while traveling, the barrier is removed and a significantly shorter route becomes available so the agent may replan but can still continue on his old path.

I have some ideas on how to work on the first case, but I'm at a loss for where to start for the second case. Does anyone know how other path planning algorithms deal with replanning, or can point me to any resources that can help me find some direction in tackling this problem?

**Tags:** ds.algorithms, graph-theory, graph-algorithms


---

## 2 answers

### Answer by username_1 on 2014-01-30. Score: 3 | Accepted answer

The problem is known as the **Canadian Traveler Problem**.


---

### Answer by username_2 on 2014-01-30. Score: 3

The problem is also knwon and heavily studied as **Dynamic Vehicle Routing Problem** (or *On-line vehicle routing problem*):

It differs from the static counterpart because:

1. Not all information relevant to the planning of the routes is known by the planner when the routing process begins;
2. Information can change after the initial routes have been constructed.

You can take a look to:

* Victor Pillaca, Michel Gendreauc, Christelle Guéreta, Andrés L. Medaglia, [A review of dynamic vehicle routing problems](http://www.sciencedirect.com/science/article/pii/S0377221712006388), (2011);
* Victor Pillaca, Christelle Guéreta, Andrés L. Medaglia, [Dynamic Vehicle Routing Problems: State of the art and Prospects](http://hal.archives-ouvertes.fr/docs/00/62/34/74/PDF/Pillac2010_-_Dynamic_vehicle_routing_problems_-_state_of_the_art_and_prospects.pdf), (2010);
* Allan Larsen's thesis: [The Dynamic Vehicle Routing Problem](http://orbit.dtu.dk/fedora/objects/orbit:83345/datastreams/file_5261816/content), with some real-world applications;


---

