Vehicle routing problems with varying degrees of dynamism

Karsten Lund / Section for Operations Analysis

Abstract

In a Dynamic Vehicle Routing Problem, DVRP, vehicles are dispatched to satisfy service requests, that evolve in real-time, opposed to the classical static vehicle routing problem where the initial input is assumed not to change afterwards. Examples of such dynamic routing problems are taxi services or delivery of oil to private customers. Traditionally the solution of such dynamic problems has been based on adaptions of static procedures; a static vehicle routing problem is solved, each time an input update has occurred. We show, by using a simulator, that such an approach is only appropriate in situations where the ``Degree of dynamism'', defined as how much input of a problems changes over time, is very weak. As the degree of dynamism increases, we show that a static algorithm is not capable handling the input updates and gives ``suboptimal'' solutions.

IMM Technical Report 1/96