The flowtime network construction problem

Igor Averbakh, Jordi Pereira

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


Given a network whose edges need to be constructed, the problem is to find a construction schedule that minimizes the total recovery time of the vertices, where the recovery time of a vertex is the time when the vertex becomes connected to a special vertex (depot) that is the initial location of the construction crew. The construction speed is constant and is assumed to be incomparably slower than the travel speed of the construction crew in the already constructed part of the network. In this article, this new problem is introduced, its complexity is discussed, mixed-integer linear programming formulations are developed, fast and simple heuristics are proposed, and an exact branch-and-bound algorithm is presented which is based on specially designed lower bounds and dominance tests that exploit the problem's combinatorial structure. The results of extensive computational experiments are also presented. Connections between the problem and the Traveling Repairman Problem, also known as the Delivery Man Problem, and applications in emergency restoration operations are discussed.

Original languageEnglish
Pages (from-to)681-694
Number of pages14
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number8
StatePublished - Aug 2012
Externally publishedYes


  • Deliveryman problem
  • Emergency restoration operations
  • Network construction planning
  • Scheduling
  • Traveling repairman problem


Dive into the research topics of 'The flowtime network construction problem'. Together they form a unique fingerprint.

Cite this