<p>This thesis is devoted to introducing new problem formulations and exact solution methods for a class of continuous covering location models. The manuscript includes three self-contained studies which are organized as in the following. </p>
<p> In the first study, we introduce the planar expropriation problem with non-rigid rectangular facilities which has many applications in regional planning and undesirable facility location domains. This model is proposed for determining the locations and formations of two-dimensional rectangular facilities. Based on the geometric properties of such facilities, we developed a new formulation which does not require employing distance measures. The resulting model is a mixed integer nonlinear program. For solving this new model, we derived a continuous branch-and-bound framework utilizing linear approximations for the tradeoff curve associated with the facility formation alternatives. Further, we developed new problem generation and bounding strategies suitable for this particular branch-and-bound procedure. We designed a computational study where we compared this algorithm with two well-known mixed integer nonlinear programming solvers. Computational experience showed that the branch-and-bound procedure we developed performs better than BARON and SBB both in terms of processing time and size of the branching tree.</p>
<p> The second study is referred to as the planar maximal covering problem with single convex polygonal shapes and it has ample applications in transmitter location, inspection of geometric shapes and directional antenna location. In this study, we investigated maximal point containment by any convex polygonal shape in the Euclidean plane. Using a fundamental separation property of convex sets, we derived a mixed integer linear formulation for this problem. We were able to identify two types of special cuts based on the geometric properties of the shapes under study, which were later employed for developing a branch-and-cut procedure for solving this particular location model. We also evaluated the resultant bound quality after employing the afore-mentioned cuts. </p>
<p> In the third study, we discuss the dynamic planar expropriation problem with single convex polygonal shapes. We showed how the basic problem formulations discussed in the first two studies extend to their diametric opposites, and further to models in higher dimensions. Subsequently, we allowed a dynamic setting where the shape under study is expected to function over a finite planning horizon and the system parameters such as the fixed point locations and expropriation costs are subject to change. The shape was permitted to relocate at the beginning of each time period according to particular relocation costs. We showed that this dynamic problem structure can be decomposed into a set of static problems under a particular vector of relocations. We discussed the solution of this model by two enumeration procedures. Subsequently, we derived an incomplete dynamic programming procedure which is suitable for this distinct problem structure. In this method, there is no need to evaluate all the branches of the branching tree and one proceeds with keeping the minimum stage cost. The evaluation of a branch is postponed until relocation takes place in the lower-level problems. With this postponing structure, the procedure turned out to be superior to the two enumeration procedures in terms of tree size. </p> / Thesis / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/17249 |
| Date | January 2009 |
| Creators | Cakir, Ozan |
| Contributors | Wesolowsky, George O., Business |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0022 seconds