Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2007-013 (June 30, 2007)
An Iterated Local Search Algorithm for the Time-Dependent Vehicle Routing Problem with Time Windows
by Hideki Hashimoto, Mutsunori Yagiura, Toshihide Ibaraki
We generalize the standard vehicle routing problem with time windows
by allowing both traveling times and traveling costs to be time-dependent functions.
In our algorithm, we use a local search to determine routes of the vehicles.
When we evaluate a neighborhood solution,
we must compute an optimal time schedule of each route.
We show that
this subproblem can be efficiently solved by dynamic programming,
which is incorporated in the local search algorithm.
The neighborhood of our local search consists of slight modifications of the standard neighborhoods
called 2-opt$^*$, cross exchange and Or-opt.
We propose an algorithm that evaluates
solutions in these neighborhoods more efficiently
than computing the dynamic programming from scratch
by utilizing the information from the past dynamic programming recursion used to
evaluate
the current solution.
We further propose a filtering method that restricts the search space in the
neighborhoods
to avoid many solutions having no prospect of improvement.
We then develop an iterated local search algorithm
that incorporates all the above ingredients.
Finally we report computational results
of our iterated local search algorithm compared against existing methods,
and confirm the effectiveness of the restriction of the neighborhoods
and
the benefits of the proposed generalization.