Effective local search algorithms for routing and scheduling problems with general time-window constraints
Effective local search algorithms for routing and scheduling problems with general time-window constraints
复制标题
DOI：
10.1287/trsc.1030.0085
复制
发表时间：
2005-05-01
影响因子：
4.6
通讯作者：
Yagiura, M
中科院分区：
文献类型：
--
作者：
Ibaraki, T;Imahori, S;Yagiura, M
我们提出了用于具有软时间窗口约束的车辆路径问题的局部搜索算法。每个客户的时间窗口约束被视为惩罚函数，这是非常通用的，因为只要它是分段线性的，它就可以是非凸且不连续的。在我们的算法中，我们使用本地搜索将客户分配给车辆并查找车辆访问的客户订单。除了车辆路径问题的标准邻域之外，我们的算法还采用了一种高级邻域，称为循环交换邻域。在确定了客户的车辆拜访顺序后，我们必须确定在客户处处理的最佳开始时间，以使总损失最小化。我们证明这个问题可以通过使用动态规划来有效解决，然后将其合并到我们的算法中。我们报告车辆路径问题的各种基准实例的计算结果。时间窗口约束的通用性使我们能够处理各种各样的调度问题。作为示例，我们在本文中提到了具有库存成本的生产调度问题的应用，并报告了实际实例的计算结果。
W e propose local search algorithms for the vehicle routing problem with soft time-window constraints. The time-window constraint for each customer is treated as a penalty function, which is very general in the sense that it can be nonconvex and discontinuous as long as it is piecewise linear. In our algorithm, we use local search to assign customers to vehicles and to find orders of customers for vehicles to visit. Our algorithm employs an advanced neighborhood, called the cyclic-exchange neighborhood, in addition to standard neighborhoods for the vehicle routing problem. After fixing the order of customers for a vehicle to visit, we must determine the optimal start times of processing at customers so that the total penalty is minimized. We show that this problem can be efficiently solved by using dynamic programming, which is then incorporated in our algorithm. We report computational results for various benchmark instances of the vehicle routing problem. The generality of time-window constraints allows us to handle a wide variety of scheduling problems. As an example, we mention in this paper an application to a production scheduling problem with inventory cost, and report computational results for real-world instances.