论文标题
用于大规模定向问题的重新审视的分支机构算法
A revisited branch-and-cut algorithm for large-scale orienteering problems
论文作者
论文摘要
定向问题是一个路由优化问题，它包括找到一个简单的周期，该周期最大化收集的总利润受到最大距离限制。在过去的几十年中，在现实生活中，此问题的发生促进了许多启发式算法的发展来解决它。但是，在同一时期，对于定向问题的精确算法领域并没有太多研究。这项工作的目的是开发一种确切的方法，该方法能够在更广泛的实例中获得最佳认证，而不是以前的方法，或者在其残疾中改善上层和上限。 我们提出了针对定向问题的分支和切割算法的重审版本，其中包括来自周期问题，分离循环，变量定价的分离算法的新贡献，以及问题的下限和上限。我们的建议与258个基准实例的三种最先进的算法相比，最高7397个节点。计算实验显示了设计组件的相关性，其中有18个新的Optima，76个新的最著名的解决方案和85个新的上限值。
The orienteering problem is a route optimization problem which consists in finding a simple cycle that maximizes the total collected profit subject to a maximum distance limitation. In the last few decades, the occurrence of this problem in real-life applications has boosted the development of many heuristic algorithms to solve it. However, during the same period, not much research has been devoted to the field of exact algorithms for the orienteering problem. The aim of this work is to develop an exact method which is able to obtain optimality certification in a wider set of instances than with previous methods, or to improve the lower and upper bounds in its disability. We propose a revisited version of the branch-and-cut algorithm for the orienteering problem which includes new contributions in the separation algorithms of inequalities stemming from the cycle problem, in the separation loop, in the variables pricing, and in the calculation of the lower and upper bounds of the problem. Our proposal is compared to three state-of-the-art algorithms on 258 benchmark instances with up to 7397 nodes. The computational experiments show the relevance of the designed components where 18 new optima, 76 new best-known solutions and 85 new upper-bound values were obtained.
