A squared‐euclidean distance location‐allocation problem

Hanif D. Sherali and Cihan H. Tuncbilek

Naval Research Logistics (NRL), 1992, vol. 39, issue 4, 447-469

Abstract: This article is concerned with the analysis of a squared‐Euclidean distance location‐allocation problem with balanced transportation constraints, where the costs are directly proportional to distances and the amount shipped. The problem is shown to be equivalent to maximizing a convex quadratic function subject to transportation constraints. A branch‐and‐bound algorithm is developed that utilizes a specialized, tight, linear programming representation to compute strong upper bounds via a Lagrangian relaxation scheme. These bounds are shown to substantially dominate several other upper bounds that are derived using standard techniques as problem size increases. The special structure of the transportation constraints is used to derive a partitioning scheme, and this structure is further exploited to devise suitable logical tests that tighten the bounds implied by the branching restrictions on the transportation flows. The transportation structure is also used to generate additional cut‐set inequalities based on a cycle prevention method which preserves a forest graph for any partial solution. Results of the computational experiments, and a discussion on possible extensions, are also presented.

Date: 1992
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199206)39:43.0.CO;2-O

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:wly:navres:v:39:y:1992:i:4:p:447-469

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().