Maxflow-Based Integrated Network Design and Scheduling Problems with Downgraded Capacities

We consider the problem of upgrading edge capacities in a network in order to maximize the total flow over a time horizon. We are interested in determining both which edges to upgrade (network design decisions) and when to upgrade them (scheduling decisions) while also considering the fact that the capacities of edges undergoing their upgrading process will be downgraded. We introduce a novel heuristic method based on properties of the maximum flow to solve the problem on realistic networks and compare its performance to a mixed-integer programming (MIP) model for the problem. We further consider how to improve the heuristic solutions through simulated annealing. The heuristic method is tested on synthetic Manhattan Grid and CLARC County networks and real-world networks from Eastern Massachusetts, Anaheim, and Chicago. It is shown to produce high-quality solutions to the problem in a much shorter time than the MIP model.