Tree optimization based heuristics and metaheuristics in network construction problems

Igor Averbakh, Jordi Pereira

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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.

Original languageEnglish
Article number105190
JournalComputers and Operations Research
StatePublished - Apr 2021
Externally publishedYes


  • Heuristics
  • Local search
  • Metaheuristics
  • Network construction
  • Network design
  • Scheduling


Dive into the research topics of 'Tree optimization based heuristics and metaheuristics in network construction problems'. Together they form a unique fingerprint.

Cite this