[Back]


Talks and Poster Presentations (with Proceedings-Entry):

M. Leitner, G. Raidl:
"Variable neighborhood search for capacitated connected facility location";
Talk: International Conference on Computer Aided Systems Theory (Eurocast), Gran Canaria, Spain; 2011-02-06 - 2011-02-11; in: "Extended Abstracts of EUROCAST 2011 - 13th International Conference on Computer Aided Systems Theory", (2011), ISBN: 978-84-693-9560-8; 261 - 263.



English abstract:
The Capacitated Connected Facility Location Problem (CConFL) is an NP-
hard combinatorial optimization problem which arises in the design of last mile
communication networks (fiber-to-the-curb scenarios) [1]. Formally, we are given
an undirected, weighted graph G = (V,E), with edge costs ce 0, 8e 2 E. The
node set V = {r}[F [T is the disjoint union of the root node r, potential facility
locations F, and possible Steiner nodes T . Each facility i 2 F has associated
opening costs fi 0 and a maximum assignable capacity Di 2 N. Furthermore,
we are given a set of potential customers C, with individual capacity demands
dk 2 N and prizes pk 0, 8k 2 C, the latter corresponding to the expected
profit when supplying customer k. Each customer k 2 C may be assigned to one
facility of a subset Fk F, with assignment costs ai,k 0, 8i 2 Fk. A solution to
CConFL S = (RS, TS, FS,CS, S) consists of a Steiner Tree (RS, TS), RS V ,
TS E, connecting the set of opened facilities FS F and the root node r.
CS C is the set of customers feasibly (i.e. respecting the capacity constraints)
assigned to facilities FS, whereas the actual mapping between customers and
facilities is described by S : CS ! FS. The objective value of a feasible solution
S is given by c(S) = Pe2TS
ce+Pi2FS
fi+Pk2CS
a S(k),k+Pk2C\CS
pk, and we
aim to identify a most profitable solution minimizing this function. This variant
of CConFL has already been tackled by exact methods based on mixed integer
programming [2] and hybrid approaches based on Lagrangian relaxation [1].
Here, we present the first pure metaheuristic approach, which computes high
quality solution faster than existing approaches.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_201160.pdf


Created from the Publication Database of the Vienna University of Technology.