The mixed capacitated general routing problem with turn penalties
The mixed capacitated general routing problem with turn penalties
复制标题
DOI：
10.1016/j.eswa.2011.04.092
复制
发表时间：
2011-09-15
影响因子：
8.5
通讯作者：
Soler, David
中科院分区：
文献类型：
--
作者：
Braysy, Olli;Martinez, Eulalia;Soler, David
在本文中，我们处理具有转弯惩罚的混合容量一般路由问题。该问题概括了许多重要的弧和节点路由问题，并且考虑了转弯惩罚和禁止转弯，这在许多实际应用中至关重要，例如邮件递送、废物收集和街道维护操作。通过将所考虑的问题多项式转换为广义车辆路径问题，我们提出了一种通过将其转换为非对称容量车辆路径问题来解决这个新问题的新方法。这样，我们就可以使用现有算法以最优和启发式的方式解决新问题。还建议使用强大的模因算法和一组 336 个新基准实例。实验结果表明，所提出的求解方法相对于最优解的平均偏差小于0.05%。 (C) 2011 Elsevier Ltd. 保留所有权利。
In this paper we deal with the mixed capacitated general routing problem with turn penalties. This problem generalizes many important arc and node routing problems, and it takes into account turn penalties and forbidden turns, which are crucial in many real-life applications, such as mail delivery, waste collection and street maintenance operations. Through a polynomial transformation of the considered problem into a Generalized Vehicle routing problem, we suggest a new approach for solving this new problem by transforming it into an Asymmetric Capacitated Vehicle routing problem. In this way, we can solve the new problem both optimally and heuristically using existing algorithms. A powerful memetic algorithm and a set of 336 new benchmark instances are also suggested. The experimental results show that the average deviation of the suggested solution method is less than 0.05% with respect to optimum. (C) 2011 Elsevier Ltd. All rights reserved.