An EBM Based Dynamic Vehicle Routing Algorithm

Improving the efficiency of dynamic vehicle routing problem on large scale road network is a difficult problem. There are numerous works proposed on this problem, they try to solve the problem from different aspects. In this paper, we propose a novel method-ellipse bounding method (EBM) based dynamic vehicle routing algorithm, which maintains dynamic ellipses to prune its searching branches while routing. We combine our method with the A* algorithm as an example in the experiment. The experiment result shows that our method can narrow the searching area for A* and is much more efficient than other pruning methods with A*.