An Iterated Local Search Algorithm for the Vehicle Routing
Problem with Convex Time Penalty Functions
T. Ibaraki, S. Imahori, K. Nonobe, K. Sobue, T. Uno and M. Yagiura
We propose an iterated local search algorithm
for the vehicle routing problem with time window constraints.
We treat the time window constraint for each customer as a penalty
function, and assume that it is convex and piecewise linear.
Given an order of customers each vehicle to visit,
dynamic programming (DP) is used to determine the optimal start time
to serve the customers so that the total time penalty is minimized.
This DP algorithm is then incorporated in the iterated local search
algorithm to efficiently evaluate solutions in various neighborhoods.
The amortized time complexity of evaluating a solution in the neighborhoods
is a logarithmic order of the input size (i.e., the total number
of linear pieces that define the penalty functions).
Computational comparisons on benchmark instances with up to 1000
customers show that the proposed method is quite effective,
especially for large instances.
Vehicle routing problem with time windows, metaheuristics, dynamic programming.
Discrete Applied Mathematics,
156 (2008) 2050-2069.
(Technical report version (METR 2006-36) is available at
the METR site.)
Detailed computational results:
PS file ,
Back to the Paper List