Network construction problems with due dates

Igor Averbakh, Jordi Pereira

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


Abstract A network needs to be constructed by a server (construction crew) that has a constant construction speed which is incomparably slower than the server's travel speed within the already constructed part of the network. A vertex is recovered when it becomes connected to the depot by an already constructed path. Due dates for recovery times are associated with vertices. The problem is to obtain a construction schedule that minimizes the maximum lateness of vertices, or the number of tardy vertices. We introduce these new problems, discuss their computational complexity, and present mixed-integer linear programming formulations, heuristics, a branch-and-bound algorithm, and results of computational experiments.

Original languageEnglish
Article number12783
Pages (from-to)715-729
Number of pages15
JournalEuropean Journal of Operational Research
Issue number3
StatePublished - 1 Aug 2015
Externally publishedYes


  • Emergency restoration
  • Integrated network design and scheduling
  • Network construction
  • Network design
  • Scheduling


Dive into the research topics of 'Network construction problems with due dates'. Together they form a unique fingerprint.

Cite this