Vehicle routing problems with varying degrees of dynamism
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