Paper Info
Title
An iterated local search algorithm for the vehicle routing problem with convex time penalty functions
Abstract
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.
Year
DOI
Venue
2008
10.1016/j.dam.2007.04.022
Discrete Applied Mathematics
Keywords
Field
DocType
vehicle routing problem with time windows,total number,optimal start time,metaheuristics,time window constraint,dynamic programming,logarithmic order,iterated local search algorithm,penalty function,amortized time complexity,total time penalty,linear piece,convex time penalty function,dp algorithm,iterated local search,time complexity,piecewise linear
Combinatorics,Vehicle routing problem,Mathematical optimization,Search algorithm,Amortized analysis,Algorithm,Time complexity,Piecewise linear function,Mathematics,Iterated local search,Metaheuristic,Penalty method
Journal
Volume
Issue
ISSN
156
11
Discrete Applied Mathematics
Citations 
PageRank 
References 
41
1.44
19
Authors
6
Name
Order
Citations
PageRank
Toshihide Ibaraki12593385.64
Shinji Imahori219015.31
Koji Nonobe31367.70
Kensuke Sobue4411.44
Takeaki Uno51319107.99
Mutsunori Yagiura661446.59