[Back]

T. Petelin:
"Two-phase local search for the bi-objective connected facility location problem";
Supervisor: G. Raidl, M. Leitner; Institut für Computergraphik and Algorithmen, 2013; final examination: 2013-12.

In this thesis a two-phase local search based metaheuristic algorithm for the Bi-objective Connected
Facility Location Problem (BoConFL) is presented.
The Connected Facility Location Problem (ConFL) is an NP-hard combinatorial optimization
problem that has been recently proposed to model the extension of fiber-optic-networks using
so-called fiber-to-the-curb (FTTc) strategies. In FTTc scenarios telecommunication providers
aim to extend their fiber-optic networks to mediation points (facilities) that bridge between fiberoptic
and copper technology. Customers are finally connected to facilities using the previously
existing copper network. Thus, the bandwidth of customers can be significantly increased with
less investment costs compared to connecting each customer using fiber-optics, i.e., compared
to fiber-to-the-home scenarios.
The main drawbacks of previously considered variants of ConFL are that they either aim to
mandatorily connect all potential customers or that they simply optimize the difference between
the revenue obtained by connecting a subset of customers and the resulting network construction
costs. In many realistic settings, however, customer "revenues" may be given e.g. by means
of demands rather than in monetary units. Thus, simply maximizing the previously mentioned
difference is not meaningful. Hence, the Bi-objective Connected Facility Location Problem (Bo-
ConFL) which is addressed in this thesis aims to simultaneously maximize the collected revenue
and minimize the resulting costs for constructing the network. In many relevant scenarios, the
addition of a second objective function provides a better representation of the real world since
these two objectives are conflicting, rather than finding a single optimal solution in the BoConFL
we are interested in identifying the set of non-dominated, i.e., Pareto-optimal, solutions.
Based on previous work for single-objective variants of the problem and successful approaches
for different bi-objective combinatorial optimization problem a two-phase algorithm
is developed in order to get a good approximation of the Pareto front with the following two
main steps:
a) Construction of a set of promising solutions by aggregation of the two objectives to a
single one. Variable neighborhood descent is used to further improve the obtained set of
initial solution candidates.
b) Application of a Pareto local search algorithm that takes both objectives explicitly into
account to further improve the quality of the solution set.
The influence of the algorithms components and parameters on the runtime and the quality
of the obtained approximation is analyzed using a computational study.

In dieser Arbeit wird ein auf lokaler Suche basierender zwei phasiger metaheuristischer Algorithms
für das Bi-objective Connected Facility Location Problem (BoConFL) präsentiert.
Das Connected Facility Location (ConFL) Problem ist ein NP hartes kombinatorisches Optimierungsproblem,
welches erst kürzlich als Modell für die Erweiterung von Glasfaserkabelnetzwerken
zu sogenannten Fiber-to-the-Curb (FTTc) Strategien vorgeschlagen wurde. Bei solchen
FTTc Szenarien versuchen Telekommunikationsanbieter ihr Glasfasernetzwerk zu sogenannten
Vermittlungspunkten (Facilities) zu erweitern, welche den Übergang von Glasfaser zu Kupfer
handhaben. Dadurch wird dem Kunden deutlich mehr Bandbreite geboten und zusätlich werden
die Ausbaukosten geringer gehalten, als würde jeder Kunde einen direkten Glasfaseranschluss
bekommen.
Der größte Nachteil in den bisher präsentierten Varianten des ConFL Problems liegt darin,
dass entweder versucht wird jeden Kunden mit einer Facility zu verbinden oder es wird einfach
versucht die Differenz zwischen Ausbaukosten und Gewinn zu minimieren indem nur ein bestimmter
Teil aller möglichen Kunden angebunden wird. In vielen realistischen Szenarien kann
der "Ertrag" eines Kunden eher durch dessen Anforderung definiert werden als über erhaltenen
Gewinn. Dadurch ist die einfache Maximierung von Gewinn minus Ausbaukosten nicht aussagekräftig.
Auf Grund dessen haben wir versucht das BoConFL Problem zu lösen, mit dem Ziel
den Kundennutzen zu maximieren während wir die Ausbaukosten minimieren. Da die Erweiterung
des ConFL Problems um eine weitere Zielfunktion eine bessere Abbildung der Realität
darstellt, weil sich die beiden Zielfunktionen widersprechen, haben wir versucht eine Menge
von sich nicht gegenseitig dominierenden (Pareto-optimale) Lösungen zu suchen anstatt einer
einzelnen optimierten Lösung.
Basierend auf bisherigen Arbeiten zu dem normalen, single-objective ConFL Problem und
diversen erfolgreichen Ansätzen für bi-objective kombinatorische Optimierungsprobleme werden
wir einen zwei-Phasen Algorithmus entwickeln, welcher versucht die Paretofront so gut als
möglich anzunähern. Dieser Algorithmus besteht aus folgenden zwei Schritten:
a) Konstruktion einer Menge von vielversprechenden Lösungen durch Aggregation der beiden
Zielfunktionen zu einer einzigen, unter Verwendung von Gewichten. Weiters verwenden
wir eine variable Nachbarschaftssuche um die initialen Lösungen nochmals zu
verbessern.
b) Anwendung einer Pareto-lokalen Suche, welche beide Zielfunktionen berücksichtigt, um
die Lösungen weiter zu verbessern.
Um den Einfluss der Komponenten des Algorithmus und seiner Parameter auf die Laufzeit
und die Qualität der berechneten Lösungen zu analysieren, werden wir den Algorithmus auf ein
Set verschiedener Testinstanzen anwenden.

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