A dynamic discrete network design problem for maintenance planning in traffic networks

We propose a dynamic model for network maintenance planning by extending the Discrete Network Design Problem. The leader decides which road in the network is maintained in which period and the follower, as in the Discrete Network Design Problem, optimizes its own path through the network. The non-linear bilevel problem is first linearized and then transformed into a single-level mixed-integer program by using the Karush–Kuhn–Tucker conditions. This model is solved with Benders Decomposition. The numerical study shows that this method finds better solutions faster compared to solving the mixed-integer formulation directly and using a genetic algorithm. Furthermore, we show the benefit of this approach compared to simple greedy heuristics.