Return to search

Mathematical Programming Formulations of the Planar Facility Location Problem

The facility location problem is the task of optimally placing a
given number of facilities in a certain subset of the plane. In
this thesis, we present various mathematical programming
formulations of the planar facility location problem, where
potential facility locations are not specified. We first consider
mixed-integer programming formulations of the planar facility
locations problems with squared Euclidean and rectangular distance
metrics to solve this problem to provable optimality. We also
investigate a heuristic approach to solving the problem by extending
the $K$-means clustering algorithm and formulating the facility
location problem as a variant of a semidefinite programming problem,
leading to a relaxation algorithm. We present computational results
for the mixed-integer formulations, as well as compare the objective
values resulting from the relaxation algorithm and the modified
$K$-means heuristic. In addition, we briefly discuss some of the
practical issues related to the facility location model under the
continuous customer distribution.
Date January 2007
CreatorsZvereva, Margarita
Source SetsUniversity of Waterloo Electronic Theses Repository
Detected LanguageEnglish
TypeThesis or Dissertation

Page generated in 0.0016 seconds