Solutions to facility location-network design problems [Elektronische Ressource] / vorgelegt von Cara Cocking

I N A U G U R A L – D I S S E R T A T I O NzurErlangung der Doktorwu¨rdederNaturwissenschaflich-MathematischenGesamtfakult¨atderRuprecht-Karls-Universit¨atHeidelbergvorgelegt vonCara Cocking, M.Sc.aus New YorkTag der mu¨ndlichen Pru¨fung: 15. September 2008Solutions toFacility Location–Network DesignProblemsGutachter: Prof. Dr. Gerhard ReineltProf. Dr. Klaus Ambos-SpiesTo my sister WendyAbstractThis doctoral thesis presents new solution strategies for facility location–networkdesign (FLND) problems. FLND is a combination of facility location and networkdesign: the overall goal is to improve clients’ access to facilities and the means ofreaching this goal include both building facilities (as in facility location) and buildingtravelable links (as in network design). We measure clients’ access to facilities by thesumofthetravelcosts, andourobjectiveistominimizethissum. FLNDproblemshavefacility location problems and network design problems, both of which areNP-hard,as subproblems and are therefore themselves theoretically difficult problems.We approach the search for optimal solutions from both above and below, con-tributing techniques for finding good upper bounds as well as good lower bounds onan optimal solution.On the upper bound side, we present the first heuristics in the literature for thisproblem.