Variable neighborhood and greedy randomized adaptive search for capacitated connected facility location

Markus Leitner; Günther R. Raidl

doi:10.1007/978-3-642-27549-4_38

Variable neighborhood and greedy randomized adaptive search for capacitated connected facility location

Markus Leitner^*, Günther R. Raidl

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

The Connected Facility Location problem combining facility location and Steiner trees has recently gained stronger scientific interest as it can be used to model the extension of last mile communication networks in so-called fiber-to-the-curb scenarios. We consider a generalization of this problem which considers capacity constraints on potential facilities and aims at maximizing the resulting profit by potentially supplying only a subset of all customers. In this work, we discuss two metaheuristic approaches for this problem based on variable neighborhood search and greedy randomized adaptive search. Computational results show that both approaches allow for computing high quality solutions in relatively short time.

Original language	English
Title of host publication	Computer Aided Systems Theory, EUROCAST 2011 - 13th International Conference, Revised Selected Papers
Pages	295-302
Number of pages	8
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-27549-4_38
Publication status	Published - 20 Feb 2012
Externally published	Yes
Event	13th International Conference on Computer Aided Systems Theory, EUROCAST 2011 - Las Palmas de Gran Canaria, Spain Duration: 6 Feb 2011 → 11 Feb 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6927 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th International Conference on Computer Aided Systems Theory, EUROCAST 2011
Country/Territory	Spain
City	Las Palmas de Gran Canaria
Period	6/02/11 → 11/02/11

Keywords

connected facility location
greedy randomized adaptive search procedure
network design
variable neighborhood search

Access to Document

10.1007/978-3-642-27549-4_38

Persistent URL (handle)

Copy link address

Cite this

Leitner, M., & Raidl, G. R. (2012). Variable neighborhood and greedy randomized adaptive search for capacitated connected facility location. In Computer Aided Systems Theory, EUROCAST 2011 - 13th International Conference, Revised Selected Papers (PART 1 ed., pp. 295-302). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6927 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-27549-4_38

Leitner, Markus ; Raidl, Günther R. / Variable neighborhood and greedy randomized adaptive search for capacitated connected facility location. Computer Aided Systems Theory, EUROCAST 2011 - 13th International Conference, Revised Selected Papers. PART 1. ed. 2012. pp. 295-302 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{5cbcde86b0774baab7de033275099597,

title = "Variable neighborhood and greedy randomized adaptive search for capacitated connected facility location",

abstract = "The Connected Facility Location problem combining facility location and Steiner trees has recently gained stronger scientific interest as it can be used to model the extension of last mile communication networks in so-called fiber-to-the-curb scenarios. We consider a generalization of this problem which considers capacity constraints on potential facilities and aims at maximizing the resulting profit by potentially supplying only a subset of all customers. In this work, we discuss two metaheuristic approaches for this problem based on variable neighborhood search and greedy randomized adaptive search. Computational results show that both approaches allow for computing high quality solutions in relatively short time.",

keywords = "connected facility location, greedy randomized adaptive search procedure, network design, variable neighborhood search",

author = "Markus Leitner and Raidl, {G{\"u}nther R.}",

year = "2012",

month = feb,

day = "20",

doi = "10.1007/978-3-642-27549-4_38",

language = "English",

isbn = "9783642275487",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "295--302",

booktitle = "Computer Aided Systems Theory, EUROCAST 2011 - 13th International Conference, Revised Selected Papers",

edition = "PART 1",

note = "13th International Conference on Computer Aided Systems Theory, EUROCAST 2011 ; Conference date: 06-02-2011 Through 11-02-2011",

}

Leitner, M & Raidl, GR 2012, Variable neighborhood and greedy randomized adaptive search for capacitated connected facility location. in Computer Aided Systems Theory, EUROCAST 2011 - 13th International Conference, Revised Selected Papers. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6927 LNCS, pp. 295-302, 13th International Conference on Computer Aided Systems Theory, EUROCAST 2011, Las Palmas de Gran Canaria, Spain, 6/02/11. https://doi.org/10.1007/978-3-642-27549-4_38

Variable neighborhood and greedy randomized adaptive search for capacitated connected facility location. / Leitner, Markus; Raidl, Günther R.
Computer Aided Systems Theory, EUROCAST 2011 - 13th International Conference, Revised Selected Papers. PART 1. ed. 2012. p. 295-302 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6927 LNCS, No. PART 1).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Variable neighborhood and greedy randomized adaptive search for capacitated connected facility location

AU - Leitner, Markus

AU - Raidl, Günther R.

PY - 2012/2/20

Y1 - 2012/2/20

N2 - The Connected Facility Location problem combining facility location and Steiner trees has recently gained stronger scientific interest as it can be used to model the extension of last mile communication networks in so-called fiber-to-the-curb scenarios. We consider a generalization of this problem which considers capacity constraints on potential facilities and aims at maximizing the resulting profit by potentially supplying only a subset of all customers. In this work, we discuss two metaheuristic approaches for this problem based on variable neighborhood search and greedy randomized adaptive search. Computational results show that both approaches allow for computing high quality solutions in relatively short time.

AB - The Connected Facility Location problem combining facility location and Steiner trees has recently gained stronger scientific interest as it can be used to model the extension of last mile communication networks in so-called fiber-to-the-curb scenarios. We consider a generalization of this problem which considers capacity constraints on potential facilities and aims at maximizing the resulting profit by potentially supplying only a subset of all customers. In this work, we discuss two metaheuristic approaches for this problem based on variable neighborhood search and greedy randomized adaptive search. Computational results show that both approaches allow for computing high quality solutions in relatively short time.

KW - connected facility location

KW - greedy randomized adaptive search procedure

KW - network design

KW - variable neighborhood search

UR - http://www.scopus.com/inward/record.url?scp=84856827105&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84856827105&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-27549-4_38

DO - 10.1007/978-3-642-27549-4_38

M3 - Conference contribution

AN - SCOPUS:84856827105

SN - 9783642275487

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 295

EP - 302

BT - Computer Aided Systems Theory, EUROCAST 2011 - 13th International Conference, Revised Selected Papers

T2 - 13th International Conference on Computer Aided Systems Theory, EUROCAST 2011

Y2 - 6 February 2011 through 11 February 2011

ER -

Leitner M, Raidl GR. Variable neighborhood and greedy randomized adaptive search for capacitated connected facility location. In Computer Aided Systems Theory, EUROCAST 2011 - 13th International Conference, Revised Selected Papers. PART 1 ed. 2012. p. 295-302. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-27549-4_38

Variable neighborhood and greedy randomized adaptive search for capacitated connected facility location

Abstract

Publication series

Conference

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this