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.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/3283 |
| Date | January 2007 |
| Creators | Zvereva, Margarita |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0353 seconds