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.

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.

http://publik.tuwien.ac.at/files/PubDat_201160.pdf

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