The flowtime network construction problem

Abstract

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.

Keywords:

• Scheduling
• network construction planning
• emergency restoration operations
• deliveryman problem
• traveling repairman problem