Network construction problems with due dates

•Two new network construction problems are introduced.•Complexity results are presented.•MILP formulations and a branch-and-bound algorithm are developed.•Novel lower bounding technique based on Steiner tree relaxations is used.•Computational experiments use random instances and real-life data.•Branch-and-bound algorithm is currently the best exact method.

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.