Tree Optimization Based Heuristics and Metaheuristics in Network Construction Problems

DOI10.1016/J.COR.2020.105190MaRDI QIDQ6344571arXivFDO

Authors Igor Averbakh, Jordi Pereira

Publication date 3 July 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.COR.2020.105190

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

arXiv classification

cs.AImath.OC

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.

This page was built for publication: Tree Optimization Based Heuristics and Metaheuristics in Network Construction Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6344571)