A minisum location problem with regional demand considering farthest Euclidean distances


OPTIMIZATION METHODS & SOFTWARE, vol.31, no.3, pp.446-470, 2016 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 31 Issue: 3
  • Publication Date: 2016
  • Doi Number: 10.1080/10556788.2015.1121486
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.446-470
  • Middle East Technical University Affiliated: Yes


We consider a continuous multi-facility location-allocation problem that aims to minimize the sum of weighted farthest Euclidean distances between (closed convex) polygonal and/or circular demand regions, and facilities they are assigned to. We show that the single facility version of the problem has a straightforward second-order cone programming formulation and can therefore be efficiently solved to optimality. To solve large size instances, we adapt a multi-dimensional direct search descent algorithm to our problem which is not guaranteed to find the optimal solution. In a special case with circular and rectangular demand regions, this algorithm, if converges, finds the optimal solution. We also apply a simple subgradient method to the problem. Furthermore, we review the algorithms proposed for the problem in the literature and compare all these algorithms in terms of both solution quality and time. Finally, we consider the multi-facility version of the problem and model it as a mixed integer second-order cone programming problem. As this formulation is weak, we use the alternate location-allocation heuristic to solve large size instances.