title: Solutions to Facility Location–Network Design Problems
creator: Cocking, Cara
subject: 004
subject: 004 Data processing Computer science
description: 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.
date: 2008
type: Dissertation
type: info:eu-repo/semantics/doctoralThesis
type: NonPeerReviewed
format: application/pdf
identifier: https://archiv.ub.uni-heidelberg.de/volltextserverhttps://archiv.ub.uni-heidelberg.de/volltextserver/8660/1/dissertation.pdf
identifier: DOI:10.11588/heidok.00008660
identifier: urn:nbn:de:bsz:16-opus-86601
identifier:   Cocking, Cara  (2008) Solutions to Facility Location–Network Design Problems.  [Dissertation]     
relation: https://archiv.ub.uni-heidelberg.de/volltextserver/8660/
rights: info:eu-repo/semantics/openAccess
rights: http://archiv.ub.uni-heidelberg.de/volltextserver/help/license_urhg.html
language: eng