An Iterated Local Search Algorithm
for the Time-Dependent Vehicle Routing Problem with Time Windows
H. Hashimoto, M. Yagiura and T. 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.
5 (2008) 434-456.
Draft version is available as
Technical Report 2007-013,
Department of Applied Mathematics and Physics,
Graduate School of Informatics,
the AMP site.
Detailed computational results:
Back to the Paper List