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. / Ph. D.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/30694 |
| Date | 06 August 1997 |
| Creators | Al-Loughani, Intesar Mansour |
| Contributors | Industrial and Systems Engineering, Sherali, Hanif D., Koelling, C. Patrick, Loganathan, G. V., Burns, John A., Sarin, Subhash C. |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Dissertation |
| Format | application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | COVER.PDF, ABSTRACT.PDF, ACKNOW_2.PDF, CONTENT.PDF, CH1.PDF, CH2.PDF, CH3_1.PDF, CH3_2.PDF, CH3_3.PDF, CH3_4.PDF, CH5_1.PDF, CH5_2.PDF, CH5_3.PDF, CH5_4.PDF, CH5_5.PDF, CH5_6.PDF, CH5_7.PDF, CH5_8.PDF, CH5_9.PDF, CH5_10.PDF, CH4.PDF, CH6.PDF, APPENDIX.PDF, REF.PDF, VITA.PDF |
Page generated in 0.0147 seconds