An iterated local search algorithm for the vehicle routing problem with convex time penalty functions
An iterated local search algorithm for the vehicle routing problem with convex time penalty functions
复制标题
DOI：
10.1016/j.dam.2007.04.022
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
T. Ibaraki;S. Imahori;K. Nonobe;Kensuke Sobue;T. Uno;M. Yagiura
中科院分区：
文献类型：
--
作者：
T. Ibaraki;S. Imahori;K. Nonobe;Kensuke Sobue;T. Uno;M. Yagiura
提出了一种求解时间窗约束车辆路径问题的迭代局部搜索算法。我们将每个客户的时间窗约束作为惩罚函数，并假设它是凸的和分段线性的。在给定每辆车要访问的客户顺序的情况下，使用动态规划(DP)来确定服务客户的最优启动时间，从而使总时间损失最小。然后，将该DP算法结合到迭代局部搜索算法中，以有效地评估各个邻域中的解。评估邻域中的解的摊销时间复杂性是输入大小的对数阶(即，定义惩罚函数的线性段的总数)。在1000个客户的基准实例上的计算结果表明，该方法是非常有效的，尤其是对于大型实例。
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.