Variable Neighborhood Search for a Prize Collecting Capacity Constrained Connected Facility Location Problem

Author

Leitner, Markus ; Raidl, Günther R.

Author_Institution

Sch. of Telematics / Network Eng., Carinthia Univ. of Appl. Sci., Klagenfurt

fYear

2008

fDate

July 28 2008-Aug. 1 2008

Firstpage

233

Lastpage

236

Abstract

We present a variable neighborhood search approach for a network design problem occurring in real world when the bandwidth of an existing network shall be enhanced. Using two different neighborhood structures we show that a carefully designed combination of a metaheuristic and an exact method based on integer linear programming is able to improve solution quality compared to using heuristic methods only.

Keywords

costing; facility location; graph theory; integer programming; linear programming; network theory (graphs); search problems; bandwidth enhancement; costing; graph theory; integer linear programming; metaheuristics; network design problem; prize collecting capacity constrained connected facility location problem; variable neighborhood search; Application software; Approximation algorithms; Bandwidth; Computer graphics; Costs; Design engineering; Fiber optics; IP networks; Joining processes; Telematics; Connected Facility Location; Integer Linear Programming; Network Design; Variable Neighborhood Search;

fLanguage

English

Publisher

ieee

Conference_Titel

Applications and the Internet, 2008. SAINT 2008. International Symposium on

Conference_Location

Turku

Print_ISBN

978-0-7695-3297-4

Type

conf

DOI

10.1109/SAINT.2008.57

Filename

4604579