论文标题
基于树木优化的网络构建问题中的启发式和元启发式学
Tree Optimization Based Heuristics and Metaheuristics in Network Construction Problems
论文作者
论文摘要
我们考虑了最近引入的网络构建问题类别，其中需要由服务器（施工人员）构建运输网络的边缘。服务器的构造速度远低于其行进速度，因此，相对于施工时间，搬迁时间可以忽略不计。需要找到一个施工时间表，以最大程度地减少各种兴趣连接的时代的非降低功能。该类别的大多数问题在通用网络上是强烈的NP障碍，但通常是树木效率的，即在树上可以解决多项式。我们开发了一种通用的本地搜索启发式方法和两种元启发式方法（迭代的本地搜索和禁忌搜索），以解决一般网络上的树木效率网络构建问题，并在计算上探索它们。计算实验的结果表明该方法具有出色的性能。
We consider a recently introduced class of network construction problems where edges of a transportation network need to be constructed by a server (construction crew). The server has a constant construction speed which is much lower than its travel speed, so relocation times are negligible with respect to construction times. It is required to find a construction schedule that minimizes a non-decreasing function of the times when various connections of interest become operational. Most problems of this class are strongly NP-hard on general networks, but are often tree-efficient, that is, polynomially solvable on trees. We develop a generic local search heuristic approach and two metaheuristics (Iterated Local Search and Tabu Search) for solving tree-efficient network construction problems on general networks, and explore them computationally. Results of computational experiments indicate that the methods have excellent performance.
