Benders decomposition for Network Design Covering Problems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Computers and Operations Research Année : 2022

Benders decomposition for Network Design Covering Problems

Résumé

We consider two covering variants of the network design problem. We are given a set of origin/destination (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 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 two different stabilization methods to determine the Benders cuts as well as the addition of cut-set inequalities to the master problem. Computational experiments show the efficiency of these different aspects.
Fichier principal
Vignette du fichier
main.pdf (769.43 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03137944 , version 1 (10-02-2021)

Identifiants

  • HAL Id : hal-03137944 , version 1

Citer

Víctor Bucarey, Bernard Fortz, Natividad González-Blanco, Martine Labbé, Juan A Mesa. Benders decomposition for Network Design Covering Problems. Computers and Operations Research, 2022. ⟨hal-03137944⟩
57 Consultations
214 Téléchargements

Partager

Gmail Facebook X LinkedIn More