Title page for ETD etd-7497-124042


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 PhD
Department Industrial and Systems Engineering
Advisory Committee
Advisor Name Title
Sherali, Hanif D. Committee Chair
Burns, John A. Committee Member
Koelling, Charles Patrick Committee Member
Loganathan, G. V. Committee Member
Sarin, Subhash C. Committee Member
Keywords
  • Reformulation-Linearization Technique
  • Location-Allocation
  • Location
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

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

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