Two-phase local search for the bi-objective connected facility location problem

Abstract

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.

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.