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.