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.
Working paper, STOR-i Centre for Doctoral Training, Lancaster University, UK