Benders decomposition for network design covering problems

Autor: Natividad González-Blanco, Bernard Fortz, Martine Labbé, Juan A. Mesa, Victor Bucarey
Přispěvatelé: Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI), Ministerio de Ciencia y Tecnología(España), Ministerio de Economía y Competitividad (España), Data Analytics Laboratory, Vrije Universiteit Brussel (VUB), Département d'informatique [Bruxelles], Université libre de Bruxelles (ULB), Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Departamento de Matematica Aplicada II, Universidad de Sevilla, Universidad de Sevilla / University of Sevilla
Jazyk: angličtina
Rok vydání: 2022
Předmět:
0209 industrial biotechnology
Mathematical optimization
General Computer Science
Computer science
Existential quantification
Benders decomposition
0211 other engineering and technologies
Rapid transit network
02 engineering and technology
Management Science and Operations Research
Benders' decomposition
Upper and lower bounds
Set (abstract data type)
Facility planning and design
020901 industrial engineering & automation
Network Design
Informatique mathématique
Théorie de la décision et des choix collectifs
Network design
Mathematics - Optimization and Control
Budget constraint
021103 operations research
Informatique générale
Covering problems
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Network planning and design
Modeling and Simulation
Path (graph theory)
Rapid Transit Network
Zdroj: Computers and Operations Research
Computers and Operations Research, Elsevier, 2022
Computers and Operations Research, 2022
Computers & operations research, 137
idUS. Depósito de Investigación de la Universidad de Sevilla
instname
ISSN: 0305-0548
1873-765X
Popis: 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.
SCOPUS: ar.j
info:eu-repo/semantics/published
Databáze: OpenAIRE
Externí odkaz: