Type of Document	Dissertation
Author	Al-Loughani, Intesar Mansour
Author's Email Address	loughani@vt.edu
URN	etd-7497-124042
Title	Algorithmic Approaches for Solving the Euclidean Distance Location and Location-Allocation Problems
Degree	DOCTOR OF PHILOSOPHY
Department	Industrial and Systems Engineering
Advisory Committee	Advisor Name Title Hanif D. Sherali Committee Chair G. V. Loganathan Committee Member John A. Burns Committee Member Patrick Koelling Committee Member Subhash C. Sarin Committee Member
Keywords	Location Location-Allocation Reformulation-Linearization Technique
Date of Defense	1997-07-08
Availability	unrestricted
Abstract This dissertation is concerned with the development of algorithmic approaches for solving the minisum location and location-allocation problems in which the Euclidean metric is used to measure distances. To overcome the nondifferentiability difficulty associated with the Euclidean norm function, specialized solution procedures are developed for both the location and the location-allocation problems. For the multifacility location problem (EMFLP), two equivalent convex differentiable reformulations are proposed. The first of these is formulated directly in the primal space, and relationships between its Karush-Kuhn- Tucker (KKT) conditions and the necessary and sufficient optimality conditions for EMFLP are established in order to explore the use of standard convex differentiable nonlinear programming algorithms that are guaranteed to converge to KKT solutions. The second equivalent differentiable formulation is derived via a Lagrangian dual approach based on the optimum of a linear function over a unit ball (circle). For this dual approach, which recovers Francis and Cabot’s (1972) dual problem, we also characterize the recovery of primal location decisions, hence settling an issue that has remained open since 1972. In another approach for solving EMFLP, conjugate or deflected subgradient based algorithms along with suitable line-search strategies are proposed. The subgradient deflection method considered is the Average Direction Strategy (ADS) imbedded within the Variable Target Value Method (VTVM). The generation of two types of subgradients that are employed in conjunction with ADS are investigated. The first type is a simple valid subgradient that assigns zero components corresponding to the nondifferentiable terms in the objective function. The second type expends more effort to derive a low-norm member of the subdifferential in order to enhance the prospect of obtaining a descent direction. Furthermore, a Newton-based line-search is also designed and implemented in order to enhance the convergence behavior of the developed algorithm. Various combinations of the above strategies are composed and evaluated on a set of test problems. Computational results for all the proposed algorithmic approaches are presented, using a set of test problems that include some standard problems from the literature. These results exhibit the relative advantages of employing the new proposed procedures. Finally, we study the capacitated Euclidean distance location-allocation problem. There exists no global optimization algorithm that has been developed and tested for this class of problems, aside from a total enumeration approach. We develop a branch-and-bound algorithm that implicitly/partially enumerates the vertices of the feasible region of the transportation constraints in order to determine a global optimum for this nonconvex problem. For deriving lower bounds on node subproblems, a specialized variant of the Reformulation-Linearization Technique (RLT) is suitably designed which transforms the representation of this nonconvex problem from the original defining space into a higher dimensional space associated with a lower bounding (largely linear) convex program. The maximum of the RLT relaxation based lower bound that is obtained via a deflected subgradient strategy applied to a Lagrangian dual formulation of this problem, and another readily computed lower bound in the projected location space is considered at each node of the branch-and-bound tree for fathoming purposes. In addition, certain cut-set inequalities in the allocation space, and objective function based cuts in the location space are generated to further tighten the lower bounding relaxation. Computational experience is provided on a set of randomly generated test problems to investigate both the RLT-based and the projected location- space lower bounding schemes. The results indicate that the proposed global optimization approach for this class of problem offers a promising viable solution procedure. In fact, for two instances available available in the in the literature, we report significantly improved solutions. The dissertation concludes with recommendations for further research for this challenging class of problems. Data for the collection of test problems is provided in the Appendix to facilitate further testing in this area.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    ABSTRACT.PDF 6.89 Kb 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01   ACKNOW_2.PDF 2.68 Kb < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01   APPENDIX.PDF 21.55 Kb 00:00:05 00:00:03 00:00:02 00:00:01 < 00:00:01   CH1.PDF 32.96 Kb 00:00:09 00:00:04 00:00:04 00:00:02 < 00:00:01   CH2.PDF 74.91 Kb 00:00:20 00:00:10 00:00:09 00:00:04 < 00:00:01   CH3_1.PDF 48.47 Kb 00:00:13 00:00:06 00:00:06 00:00:03 < 00:00:01   CH3_2.PDF 69.78 Kb 00:00:19 00:00:09 00:00:08 00:00:04 < 00:00:01   CH3_3.PDF 39.59 Kb 00:00:10 00:00:05 00:00:04 00:00:02 < 00:00:01   CH3_4.PDF 46.49 Kb 00:00:12 00:00:06 00:00:05 00:00:02 < 00:00:01   CH4.PDF 80.15 Kb 00:00:22 00:00:11 00:00:10 00:00:05 < 00:00:01   CH5_1.PDF 31.93 Kb 00:00:08 00:00:04 00:00:03 00:00:01 < 00:00:01   CH5_10.PDF 23.49 Kb 00:00:06 00:00:03 00:00:02 00:00:01 < 00:00:01   CH5_2.PDF 31.19 Kb 00:00:08 00:00:04 00:00:03 00:00:01 < 00:00:01   CH5_3.PDF 31.85 Kb 00:00:08 00:00:04 00:00:03 00:00:01 < 00:00:01   CH5_4.PDF 23.70 Kb 00:00:06 00:00:03 00:00:02 00:00:01 < 00:00:01   CH5_5.PDF 14.09 Kb 00:00:03 00:00:02 00:00:01 < 00:00:01 < 00:00:01   CH5_6.PDF 40.24 Kb 00:00:11 00:00:05 00:00:05 00:00:02 < 00:00:01   CH5_7.PDF 40.53 Kb 00:00:11 00:00:05 00:00:05 00:00:02 < 00:00:01   CH5_8.PDF 60.89 Kb 00:00:16 00:00:08 00:00:07 00:00:03 < 00:00:01   CH5_9.PDF 51.04 Kb 00:00:14 00:00:07 00:00:06 00:00:03 < 00:00:01   CH6.PDF 12.61 Kb 00:00:03 00:00:01 00:00:01 < 00:00:01 < 00:00:01   CONTENT.PDF 10.96 Kb 00:00:03 00:00:01 00:00:01 < 00:00:01 < 00:00:01   COVER.PDF 2.32 Kb < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01   REF.PDF 50.83 Kb 00:00:14 00:00:07 00:00:06 00:00:03 < 00:00:01   VITA.PDF 3.68 Kb 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01

If you have questions or technical problems, please Contact DLA.