Insertion Heuristics for a Class of Dynamic Vehicle Routing Problems

We consider a simple family of dynamic vehicle routing problems, in which we have a fixed fleet of identical vehicles, and customer requests arrive during the route-planning process. For this kind of problem, it is natural to use an insertion heuristic. We test several such heuristics computationally, on two different variants of the problem. It turns out that a parallel heuristic, based on a certain “sum-of-squares” insertion criterion, significantly outperforms the others.

Citation

Working paper, STOR-i Centre for Doctoral Training, Lancaster University, UK

Article

Download

View Insertion Heuristics for a Class of Dynamic Vehicle Routing Problems