Opening book details…
Can I read An Iterated Local Search Algorithm for the Vehicle Routing Problem with Convex Time Penalty Functions on EtoBox?
An Iterated Local Search Algorithm for the Vehicle Routing Problem with Convex Time Penalty Functions by Toshihide Ibaraki; Shinji Imahori; Koji Nonobe; Kensuke Sobue; Takeaki Uno; Mutsunori Yagiura is a Computer Science article available to read on EtoBox.
What is An Iterated Local Search Algorithm for the Vehicle Routing Problem with Convex Time Penalty Functions about?
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.
Who reads An Iterated Local Search Algorithm for the Vehicle Routing Problem with Convex Time Penalty Functions?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Toshihide Ibaraki; Shinji Imahori; Koji Nonobe; Kensuke Sobue; Takeaki Uno; Mutsunori Yagiura
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0166-218X)
- Published
- 2008
- Language
- EN
- Field
- Computer Science (Physical Sciences)