Search ETDs:

Export: Refworks | RIS

PLANAR k-CENTRA SINGLE-FACILITY EUCLIDEAN LOCATION PROBLEM

448.42 kB PDF file

Degree
Master of Science (MS), Ohio University, Industrial and Manufacturing Systems Engineering (Engineering), .
Abstract
Facility location represents the process of identifying the best location for a service, commodity or production facility. The objective of this thesis is to solve the planar k-centra single-facility location problem with Euclidean distances. The problem statement is to locate a single service point that minimizes the sum of the distances to the k-farthest demand points out of a set of given points. A k-centra problem is a location analysis problem which encloses attributes from both the minimax (center) as well as the minisum (median) approaches. The k-centra methodology used in this thesis employs selectively evaluating a few points out of all the existing points. This is the biggest difference between a k-centra methodology and the traditional minisum methodology. The solution procedure used in this thesis is an extension of one of the oldest heuristic methods existing in location science-Weiszfeld’s algorithm. Starting with the minimax solution, Weiszfeld’s algorithm is alternated with reducing radius points until all k points lie inside the smallest possible circle (one at a time). This method is repeated until optimality is obtained. k-Centra optimality is obtained when the same k-points are farthest away from the starting solution. Three problems based on real life city problems are solved using Excel substitution. A MATLAB solution is also provided in this thesis. Experimentation is conducted to compare solution quality and computation time of the k-centra method compared to the minisum method. Five problems each were solved for n = 15 and n = 30. Results obtained showed that the solution quality improves as the k value increases from 1 to n. At k = n, the solution obtained is optimal for the minisum objective function. To evaluate this solution characteristic, few more problems are solved to find the cutoff point of k as a percentage of n where 1% above optimal solution is obtained. Results obtained show that at 40%-50% of n, there is a 1% increase from optimal solution. A few more problems are evaluated to find out the computational time for k-centra problems. It is observed that there is negligible difference in computational time between k-centra and minisum methodologies. The proposed k-centra method provides the user with a near-optimal solution. However, it can be concluded that even though there is some reduction in the total computational time for the proposed k-centra method as compared to the minisum method, the time saved is negligible.