论文标题
一种应用于冬季道路维护的新的弧线路由算法
A New Arc-Routing Algorithm Applied to Winter Road Maintenance
论文作者
论文摘要
本文研究了一个相当普遍的路线问题的大规模实例，并纳入了尤其是来自冬季道路维护的调度问题（例如，道路维护的不同优先级和方法）。我们基于bin包装的启发式算法开发了一种新算法，该算法易于启发，并且能够在几分钟内在数千个十字路口和道路细分市场上解决道路网络。由于不可能找到这样大型实例与我们的算法结果进行比较的最佳解决方案，因此我们还开发了基于整数线性编程和懒惰约束的技术来计算下限。
This paper studies large scale instances of a fairly general arc-routing problem as well as incorporate practical constraints in particular coming from the scheduling problem of the winter road maintenance (e.g. different priorities for and methods of road maintenance). We develop a new algorithm based on a bin-packing heuristic which is well-scalable and able to solve road networks on thousands of crossroads and road segments in few minutes. Since it is impossible to find an optimal solution for such a large instances to compare it with a result of our algorithm, we also develop techniques to compute lower bounds which are based on Integer Linear Programming and Lazy Constraints.
