Tree optimization based heuristics and metaheuristics in network construction problems
Averbakh
I
author
Pereira
J
author
2021
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.
Network design
Scheduling
Network construction
Heuristics
Metaheuristics
Local search
WOS:000632975100009
exported from refbase (show.php?record=1362), last updated on Wed, 21 Apr 2021 16:20:46 -0400
text
10.1016/j.cor.2020.105190
Averbakh+Pereira2021
Computers & Operations Research
Comput. Oper. Res.
2021
continuing
periodical
academic journal
128
105190
0305-0548