The vehicle routing problem with flexible time windows and traveling times
The vehicle routing problem with flexible time windows and traveling times
复制标题
DOI：
10.1016/j.dam.2006.04.009
复制
发表时间：
2006-11
期刊：
影响因子：
--
通讯作者：
H. Hashimoto;T. Ibaraki;S. Imahori;M. Yagiura
中科院分区：
文献类型：
--
作者：
H. Hashimoto;T. Ibaraki;S. Imahori;M. Yagiura
我们推广了标准的车辆路径问题，允许软时间窗和软行驶时间的限制，这两个约束被视为成本函数。随着建议的推广，问题变得非常普遍。在我们的算法中，我们使用局部搜索来确定车辆的路线。在确定每辆车的路线后，我们必须确定在访问客户时服务的最佳开始时间。我们表明，这个子问题是NP-困难的成本函数是一般的，但可以有效地解决与动态规划时，旅行时间成本函数是凸的，即使时间窗口成本函数是非凸的。我们处理后者的情况下，在开发的迭代局部搜索算法。最后，我们报告的基准实例的计算结果，并确认所提出的推广的好处。
We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general. In our algorithm, we use local search to determine the routes of vehicles. After fixing the route of each vehicle, we must determine the optimal start times of services at visited customers. We show that this subproblem is NP-hard when cost functions are general, but can be efficiently solved with dynamic programming when traveling time cost functions are convex even if time window cost functions are non-convex. We deal with the latter situation in the developed iterated local search algorithm. Finally we report computational results on benchmark instances, and confirm the benefits of the proposed generalization.