2020/07/13 by Bucarey, Víctor, Fortz, Bernard, González-Blanco, Natividad +2 · 1 citation
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2007.06647
We consider two covering variants of the network design problem. We are given a set of origin/destination pairs, called O/D pairs, and each such O/D pair is covered if there exists a path in the network from the origin to the destination whose length is not larger than a given threshold. In the first problem, called the Maximal Covering Network Design problem, one must determine a network that maximizes the total fulfilled demand of the covered O/D pairs subject to a budget constraint on the design costs of the network. In the second problem, called the Partial Covering Network Design problem, the design cost is minimized while a lower bound is set on the total demand covered. After presenting formulations, we develop a Benders decomposition approach to solve the problems. Further, we consider several stabilization methods to determine Benders cuts as well as the addition of cut-set inequalities to the master problem. We also consider the impact of adding an initial solution to our methods. Computational experiments show the efficiency of these different aspects.