Exact solution for time sequence optimization of road reconstruction projects considering network capacity limitation

The problem is often encountered in road network reconstruction: there are multiple road sections (each road section is defined as a project or work zone) that need to be reconstructed in a period and how to arrange the time sequence of these projects to minimize the total construction duration under the premise of meeting the capacity constraints of the road network. This paper proposes an exact solution algorithm based on the branch-and-bound approach to solve the problem. The methods for estimating the upper and lower bounds of the duration of the project combination represented by each node are proposed, and the pruning rules and search principles are defined. The optimality of the solution obtained by the proposed algorithm is proved. Finally, an example is presented to demonstrate the search process and the effectiveness of the algorithm.