German Title: Lösungsmethoden für das Facility Location–Network Design Problem

Preview

PDF, English Download (1MB) | Terms of use

Abstract

This doctoral thesis presents new solution strategies for facility location–network design (FLND) problems. FLND is a combination of facility location and network design: the overall goal is to improve clients’ access to facilities and the means of reaching this goal include both building facilities (as in facility location) and building travelable links (as in network design). We measure clients’ access to facilities by the sum of the travel costs, and our objective is to minimize this sum. FLND problems have facility location problems and network design problems, both of which are NP-hard, as subproblems and are therefore themselves theoretically difficult problems. We approach the search for optimal solutions from both above and below, contributing techniques for finding good upper bounds as well as good lower bounds on an optimal solution. On the upper bound side, we present the first heuristics in the literature for this problem. We have developed a variety of heuristics: simple greedy heuristics, a local search heuristic, metaheuristics including simulated annealing and variable neighborhood search, as well as a custom heuristic based on the problem-specific structure of FLND. Our computational results compare the performance of these heuristics and show that the basic variable neighborhood search performs the best, achieving a solution within 0.6% of optimality on average for our test cases. On the lower bound side, we work with an existing IP formulation whose LP relaxation provides good lower bounds. We present a separation routine for a new class of inequalities that further improve the lower bound, in some cases even obtaining the optimal solution. Putting all this together, we develop a branch-and-cut approach that uses heuristic solutions as upper bounds, and cutting planes for increasing the lower bound at each node of the problem tree, thus reducing the number of nodes needed to solve to optimality. We also present an alternate IP formulation that uses fewer variables than the one accepted in the literature. This formulation allows some problems to be solved more quickly, although its LP relaxation is not as tight. To aid in the visualization of FLND problem instances and their solutions, we have developed a piece of software, FLND Visualizer. Using this application one can create and modify problem instances, solve using a variety of heuristic methods, and view the solutions. Finally, we consider a case study: improving access to health facilities in the Nouna health district of Burkina Faso. We demonstrate the solution techniques developed here on this real-world problem and show the remarkable improvements in accessibility that are possible.

Translation of abstract (German)

In der vorliegenden Arbeit leisten wir neue Lösungsmethoden für das Facility Location–Network Design (FLND) Problem. Dieses Problem ist eine Kombination aus Facility Location und Network Design: das Ziel ist es, den Zugang von Kunden zu gewissen Einrichtungen zu verbessern, sowohl durch das Bauen von Einrichtungen (wie im Facility Location Problem) als auch von Kanten (wie im Network Design Problem). Die Güte des Zugangs zu Einrichtungen entspricht der Summe der Reisekosten. Diese Summe gilt es zu minimieren. FLND Probleme enthalten Facility Location Probleme und Network Design Probleme, beide NP-hard, als Subprobleme und sind daher selbst theoretisch schwere Probleme. Wir leisten Beiträge zum Berechnen von guten oberen und unteren Schranken für optimale Lösungen. Was obere Schranken betrifft, präsentieren wir die ersten Heuristiken überhaupt für dieses Problem. Wir haben verschiedene Heuristiken entwickelt: einfache Greedy Heuristiken, eine Local Search Heuristik, Metaheuristiken inklusive Simulated Annealing und Variable Neighborhood Search und auch eine Heuristik, die auf der problemspezifischen Struktur von FLND basiert. Rechenexperimente zeigen, dass die Basic Variable Neighborhood Search Heuristik die Beste ist, mit einer durchschnittlichen Lösungsqualität, die innerhalb von 0.6% von der optimalen Lösung liegt. Was untere Schranken betrifft, gibt es schon eine IP Formulierung, deren LP Relaxierung gute Resultate liefert. Wir präsentieren aber Methoden für die Separierung von einer neue Klasse von Ungleichungen, die die unteren Schranken verbessern, manchmal sogar die optimale Lösung im Wurzelknoten finden. Zudem erweitern wir eine branch-and-cut Methode, die Heuristiken für obere Schranken und Schnittebene für bessere untere Schranken an jedem Knoten des Problembaums verwendet. Die Anzahl der branch-and-cut Knoten wird dadurch stark reduziert. Wir präsentieren auch eine neue IP Formulierung, die weniger Variablen hat. Diese Formulierung ermöglicht es, dass einige Probleme schneller gelöst werden können, obwohl die LP Relaxierung nicht so stark ist. Um FLND Probleme und Lösungen visualisieren zu können, haben wir die Software FLND Visualizer entwickelt. Mit dieser Software kann man Probleme entwerfen und abändern, Heuristiken aufrufen, und Lösungen ansehen. Schließlich machen wir eine Fallstudie: Das Ziel ist die Verbesserung des Zugangs zu Gesundheitseinrichtungen in Nouna, Burkina Faso. Wir verwenden die neuentwickelten Lösungsmethoden anhand dieses anwendungsnahen Problems und zeigen, dass bemerkenswerte Verbesserungen des Zugangs möglich sind.