TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Mett, Fabian A1 - Pulaj, Jonad T1 - An (MI)LP-based Primal Heuristic for 3-Architecture Connected Facility Location in Urban Access Network Design N2 - We investigate the 3-architecture Connected Facility Location Problem arising in the design of urban telecommunication access networks integrating wired and wireless technologies. We propose an original optimization model for the problem that includes additional variables and constraints to take into account wireless signal coverage represented through signal-to-interference ratios. Since the problem can prove very challenging even for modern state-of-the art optimization solvers, we propose to solve it by an original primal heuristic that combines a probabilistic fixing procedure, guided by peculiar Linear Programming relaxations, with an exact MIP heuristic, based on a very large neighborhood search. Computational experiments on a set of realistic instances show that our heuristic can find solutions associated with much lower optimality gaps than a state-of-the-art solver. T3 - ZIB-Report - 15-62 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57139 SN - 1438-0064 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Mett, Fabian A1 - Pulaj, Jonad T1 - An (MI)LP-based Primal Heuristic for 3-Architecture Connected Facility Location in Urban Access Network Design T2 - EvoApplications: European Conference on the Applications of Evolutionary Computation. Applications of Evolutionary Computation. 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 -- April 1, 2016, Proceedings, Part I N2 - We investigate the 3-architecture Connected Facility Location Problem arising in the design of urban telecommunication access networks integrating wired and wireless technologies. We propose an original optimization model for the problem that includes additional variables and constraints to take into account wireless signal coverage represented through signal-to-interference ratios. Since the problem can prove very challenging even for modern state-of-the art optimization solvers, we propose to solve it by an original primal heuristic that combines a probabilistic fixing procedure, guided by peculiar Linear Programming relaxations, with an exact MIP heuristic, based on a very large neighborhood search. Computational experiments on a set of realistic instances show that our heuristic can find solutions associated with much lower optimality gaps than a state-of-the-art solver. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-31204-0_19 VL - 9597 SP - 283 EP - 298 ER - TY - THES A1 - Mett, Fabian T1 - The Connected Facility Location Problem Y1 - 2015 ER - TY - JOUR A1 - D'Andreagiovanni, Fabio A1 - Mett, Fabian A1 - Nardin, Antonella A1 - Pulaj, Jonad T1 - Integrating LP-guided variable fixing with MIP heuristics in the robust design of hybrid wired-wireless FTTx access networks JF - Applied Soft Computing N2 - This study investigates how to model and solve the problem of optimally designing FTTx telecommunications access networks integrating wired and wireless technologies, while taking into account the uncertainty of wireless signal propagation. We propose an original robust optimization model for the related robust 3-architecture Connected Facility Location problem, which includes additional variables and constraints to model wireless signal coverage represented through signal-to-interference ratios. Since the resulting robust problem can prove very challenging even for a modern state-of-the art optimization solver, we propose to solve it by an original primal heuristic that combines a probabilistic variable fixing procedure, guided by peculiar Linear Programming relaxations, with a Mixed Integer Programming heuristic, based on an exact very large neighborhood search. A numerical study carried out on a set of realistic instances show that our heuristic can find solutions of much higher quality than a state-of-the-art solver. Y1 - 2017 U6 - https://doi.org/10.1016/j.asoc.2017.07.018 VL - 61 SP - 1074 EP - 1087 ER - TY - THES A1 - Mett, Fabian T1 - Über die optimale Platzierung von Ladestationen für Elektrobusse N2 - In dieser Arbeit wird die Platzierung von Ladestationen für Elektrobusse untersucht. Dabei soll für eine Menge an gegebenen Linien eine Menge an Ladestationen gefunden werden, sodass jede Linie mit Nutzung der Ladestationen befahren werden kann und gleichzeitig die Kosten minimal sind. Zunächst wird der Fall betrachtet, dass die Batterie an jeder Station komplett vollgeladen werden könnte. Dieses Problem stellt sich als NP-schwer heraus. Für einige einfachere Fällewerden zudem Algorithmen entwickelt und untersucht. Anschließend wird der Fall einer unbegrenzt großen Batterie betrachtet, wobei an jeder Station derselbe Wert geladen werden kann. Auch dieses Problem ist NP-schwer. Erneut werden Algorithmen zur Lösung vereinfachter Problemstellungen gegeben und analysiert. Wird zudem angenommen, an jeder Station würde ein individueller Wert geladen, so ist das Problem schon für nur eine einzige Linie NP-schwer. Dennoch werden zwei exakte und ein approximierender Algorithmus entwickelt. Schließlich wird eine Batteriekapazität hinzugefügt und die zuvor entwickelten Algorithmen werden entsprechend angepasst. Für die abschließende Problemdefinition werden verschiedene Batteriegrößen betrachtet und es werden zwei gemischt-ganzzahlige Programme aufgestellt. Anhand von existierenden Buslinien aus Berlin werden diese untersucht. Dabei stellt sich heraus, dass die Batteriekosten einen deutlich größeren Teil der Kosten ausmachen als die Ladestationen. Zudem sollten kleinere Batterien statt größerer und mehr Ladestationen genutzt werden. Y1 - 2018 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Euler, Ricardo A1 - Karbstein, Marika A1 - Mett, Fabian T1 - Ein mathematisches Modell zur Beschreibung von Preissystemen im öV N2 - Dieses Dokument fasst den Stand der mathematischen Modellierung von Preissystemen des öV mittels eines am ZIB entwickelten Tarifgraphenmodells zusammen. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen möglich, die sich algorithmisch behandeln lassen: Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Tarifgraphen kann schon während einer Routenberechnung der Preis bestimmt werden. Wir beschreiben zunächst das Konzept. Die konkrete Realisierung wird im Folgenden beispielhaft an den Tarifsystemen der Verkehrsverbünde Warnow, MDV, Vogtland, Bremen/Niedersachsen, Berlin/Brandenburg und Mittelsachsen erläutert. Anschließend folgen Überlegungen zur konkreten Implementierung von Kurzstrecken-Tarifen und zur Behandlung des Verbundübergriffs. T3 - ZIB-Report - 18-47 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70564 SN - 1438-0064 ER -