Article
Benders decomposition for network design covering problems
Author/s | Bucarey, Víctor
Fortz, Bernard González Blanco, Natividad Labbé, Martine Mesa López-Colmenar, Juan Antonio |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI) |
Publication Date | 2022 |
Deposit Date | 2022-03-10 |
Published in |
|
Abstract | 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 ... 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. |
Funding agencies | Ministerio de Ciencia y Tecnología(España) Ministerio de Economía y Competitividad (España) |
Project ID. | PID2019- 106205GB-I00
MTM2015-67706-P PDR T0098.18 |
Citation | Bucarey, V., Fortz, B., González Blanco, N., Labbé, M. y Mesa López-Colmenar, J.A. (2022). Benders decomposition for network design covering problems. Computers and Operations Research, 137, Article number 105417. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Benders decomposition for network ... | 1.133Mb | [PDF] | View/ | |