Global Optimization Procedures for the Capacitated Euclidean and l p Distance Multifacility Location-Allocation Problems

Hanif D. Sherali (), Intesar Al-Loughani () and Shivaram Subramanian ()
Additional contact information
Hanif D. Sherali: Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Intesar Al-Loughani: Department of Mathematics, Kuwait University, Safar, Kuwait
Shivaram Subramanian: Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061

Operations Research, 2002, vol. 50, issue 3, 433-448

Abstract: In this paper, we study the capacitated Euclidean and l p distance location-allocation problems. There exists no global optimization algorithm that has been developed and tested for this class of problems, aside from a total enumeration approach. Beginning with the Euclidean distance problem, we design a branch-and-bound algorithm based on a partitioning of the allocation space that finitely converges to a global optimum for this nonconvex problem. For deriving lower bounds at node subproblems in this partial enumeration scheme, we employ two types of procedures. The first approach computes a lower bound via a projected location space subproblem. The second approach derives a significantly enhanced lower bound by using a Reformulation-Linearization Technique (RLT) to transform an equivalent representation of the original nonconvex problem into a higher dimensional linear programming relaxation. In addition, certain cut-set inequalities are generated in the allocation space, and objective function based cuts are derived in the location space to further tighten the lower bounding relaxation. The RLT procedure is then extended to the general l p distance problem, for p > 1. Computational experience is provided on a set of test problems to investigate both the projected location space and the RLT-lower bounding schemes. The results indicate that the proposed global optimization approach using the RLT-based scheme offers a promising viable solution procedure. In fact, among the problems solved, for the only two test instances available in the literature for the Euclidean distance case, we report significantly improved solutions.

Keywords: Facilities planning: location continuous; Programming: nonlinear algorithms; applications; nonconvex; Transportation: models/location (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.50.3.433.7739 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:50:y:2002:i:3:p:433-448

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().