Tree Optimization Based Heuristics and Metaheuristics in Network Construction Problems
From MaRDI portal
Publication:6344571
DOI10.1016/J.COR.2020.105190zbMATH Open1510.90094arXiv2007.03425MaRDI QIDQ6344571
Publication date: 3 July 2020
Abstract: 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.
Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10)
This page was built for publication: Tree Optimization Based Heuristics and Metaheuristics in Network Construction Problems
